โ Compiler Design learning pathCompiler Design ยท Module 3 of 10
Syntax analysis and top-down parsing
Grammars, LL(1) and recursive descent.
๐ Key ideas
- The parser checks token order against a context-free grammar and builds a parse tree.
- Top-down parsers start from the start symbol and expand productions: recursive descent, LL(1).
- Left recursion (A -> A a) must be removed for top-down parsing.
- Left factoring removes common prefixes so the parser can choose with one look-ahead token.
- FIRST and FOLLOW sets are used to build the LL(1) parsing table.
๐ก Real-life example: Top-down parsing is like guessing a recipe from its name and checking each step against the dish in front of you.
ParserChecks syntax and builds a parse tree
LL(1)Left-to-right, leftmost derivation, 1 look-ahead
Left recursionProduction of the form A -> A alpha
FIRST setTerminals that can begin strings derived from a symbol