Chapter 3 · Bottom-Up Parsing¶

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

The problem¶

Given a context-free grammar $G = (N, T, P, S)$ and a token sequence $w = t_1 \cdots t_n$, decide whether $w \in L(G)$ and build its parse tree bottom up: shift tokens onto a stack and, whenever the top of the stack is the right side of a production that belongs in the tree (a handle), replace it by the left side. The output is the rightmost derivation of $w$ in reverse. The whole difficulty is to know, from the stack and a bounded look at the input, when to reduce and by which production. This chapter builds the answer: a finite automaton over stack contents (the LR(0) automaton), lookahead refinements of increasing precision and cost (SLR(1), LALR(1), minimal LR(1), canonical LR(1)), declarations that resolve ambiguity (precedence), a generalization that keeps every choice (GLR), and what LR parsers do when the input is wrong. pebblec parses with hand-written recursive descent (Ch 2, Ch 4); this chapter's toolkit checks that Pebble's grammar is LR(1) and gives you the generator-side view used by Bison, Menhir, PostgreSQL and tree-sitter.

What you will be able to do¶

Find the handle of a right-sentential form, trace a shift-reduce parse with an LR table, and prove that the stack is always a viable prefix and that viable prefixes form a regular language.
Compute CLOSURE and GOTO of LR(0) and LR(1) item sets by hand and build the canonical LR(0) and LR(1) automata with the course's state numbering.
Fill in LR(0), SLR(1), LALR(1) and canonical LR(1) tables, classify every conflict, and place a grammar in the hierarchy LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1) (and explain why every LL(1) grammar is LR(1) but not always LALR(1)).
Compute LALR(1) lookaheads two ways — merging LR(1) states and DeRemer–Pennello's reads/includes/lookback with the Digraph algorithm — and prove they agree; explain why merging can only add reduce/reduce conflicts.
Explain how Pager's method and IELR(1) keep LR(1) power at LALR size, and read Bison's and Menhir's state counts.
Resolve an ambiguous expression grammar with %left/%right/%nonassoc, prove the result equals the layered grammar's trees, and say when such resolution is unsafe.
Trace Tomita's GLR algorithm with a graph-structured stack and read the shared packed parse forest it builds; explain what RNGLR fixes.
Trace yacc's error recovery and a Burke–Fisher repair, and use Menhir's .messages workflow; implement all four LR constructions, one driver, and ★ a GLR parser (./course test 3).

Prerequisites: Ch 2: grammars, derivations and parse trees (Lesson 2.1), nullable/FIRST/FOLLOW and the Digraph algorithm (Lesson 2.2), LL(1) tables (Lesson 2.3). Regular languages and DFAs from Ch 1. The lab reuses Chapter 2's grammar model (labs/ch02-ll1-toolkit/include/ll1/Grammar.h).

Notation¶

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

