Parse trees and derivations in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Parse Tree Structure

Consider a simple grammar for arithmetic expressions with rules:
E → E + T | T
T → T * F | F
F → (E) | id

Which of the following statements about the parse tree for the expression id + id * id is correct?

A The parse tree has <code>id + id + id</code> as a flat structure without multiplication.

B The parse tree groups as <code>(id + id) * id</code>, ignoring operator precedence.

C The parse tree shows <code>id + (id * id)</code> grouping, reflecting operator precedence.

D The parse tree cannot represent this expression due to ambiguity.

💡 Hint

Recall that multiplication has higher precedence than addition in arithmetic expressions.

The grammar is left-recursive but respects operator precedence by the order of rules. Multiplication binds tighter, so the parse tree groups id * id first, then adds the first id.

📋 Factual

intermediate

Derivation Types in Context-Free Grammars

Which of the following best describes the difference between a leftmost derivation and a rightmost derivation in context-free grammars?

A Leftmost derivation always replaces the leftmost non-terminal first; rightmost derivation replaces the rightmost non-terminal first.

B Leftmost derivation replaces terminals first; rightmost derivation replaces non-terminals first.

C Leftmost derivation applies only to left-recursive grammars; rightmost derivation applies only to right-recursive grammars.

D Leftmost and rightmost derivations produce different languages from the same grammar.

💡 Hint

Think about the order in which non-terminals are expanded during derivation.

Leftmost derivation always expands the leftmost non-terminal symbol first in each step, while rightmost derivation expands the rightmost non-terminal first. Both produce the same language but differ in derivation order.

🔍 Analysis

advanced

Identifying Ambiguity from Parse Trees

Given the grammar rules:
S → S + S | S * S | (S) | id

Which of the following statements about the parse trees for the string id + id * id is true?

A There is exactly one parse tree, showing multiplication before addition.

B There are multiple parse trees, indicating the grammar is ambiguous for this string.

C The parse tree shows addition before multiplication, ignoring operator precedence.

D No parse tree can be constructed because the grammar is incomplete.

💡 Hint

Consider if the grammar enforces operator precedence or allows multiple interpretations.

The grammar allows both (id + id) * id and id + (id * id) parse trees for the same string, showing ambiguity because it does not enforce operator precedence.

❓ Comparison

advanced

Comparing Parse Trees and Derivations

Which of the following best explains the relationship between a parse tree and a derivation sequence for a given string in a context-free grammar?

A A derivation sequence is always shorter than the parse tree height.

B A derivation sequence is a graphical representation of a parse tree with nodes and branches.

C Parse trees and derivation sequences are unrelated concepts used in different grammar types.

D A parse tree visually represents the hierarchical structure of a derivation sequence, showing how the string is generated step-by-step.

💡 Hint

Think about how derivations and parse trees represent the generation of strings.

A derivation sequence lists the steps of replacing non-terminals to produce a string. The parse tree shows these steps as a tree structure, making the hierarchy clear.

❓ Reasoning

expert

Determining the Number of Leaves in a Parse Tree

Consider a parse tree generated from a context-free grammar for the string id + id * id. If each id corresponds to a leaf node, how many leaf nodes will the parse tree have?

A 5

B 7

C 3

D 9

💡 Hint

Count the number of terminal symbols in the string.

The string id + id * id has five terminal symbols: three id tokens and two operators (+ and *). All terminals are leaves in the parse tree, so there are 5 leaf nodes.

Practice

1. What does a parse tree represent in compiler design?

easy

A. The list of tokens from lexical analysis

B. The sequence of machine instructions generated

C. The memory layout of variables

D. The hierarchical structure of a sentence based on grammar rules

Solution

1. Step 1: Understand the role of parse trees

   Parse trees visually show how a sentence is broken down into parts according to grammar rules.

2. Step 2: Differentiate from other compiler components

   Unlike tokens or machine instructions, parse trees focus on syntax structure, not code or memory.

