GATE CS - COMPILER DESIGN:Parsing Techniques
Mastering parsing techniques concepts and implementation.
Parsing Techniques for GATE CS
Parsing builds a derivation / parse tree from tokens. GATE cares whether a grammar is LL(1) or LR-family, and whether a given table has conflicts. Detail tables live in the LL/LR chapter.
Top-down vs bottom-up
| Top-down | Bottom-up | |
|---|---|---|
| Builds tree | Root → leaves | Leaves → root |
| Typical | LL(1) predictive | LR / shift-reduce |
| Struggle with | Left recursion, common prefixes | Need careful automaton design |
Ambiguity
More than one parse tree for some string ⇒ ambiguous ⇒ not LL(1) / not LR. Classic: dangling else. Fix with grammar rewrite or parser convention.
FIRST / FOLLOW reminder
You need them before filling an LL(1) table. FIRST of a right-hand side drives which lookahead predicts a production; FOLLOW handles ε-productions.
Shift-reduce sketch
Stack of symbols + input. Shift push next token; reduce replace handle by head of production. Conflicts: shift/reduce or reduce/reduce ⇒ not in that LR class.
Go deep: LL(1) and LR Parsing. Then SDT.