Symbol	Meaning
$G = (N, T, P, S)$, $S'$	a grammar and its augmented start symbol, with production $(0)\ S' \to S$ (Lesson 3.1 §2)
$\Rightarrow_{\mathrm{rm}}$, $\Rightarrow_{\mathrm{rm}}^{*}$	rightmost derivation step(s) (Definition 2.1.2)
$\alpha, \beta, \gamma, \delta \in (N \cup T)^{}$; $w, x, y, z \in T^{}$	strings of symbols; strings of terminals
$(A \to \beta, k)$	a handle: production and the position where its right side ends (Definition 3.1.2)
$[A \to \alpha \bullet \beta]$, $[A \to \alpha \bullet \beta,\ a]$	LR(0) and LR(1) items (Definitions 3.1.6, 3.2.2); in code `(p, d)` = production, dot position
$V(\gamma)$, $V_1(\gamma)$	the LR(0) / LR(1) items valid for $\gamma$
$\mathrm{CLOSURE}$, $\mathrm{GOTO}$, $\mathrm{CLOSURE}_1$, $\mathrm{GOTO}_1$	item-set operations (Definitions 3.1.7, 3.2.3)
$\mathcal{A}_0 = (Q, \delta, q_0)$, $\mathcal{A}_1$	the canonical LR(0) automaton and the canonical LR(1) automaton; $\delta^{}$ extends $\delta$ to strings; $p \xrightarrow{\beta} q$ means $\delta^{}(p, \beta) = q$
I0, I1, …	LR(0) states in the course's canonical numbering: breadth first, successors in symbol order (terminals by first appearance, then nonterminals)
ACTION$[q, a]$, GOTO$[q, A]$	the parse table; actions `s`$j$ (shift to $j$), `r`$p$ (reduce by production $p$), `acc`
$\mathrm{first}_1(x)$, $\mathrm{FIRST}_k$	first symbol of $x\,\$$; first $k$ symbols (Definition 2.3.2, 2.6.1)
$\mathrm{LA}(q, A \to \omega)$	the LALR(1) lookahead set of a reduce item (Definition 3.3.2)
$\mathcal{N}$, $\mathrm{DR}$, reads, includes, lookback, $\mathrm{Read}$, $\mathrm{Follow}(p, A)$	DeRemer–Pennello's nonterminal transitions, relations and sets (Definition 3.3.3) — $\mathrm{Follow}(p, A)$ is per transition, not the grammar-wide $\mathrm{FOLLOW}(A)$
$\mathrm{lev}(t)$, $\mathrm{assoc}(t)$	precedence level and associativity of a declared token (Definition 3.5.3)
$\lessdot$, $\doteq$, $\gtrdot$	Floyd's operator-precedence relations (Definition 3.5.4)
$(s, i)$, $U_i$, $(X, j, i)$	a GSS node (state, level), the frontier at level $i$, an SPPF symbol node deriving $t_{j+1} \cdots t_i$ (Definitions 3.6.1–3.6.2)
$\#(X, j, i)$	the number of trees an SPPF node represents
$n$, $\lvert G \rvert$, $\lvert Q \rvert$, $p$	input length; grammar size (number of LR(0) items); number of states; longest right side

Technique map¶