3. Final Answer:

   The hierarchical structure of a sentence based on grammar rules -> Option D

4. Quick Check:

   Parse tree = hierarchical structure [OK]

Hint: Parse tree = sentence structure, not code or memory [OK]

Common Mistakes:

• Confusing parse tree with tokens list
• Thinking parse tree shows machine code
• Mixing parse tree with memory layout

2. Which of the following is the correct way to represent a derivation step in grammar?

easy

A. S → aSb

B. S = a + Sb

C. S := aSb

D. S <- aSb

Solution

1. Step 1: Identify standard grammar notation

   In grammar, derivations use the arrow symbol → to show how a symbol expands.

2. Step 2: Check each option's correctness

   S → aSb uses → correctly; others use assignment or incorrect symbols.

3. Final Answer:

   S → aSb -> Option A

4. Quick Check:

   Derivation uses → symbol [OK]

Hint: Look for arrow → in grammar rules [OK]

Common Mistakes:

• Using assignment symbols instead of arrow
• Confusing programming assignment with grammar rules
• Using incorrect arrow symbols

3. Given the grammar rules:
S → aSb | ab
What is the leftmost derivation of the string aabb?

medium

A. S → aSb → aaSbb → aabb

B. S → ab → aabb

C. S → aSb → ab

D. S → aSb → aab

Solution

1. Step 1: Apply leftmost derivation rules

   Start with S, replace leftmost S using S → aSb to get aSb.

2. Step 2: Apply rule again to inner S

   Replace inner S with aSb again to get aaSbb, then replace S with ab to get aabb.

3. Final Answer:

   S → aSb → aaSbb → aabb -> Option A

4. Quick Check:

   Leftmost derivation = S → aSb → aaSbb → aabb [OK]

Hint: Replace leftmost non-terminal first [OK]

Common Mistakes:

• Replacing rightmost non-terminal first
• Skipping intermediate derivation steps
• Confusing production rules

4. Identify the error in this derivation sequence for grammar S → aSb | ab to produce aabb:
S → aSb → ab → aabb

medium

A. Used wrong production rule for S

B. String aabb cannot be derived from this grammar

C. Incorrectly replaced inner S with ab too early

D. No error, derivation is correct

Solution

1. Step 1: Analyze the derivation steps

   The derivation replaces S with aSb, then immediately replaces S with ab but in the wrong position.

2. Step 2: Check correctness of replacement order

   The inner S should be replaced after expanding the outer S fully; here it skips a step causing incorrect string formation.

3. Final Answer:

   Incorrectly replaced inner S with ab too early -> Option C

4. Quick Check:

   Early replacement error = Incorrectly replaced inner S with ab too early [OK]

Hint: Check order of non-terminal replacements carefully [OK]

Common Mistakes:

• Replacing non-terminals out of order
• Assuming all strings are derivable
• Ignoring grammar rules sequence

5. Consider the grammar:
E → E + T | T
T → T * F | F
F → (E) | id
Which parse tree correctly represents the expression id + id * id?

hard

A. Parse tree where '*' is root, left child '+' with two 'id' leaves, right child 'id'

B. Parse tree where '+' is root, left child 'id', right child '*' with two 'id' leaves

C. Parse tree with '+' as root and both children as 'id'

D. Parse tree with '*' as root and both children as 'id'

Solution

1. Step 1: Understand operator precedence in grammar

   Multiplication (*) has higher precedence than addition (+), so '*' groups tighter.

2. Step 2: Build parse tree accordingly

   The root is '+', left child is 'id', right child is '*', which has two 'id' children.

3. Final Answer:

   Parse tree where '+' is root, left child 'id', right child '*' with two 'id' leaves -> Option B

4. Quick Check:

   Operator precedence respected = Parse tree where '+' is root, left child 'id', right child '*' with two 'id' leaves [OK]

Hint: Remember * binds tighter than + in parse trees [OK]

Common Mistakes:

• Ignoring operator precedence
• Swapping '+' and '*' as root
• Misplacing leaves in parse tree