Parse trees and derivations in Compiler Design - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to represent the root of a parse tree.

Compiler Design

root = ParseTreeNode([1])

Drag options to blanks, or click blank then click option'

Aexpression

Btoken

Cgrammar

Dsyntax

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'grammar' or 'syntax' instead of a token for the root node.

The root of a parse tree typically holds a token representing the start symbol or main expression.

2fill in blank

medium

Complete the code to create a derivation step from a non-terminal to a production.

Compiler Design

derivation = DerivationStep([1], production_rule)

Drag options to blanks, or click blank then click option'

Anon_terminal

Bterminal

Ctoken

Dleaf

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing terminal and non-terminal symbols in derivations.

A derivation step starts from a non-terminal symbol and applies a production rule.

3fill in blank

hard

Fix the error in the code to correctly build a parse tree node with children.

Compiler Design

node = ParseTreeNode(symbol=[1], children=children_list)

Drag options to blanks, or click blank then click option'

Anon_terminal

Btoken

Cproduction

Dterminal

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'token' or 'terminal' for nodes that have children.

Parse tree nodes represent non-terminal symbols with children nodes representing expansions.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension mapping non-terminals to their productions.

Compiler Design

{ [1]: [2] for [1] in grammar.non_terminals }

Drag options to blanks, or click blank then click option'

Ant

Bproduction_list

Csymbol

Drule

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'symbol' or 'rule' as keys or values incorrectly.

This comprehension maps each non-terminal (nt) to its list of productions.

5fill in blank

hard

Fill all three blanks to filter productions that derive a terminal symbol.

Compiler Design

[prod for prod in productions if prod.[1] == [2] and prod.[3]]

Drag options to blanks, or click blank then click option'

Aleft_side

Bterminal

Cis_terminal

Dright_side

Attempts:

3 left

💡 Hint

Common Mistakes

Checking left_side instead of right_side.

Confusing property names.

This list comprehension selects productions whose right side is a terminal and confirms it is terminal.

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