Skip to content

Chapter 4 · Parsing in Practice: Expressions, Other Paradigms, Recovery & Syntax Trees

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

The problem

Chapters 2 and 3 answered "is this token sequence in \(L(G)\), and what is its tree?" for the grammar classes LL and LR. A production front end needs more: expressions with a dozen precedence levels parsed without a dozen functions; grammars that are not LL or LR (ambiguous, left-recursive, written for humans) parsed anyway; a parser that turns any text into a useful tree with every error reported once, and updates that tree in milliseconds after an edit; and a tree representation that later phases can walk, share and lower. The input is a token sequence (Chapter 1) plus a grammar or operator table; the output is a syntax tree (lossless or abstract) and a list of diagnostics. In pebblec this is parseModule(Lexer&, ASTContext&, DiagnosticEngine&) in pebble/lib/Parse, whose AST every later chapter reads; the chapter ends with how syntax is extended by macros before or during parsing.

What you will be able to do

  • Parse expressions with Pratt parsing, precedence climbing, shunting-yard and a layered grammar, prove the four agree (Theorem 4.1.14), and trace binding powers by hand.
  • Write a PEG, explain why ordered choice changes the language, make it linear with packrat memoization and handle left recursion by seed growing.
  • Fill Earley charts and CYK tables by hand, explain Leo's optimization and SPPFs, and say which paradigm accepts a given grammar.
  • Compare parser combinators (backtracking, committed choice, furthest failure, recovery) on real libraries: nom, Parsec, chumsky.
  • Implement pebblec's parser (recursive descent + Pratt) with multi-error recovery, error nodes, an error cap and a nesting limit, tested by golden ASTs, random precedence tests and round trips.
  • Explain resilient LL parsing, error nodes vs error productions, and incremental reparsing (tree-sitter, rust-analyzer), and build an item-level incremental reparser (★).
  • Choose a syntax-tree design (class hierarchy with LLVM RTTI, std::variant, arena/indices, red–green, CST → AST → HIR) for a given compiler, and explain token vs AST macros and hygiene.

Prerequisites: Ch 1 (tokens, lossless lexing), Ch 2 (grammars, FIRST/FOLLOW, recursive descent, panic-mode recovery), Ch 3 (LR items, GLR and the graph-structured stack, SPPF).

Notation

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

Symbol Meaning
\(T = (O, \mathrm{lev}, \mathrm{assoc}, \mathrm{Pre})\), \(O_p\), \(k\) an operator table: infix operators, levels \(1..k\) (1 loosest), associativity per level, prefix operators at level \(k+1\); \(O_p\) the operators of level \(p\) (Definition 4.1.1)
\(E_1, \dots, E_{k+1}\) the nonterminals of the layered grammar \(G_T\), one per level (Definition 4.1.2)
chunk, depth-0 operator a maximal operand with its prefix operators, and an operator outside every parenthesis (Definition 4.1.3)
\((\mathrm{lbp}(o), \mathrm{rbp}(o))\), \(\lambda(m)\) the left and right binding powers of an operator: \((2p, 2p+1)\) for left/non-associative level \(p\), \((2p+1, 2p)\) for right; \(\lambda(m) = \max(1, \lceil m/2 \rceil)\) the lowest level allowed at minimum power \(m\) (Definition 4.1.7)
\(G = (N, T, R, e_S)\), \(e_1 / e_2\), \(\&e\), \(!e\) a PEG, ordered choice, and- and not-predicates (Definition 4.2.1)
\(\mathrm{match}(e, i)\), \(\mathsf{fail}\) the PEG match function: end position or failure (Definition 4.2.2)
\([A \to \alpha \bullet \beta, j]\), \(S_0, \dots, S_n\) an Earley item with origin \(j\); the Earley sets (Definition 4.3.1)
\(\tau(B, i)\) the topmost item of Leo's deterministic reduction path (Definition 4.3.5)
\((X, i, j)\), \((A \to \alpha \bullet \beta, i, j)\) SPPF symbol and intermediate nodes spanning \(t_{i+1} \cdots t_j\) (Definition 4.3.7)
\(V[i, j]\) the CYK table cell: nonterminals deriving the substring of length \(j\) starting at \(i\) (Algorithm 4.4.3)
\(X ::= \alpha \cdot \beta\), \(\langle L, j \rangle\), \((L, u, i)\), \(\mathcal{U}_i\), \(\mathcal{P}\) a grammar slot, a GSS node, a GLL descriptor, the descriptors created at \(i\), the popped set (Definition 4.4.4)
\(p : T^{*} \to \mathrm{List}(\tau \times T^{*})\), \(\mathbin{>\!\!>\!\!=}\) a list-of-successes parser and sequencing (Definition 4.5.1)
\(\mathsf{Cok}, \mathsf{Cerr}, \mathsf{Eok}, \mathsf{Eerr}\) Parsec's four replies: consumed/empty × ok/error (Definition 4.5.4)
\(R\) (recovery set), ERROR the tokens an enclosing construct can use; an error node (Definitions 4.6.1–4.6.2)
\([a, b) \mapsto s\) an edit replacing bytes \(a..b-1\) by \(s\) (Definition 4.6.5)
\(\kappa\), \(S_D\), \(\mathit{first}(D)\), \(\mathit{last}(D)\) kind numbering of a class hierarchy and the kinds below class \(D\) (Definition 4.7.1)
\(w(g)\), \(r_i\), \((g, \text{parent}, o)\) width of a green element, relative offset of child \(i\), a red node with absolute offset \(o\) (Definition 4.7.7)
\(\ell : L_1 \to L_2\), \([\![\cdot]\!]\) a lowering between tree languages and their meaning (Definition 4.7.9)
\(\mu\), \((n, c)\) an expansion mark; an identifier with name \(n\) and syntax context \(c\) (Definition 4.8.5)
\(n\), \(\lvert G \rvert\), \(d\) input length (tokens or bytes, as stated), grammar size, tree depth