Family	Techniques (origin)	Lesson
Foundations	Shift-reduce parsing, handles, viable prefixes (Knuth 1965); LR(0) items, CLOSURE/GOTO, the canonical LR(0) automaton / characteristic FSM (Knuth 1965; DeRemer 1969) with the regularity of viable prefixes	3.1
Lookahead	SLR(1) (DeRemer 1971); canonical LR(1) (Knuth 1965); LR(k) grammars are unambiguous; every LL(1) grammar is LR(1) (Nijholt 1982)	3.2
LALR(1)	Merging LR(1) cores (DeRemer 1969; LaLonde–Lee–Horning 1971; Anderson–Eve–Horning 1973; yacc 1975); DeRemer–Pennello lookaheads with reads/includes and Digraph (1982); mysterious conflicts; LL(1) but not LALR(1) (Beatty 1982)	3.3
Minimal LR(1)	Pager's practical general method (1977); IELR(1) (Denny–Malloy 2010); state-count comparisons	3.4
Conflicts and precedence	Shift/reduce and reduce/reduce conflicts, counterexamples (Isradisaikul–Myers 2015); precedence and associativity declarations (Aho–Johnson–Ullman 1975; yacc); operator-precedence parsing (Floyd 1963)	3.5
Generalized LR	Tomita's GLR with graph-structured stack and SPPF (Lang 1974; Tomita 1985/1991; Rekers 1992); RNGLR and BRNGLR (Scott–Johnstone 2006; Scott–Johnstone–Economopoulos 2007); Bison `%glr-parser`, Elkhound (2004), tree-sitter	3.6
Error handling	yacc's `error` token (Johnson 1975); Burke–Fisher repair (1987); Menhir `.messages` and reachability (Jeffery 2003; Pottier 2016)	3.7
In practice	Generated LR parsers in production (Bison, Lemon, Lrama, Menhir, tree-sitter); hand-written recursive descent (GCC 3.4's C++ parser 2004, GCC 4.1's C parser, Clang, Ruby's Prism)	3.8

flowchart LR
  SR["Shift-reduce parsing<br/>handles, viable prefixes"] --> LR0["LR(0) automaton<br/>Knuth 1965, DeRemer 1969"]
  FL["Operator precedence<br/>Floyd 1963"] -.->|historical special case| SR
  LR0 -->|"+ FOLLOW"| SLR["SLR(1)<br/>DeRemer 1971"]
  LR0 -->|"+ lookaheads in items"| LR1["canonical LR(1)<br/>Knuth 1965"]
  LR1 -->|"merge equal cores"| LALR["LALR(1)<br/>DeRemer 1969, yacc"]
  LR0 -->|"reads/includes + Digraph"| DP["LALR(1) lookaheads<br/>DeRemer–Pennello 1982"]
  DP ---|same tables| LALR
  LR1 -->|"merge weakly compatible"| PGM["Pager PGM 1977"]
  LALR -->|"split where inadequate"| IELR["IELR(1)<br/>Denny–Malloy 2010"]
  LALR -->|"%left/%right"| PREC["precedence declarations<br/>AJU 1975"]
  LALR -->|"keep all actions"| GLR["GLR<br/>Tomita 1985"]
  GLR -->|"right-nulled, binarized"| RN["RNGLR / BRNGLR<br/>Scott–Johnstone"]

Who uses what¶

System	Technique	Notes
Bison 3.8 (yacc)	LALR(1) by DeRemer–Pennello (default), IELR(1), canonical LR(1); precedence; `error` token; `%glr-parser`	Lessons 3.3–3.7; `src/lalr.c`, `src/ielr.c`
PostgreSQL 17, PHP 8.3, Ruby ≤ 3.3 (`parse.y` via Lrama)	Bison-style LALR(1) with precedence, `%expect 0`	Lesson 3.8
SQLite	Lemon LALR(1)	Lesson 3.8
Menhir (OCaml, CompCert)	Pager's method (default), LALR, canonical LR(1); `.messages` via reachability; Coq-validated parsers	Lessons 3.4, 3.7
tree-sitter 0.27	LR(1)-style item sets with post-hoc state merging; GLR forking on declared conflicts, dynamic precedence	Lessons 3.3, 3.6
ML-Yacc (SML/NJ)	LALR(1) with Burke–Fisher error correction	Lesson 3.7
GCC 15, Clang/LLVM 23, Ruby 3.4 (Prism)	Hand-written recursive descent; operator-precedence stacks / precedence climbing for expressions; tentative parsing	Lessons 3.5, 3.8

Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Shift-reduce parsing (with a handle oracle)	Any grammar for which the oracle exists; reverse rightmost derivation	$O(n)$ moves · a table lookup per move	Depends on the oracle; LR oracles detect errors at the first bad token	The driver is 30 lines; the oracle is the work	Every LR, precedence and GLR parser
LR(0) automaton	Exactly the viable prefixes (Theorem 3.1.16); alone, only LR(0) grammars are deterministic	$O(\lvert Q\rvert \lvert G\rvert)$, worst case exponential · 6 458 states for PostgreSQL in ~2 s	Items name every production that could be in progress (Menhir `.messages`, Lesson 3.7)	Moderate: closure, GOTO, hashing kernels	The core of every LR generator (yacc, Bison, Menhir, tree-sitter)
SLR(1)	SLR(1) grammars: LR(0) ⊊ SLR(1) ⊊ LALR(1); fails on context-dependent followers	LR(0) automaton + FOLLOW · as fast as LR(0)	Correct prefix, but extra reductions before an error; spurious conflicts	Low: LR(0) + FOLLOW	Teaching; historical generators
Canonical LR(1)	Exactly the LR(1) grammars (Theorem 3.2.12); ⊋ LL(1) (Theorem 3.2.14)	$\lvert Q_1\rvert$ can be many times $\lvert Q_0\rvert$ · PostgreSQL: > 600 s	Immediate error detection (no extra reductions); one state per context helps messages	Moderate: lookahead propagation in closure	Reference semantics; Menhir `--canonical`, Bison `canonical-lr`
LALR(1) by merging LR(1) states	LALR(1) = LR(0) states with the union of canonical lookaheads; can add reduce/reduce conflicts (Theorem 3.3.9)	Needs $\mathcal{A}_1$ first · impractical for large grammars	Same table as DeRemer–Pennello	Low once LR(1) exists	Definition, testing, teaching
DeRemer–Pennello lookaheads	Identical sets (Theorem 3.3.12)	Linear in the relations · 2.2 s for PostgreSQL	Same table; lookaheads can be computed only where needed	Moderate: four relations and Digraph	Bison's default, most LALR generators
Pager's PGM	LR(1) (Theorem 3.4.8); merges only weakly compatible isocores	Near LALR · Menhir builds OCaml-scale grammars in seconds	No mysterious conflicts; error behavior between LALR and canonical	Moderate: LR(1) closure plus a merge test and re-expansion	Menhir (default), Hyacc
IELR(1)	Same actions as canonical LR(1), including resolved conflicts (Theorem 3.4.10); LALR-sized when LALR is adequate	LALR + annotations · PostgreSQL: 3.3 s vs 2.2 s	Exactly canonical decisions; still default reductions	High: five phases, annotation lists	Bison `%define lr.type ielr`
Conflict classification and counterexamples	Diagnoses every conflict; unifying ones prove ambiguity	Linear classification · counterexamples usually < 1 s	The best explanation a generator can give	Classification low; unifying search high	Every generator (Bison `-Wcounterexamples`, Menhir `.conflicts`)
Precedence and associativity declarations	Resolves operator ambiguities exactly (Theorem 3.5.10); can remove sentences if misapplied	Free at parse time; fewer states than layering	Silent once resolved; Bison logs with `--report=solved`	Trivial for the user	yacc/Bison/Menhir/tree-sitter expression grammars, PostgreSQL
Operator-precedence parsing	Operator-precedence grammars only; skeletons, may accept non-sentences	$O(n)$, tiny tables	Weak: errors only on missing relations	Very low	Historical compilers; the operator stack inside RD parsers (GCC, LLVM MC)
Tomita GLR (GSS + SPPF)	All ε-free acyclic CFGs; all parses	$O(n^{p+1})$ · LR speed on deterministic regions	Returns every parse; ambiguity must be resolved (dprec/merge/dynamic precedence)	Moderate: GSS, path enumeration, forest	Bison `%glr-parser`, Elkhound, tree-sitter
RNGLR / BRNGLR	All CFGs; BRNGLR cubic	$O(n^{p+1})$ / $O(n^3)$ · research implementations	Same forests, correct with ε and hidden left recursion	High: RN tables, ε-SPPFs, binarization	Scott–Johnstone tools, SGLR-style systems
yacc `error` token	Resynchronizes where the author put error productions	$O(n \cdot d)$ extra · negligible	Generic "syntax error, unexpected X, expecting Y"; cascades limited by the 3-token rule	Low for the generator; the grammar author places error rules	Bison/yacc parsers, PostgreSQL-style DSLs
Burke–Fisher repair	Best single-token edit within a window	$O(k \lvert T \rvert (k + c))$ per error · milliseconds	"inserting )" style messages; can guess wrong	Moderate: deferred window, candidate generation	ML-Yacc; CPCT+ (grmtools)
Menhir `.messages` + reachability	Complete list of reachable error states; hand-written messages	LRijkstra polynomial · seconds–minutes offline	The best messages, maintained per state	High for the tool (done once), moderate for the grammar author	Menhir (OCaml, CompCert, Coq)
Generated LR parsers	LR(1) (IELR/Pager) + precedence + GLR where needed; the grammar is checked	$O(n)$ · fast tables; generation in seconds	Earliest detection; messages need `error` rules or `.messages`	Low per change; grammar expertise needed for conflicts	SQL engines, PHP, OCaml, CompCert, tree-sitter
Hand-written recursive descent	Anything, with tentative parsing and semantic lookups; no static check	$O(n)$ typical · often fastest	Best messages and recovery, tailored per construct	High, and grows with the language	GCC, Clang, rustc, Swift, Go, V8, Ruby's Prism

Comparison-lab results (reproduce with build/linux/bin/lr compare tests/ch02/Inputs/*.grammar tests/ch03/Inputs/*.grammar; golden tests/ch03/Inputs/corpus.compare): across the 33 grammars, LALR(1) never needs more states than LR(0) (by construction), canonical LR(1) needs 1.0–1.9× as many (1.44× on average) (e.g. 75 vs 43 for the Pebble-like statements.grammar, 54 vs 28 for json.grammar), and the classes separate as predicted: expr SLR(1), assign LALR(1), nonlalr/bison-mysterious/ll1-not-lalr LR(1), every LL(1) grammar at least LALR(1) except ll1-not-lalr.

Route through this chapter¶

Step	What	Techniques	How it is exercised
1	Lesson 3.1	shift-reduce, handles, viable prefixes, LR(0) automaton	drills `lr0-closure`, `shift-reduce-trace`; E1, E5
2	Lesson 3.2	SLR(1), canonical LR(1), LR(k) theory	drills `lr-table`, `lr0-closure --difficulty hard`, `lr-classify`; E2, E4
3	Lesson 3.3	LALR(1) by merging and by DeRemer–Pennello	drill `lalr-lookaheads`; E3
4	Lesson 3.4	Pager PGM, IELR(1), state counts	drill `lr-classify --difficulty hard`; ★ E6 (PGM); theory + Bison/Menhir
5	Lesson 3.5	conflicts, precedence declarations, operator precedence	drills `lr-table --difficulty hard`, `shift-reduce-trace --difficulty hard`; E4
6	Lesson 3.6	Tomita GLR, RNGLR/BRNGLR	★ lab G1 (`parseGLR`), `lr glr`
7	Lesson 3.7	yacc recovery, Burke–Fisher, Menhir `.messages`	theory + oracle traces + Bison/ML-Yacc/Menhir
8	Lesson 3.8	generators vs hand-written parsers	survey; quiz
9	Exercises and the lab spec `labs/ch03-lr-toolkit/SPEC.md`	You implement LR(0), SLR(1), LALR(1) two ways, LR(1), the table with precedence and the driver behind `include/lr/LR.h` (E1–E5)	`./course test 3`
10	Comparison lab, same spec	state and conflict counts of the four methods on 33 grammars; agreement with Chapter 2's LL(1) parser; ★ GLR forests	`ch03.Corpus/Classify.`, `ch03.AgreeWithLL1.`, `lr compare`
11	Theory test	all	`./course quiz 3` (≥ 80 % to finish)

Practice and check¶

./course drill lr0-closure --difficulty easy      # warm up; --solution shows every closure step
./course drill lr-table                           # SLR cells from an LR(0) automaton
./course drill shift-reduce-trace                 # drive a table by hand
./course drill lalr-lookaheads --difficulty hard  # DeRemer–Pennello relations and lookback
./course drill lr-classify --difficulty hard      # LR(0)/SLR/LALR/LR(1)/none + state counts
./course flash 3                                  # daily, a few minutes
./course quiz 3                                   # after the lessons
./course test 3                                   # after the exercises
build/linux/bin/lr report tests/ch03/Inputs/assign.grammar --method lalr   # 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] (§4.5–4.8, the classical presentation followed in Lessons 3.1–3.3 and 3.5), [Knu65] (where LR(k) and viable prefixes come from), [DP82] (LALR lookaheads, the algorithm Bison runs), [DM10] (IELR(1)), [SJ06] (GLR done right), [GJ08] (ch. 9 and 11, the broadest survey), [EaC3] (ch. 3, an engineering-first alternative), and [AJ74] (the classic LR tutorial).

Symbol	Meaning
\(G = (N, T, P, S)\), \(S'\)	a grammar and its augmented start symbol, with production \((0)\ S' \to S\) (Lesson 3.1 §2)
\(\Rightarrow_{\mathrm{rm}}\), \(\Rightarrow_{\mathrm{rm}}^{*}\)	rightmost derivation step(s) (Definition 2.1.2)
\(\alpha, \beta, \gamma, \delta \in (N \cup T)^{}\); \(w, x, y, z \in T^{}\)	strings of symbols; strings of terminals
\((A \to \beta, k)\)	a handle: production and the position where its right side ends (Definition 3.1.2)
\([A \to \alpha \bullet \beta]\), \([A \to \alpha \bullet \beta,\ a]\)	LR(0) and LR(1) items (Definitions 3.1.6, 3.2.2); in code `(p, d)` = production, dot position
\(V(\gamma)\), \(V_1(\gamma)\)	the LR(0) / LR(1) items valid for \(\gamma\)
\(\mathrm{CLOSURE}\), \(\mathrm{GOTO}\), \(\mathrm{CLOSURE}_1\), \(\mathrm{GOTO}_1\)	item-set operations (Definitions 3.1.7, 3.2.3)
\(\mathcal{A}_0 = (Q, \delta, q_0)\), \(\mathcal{A}_1\)	the canonical LR(0) automaton and the canonical LR(1) automaton; \(\delta^{}\) extends \(\delta\) to strings; \(p \xrightarrow{\beta} q\) means \(\delta^{}(p, \beta) = q\)
I0, I1, …	LR(0) states in the course's canonical numbering: breadth first, successors in symbol order (terminals by first appearance, then nonterminals)
ACTION\([q, a]\), GOTO\([q, A]\)	the parse table; actions `s`\(j\) (shift to \(j\)), `r`\(p\) (reduce by production \(p\)), `acc`
\(\mathrm{first}_1(x)\), \(\mathrm{FIRST}_k\)	first symbol of \(x\,\$\); first \(k\) symbols (Definition 2.3.2, 2.6.1)
\(\mathrm{LA}(q, A \to \omega)\)	the LALR(1) lookahead set of a reduce item (Definition 3.3.2)
\(\mathcal{N}\), \(\mathrm{DR}\), reads, includes, lookback, \(\mathrm{Read}\), \(\mathrm{Follow}(p, A)\)	DeRemer–Pennello's nonterminal transitions, relations and sets (Definition 3.3.3) — \(\mathrm{Follow}(p, A)\) is per transition, not the grammar-wide \(\mathrm{FOLLOW}(A)\)
\(\mathrm{lev}(t)\), \(\mathrm{assoc}(t)\)	precedence level and associativity of a declared token (Definition 3.5.3)
\(\lessdot\), \(\doteq\), \(\gtrdot\)	Floyd's operator-precedence relations (Definition 3.5.4)
\((s, i)\), \(U_i\), \((X, j, i)\)	a GSS node (state, level), the frontier at level \(i\), an SPPF symbol node deriving \(t_{j+1} \cdots t_i\) (Definitions 3.6.1–3.6.2)
\(\#(X, j, i)\)	the number of trees an SPPF node represents
\(n\), \(\lvert G \rvert\), \(\lvert Q \rvert\), \(p\)	input length; grammar size (number of LR(0) items); number of states; longest right side

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Shift-reduce parsing (with a handle oracle)	Any grammar for which the oracle exists; reverse rightmost derivation	\(O(n)\) moves · a table lookup per move	Depends on the oracle; LR oracles detect errors at the first bad token	The driver is 30 lines; the oracle is the work	Every LR, precedence and GLR parser
LR(0) automaton	Exactly the viable prefixes (Theorem 3.1.16); alone, only LR(0) grammars are deterministic	\(O(\lvert Q\rvert \lvert G\rvert)\), worst case exponential · 6 458 states for PostgreSQL in ~2 s	Items name every production that could be in progress (Menhir `.messages`, Lesson 3.7)	Moderate: closure, GOTO, hashing kernels	The core of every LR generator (yacc, Bison, Menhir, tree-sitter)
SLR(1)	SLR(1) grammars: LR(0) ⊊ SLR(1) ⊊ LALR(1); fails on context-dependent followers	LR(0) automaton + FOLLOW · as fast as LR(0)	Correct prefix, but extra reductions before an error; spurious conflicts	Low: LR(0) + FOLLOW	Teaching; historical generators
Canonical LR(1)	Exactly the LR(1) grammars (Theorem 3.2.12); ⊋ LL(1) (Theorem 3.2.14)	\(\lvert Q_1\rvert\) can be many times \(\lvert Q_0\rvert\) · PostgreSQL: > 600 s	Immediate error detection (no extra reductions); one state per context helps messages	Moderate: lookahead propagation in closure	Reference semantics; Menhir `--canonical`, Bison `canonical-lr`
LALR(1) by merging LR(1) states	LALR(1) = LR(0) states with the union of canonical lookaheads; can add reduce/reduce conflicts (Theorem 3.3.9)	Needs \(\mathcal{A}_1\) first · impractical for large grammars	Same table as DeRemer–Pennello	Low once LR(1) exists	Definition, testing, teaching
DeRemer–Pennello lookaheads	Identical sets (Theorem 3.3.12)	Linear in the relations · 2.2 s for PostgreSQL	Same table; lookaheads can be computed only where needed	Moderate: four relations and Digraph	Bison's default, most LALR generators
Pager's PGM	LR(1) (Theorem 3.4.8); merges only weakly compatible isocores	Near LALR · Menhir builds OCaml-scale grammars in seconds	No mysterious conflicts; error behavior between LALR and canonical	Moderate: LR(1) closure plus a merge test and re-expansion	Menhir (default), Hyacc
IELR(1)	Same actions as canonical LR(1), including resolved conflicts (Theorem 3.4.10); LALR-sized when LALR is adequate	LALR + annotations · PostgreSQL: 3.3 s vs 2.2 s	Exactly canonical decisions; still default reductions	High: five phases, annotation lists	Bison `%define lr.type ielr`
Conflict classification and counterexamples	Diagnoses every conflict; unifying ones prove ambiguity	Linear classification · counterexamples usually < 1 s	The best explanation a generator can give	Classification low; unifying search high	Every generator (Bison `-Wcounterexamples`, Menhir `.conflicts`)
Precedence and associativity declarations	Resolves operator ambiguities exactly (Theorem 3.5.10); can remove sentences if misapplied	Free at parse time; fewer states than layering	Silent once resolved; Bison logs with `--report=solved`	Trivial for the user	yacc/Bison/Menhir/tree-sitter expression grammars, PostgreSQL
Operator-precedence parsing	Operator-precedence grammars only; skeletons, may accept non-sentences	\(O(n)\), tiny tables	Weak: errors only on missing relations	Very low	Historical compilers; the operator stack inside RD parsers (GCC, LLVM MC)
Tomita GLR (GSS + SPPF)	All ε-free acyclic CFGs; all parses	\(O(n^{p+1})\) · LR speed on deterministic regions	Returns every parse; ambiguity must be resolved (dprec/merge/dynamic precedence)	Moderate: GSS, path enumeration, forest	Bison `%glr-parser`, Elkhound, tree-sitter
RNGLR / BRNGLR	All CFGs; BRNGLR cubic	\(O(n^{p+1})\) / \(O(n^3)\) · research implementations	Same forests, correct with ε and hidden left recursion	High: RN tables, ε-SPPFs, binarization	Scott–Johnstone tools, SGLR-style systems
yacc `error` token	Resynchronizes where the author put error productions	\(O(n \cdot d)\) extra · negligible	Generic "syntax error, unexpected X, expecting Y"; cascades limited by the 3-token rule	Low for the generator; the grammar author places error rules	Bison/yacc parsers, PostgreSQL-style DSLs
Burke–Fisher repair	Best single-token edit within a window	\(O(k \lvert T \rvert (k + c))\) per error · milliseconds	"inserting )" style messages; can guess wrong	Moderate: deferred window, candidate generation	ML-Yacc; CPCT+ (grmtools)
Menhir `.messages` + reachability	Complete list of reachable error states; hand-written messages	LRijkstra polynomial · seconds–minutes offline	The best messages, maintained per state	High for the tool (done once), moderate for the grammar author	Menhir (OCaml, CompCert, Coq)
Generated LR parsers	LR(1) (IELR/Pager) + precedence + GLR where needed; the grammar is checked	\(O(n)\) · fast tables; generation in seconds	Earliest detection; messages need `error` rules or `.messages`	Low per change; grammar expertise needed for conflicts	SQL engines, PHP, OCaml, CompCert, tree-sitter
Hand-written recursive descent	Anything, with tentative parsing and semantic lookups; no static check	\(O(n)\) typical · often fastest	Best messages and recovery, tailored per construct	High, and grows with the language	GCC, Clang, rustc, Swift, Go, V8, Ruby's Prism