Parsing

Turning tokens into structure: recursive descent, the FIRST and FOLLOW sets behind predictive parsing, table-driven LL(1) parsing and bottom-up shift-reduce parsing.

About 6 hours of study

Learning objectives

Lessons

  1. 1

    Recursive-descent parsing Intermediate

    Turn a grammar into a parser by writing one function per rule. Handle precedence with levels, associativity with loops or recursion, remove left recursion, and report syntax errors clearly.

  2. 2

    FIRST and FOLLOW sets Advanced

    Predictive parsers decide which rule to use by looking at the next token. Compute nullable symbols, FIRST sets and FOLLOW sets by repeating simple rules until nothing changes.

  3. 3

    LL(1) parsing with a table Advanced

    Build a parse table from FIRST and FOLLOW sets, then parse with an explicit stack instead of recursion. Detect grammars that need more than one token of lookahead.

  4. 4

    Bottom-up parsing: shift and reduce Advanced

    Bottom-up parsers read tokens onto a stack and reduce them to grammar rules when a rule's body is on top. See shift-reduce parsing step by step, resolve conflicts with precedence, and learn why LR parsers accept left-recursive grammars.

Module practice

Module quiz

1. In a recursive-descent parser, which function handles the lowest-precedence operator?
2. Why must E → E + T be rewritten for recursive descent?
3. Which symbol is always in FOLLOW of the start symbol?
4. Where does the ε-rule A → ε go in an LL(1) table?
5. A shift-reduce parser has E + E on its stack and sees *. What does it do?
6. A cell of an LL(1) table receives two different rules. What does that mean?

‹ From source to tokensTrees, scopes and types ›