Technique map

Family Techniques (origin) Lesson
Expression parsing precedence-layered grammar (ALGOL 60 report, Naur 1960); precedence climbing (Richards 1979; Clarke 1986); Pratt parsing / top-down operator precedence (Pratt 1973); shunting-yard (Dijkstra 1961) — and the proof that they agree 4.1
PEG and packrat parsing expression grammars (Ford 2004; TDPL, Birman & Ullman 1973); packrat memoization (Ford 2002); left recursion by seed growing (Warth, Douglass & Millstein 2008) and bounded left recursion (Medeiros, Mascarenhas & Ierusalimschy 2014) 4.2
Earley parsing Earley's algorithm (Earley 1970) with nullable handling (Aycock & Horspool 2002); Leo's right-recursion optimization (Leo 1991); SPPFs from Earley charts (Scott 2008) 4.3
CYK and GLL Chomsky normal form and CYK (Kasami 1965; Younger 1967), Valiant's reduction (1975); GLL (Scott & Johnstone 2010) 4.4
Parser combinators list of successes (Wadler 1985; Hutton & Meijer 1996/1998) and backtracking libraries (nom); committed choice and try (Parsec, Leijen & Meijer 2001); furthest-failure errors and recovery (Ford 2002; chumsky) 4.5
Resilient and incremental parsing resilient LL with recovery sets (rust-analyzer; Kladov 2023); error nodes vs error productions (yacc, Johnson 1975); incremental LR with subtree reuse (Wagner & Graham 1998; tree-sitter, Brunsfeld 2018); block-level reparsing (rust-analyzer) 4.6
Syntax-tree design class hierarchies with LLVM-style RTTI (Clang); sum types / std::variant (ML datatypes; the expression problem, Wadler 1998); arena and index-based trees (Hanson 1990; rustc HirId); lossless red–green trees (Roslyn; rowan; SwiftSyntax); lowering CST → AST → HIR (rustc) 4.7
Syntax extension token-based macros (the C preprocessor); AST-based macros (macros by example, procedural and Swift macros); hygiene (Kohlbecker et al. 1986; Dybvig, Hieb & Bruggeman 1992; Flatt 2016) 4.8 
flowchart LR
  subgraph EXPR[Expression parsing]
    L[Layered grammar<br/>Naur 1960] -->|one loop per level| C[Precedence climbing<br/>Richards 1979, Clarke 1986]
    C -->|levels to binding powers| P[Pratt<br/>1973]
    C -->|explicit stacks| S[Shunting-yard<br/>Dijkstra 1961]
  end
  subgraph GEN[Beyond LL/LR]
    RD[Backtracking RD] -->|ordered choice, predicates| PEG[PEG<br/>Ford 2004]
    PEG -->|memoize| PK[Packrat<br/>Ford 2002]
    PK -->|seed growing| LR[Left-recursive PEG<br/>Warth 2008]
    E[Earley 1970] -->|right recursion| LEO[Leo 1991]
    E -->|all parses| SP[SPPF<br/>Scott 2008]
    CYK[CYK 1965-67] -->|matrix mult.| VAL[Valiant 1975]
    GLR[GLR, Ch 3] -->|same GSS, top-down| GLL[GLL<br/>Scott & Johnstone 2010]
    RD -->|as a library| COMB[Combinators<br/>Wadler 1985, Parsec 2001]
  end
  subgraph IDE[Resilience and incrementality]
    PM[Panic mode, Ch 2] -->|recovery sets, error nodes| RES[Resilient LL<br/>rust-analyzer]
    YE[yacc error productions<br/>Johnson 1975] -.->|alternative| RES
    WG[Wagner & Graham 1998] -->|GLR + reuse| TS[tree-sitter]
    RES -->|persistent trees| BR[Block reparsing]
  end
  subgraph TREES[Trees and extension]
    H[Class hierarchy + RTTI] ---|expression problem| V[Sum types]
    AR[Arenas and indices] --> H
    AR --> V
    RG[Red-green trees<br/>Roslyn, rowan] -->|lower| AST[AST] -->|desugar| HIR[HIR]
    TOK[Token macros, cpp] -->|parse fragments| MBE[AST macros]
    MBE -->|marks| HYG[Hygiene<br/>Kohlbecker 1986]
  end
  RES --> RG
  BR --> RG

