Top-Down Parsing
1. Idea
Top-down builds the parse tree from root (start) to leaves (input), predicting productions via leftmost derivation. Two forms: backtracking (try/fail/retry) and predictive (LL(1) table, no backtracking).
2. Recursive Descent (one function per non-terminal)
void E(){ T(); Eprime(); }
void Eprime(){ if(lookahead=='+'){ match('+'); T(); Eprime(); } /* else ε */ }
void match(t){ if(lookahead==t) lookahead=next(); else error(); }
- Direct code from LL(1) grammar; needs one lookahead.
- Fails on left recursion — remove it first.
3. Table-Driven LL(1) Parsing (stack algorithm)
push $ , S; ip → first token
while stack top X:
if X==ip: pop, advance
elif X terminal: error
elif M[X,ip] = X→Y1..Yk: pop, push Yk..Y1
else error
accept iff stack $ + input $ meet
Trace id+id:
stack: $E → $E'T → $E'T'F → $E'T'id → (match id) → $E'T' → $E' (ε) → $E'T+ → match + → ... accept
4. Error Handling
- Panic: on blank M[X,a], skip input till a FOLLOW(X) token.
- Phrase-level: insert/delete token (
;missing → insert).
5. Exam Points
- Trace table-driven parse on given string — 7 marks, very frequent.
- Write recursive-descent code for small grammar — 5 marks, frequent.
- Backtracking vs predictive difference + error recovery — 3-5 marks, frequent.