CD Notes
Comprehensive guide to top-down parsing covering recursive descent, predictive parsing, LL(1) parsing, FIRST and FOLLOW sets, and left recursion elimination.
Introduction
Top-down parsing builds the parse tree from the root (start symbol) down to the leaves (terminals), making decisions about which production to apply at each step. It corresponds to finding a leftmost derivation of the input string. The parser starts with the start symbol and tries to match the input by expanding non-terminals.
Types of Top-Down Parsers
Recursive Descent Parsing
| Grammar: S | aBc, B → bc | b |
| match('c'); // B | bc |
| // else B | b (just matched b already) |
| Problem | With backtracking, may try wrong production first. |
| Solution | Use lookahead to make deterministic choice (predictive). |
FIRST and FOLLOW Sets
| FIRST(α) | Set of terminals that can begin strings derived from α. |
| 1. If a is terminal | FIRST(a) = {a} |
| 2. If X | ε is a production: ε ∈ FIRST(X) |
| 3. If X | Y₁Y₂...Yₖ: add FIRST(Y₁) to FIRST(X) |
| If ε ∈ FIRST(Y₁) | also add FIRST(Y₂), etc. |
| FOLLOW(A) | Set of terminals that can appear after A in any derivation. |
| 2. If B | αAβ: add FIRST(β)−{ε} to FOLLOW(A) |
| 3. If B | αA or B → αAβ where ε ∈ FIRST(β): |
| Example: E | TE', E' → +TE' | ε, T → FT', T' → *FT' | ε, F → (E) | id |
LL(1) Parsing Table Construction
| id | + | * | ( | ) | $ | |
|---|---|---|---|---|---|---|
| E | E→TE' | E→TE' | ||||
| E' | E'→+TE' | E'→ε | E'→ε | |||
| T | T→FT' | T→FT' | ||||
| T' | T'→ε | T'→*FT' | T'→ε | T'→ε | ||
| F | F→id | F→(E) |
LL(1) Parsing Algorithm
| if X == a | pop X, advance ip |
| else | ERROR |
| if M[X, a] = X | Y₁Y₂...Yₖ: |
| else | ERROR |
| $E id+id*id$ M[E,id]=E | TE' |
| $E'T id+id*id$ M[T,id]=T | FT' |
| $E'T'F id+id*id$ M[F,id]=F | id |
| $E'T' +id*id$ M[T',+]=T' | ε |
| $E' +id*id$ M[E',+]=E' | +TE' |
| $E'T id*id$ M[T,id]=T | FT' |
| $E'T'F id*id$ M[F,id]=F | id |
| $E'T' *id$ M[T',*]=T' | *FT' |
| $E'T'F id$ M[F,id]=F | id |
| $E'T' $ M[T',$]=T' | ε |
| $E' $ M[E',$]=E' | ε |
Conditions for LL(1)
A grammar is LL(1) if and only if for every pair of productions
A → α | β:
1. FIRST(α) ∩ FIRST(β) = ∅
2. If ε ∈ FIRST(α), then FIRST(β) ∩ FOLLOW(A) = ∅
3. If ε ∈ FIRST(β), then FIRST(α) ∩ FOLLOW(A) = ∅
In other words: for any non-terminal, the lookahead uniquely
determines which production to use.
Interview Questions
- Q: What does LL(1) stand for?
A: L = Left-to-right scanning of input, L = Leftmost derivation constructed, 1 = one token of lookahead. It processes input left-to-right, builds a leftmost derivation, and needs only the next input token to decide which production to apply.
- Q: Why must left recursion be eliminated for top-down parsing?
A: A left-recursive production A → Aα causes the parser to call A() which immediately calls A() again — infinite recursion without consuming any input. The parser never advances, causing a stack overflow. Right recursion is fine because it consumes input before recurring.
- Q: What are the limitations of LL(1) parsing?
A: LL(1) cannot handle: left-recursive grammars, ambiguous grammars, grammars where two alternatives start with the same token (need left factoring), or grammars requiring more than one token of lookahead. Many programming language constructs need LL(k) or more general parsers.
- Q: How do FIRST and FOLLOW sets determine parser actions?
A: FIRST(α) tells the parser: "if you see a token in FIRST(α), you can start deriving α." FOLLOW(A) tells: "if A can derive ε and you see a token in FOLLOW(A), choosing A → ε is safe." Together they fill the parsing table unambiguously for LL(1) grammars.
- Q: How does error recovery work in LL(1) parsers?
A: Panic mode: skip input until a token in FOLLOW(A) is found, then pop A. Phrase-level: for each empty cell M[A,a], define a recovery action (insert expected token, skip unexpected token, or pop). Error productions: add rules like stmt → error ';' to resynchronize at statement boundaries.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Top-Down Parsing Techniques 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, top, down
Related Compiler Design Topics