Who uses what

System Technique Notes
Clang/LLVM 23 precedence climbing (ParseRHSOfBinaryExpression); class hierarchy + LLVM RTTI in a bump arena; token-based preprocessor Lessons 4.1, 4.7, 4.8
GCC 15 shunting-yard-style operator stack for binary expressions (c_parser_binary_expression, cp_parser_binary_expression) Lesson 4.1
rustc 1.94 precedence climbing (parse_expr_assoc_with); sum-type AST; HirId indices; CST-free AST → HIR lowering; macros by example with mixed-site hygiene Lessons 4.1, 4.7, 4.8
rust-analyzer Pratt (expr_bp); resilient LL with recovery sets; red–green trees (rowan); block-level reparsing Lessons 4.1, 4.6, 4.7
CPython 3.11+ PEG with packrat memoization and left recursion (pegen) Lesson 4.2
tree-sitter 0.25 GLR with incremental subtree reuse and error recovery Lesson 4.6
Lark 1.3 Earley (SPPF, explicit ambiguity), CYK, LALR Lessons 4.3, 4.4
Swift 6 / swift-syntax sequence folding of operators after parsing; lossless trees with a raw arena; recovery by precedence; macros on syntax trees Lessons 4.1, 4.6, 4.7, 4.8
Go 1.24, V8 13 precedence climbing (parseBinaryExpr, ParseBinaryExpression) Lesson 4.1
nom 8, Parsec 3.1, chumsky 0.10 combinators: backtracking, committed choice, recovery Lesson 4.5
Roslyn (C#) red–green trees, skipped-token trivia Lessons 4.6, 4.7
pebblec recursive descent + Pratt, panic-mode recovery with sync sets and error nodes; class hierarchy in a bump arena Exercises

Comparison

The rows are the lessons' comparison tables (§8), verbatim, in lesson order.

Technique Power / precision Speed (asymptotic · practical) Output / error quality Implementation effort Typical use
Precedence-layered grammar Any finite table of infix levels (+ prefix above them), as an unambiguous CFG usable by every LL/LR/PEG tool \(\Theta(k\,n)\) · up to \((k+1)\) calls per operand (16 calls for 6 operands in §3) The grammar documents the language; errors per level ("expected term") Low per level, but one rule and function per level Language standards, generated parsers, CPython's PEG grammar
Precedence climbing Same trees as the layered grammar (Theorem 4.1.14); ?: and context flags added by hand \(\Theta(n)\) · one call per operand Good; errors where an operand is missing Low: one loop and a level table Clang, Go, rustc, V8
Pratt parsing Same, plus prefix/postfix/mixfix/call/index as per-token handlers \(\Theta(n)\) · one call per operand (1.18 steps/token, 7.8 ms at 28 500 tokens in the lab) Good; handlers give token-specific messages Low: a table of (nud, led, powers) rust-analyzer, JSLint, pebblec
Shunting-yard Same trees; prefix/postfix via a two-state automaton \(\Theta(n)\) · no recursion (1.18 steps/token, 5.8 ms at 28 500 tokens in the lab) Weaker: errors are detected on stack states, far from their cause Low for infix; fiddly for calls and prefix operators GCC's C/C++ binary expressions, calculators, RPN conversion
Parsing expression grammars Unambiguous by construction; recognizes some non-CFLs (\(a^m b^m c^m\), Theorem 4.2.5); ordered choice can silently shrink a CFG's language (Proposition 4.2.6) Linear with packrat; exponential without on adversarial grammars Furthest-failure messages; no conflicts to report Low: the grammar is the parser CPython, DSLs (pest, PEG.js, LPeg), scannerless parsers
Packrat memoization Same language as the PEG \(O(\lvert G \rvert\, n)\) · 4.46 calls+hits/token and 11.5 ms at 28 500 tokens in the lab Same as PEG Low: one table CPython (selectively), the lab
Left recursion in PEGs (seed growing) Adds direct (and, with cycle leaders, indirect) left recursion with left-nested trees One extra round per left-recursive call Same as PEG Medium: the growing loop and the leader analysis CPython's sum/term, Ohm, pegen
Earley (with Aycock–Horspool) Every CFG, exact (Theorem 4.3.8); left recursion and ε included \(O(n^3)\), \(O(n^2)\) unambiguous, linear on bounded-state grammars · 25.3 items/token, 157 ms at 28 500 tokens in the lab (≈20× Pratt) Correct-prefix error position (first empty set); the chart lists what was expected Medium: three operations plus tree extraction Lark, Marpa, NLTK, grammar prototyping, the lab
Leo's completer Same language; removes right-recursion blow-up Linear on LR-regular grammars (all LR(k)) Same; trees need path expansion Medium–high (tree recovery) Marpa; general parsers for grammars written with right recursion
SPPF construction All parses of an ambiguous sentence in \(O(n^3)\) space Proportional to the chart Every tree, shared and packed Medium (binarization) Lark ambiguity="explicit", GLL/GLR back ends, grammar debugging
CYK Every CFG (after CNF, Theorem 4.4.6), exact membership, all parses countable \(\Theta(n^3 \lvert P \rvert)\) on every input (166 million span/split pairs at \(n = 1000\)) No error position (only "not in \(V[1,n]\)"); trees over CNF helpers unless reverted Low: three loops + CNF conversion NLP (probabilistic CKY), teaching, Lark, complexity theory
GLL Every CFG, left recursion and ambiguity included; SPPF of all parses \(O(n^3)\); near-linear on near-deterministic grammars with FIRST/FOLLOW tests Recursive-descent-shaped; errors at the furthest descriptor position Medium–high: GSS, descriptors, SPPF Grammar engineering (Iguana, Rascal), language composition, gll-pg
Backtracking combinators (list of successes; nom-style ordered choice) All parses of any non-left-recursive CFG (list of successes); PEG semantics for single-result backtracking (Proposition 4.5.9) Exponential worst case; linear when failures are shallow Poor by default: leftover input instead of an error (nom box) unless errors are merged or cut is used Lowest: a library, grammar in the host language nom for binary formats, prototypes, small DSLs
Committed choice (Parsec + try) LL(1)-style predictive, plus local backtracking where try is written \(O(k\,n)\) without try (Theorem 4.5.10) Good: the error is at the first token no alternative consumes (column 9 and 6 in the Parsec box) Low; try placement needs understanding Parsec/Megaparsec in Haskell compilers and tools
Furthest-failure reporting and recovery (chumsky) Adds error merging and recovery to either family \(O(1)\) per failure; recovery linear in skipped tokens Best among combinators: several errors per run, partial ASTs with placeholders Medium: recovery strategies per construct chumsky-based compilers and language servers, packrat parsers
Resilient LL parsing Any input → a tree with every token; well-formed parts intact \(O(n\,D)\) · no measurable cost over a non-recovering parser Errors at the offending token, no cascades (6 errors, 0 cascades on err-statements.pbl) Medium: recovery sets per list, discipline in every function rust-analyzer, swift-syntax, pebblec
Error nodes vs error productions Error nodes: exact skipped regions in the tree; error productions: grammar-level resynchronization Both linear Error nodes: precise and tool-friendly; productions: coarse ("skipped to ;") Nodes: in the parser; productions: in the grammar Nodes: IDE parsers; productions: yacc/Bison grammars
Incremental LR with subtree reuse Exact (Theorem 4.6.11) for LR and, in tree-sitter, GLR grammars \(O(e + d)\) per edit · 62 ms vs 374 ms full on 20 000 functions Keeps error nodes across edits; changed ranges for highlighting High: stateful nodes, breakdown, lexer lookahead tracking tree-sitter (GitHub, Neovim, Zed, Helix), Ensemble
Block-level reparsing Exact when it does not fall back (Theorem 4.6.12) \(O(b + d)\) · one block or item Same as the underlying parser Low–medium: persistent trees + a fallback rust-analyzer, the lab's ★
Class hierarchies with LLVM-style RTTI Any node shape; open to new operations via visitors \(O(1)\) kind tests · Clang nodes 16–32 B, 2 slabs for a small file Exhaustiveness only via -Wswitch Medium: node list + classof per class (generated) Clang, LLVM IR, Swift, pebblec
Sum types with std::variant Closed set of kinds, checked exhaustive case analysis \(O(1)\) visit · every node sized to the largest alternative (24 B example) Missing cases rejected at compile time (7 errors, library-deep) Low in Rust/ML; medium in C++ rustc AST/HIR, OCaml, GHC
Arena and index-based trees Any shape; ids usable as keys in side tables \(O(1)\) bump allocation (Prop. 4.7.13) · 4-byte links Stale indices are logic errors, not crashes Low Clang/pebblec arenas, rustc HirId, the lab's Tree.h
Lossless red–green trees Every byte kept; shareable across versions \(O(1)\) navigation, \(O(d)\) edits · 1+1 shared, 1 + 1 not Error tokens stay in the tree (Lesson 4.6) High: two layers, interning, typed views Roslyn, rust-analyzer, SwiftSyntax
Lowering CST → AST → HIR Each level fits one family of phases \(O(n)\) per level Diagnostics must map back through ids/spans Medium per level rustc, rust-analyzer, Swift, Kotlin
Token-based macros Any token rewrite, no structure; DOUBLE(1 + 2) = 5 \(O(N \cdot d)\) · fast, before parsing Errors point into expansions ("expanded from macro"); no grouping, no scoping Low C, C++, assembly, #include guards
AST-based macros Rewrites of parsed fragments; double!(1 + 2) = 6 matching per rule, parsing per expansion Errors in terms of fragments; "no rules expected this token" Medium (by example) to high (procedural) Rust, Scheme, Swift, Elixir
Hygiene Prevents capture both ways (Theorem 4.8.10) \(O(N)\) with lazy marks, \(O(N^2)\) eager Correct programs by default (tmp=2 other=1) Medium: contexts on every identifier, resolution by context Rust, Racket, Scheme; not C or Swift

Comparison-lab results (reproduce with build/<preset>/bin/ch04-parsebench): at about 28 500 tokens of random Pebble expressions, Pratt 7.8 ms (1.18 steps/token), shunting-yard 5.8 ms (1.18), packrat 11.5 ms (4.46 calls + hits/token), Earley 157 ms (25.3 items/token); all four grow linearly on this grammar (Proposition 4.3.12 for Earley).

Route through this chapter

Step What Techniques How it is exercised
1 Lesson 4.1 layered grammar, climbing, Pratt, shunting-yard drills pratt-trace, shunting-yard; quiz; flashcards
2 Exercises E1–E6 pebblec uses recursive descent + Pratt with panic-mode recovery (full implementation) ./course test 4 (ch04.PebbleParser.*, lit goldens)
3 Lesson 4.2 PEG, packrat, left recursion drill packrat-memo; quiz
4 Lesson 4.3 Earley, Leo, SPPF drill earley-chart; quiz
5 Comparison lab labs/ch04-paradigms/ L1–L5 Pratt vs shunting-yard vs packrat vs Earley lab tests + ch04-parsebench measurements
6 Lesson 4.4 CYK, GLL (theory + drills + oracle) drills cyk-table, paradigm-accepts; quiz
7 Lesson 4.5 combinators (theory + real library runs) quiz; flashcards
8 Lesson 4.6 resilient LL, error nodes, incremental LR, block reparsing exercises E5–E6; ★ lab L6 (item-level incremental reparser)
9 Lessons 4.7 and 4.8 tree designs, lowering, macros, hygiene (theory + real compiler runs) quiz; flashcards
10 Theory test all ./course quiz 4 (≥ 80 % to finish)

Practice and check

./course drill pratt-trace --difficulty easy          # warm up; --solution shows every step
./course drill shunting-yard
./course drill packrat-memo
./course drill earley-chart
./course drill cyk-table
./course drill paradigm-accepts
./course flash 4                                      # daily, a few minutes
./course quiz 4                                       # after the lessons
./course test 4                                       # after the exercises and the lab
./course status                                       # done = quiz ≥ 80 % and tests pass

References

The chapter's annotated bibliography — papers, textbook sections, pinned source files, docs, talks — is in references.md. Start with: [Pra73] (Pratt's paper, short and still the best introduction to binding powers), [For04] (the PEG paper, with the formal semantics of Lesson 4.2), [Ear70] (Earley's algorithm), [Kla23] (resilient LL parsing as rust-analyzer does it), [WG98] (incremental LR parsing) and [KFFD86] (hygienic macro expansion).