Lesson 3.8 — Bottom-up parsing in practice: generators vs hand-written parsers¶

Techniques: generated LR parsers in production (Bison/yacc, Lemon, Lrama, Menhir, tree-sitter); hand-written recursive descent as the alternative most production compilers chose (GCC's C++ parser rewrite, GCC 3.4, 2004; its C parser, GCC 4.1; Clang; Ruby's Prism) · Pebble implements: hand-written recursive descent (Ch 2, Ch 4) · Lab: the comparison lab's corpus measurements (lr compare) · Prerequisites: Lessons 3.1–3.7 · Time: 1.5 hours

You now know what LR generators can do: accept left-recursive grammars, prove the grammar unambiguous, detect every syntax error at the earliest token, and run in linear time with small tables. Yet GCC, Clang, rustc, Swift, Go, V8 and (since 2024) Ruby parse with hand-written recursive descent. This lesson weighs the two sides with evidence from real systems, so that you can decide for your own language.

1. Problem and motivation¶

Input: a programming language to implement. Output: a parser architecture — generated from a grammar or written by hand — that meets the project's needs for correctness, speed, error messages, tooling and maintenance over decades.

Generated LR parsers in production¶

LR generators remain dominant where the grammar is large, changes often and is owned by people who want the grammar to be the specification: database query languages (PostgreSQL's 19 513-line Bison grammar with %expect 0 [PG-gram], MySQL, SQLite's Lemon grammar [SQLITE-parse]), scripting languages (PHP's zend_language_parser.y [PHP-parser], Ruby's parse.y until 3.4, built with Bison until 3.3 and with the Lrama LALR generator since [RUBY-news33]), OCaml (Menhir since OCaml 4.08 [OCAML-parser]), verified compilers (CompCert's C parser, whose LR(1) automaton is validated in Coq [JPL12]) and editor tooling (tree-sitter grammars for hundreds of languages [TS-docs]).

Hand-written recursive descent in production compilers¶

The large C-family compilers went the other way. GCC's C++ front end had a yacc grammar (parse.y) that could not express C++ without lexer feedback and hacks; Mark Mitchell's hand-written parser replaced it (the ChangeLog entry "parse.y: Remove." is dated 2002-12-30, released in GCC 3.4, 2004 [GCC34, GCC-CPChangeLog]), and Joseph Myers' hand-written C parser replaced c-parse.in in GCC 4.1 [GCC41]. Clang was hand-written from the start; Ruby 3.4 made the hand-written Prism parser its default [RUBY-news34]. The reasons are recurring: languages that are not LR(k) (C++'s declaration/expression ambiguity, contextual keywords), error messages and recovery tailored per construct, tooling (IDE, incremental reparsing, lossless trees), and control over performance.

2. Definitions and algorithms¶

This lesson is a survey. The objects it compares are defined elsewhere: LR tables and generators (Lessons 3.1–3.4), conflicts and precedence (Lesson 3.5), GLR (Lesson 3.6), error recovery (Lesson 3.7); recursive descent and tentative parsing (Lesson 2.5). The decision procedure used in §8 is:

function ChooseParser(language, project):
    if the grammar is the specification and changes often (SQL, DSLs):   generate (IELR/LALR + precedence)
    if the language is not LR(k) and ambiguities need semantics (C++):   hand-written RD with tentative
                                                                          parsing, or GLR with semantic filters
    if error messages are a product feature:                            RD, or LR + Menhir .messages
    if the parser feeds an editor (incremental, error-tolerant):        tree-sitter (GLR) or resilient RD
    if a machine-checked parser is required:                            Menhir --coq (validated LR(1))

Generated LR parsers in production¶

The shape of a production LR setup: a grammar file with precedence declarations and %expect, a generator run at build time (Bison -Wcounterexamples in CI), semantic actions that build the AST, error productions or .messages files for diagnostics, and sometimes a lexer hack or GLR mode for the few places the language is not LR(1).

Hand-written recursive descent in production compilers¶

The shape of a production recursive-descent parser: one function per construct, precedence climbing for expressions, tentative (backtracking) parsing with state snapshots for the non-LL(k) spots, and recovery by skipping to synchronizing tokens with context-specific messages.

3. Worked example¶

Generated LR parsers in production on an example¶

The course corpus measured by the comparison lab (lr compare, golden tests/ch03/Inputs/corpus.compare): of the 22 Chapter 2 grammars, 12 are LR(1) — every LL(1) one among them — and the 10 non-LR(1) ones are ambiguous or need more lookahead; the Pebble-like statements.grammar is SLR(1) with 43 LR(0) states against 75 canonical LR(1) states. The real grammar in the box below (PostgreSQL 17) has 3 408 rules and 6 458 LALR states, conflict-free.

