Chapter 2 · Grammars & Top-Down Parsing¶

Part 1 · Front End · about 2–3 weeks · Previous: Ch 1 · Next: Ch 3

The problem¶

Given a context-free grammar $G = (N, T, P, S)$ and a token sequence $w = t_1 \cdots t_n$ from the lexer (Ch 1), decide whether $S \Rightarrow^{*} w$ and, if so, build the parse tree (or AST) that name resolution, type checking and lowering (Ch 5, Ch 6, Ch 11) walk; if not, report every syntax error once and keep going. A top-down parser builds the tree from the root, reconstructing a leftmost derivation, and chooses each production by looking at the next token(s). This chapter covers the grammar theory that defines the problem, the sets and tables that make top-down choices deterministic, the transformations that make a grammar fit, the parsers themselves (predictive and backtracking), stronger lookahead (LL(k), LL(*), ALL(*)) and error recovery. pebblec's parser is hand-written predictive recursive descent with panic-mode recovery; bottom-up parsing is Ch 3, and Pratt/PEG/Earley are Ch 4.

What you will be able to do¶

Write leftmost and rightmost derivations, count the parse trees of a sentence, and explain why ambiguity is undecidable (reduction from Post's correspondence problem).
Turn a precedence table into a layered, unambiguous grammar, and fully parenthesize any expression by it.
Compute nullable, FIRST and FOLLOW by hand with three algorithms (round-robin, worklist, DeRemer–Pennello digraph) and prove the result is the least fixed point.
Build an LL(1) table, classify every conflict as FIRST/FIRST or FIRST/FOLLOW, and decide when priority resolution (the dangling else) is safe.
Remove direct and indirect left recursion (Paull's algorithm) and left-factor a grammar, and argue that the language is preserved.
Implement a table-driven LL(1) parser, a recursive-descent parser that agrees with it token for token, and a backtracking parser whose exponential cost you then remove by memoization (./course test 2).
Explain strong LL(k) vs LL(k), trace an ALL(*) prediction through its SLL and LL stages, and find the corresponding code in ANTLR 4 and Clang.
Trace panic-mode recovery with FOLLOW sets, design phrase-level routines, and compute the minimum repair distance of an erroneous input.

Prerequisites: Ch 1 (tokens; regular languages and DFAs, which reappear as LL(*) lookahead DFAs). Comfortable C++ and recursion. Fixed points appear here first and are generalized in Ch 14.

Notation¶

Shared notation follows the house notation (§1 sets and functions, §2 orders and lattices, §5 grammars and parsing, §8 complexity). In this chapter:

Symbol	Meaning
$G = (N, T, P, S)$	a context-free grammar: nonterminals, terminals (token kinds), productions, start symbol (Definition 2.1.1)
$A, B, X, Y \in N \cup T$; $a, b, t \in T$	nonterminals (upper case), grammar symbols, terminals; $\alpha, \beta, \gamma, \delta \in (N \cup T)^{}$ are strings of symbols, $w, x, y, z \in T^{}$ strings of terminals
$A \to \alpha$, $\lvert P \rvert$, $\lvert G \rvert$, $r$	a production; number of productions; grammar size $\sum (1 + \lvert \alpha \rvert)$; longest right side (Definition 2.1.1)
$\Rightarrow$, $\Rightarrow^{*}$, $\Rightarrow^{+}$, $\Rightarrow_{\mathrm{lm}}$, $\Rightarrow_{\mathrm{rm}}$	one derivation step, zero or more, one or more, leftmost, rightmost (Definition 2.1.2)
$L(G)$, $L(X)$	the language of $G$; the terminal strings derived from $X$
$\varepsilon$	the empty string
$\$$	the end-of-input marker, never in a production (written `$` in code, $\$$ in math, $ in tables)
$\#_{G}(w)$	the number of parse trees of $w$ (Definition 2.1.5)
$\mathrm{Nullable}$, $\mathrm{FIRST}(\alpha)$, $\mathrm{FOLLOW}(A)$	the sets of Definition 2.2.1; FIRST never contains $\$$, FOLLOW never contains $\varepsilon$; tables print $\varepsilon \in \mathrm{FIRST}(A)$ for nullable $A$
$F_{\mathrm{N}}, F_{\mathrm{F}}^{\nu}, F_{\mathrm{W}}^{\nu,\phi}$, $\mathrm{lfp}$, $h$	the rule operators of Definition 2.2.2, least fixed point, lattice height; the order is $\subseteq$ and sets grow up from $\bot = \emptyset$
$\mathrm{PREDICT}(A \to \alpha)$, $M[A, t]$	the lookahead set of a production and the LL(1) table (Definition 2.3.1)
$\mathrm{first}_1(x)$, $x{:}k$	the first symbol of $x\,\$$; the first $k$ symbols of $x$ (Definitions 2.3.2, 2.6.1)
$\oplus_k$, $\mathrm{FIRST}_k$, $\mathrm{FOLLOW}_k$, $\mathrm{LA}_k$	$k$-concatenation and the $k$-token sets (Definitions 2.6.1–2.6.3)
$(A, L)$, $T_{A,L}$	a context with local follow set $L$ and its LL(k) table (Definition 2.6.5)
$(i, \sigma)$, $\uparrow X$	an ATN configuration (alternative, stack) and a return marker (Definition 2.6.7)
$(\gamma, i)$, $\vdash$	a predictive-parser configuration (stack, input position) and a move (Definition 2.5.1)
$\mathrm{Parse}(X, i)$	the end positions of $X$ from position $i$ (Definition 2.5.3)
$\mathrm{SYNC}(A)$, $d(w)$, $\mathrm{cost}(X, i, j)$	synchronizing set, repair distance, span repair cost (Definitions 2.7.1–2.7.2)
$n$	the number of input tokens (or nonterminals in Lesson 2.4 §5, as stated there)

Numbered statements are Definition/Theorem/Lemma/Algorithm 2.k.m: chapter 2, lesson $k$, one counter per lesson.

Technique map¶

Family	Techniques (origin)	Lesson
Grammar theory	CFGs, derivations and parse trees, CST vs AST, the Chomsky hierarchy (Chomsky 1956, 1959 [Cho56, Cho59]; Backus–Naur 1960 [Nau60]); ambiguity and its undecidability (Cantor 1962; Floyd 1962; Chomsky & Schützenberger 1963 [Can62, Flo62, CS63]); precedence and associativity by layering (ALGOL 60 report, Naur 1960 [Nau60])	2.1
nullable / FIRST / FOLLOW as least fixed points	round-robin iteration (Lewis & Stearns 1968; Knuth 1971 [LS68, Knu71]), worklist propagation (Dowling & Gallier 1984 for nullable [DG84]), relational closure / digraph (DeRemer & Pennello 1982; Tarjan 1972 [DP82, Tar72])	2.2
Predictive tables	LL(1) table construction and conflict classification (Knuth 1971; Rosenkrantz & Stearns 1970 [Knu71, RS70]), conflict resolution by priority (dangling else; ALGOL 60 / C convention; yacc 1975 [Joh75])	2.3
Grammar transformations	direct left-recursion removal (Greibach 1965 [Gre65]), Paull's algorithm for indirect left recursion (Hopcroft & Ullman 1979; Moore 2000 [HU79, Moo00]), left factoring [ALSU07 §4.3.4]	2.4
Recursive descent	table-driven predictive parsing (Lewis & Stearns 1968 [LS68]), hand-written predictive recursive descent (Lucas 1961; Conway 1963 [Luc61, Con63]), backtracking recursive descent (Wadler 1985 [Wad85]), memoized backtracking (Birman & Ullman 1973; Ford 2002; Frost & Hafiz 2006 [BU73, For02, FH06])	2.5
More lookahead	strong LL(k) and full LL(k) (Lewis & Stearns 1968; Rosenkrantz & Stearns 1970 [LS68, RS70]), LL() (Parr & Fisher 2011 [PF11]), ALL() (Parr, Harwell & Fisher 2014 [PHF14])	2.6
Error recovery	panic mode with FOLLOW-based synchronizing sets (Wirth 1976 [Wir76]; Dragon book [ALSU07 §4.4.5]), phrase-level recovery (Graham & Rhodes 1975 [GR75]), insertion/deletion repair (Irons 1963; Aho & Peterson 1972; Fischer, Milton & Quiring 1980; Burke & Fisher 1987 [Iro63, AP72, FMQ80, BF87])	2.7

flowchart LR
  CFG["CFGs, derivations<br/>Chomsky 1956"] --> AMB["Ambiguity<br/>undecidable 1962"]
  CFG --> LAY["Layering<br/>ALGOL 60"]
  CFG --> FF["nullable / FIRST / FOLLOW<br/>least fixed points"]
  FF -->|fills| LL1["LL(1) table<br/>Knuth 1971"]
  LL1 -->|conflicts| TR["Left-recursion removal,<br/>left factoring"]
  LL1 -->|conflicts| PRI["Priority resolution"]
  LL1 -->|drives| TD["Table-driven parser"]
  TD -->|same decisions as code| RD["Recursive descent"]
  RD -->|no table: try all| BT["Backtracking"]
  BT -->|memoize| MEMO["Memoization<br/>to packrat, Ch 4"]
  LL1 -->|more tokens| LLK["Strong LL(k) / LL(k)<br/>1968-70"]
  LLK -->|regular lookahead| LLS["LL(*)<br/>2011"]
  LLS -->|at parse time| ALLS["ALL(*)<br/>2014"]
  TD --> ER["Error recovery:<br/>panic, phrase level, repair"]

Who uses what¶

System	Technique	Notes
Clang (LLVM 23)	hand-written predictive recursive descent; LL(2) peeks; tentative (backtracking) parsing; panic mode `SkipUntil` + phrase-level `ExpectAndConsume`	2.5, 2.6, 2.7
GCC 15	hand-written recursive descent since 3.4 (C++) and 4.1 (C); `cp_parser_parse_tentatively`	2.5
rustc 1.90	recursive descent with `look_ahead`, snapshots for recovery, `recover_stmt`	2.5, 2.7
swiftc / swift-syntax 6.1	recursive descent with `BacktrackingScope`; lossless CST and precedence-based recovery	2.1, 2.7
Go 1.23 `go/parser`	recursive descent; panic mode synchronizing on statement starts	2.7
ANTLR 4 (4.13.2)	ALL(*) prediction; direct left-recursion rewriting; single-token repair	2.4, 2.6, 2.7
ANTLR 3	LL(*) lookahead DFAs	2.6
CPython ≤ 3.8 pgen / 3.9+ pegen	LL(1) FIRST-set check and table-driven parser / memoized PEG with left-corner SCCs	2.3, 2.5
Bison 3.8	counting nullable, digraph relations (for LALR, Ch 3); counterexamples for ambiguous grammars; shift-wins priority	2.1, 2.2, 2.3

Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Derivations and parse trees (CST vs AST)	Describe every CFG; one tree ⇔ one leftmost ⇔ one rightmost derivation	Replay O(m·n); CST O(n) nodes · negligible next to parsing	CST is lossless (every token); AST keeps meaning only	Low: node types and a printer	CST in IDE tooling (Roslyn, swift-syntax); AST in Clang, GCC
Ambiguity detection	Undecidable in general; counting decides one sentence; LL(1)/LR(1) tests are sufficient only	CountTrees O(\|P\|·r·n³) · bounded search exponential in L	Produces a witness sentence with two trees	Medium: memoized counting + enumeration	Grammar design and review; GLR/ANTLR run-time ambiguity reports
Precedence/associativity layering	Any finite table of binary infix operators, unambiguously	O(m) grammar; m unit steps per operand in the CST	Grammar is the specification; deep trees	Low, but left recursion then needs Lesson 2.4	Language standards (C, Java); LR grammars without %left
Round-robin iteration	Exact least fixed point for nullable, FIRST, FOLLOW	O(p·\|G\|·\|T\|), p ≤ \|N\|·\|T\|+1 · 2–6 passes on the corpus	Pass-by-pass tables make every step explainable	Lowest: three nested loops	Textbooks, small generators, this course's lab and oracles
Worklist propagation	Exact (same sets)	O(\|G\| + e·\|T\|); nullable in O(\|G\|) · touches only what changed	The trace names the dependency that fired	Medium: inclusion graph + queue (+ counters)	Bison's nullable, large or incrementally edited grammars
Relational closure (digraph)	Exact (same sets)	O(\|N\| + e) set unions · one DFS	Exposes the relations that also explain conflicts	Medium–high: Tarjan's SCC algorithm	LALR generators (Bison, Menhir), large grammars
LL(1) table construction + conflict classification	Exactly the LL(1) grammars (a proper subset of LR(1)); a conflict-free table proves unambiguity	O(\|G\| + \|P\|·\|T\|) · milliseconds; ~25 % of cells filled	Names every conflicting cell and its kind (FIRST/FIRST vs FIRST/FOLLOW)	Low once FIRST/FOLLOW exist	LL generators (CPython ≤ 3.8 pgen, JavaCC, ANTLR's LL(1) decisions), grammar review
Conflict resolution by priority	Deterministic parser for a subset of L(G); equal to L(G) for the dangling else, smaller in general	O(#conflicts) at build time · free at parse time	Silent unless warned; can drop sentences	Trivial	Dangling else (C, C++, Java), ANTLR's "first alternative wins"
Direct left-recursion removal	Removes immediate left recursion; preserves the language, not the tree shape	O(\|G\|) · instant	Right-nested trees: the AST must re-associate	Low	Every LL grammar for left-associative operators; as EBNF loops in hand-written parsers
Paull's algorithm (textbook / SCC-restricted)	Removes all left recursion from cycle-free, ε-free grammars; reports hidden left recursion otherwise	Θ(2ⁿ) output in the worst case · SCC restriction avoids needless growth (json: 18 vs 24 productions)	Unreadable grammars, renamed structure	Medium	Grammar tools, textbooks; production generators reject or natively support left recursion instead
Left factoring	Removes FIRST/FIRST conflicts caused by syntactic common prefixes only	O(\|G\|²·r) · instant	Adds helper nonterminals; trees change shape	Low	if/else, statement starts; grammars for JavaCC or LL(1) tables
Table-driven predictive parsing	Exactly the LL(1) grammars	Θ(n) · one table lookup per step (17 steps for 5 tokens)	Correct-prefix error detection; generic "expected one of" messages	Low driver (~50 lines), needs a generator	Generated LL parsers (CPython ≤ 3.8), teaching
Hand-written predictive recursive descent	LL(1) plus any hand-coded lookahead or predicates	Θ(n) · fastest in practice	Best: each function can give context-specific messages and recovery	High to write and maintain, full control	Clang, GCC, rustc, swiftc, Go, V8, `pebblec`
Backtracking recursive descent	Every non-left-recursive CFG, ambiguous included	Exponential: 24 573 calls at depth 12	Poor: the failure is wherever the last attempt died	Low	Prototypes; bounded tentative parsing in C++ front ends
Memoized backtracking	Same as backtracking	O(\|N\|·\|G\|·n³); 26 calls at depth 12	Same as backtracking	Low + a table	Packrat/PEG parsers (CPython pegen, Ch 4)
Strong LL(k)	Strong LL(k) grammars; = LL(1) at k = 1, strictly weaker than LL(k) for k ≥ 2	\|T\|^k-size sets · fine for k ≤ 3	Like LL(1): the conflicting k-strings are reported	Medium	JavaCC LOOKAHEAD(k); hand-coded k = 2 peeks (Clang, rustc)
Full (canonical) LL(k)	All LL(k) grammars; LL(k) ⊊ LL(k+1)	Exponentially many tables · impractical	Exact	High	Theory; defines the class others approximate
LL(*)	Decisions with regular lookahead, plus predicate/backtracking fallback	Static analysis may blow up; parsing is linear with the DFAs	Good; analysis warnings for non-LL(*) decisions	High	ANTLR 3
ALL(*)	Every non-left-recursive CFG (ambiguities resolved to the minimum alternative)	O(n⁴) worst · linear in practice with DFA caching	Good; reports real ambiguities at run time	Very high (runtime ATN simulation)	ANTLR 4 in all its target languages
Panic mode (FOLLOW sync)	Always terminates; may skip large parts of the input	O(n) extra · negligible	Correct first error; later ones may be cascades	Low: a FOLLOW test and a skip loop	Clang `SkipUntil`, GCC, rustc, Go, `pebblec`
Phrase-level recovery	Local, grammar-specific corrections; complete if every error cell has a routine	O(1) per error	Precise messages and fix-its when routines are well designed	High: one routine per error entry, maintained with the grammar	Hand-written parsers' "expected ';'" (Clang `ExpectAndConsumeSemi`), swift-syntax
Insertion/deletion repair	Local: one-token edits; global: the true minimum distance	Local O(1) per error · global O(\|P\|·r·n³) per pass	Best messages ("insert ')'"), but the minimum edit may not be the intended one	Medium (local) to high (global)	ANTLR 4 DefaultErrorStrategy; research tools; bounded windows

Comparison-lab results (reproduce with build/<preset>/bin/ll1 backtrack --max-depth 12 and ll1 rd <tokens>): the hand-written recursive-descent parser and the table-driven parser agree on 2 000 random inputs (trees and error positions, ch02.RDCompare.*); naive backtracking needs 24 573 rule invocations on 12 nested parentheses where the memoized version needs 26 ($3 \cdot 2^{d+1} - 3$ vs $2d + 2$, Proposition 2.5.14).

Route through this chapter¶

Step	What	Techniques	How it is exercised
1	Lesson 2.1	derivations, ambiguity, layering	drill `derivations`; quiz; flashcards
2	Lesson 2.2	round-robin, worklist, digraph	drill `first-follow`; E1–E3
3	Lesson 2.3	LL(1) table, priority resolution	drill `ll1-table`; E4
4	Lesson 2.4	left-recursion removal, Paull, left factoring	drill `left-recursion`; E7–E8
5	Lesson 2.5	table-driven, recursive descent, backtracking, memoization	drill `predict-trace`; E5; lab L1–L4
6	Lesson 2.6	strong LL(k), LL(k), LL(), ALL()	drill `lookahead` (theory + drills only)
7	Lesson 2.7	panic mode, phrase level, repair	drill `predict-trace --difficulty hard`; E6
8	Exercises and the lab spec `labs/ch02-ll1-toolkit/SPEC.md`	Pebble uses predictive recursive descent with panic mode; you implement the sets, the table, the table-driven parser with recovery and the transformations behind the contract `include/ll1/LL1.h` (E1–E8)	`./course test 2`
9	Comparison lab, same spec (your code in `labs/ch02-ll1-toolkit/rd/`, switch `rd-compare`)	table-driven vs recursive descent; naive vs memoized backtracking (L1–L4)	`ch02.RDCompare.`, `ch02.Backtracking.`, `ll1 backtrack`
10	Theory test	all	`./course quiz 2` (≥ 80 % to finish)

Practice and check¶

./course drill first-follow --difficulty easy     # warm up; --solution shows every pass
./course drill ll1-table                          # table cells and conflict kinds
./course drill left-recursion --difficulty hard   # rewrite until LL(1)
./course drill predict-trace --difficulty hard    # parser trace + panic mode + repair
./course drill lookahead --difficulty hard        # ALL(*) SLL vs LL
./course drill derivations                        # trees, derivations, precedence
./course flash 2                                  # daily, a few minutes
./course quiz 2                                   # after the lessons
./course test 2                                   # after the exercises
build/linux/bin/ll1 report tests/ch02/Inputs/running.grammar   # the toolkit on any grammar

References¶

The chapter's annotated bibliography (papers, textbook sections, pinned source files and docs) is in references.md. Start with: [ALSU07] (the classical presentation this chapter follows for FIRST/FOLLOW and LL(1), §4.2–4.4), [Knu71] (LL(1) characterized by FIRST and FOLLOW, with proofs), [GJ08] (the most complete survey of parsing, ch. 8 for every LL variant and ch. 16 for error handling), [PHF14] (ALL(*), readable and precise; read after Lesson 2.6) and [EaC3] (an engineering-first alternative, ch. 3).

Symbol	Meaning
\(G = (N, T, P, S)\)	a context-free grammar: nonterminals, terminals (token kinds), productions, start symbol (Definition 2.1.1)
\(A, B, X, Y \in N \cup T\); \(a, b, t \in T\)	nonterminals (upper case), grammar symbols, terminals; \(\alpha, \beta, \gamma, \delta \in (N \cup T)^{}\) are strings of symbols, \(w, x, y, z \in T^{}\) strings of terminals
\(A \to \alpha\), \(\lvert P \rvert\), \(\lvert G \rvert\), \(r\)	a production; number of productions; grammar size \(\sum (1 + \lvert \alpha \rvert)\); longest right side (Definition 2.1.1)
\(\Rightarrow\), \(\Rightarrow^{*}\), \(\Rightarrow^{+}\), \(\Rightarrow_{\mathrm{lm}}\), \(\Rightarrow_{\mathrm{rm}}\)	one derivation step, zero or more, one or more, leftmost, rightmost (Definition 2.1.2)
\(L(G)\), \(L(X)\)	the language of \(G\); the terminal strings derived from \(X\)
\(\varepsilon\)	the empty string
\(\$\)	the end-of-input marker, never in a production (written `$` in code, \(\$\) in math, $ in tables)
\(\#_{G}(w)\)	the number of parse trees of \(w\) (Definition 2.1.5)
\(\mathrm{Nullable}\), \(\mathrm{FIRST}(\alpha)\), \(\mathrm{FOLLOW}(A)\)	the sets of Definition 2.2.1; FIRST never contains \(\$\), FOLLOW never contains \(\varepsilon\); tables print \(\varepsilon \in \mathrm{FIRST}(A)\) for nullable \(A\)
\(F_{\mathrm{N}}, F_{\mathrm{F}}^{\nu}, F_{\mathrm{W}}^{\nu,\phi}\), \(\mathrm{lfp}\), \(h\)	the rule operators of Definition 2.2.2, least fixed point, lattice height; the order is \(\subseteq\) and sets grow up from \(\bot = \emptyset\)
\(\mathrm{PREDICT}(A \to \alpha)\), \(M[A, t]\)	the lookahead set of a production and the LL(1) table (Definition 2.3.1)
\(\mathrm{first}_1(x)\), \(x{:}k\)	the first symbol of \(x\,\$\); the first \(k\) symbols of \(x\) (Definitions 2.3.2, 2.6.1)
\(\oplus_k\), \(\mathrm{FIRST}_k\), \(\mathrm{FOLLOW}_k\), \(\mathrm{LA}_k\)	\(k\)-concatenation and the \(k\)-token sets (Definitions 2.6.1–2.6.3)
\((A, L)\), \(T_{A,L}\)	a context with local follow set \(L\) and its LL(k) table (Definition 2.6.5)
\((i, \sigma)\), \(\uparrow X\)	an ATN configuration (alternative, stack) and a return marker (Definition 2.6.7)
\((\gamma, i)\), \(\vdash\)	a predictive-parser configuration (stack, input position) and a move (Definition 2.5.1)
\(\mathrm{Parse}(X, i)\)	the end positions of \(X\) from position \(i\) (Definition 2.5.3)
\(\mathrm{SYNC}(A)\), \(d(w)\), \(\mathrm{cost}(X, i, j)\)	synchronizing set, repair distance, span repair cost (Definitions 2.7.1–2.7.2)
\(n\)	the number of input tokens (or nonterminals in Lesson 2.4 §5, as stated there)