โ† Compiler Design learning path
Compiler Design ยท Module 3 of 10

Syntax analysis and top-down parsing

Grammars, LL(1) and recursive descent.

๐Ÿ“– Key ideas

  1. The parser checks token order against a context-free grammar and builds a parse tree.
  2. Top-down parsers start from the start symbol and expand productions: recursive descent, LL(1).
  3. Left recursion (A -> A a) must be removed for top-down parsing.
  4. Left factoring removes common prefixes so the parser can choose with one look-ahead token.
  5. 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