grammar	LR(0) states	LR(0) conflicts	SLR	LALR	LR(1) states	class
`statements` (ch02)	43	18 s/r	0	0	75	SLR(1)
`json` (ch02)	28	12 s/r	0	0	54	SLR(1)
`assign` (ch03)	10	1 s/r	1 s/r	0	14	LALR(1)
`bison-mysterious` (ch03)	19	1 s/r, 4 r/r	1 r/r	1 r/r	21	LR(1)
`dangling-else` (ch02)	11	1 s/r	1 s/r	1 s/r	19	none

Hand-written recursive descent in production compilers on an example¶

C++'s T * x; is a declaration if T names a type and an expression otherwise — no LR(k) table can decide it from the tokens alone (the grammar is ambiguous; Theorem 3.2.13). GLR keeps both parses (Lesson 3.6's tree-sitter box); GCC and Clang parse tentatively: try the declaration, roll back on failure (the GCC comment in the box below).

4. Invariants and correctness¶

Generated LR parsers in production¶

What a generator guarantees and a hand-written parser does not: the grammar has no unresolved conflicts (so it is unambiguous up to the declared resolutions, Theorem 3.2.13), the parser accepts exactly the language of the grammar with those resolutions (Theorem 3.5.9), errors are detected at the earliest token (Lemma 3.2.11), and running time is linear (Proposition 3.1.20). CompCert goes further: Menhir's --coq back end emits a certificate that a validator proved correct in Coq checks against the grammar [JPL12].

Hand-written recursive descent in production compilers¶

A hand-written parser has none of these guarantees by construction; they are recovered by testing (conformance suites, fuzzing, differential testing against another parser) and by keeping each function a faithful transcription of an LL(1) row where possible (Lesson 2.5). Tentative parsing can make the worst case exponential if nested; production parsers bound it by committing early.

5. Complexity¶

Technique	Time (worst)	Time (typical)	Space	Notes
Generated LR	\(O(n)\) parse; generation \(O(\lvert Q \rvert \cdot \lvert G \rvert)\)-ish, seconds for PostgreSQL	table lookups, very fast	tables: PostgreSQL's `gram.c` is 2.9 MB of C	generation cost is paid at build time
Hand-written RD	\(O(n)\) when LL(1)-like; exponential with unbounded tentative parsing	often the fastest option (no table interpretation, direct code)	code size ∝ grammar	Clang/GCC bound backtracking

Generated LR parsers in production¶

Lexer feedback ("the lexer hack", C typedef names): the parser tells the lexer which identifiers are types — trade-off: keeps an LALR grammar for C, couples lexer and parser (Ch 1).
Generator replacement (Ruby: Bison → Lrama [RUBY-news33]): own the generator to add features (named references, parameterized rules) — trade-off: maintenance of a generator.
Verified parsers (Menhir --coq, CompCert [JPL12]) — trade-off: proof of correctness, slower table-driven interpreter.

Hand-written recursive descent in production compilers¶

