CD Notes
Guide to parse trees covering construction, relationship to derivations, concrete vs abstract syntax trees, annotated parse trees, and their role in syntax-directed translation.
Definition
A parse tree (or derivation tree) is a graphical representation of a derivation showing how a string is generated from a grammar. The root is the start symbol, internal nodes are non-terminals, leaves are terminals or ε, and children of each internal node correspond to the right-hand side of a production used in the derivation.
Parse Tree Properties
| For grammar: E | E + T | T, T → T * F | F, F → id | ( E ) |
| E + T - Leaves (L | R) = input string |
| Yield of the tree | reading leaves left-to-right = "id + id * id" |
Constructing Parse Trees
| Step 1: E | E + T Step 2: E → T Step 3: T → F |
| F + id * id (reduce id | F) |
| T + id * id (reduce F | T) |
| E + id * id (reduce T | E) |
| E + F * id (reduce id | F) |
| E + T * id (reduce F | T) |
| E + T * F (reduce id | F) |
| E + T (reduce T*F | T) |
| E (reduce E+T | E) |
Concrete vs Abstract Syntax Trees
| / | \ |
|---|---|
| / | \ |
Annotated Parse Trees
| / | \ |
|---|---|
| / | \ |
Parse Tree and Ambiguity
| If a string has two different parse trees | grammar is ambiguous. |
| "id - id - id" with E | E - E | id: |
| Tree 1 (left-associative) | Tree 2 (right-associative): |
Interview Questions
- Q: What is the yield of a parse tree?
A: The yield is the string formed by reading all leaf nodes from left to right. For a valid parse tree of string w, the yield equals w. The yield connects the tree structure back to the original input — it proves the string belongs to the grammar's language.
- Q: How many parse trees does an unambiguous grammar produce for a given string?
A: Exactly one. That is the definition of an unambiguous grammar — every string in its language has a unique parse tree. This ensures a unique interpretation, which is essential for deterministic compilation.
- Q: Why don't compilers store the full parse tree?
A: Full parse trees are wasteful — they include nodes for grammar rules that carry no semantic information (like E→T→F→id chains). Compilers build ASTs instead, which are more compact and contain only meaningful structure. Some compilers never build any tree, using syntax-directed translation to generate code during parsing.
- Q: How does a parse tree relate to operator precedence?
A: Higher-precedence operators appear deeper in the tree (closer to leaves), meaning they are evaluated first in a bottom-up traversal. Lower-precedence operators are nearer the root. The tree structure thus encodes evaluation order without needing explicit parentheses.
- Q: Can a parse tree have nodes with different numbers of children?
A: Yes. Each internal node has as many children as there are symbols on the right-hand side of the production used. A production A → BCD gives a node with 3 children. A production A → a gives a node with 1 child. ε-productions give a node with an ε-leaf child.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Parse Trees in Compiler Design.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, syntax, analysis, parse, trees
Related Compiler Design Topics