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.