Pratt/precedence climbing for expressions (Ch 4) — trade-off: compact, fast; precedence lives in code.
Lossless, error-resilient trees (Roslyn, rust-analyzer, Swift's swift-syntax, Prism) — trade-off: every token kept; more memory, better tooling.

7. In real compilers¶

Generated LR parsers in production¶

PostgreSQL (REL_17_0) src/backend/parser/gram.y [PG-gram]; SQLite (version-3.46.0) src/parse.y with the Lemon generator tool/lemon.c [SQLITE-parse]; PHP (php-8.3.0) Zend/zend_language_parser.y (%define api.pure full, %expect 0) [PHP-parser]; Ruby (v3_4_0) parse.y, built with Lrama tool/lrama/ [RUBY-news33]; OCaml (5.2.0) parsing/parser.mly for Menhir [OCAML-parser].

PostgreSQL 17's grammar through Bison: LALR vs IELR

Reproduce (bison 3.8.2, PostgreSQL source at tag REL_17_0; needs network):

curl -sS -o gram.y https://raw.githubusercontent.com/postgres/postgres/REL_17_0/src/backend/parser/gram.y
wc -l < gram.y
grep -nE '^%(expect|pure-parser)' gram.y
for t in lalr ielr; do
  bison -Wno-deprecated -Dlr.type=$t --report=states --report-file=$t.output -o /dev/null gram.y
  echo "$t: $(grep -cE '^State [0-9]+$' $t.output) states"
done
sed -n '/^Grammar$/,/^Terminals, with rules/p' lalr.output | grep -cE '^ +[0-9]+ '

Output (complete):

19513
222:%pure-parser
223:%expect 0
lalr: 6458 states
ielr: 6459 states
3408

What to notice: 3 408 rules (including rule 0), 6 458 LALR states — under two states per rule — and %expect 0: the whole SQL grammar is conflict-free after its 23 precedence lines (Lesson 3.5). IELR adds a single state. On the course container LALR took about 2.2 s and IELR 3.3 s, while -Dlr.type=canonical-lr did not finish within 600 s (measured with date around the same commands) — the case for LALR/IELR at scale [PG-gram, BISON-Manual].

Hand-written recursive descent in production compilers¶

GCC (15.1.0) gcc/cp/parser.cc (the C++ parser; its "Methodology" comment is quoted below) and gcc/c/c-parser.cc [GCC-CPParser, GCC-CParser]; the removal of parse.y is in gcc/cp/ChangeLog.3 at tag releases/gcc-3.4.0 [GCC-CPChangeLog].
Clang (23.1.2) clang/lib/Parse/ParseTentative.cpp — Parser::isCXXDeclarationStatement, the tentative parse for exactly the T * x; ambiguity [CLANG-ParseTentative].
Ruby (v3_4_0) prism/prism.c — the hand-written parser that is the default since Ruby 3.4 ("The default parser is now Prism", NEWS.md); it uses a Pratt parser for expressions [RUBY-news34].

GCC's C++ parser explains its method; Clang's recovery at work

Reproduce (GCC source at releases/gcc-15.1.0, needs network; clang 23.1.2):

curl -sS https://raw.githubusercontent.com/gcc-mirror/gcc/releases/gcc-15.1.0/gcc/cp/parser.cc \
  | sed -n '/The parser is of the standard recursive-descent variety/,/a different alternative\./p'
cat > broken.c <<'EOF'
int f(int a, int b) {
  int x = a + ;
  return x * (b;
}
EOF
clang-23 -fsyntax-only -fno-color-diagnostics broken.c

Output (complete):

   The parser is of the standard recursive-descent variety.  Upcoming
   tokens in the token stream are examined in order to determine which
   production to use when parsing a non-terminal.  Some C++ constructs
   require arbitrary look ahead to disambiguate.  For example, it is
   impossible, in the general case, to tell whether a statement is an
   expression or declaration without scanning the entire statement.
   Therefore, the parser is capable of "parsing tentatively."  When the
   parser is not sure what construct comes next, it enters this mode.
   Then, while we attempt to parse the construct, the parser queues up
   error messages, rather than issuing them immediately, and saves the
   tokens it consumes.  If the construct is parsed successfully, the
   parser "commits", i.e., it issues any queued error messages and
   the tokens that were being preserved are permanently discarded.
   If, however, the construct is not parsed successfully, the parser
   rolls back its state completely so that it can resume parsing using
   a different alternative.
broken.c:2:15: error: expected expression
    2 |   int x = a + ;
      |               ^
broken.c:3:16: error: expected ')'
    3 |   return x * (b;
      |                ^
broken.c:3:14: note: to match this '('
    3 |   return x * (b;
      |              ^
2 errors generated.

What to notice: "arbitrary look ahead" is exactly why C++ is not LR(k); tentative parsing is a bounded, hand-controlled form of the GLR idea (keep alternatives alive until the input decides). Clang reports both independent errors, each with a construct-specific message and a note pointing at the unmatched ( — the kind of message that needs a Menhir .messages entry per state in an LR parser (Lesson 3.7).

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
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

Choose a generator when the grammar is large and evolving, correctness of the language definition matters more than bespoke messages, or you want a machine-checked parser. Choose hand-written recursive descent when the language needs semantic disambiguation, error messages are a product feature, and a team will own the parser for decades. pebblec takes the second road for its parser (Ch 4) and uses this chapter's LR toolkit to check that its grammar is LR(1) and to compare parses.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch03.yaml`)	Drill	Flashcard tag	Exercises
Generated LR parsers	`where-lr-dominates`, `lr-hierarchy`	`./course drill lr-classify` (is this grammar suitable for a generator?)	`lr-practice`	comparison lab measurement (SPEC)
Hand-written RD	`where-lr-dominates`, `llparser-technique`	none (an engineering decision; §8's procedure is the exercise)	`lr-practice`	—

Generators are not obsolete

"Every real compiler uses recursive descent" is true for C-family compilers, not for the software world: most SQL you run is parsed by an LR parser, and most syntax highlighting you see in editors comes from tree-sitter's GLR parsers.

References¶

See the chapter references.

Lesson 3.8 — Bottom-up parsing in practice: generators vs hand-written parsers¶

1. Problem and motivation¶

Generated LR parsers in production¶

Hand-written recursive descent in production compilers¶

2. Definitions and algorithms¶

Generated LR parsers in production¶

Hand-written recursive descent in production compilers¶

3. Worked example¶

Generated LR parsers in production on an example¶

Hand-written recursive descent in production compilers on an example¶

4. Invariants and correctness¶

Generated LR parsers in production¶

Hand-written recursive descent in production compilers¶

5. Complexity¶

6. Variants and refinements¶

Generated LR parsers in production¶

Hand-written recursive descent in production compilers¶

7. In real compilers¶

Generated LR parsers in production¶

Hand-written recursive descent in production compilers¶

8. Comparison¶

9. Assessment¶

References¶