Parse trees and derivations in Compiler Design - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a parse tree in compiler design?

A parse tree is a tree that shows the syntactic structure of a string according to a grammar. It represents how the start symbol of the grammar derives the string step-by-step.

beginner

What is a derivation in the context of grammars?

A derivation is a sequence of production rule applications that shows how a string can be generated from the start symbol of a grammar.

intermediate

How does a leftmost derivation differ from a rightmost derivation?

In a leftmost derivation, the leftmost non-terminal is replaced first at each step. In a rightmost derivation, the rightmost non-terminal is replaced first.

beginner

Why are parse trees important in compilers?

Parse trees help compilers understand the structure of source code, which is essential for syntax checking and for generating intermediate code or machine code.

beginner

What does each node in a parse tree represent?

Each internal node represents a grammar symbol (non-terminal), and each leaf node represents a terminal symbol (token) from the input string.

What does a parse tree represent?

A The memory layout of variables

B The semantic meaning of a program

C The execution order of a program

D The syntactic structure of a string according to a grammar

A parse tree shows how a string is derived from the grammar's start symbol, representing its syntactic structure.

In a leftmost derivation, which non-terminal is replaced first?

A The rightmost non-terminal

B The leftmost non-terminal

C The middle non-terminal

D All non-terminals simultaneously

Leftmost derivation always replaces the leftmost non-terminal first at each step.

What is the root of a parse tree?

A The start symbol of the grammar

B A terminal symbol

C A leaf node

D A semantic action

The root of a parse tree is the start symbol from which the string is derived.

Which of the following is NOT represented in a parse tree?

A Semantic meanings

B Non-terminal symbols

C Production rules

D Terminal symbols

Parse trees represent syntax, not semantic meanings.

What does a derivation show?

A The runtime behavior of a program

B The memory usage of a program

C The sequence of grammar rule applications to generate a string

D The optimization steps in compilation

A derivation is the step-by-step application of grammar rules to produce a string.

Explain what a parse tree is and how it relates to derivations.

Think about how a grammar generates a string and how that process can be shown as a tree.

Describe the difference between leftmost and rightmost derivations with an example.

Focus on the order of replacing non-terminals during derivation.

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