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
- Write a recursive-descent parser with precedence and associativity
- Compute FIRST and FOLLOW sets and build an LL(1) table
- Trace a shift-reduce parse and resolve conflicts with precedence
Lessons
- 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
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
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
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
- Compilers: Show the grouping with bracketsEasy
- Compilers: Parse to a tree in prefix formMedium
- Compilers: Evaluate, or explain the syntax errorHard
- Compilers: Which nonterminals can vanish?Easy
- Compilers: FIRST setsMedium
- Compilers: FOLLOW setsHard
- Compilers: A table-driven parser for bracketsEasy
- Compilers: Build an LL(1) tableMedium
- Compilers: A complete LL(1) parserHard
- Compilers: Shift and reduce a sumEasy
- Compilers: Shift-reduce with precedenceMedium
- Compilers: Evaluate while reducingHard