Skip to content

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

Every source this chapter cites, grouped by kind. Lessons cite entries inline as [KEY]; each entry says why and when to read it. Core reading marks the entries the chapter assumes you will open.

Foundational and research papers

  • [AH02] John Aycock and R. Nigel Horspool. Practical Earley parsing. The Computer Journal 45(6), 620–630, 2002. doi:10.1093/comjnl/45.6.620
    Why and when: The nullable fix to the predictor used in Algorithm 4.3.3, with a proof that it is enough. Read §2–3 after the ε example of Lesson 4.3 §3.
    Cited in: 03-earley

  • [BU73] Alexander Birman and Jeffrey D. Ullman. Parsing algorithms with backtrack. Information and Control 23(1), 1–34, 1973. doi:10.1016/S0019-9958(73)90851-6
    Why and when: TDPL/GTDPL, the formal ancestors of PEGs, and the tabular linear-time algorithm that packrat parsing revived (Lesson 4.2 §1). Read the definitions only.
    Cited in: 02-peg-and-packrat

  • [DHB92] R. Kent Dybvig, Robert Hieb, and Carl Bruggeman. Syntactic abstraction in Scheme. Lisp and Symbolic Computation 5(4), 295–326, 1992. doi:10.1007/BF01806308
    Why and when: syntax-case with lazily applied marks: hygiene in linear time instead of the quadratic eager renaming (Lesson 4.8 §5). Read §3 on marks and substitutions.
    Cited in: 08-syntax-extension

  • [Ear70] Jay Earley. An efficient context-free parsing algorithm. Communications of the ACM 13(2), 94–102, 1970. doi:10.1145/362007.362035
    Why and when: Core reading. The origin of Earley parsing (Algorithm 4.3.3) and its \(O(n^3)\)/\(O(n^2)\)/linear bounds (Theorem 4.3.11). Read the algorithm section with Lesson 4.3 §2 open.
    Cited in: overview, 03-earley

  • [FH06] Richard A. Frost and Rahmatullah Hafiz. A new top-down parsing algorithm to accommodate ambiguity and left recursion in polynomial time. SIGPLAN Notices 41(5), 46–54, 2006. doi:10.1145/1149982.1149988
    Why and when: Curtailment of left-recursive calls by a depth bound, a combinator-friendly alternative to seed growing (Lessons 4.2 §6 and 4.5 §6).
    Cited in: 02-peg-and-packrat, 05-parser-combinators

  • [Fla16] Matthew Flatt. Binding as sets of scopes. POPL 2016, 705–717, 2016. doi:10.1145/2837614.2837620
    Why and when: Racket's reformulation of hygiene: identifiers carry sets of scopes, and resolution picks the binding whose set is the largest subset (Lesson 4.8 §4 and §6). Read §2–3.
    Cited in: 08-syntax-extension

  • [For02] Bryan Ford. Packrat parsing: simple, powerful, lazy, linear time. ICFP 2002, 36–47, 2002. doi:10.1145/581478.581483
    Why and when: Core reading. The origin of packrat memoization (Algorithm 4.2.7) and of furthest-failure error reporting (Lesson 4.5). Read §2–3 after Lesson 4.2 §2.
    Cited in: 02-peg-and-packrat, 05-parser-combinators

  • [For04] Bryan Ford. Parsing expression grammars: a recognition-based syntactic foundation. POPL 2004, 111–122, 2004. doi:10.1145/964001.964011
    Why and when: Core reading. The PEG formalism: the match semantics of Definition 4.2.2, well-formedness (Theorem 4.2.4) and the non-context-free language of Theorem 4.2.5. Read §3 with Lesson 4.2 §2 and §4.
    Cited in: overview, 02-peg-and-packrat

  • [Han90] David R. Hanson. Fast allocation and deallocation of memory based on object lifetimes. Software: Practice and Experience 20(1), 5–12, 1990. doi:10.1002/spe.4380200104
    Why and when: Arenas: allocate by bumping a pointer, free everything of one lifetime at once — the design of Algorithm 4.7.6 and of every compiler AST arena. Eight pages; read after Lesson 4.7 §2.
    Cited in: 07-syntax-tree-design

  • [HM98] Graham Hutton and Erik Meijer. Monadic parsing in Haskell. Journal of Functional Programming 8(4), 437–444, 1998. doi:10.1017/S0956796898003050
    Why and when: The eight-page version of [HM96]: a complete combinator library and an expression parser. Read it first if you only read one combinator paper.
    Cited in: 05-parser-combinators

  • [IAS16] Anastasia Izmaylova, Ali Afroozeh, and Tijs van der Storm. Practical, general parser combinators. PEPM 2016, 1–12, 2016. doi:10.1145/2847538.2847539
    Why and when: Combinators on top of GLL: all CFGs, left recursion and a parse forest in cubic worst case (Lesson 4.5 §6). Read after Lesson 4.4's GLL part.
    Cited in: 04-cyk-and-gll

  • [Ier09] Roberto Ierusalimschy. A text pattern-matching tool based on parsing expression grammars. Software: Practice and Experience 39(3), 221–258, 2009. doi:10.1002/spe.892
    Why and when: LPeg: PEGs compiled to a small parsing machine instead of memoized recursion (Lesson 4.2 §6). Read §4–5 for the machine.
    Cited in: 02-peg-and-packrat

  • [KFFD86] Eugene Kohlbecker, Daniel P. Friedman, Matthias Felleisen, and Bruce Duba. Hygienic macro expansion. LFP 1986, 151–161, 1986. doi:10.1145/319838.319859
    Why and when: Core reading. The origin of hygiene: the hygiene condition of Definition 4.8.5 and the time-stamping expansion algorithm behind Algorithm 4.8.6. Read after Lesson 4.8 §2.
    Cited in: overview, 08-syntax-extension

  • [Lee02] Lillian Lee. Fast context-free grammar parsing requires fast Boolean matrix multiplication. Journal of the ACM 49(1), 1–15, 2002. doi:10.1145/505241.505242
    Why and when: The converse of Valiant's result: faster CFG parsing would give faster matrix multiplication. Read the introduction after Theorem 4.4.10.
    Cited in: 04-cyk-and-gll

  • [Leo91] Joop M. I. M. Leo. A general context-free parsing algorithm running in linear time on every LR(k) grammar without using lookahead. Theoretical Computer Science 82(1), 165–176, 1991. doi:10.1016/0304-3975(91)90180-A
    Why and when: Core reading. Deterministic reduction paths and transitive items (Definition 4.3.5, Algorithm 4.3.6), with the linear-time proof for LR-regular grammars. Read after Lesson 4.3 §4.
    Cited in: 03-earley

  • [LL09] Martin Lange and Hans Leiß. To CNF or not to CNF? An efficient yet presentable version of the CYK algorithm. Informatica Didactica 8, 2009. link
    Why and when: CYK over a binary normal form with nullable and unit-closure precomputations, avoiding the grammar blow-up of full CNF (Lesson 4.4 §6). Read after Algorithm 4.4.2.
    Cited in: 04-cyk-and-gll

  • [MMI14] Sérgio Medeiros, Fabio Mascarenhas, and Roberto Ierusalimschy. Left recursion in parsing expression grammars. Science of Computer Programming 96(2), 177–190, 2014. doi:10.1016/j.scico.2014.01.013
    Why and when: Bounded left recursion: a formal semantics for left-recursive PEGs that agrees with seed growing on direct recursion. Read after Theorem 4.2.9 for the precise definition.
    Cited in: 02-peg-and-packrat

  • [MMY10] Kota Mizushima, Atusi Maeda, and Yoshinori Yamaguchi. Packrat parsers can handle practical grammars in mostly constant space. PASTE 2010, 29–36, 2010. doi:10.1145/1806672.1806679
    Why and when: Cut operators that let a packrat parser discard its memo table, answering the memory cost of Theorem 4.2.10. Read after Lesson 4.2 §5.
    Cited in: 02-peg-and-packrat, 05-parser-combinators

  • [Nau60] Peter Naur (ed.), John W. Backus, and et al.. Report on the algorithmic language ALGOL 60. Communications of the ACM 3(5), 299–314, 1960. doi:10.1145/367236.367262
    Why and when: §3.3.1 is the layered arithmetic-expression grammar (term, factor, primary) that Lesson 4.1 generalizes into the layered grammar \(G_T\) of Definition 4.1.2; skim it before §2 of Lesson 4.1.
    Cited in: 01-expression-parsing

  • [Pra73] Vaughan R. Pratt. Top down operator precedence. POPL 1973, 41–51, 1973. doi:10.1145/512927.512931
    Why and when: Core reading. The origin of Pratt parsing: nud/led handlers and binding powers per token. Read §1–3 after Lesson 4.1 §2 and compare Pratt's left/right powers with Definition 4.1.7.
    Cited in: overview, 01-expression-parsing

  • [Sco08] Elizabeth Scott. SPPF-style parsing from Earley recognisers. Electronic Notes in Theoretical Computer Science 203(2), 53–67, 2008. doi:10.1016/j.entcs.2008.03.044
    Why and when: Building a binarized shared packed parse forest during Earley recognition (Definition 4.3.7). Read the construction after Lesson 4.3 §2's SPPF part.
    Cited in: 03-earley

  • [SD96] S. Doaitse Swierstra and Luc Duponcheel. Deterministic, error-correcting combinator parsers. Advanced Functional Programming 1996, LNCS 1129, 184–207, 1996. doi:10.1007/3-540-61628-4_7
    Why and when: Applicative combinators that can be analyzed before running, with error correction (Lesson 4.5 §6). Read after Lesson 4.5 to see what giving up >>= buys.
    Cited in: 05-parser-combinators

  • [SJ10] Elizabeth Scott and Adrian Johnstone. GLL parsing. Electronic Notes in Theoretical Computer Science 253(7), 177–189, 2010. doi:10.1016/j.entcs.2010.08.041
    Why and when: Core reading. The origin of generalized LL parsing: descriptors, the GSS and the popped set of Definition 4.4.4 and Algorithm 4.4.5. Read §3–4 after Lesson 4.4 §2.
    Cited in: 04-cyk-and-gll

  • [SJ13] Elizabeth Scott and Adrian Johnstone. GLL parse-tree generation. Science of Computer Programming 78(10), 1828–1844, 2013. doi:10.1016/j.scico.2012.03.005
    Why and when: GLL with binarized SPPF construction and the cubic bound of Theorem 4.4.11. Read after the recognizer paper [SJ10].
    Cited in: 04-cyk-and-gll

  • [Val75] Leslie G. Valiant. General context-free recognition in less than cubic time. Journal of Computer and System Sciences 10(2), 308–315, 1975. doi:10.1016/S0022-0000(75)80046-8
    Why and when: CFL recognition in Boolean matrix multiplication time (Theorem 4.4.10). Read the idea after Lesson 4.4 §4; the construction is intricate and not needed for the exercises.
    Cited in: 04-cyk-and-gll

  • [Wad85] Philip Wadler. How to replace failure by a list of successes. FPCA 1985, LNCS 201, 113–128, 1985. doi:10.1007/3-540-15975-4_42
    Why and when: The list-of-successes formulation of Definition 4.5.1: a parser returns every way to parse a prefix. Read the parsing section after Lesson 4.5 §2.
    Cited in: 05-parser-combinators

  • [Wad98] Philip Wadler. The expression problem. Message to the java-genericity mailing list, 12 November 1998, 1998. link
    Why and when: The name and statement of the trade-off between sum types and class hierarchies (adding cases vs adding operations) discussed in Lesson 4.7 §1 and §6. One page.
    Cited in: 07-syntax-tree-design

  • [WDM08] Alessandro Warth, James R. Douglass, and Todd Millstein. Packrat parsers can support left recursion. PEPM 2008, 103–110, 2008. doi:10.1145/1328408.1328424
    Why and when: Core reading. Seed growing (Algorithm 4.2.8) and its extension to indirect left recursion with heads and involved sets. Read §3 after Lesson 4.2 §2; §4 is what pegen's leaders simplify.
    Cited in: 02-peg-and-packrat

  • [WG98] Tim A. Wagner and Susan L. Graham. Efficient and flexible incremental parsing. ACM Transactions on Programming Languages and Systems 20(5), 980–1013, 1998. doi:10.1145/293677.293678
    Why and when: Core reading. Incremental LR parsing with subtree reuse (Algorithm 4.6.6) and the exactness argument of Theorem 4.6.11. Read §3–5 after Lesson 4.6 §2.
    Cited in: overview, 06-resilient-and-incremental-parsing

  • [You67] Daniel H. Younger. Recognition and parsing of context-free languages in time \(n^3\). Information and Control 10(2), 189–208, 1967. doi:10.1016/S0019-9958(67)80007-X
    Why and when: The other origin of CYK, with the cubic bound of Proposition 4.4.9. Read §2 after Lesson 4.4 §2.
    Cited in: 04-cyk-and-gll

Textbooks and monographs

  • [ALSU07] Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools, 2nd ed.. Addison-Wesley, 2007. Read: §4.3 (writing a grammar: precedence by layering), §4.9.2 (precedence and associativity in Yacc), §5.3 (syntax trees).
    Why and when: The textbook view of layered expression grammars and syntax trees; read §4.3 before Lesson 4.1 if Chapter 2's layering needs a refresher.
    Cited in: 01-expression-parsing

  • [Cro07] Douglas Crockford. Top down operator precedence, in: Beautiful Code (A. Oram, G. Wilson, eds.). O'Reilly, 2007. Read: Ch. 9 (Top down operator precedence). link
    Why and when: The chapter that revived Pratt parsing by writing JSLint's JavaScript parser with it. Read it for the style of nud/led tables after Lesson 4.1's Algorithm 4.1.8.
    Cited in: 01-expression-parsing

  • [HMU07] John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation, 3rd ed.. Pearson / Addison-Wesley, 2007. Read: §7.1 (normal forms, §7.1.5 Chomsky normal form), §7.2 (pumping lemma for CFLs), §7.4.4 (the CYK algorithm).
    Why and when: Full proofs for CNF conversion (Theorem 4.4.6), the non-context-freeness of \(a^n b^n c^n\) (Theorem 4.2.5) and CYK (Theorem 4.4.7). Read §7.4.4 with Lesson 4.4 §3.
    Cited in: 02-peg-and-packrat, 04-cyk-and-gll

  • [ModernML] Andrew W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998. Read: Ch. 4 (abstract syntax: datatypes for syntax trees, positions).
    Why and when: Abstract syntax as ML datatypes, the sum-type design of Lesson 4.7; read Ch. 4 to see a whole compiler's AST written that way.
    Cited in: 07-syntax-tree-design

  • [Wir76] Niklaus Wirth. Algorithms + Data Structures = Programs. Prentice Hall, 1976. Read: §5.9 (syntax error recovery in a recursive-descent parser, with stop-symbol sets).
    Why and when: Stop-symbol sets passed down recursive descent: the ancestor of the recovery sets of Definition 4.6.2. Read after Lesson 4.6 §2.
    Cited in: 01-expression-parsing

Theses and technical reports

  • [Cla86] Keith Clarke. The top-down parsing of expressions. Queen Mary College, Department of Computer Science, Research Report 383, 1986. link
    Why and when: The report that describes precedence climbing (Algorithm 4.1.6) as an efficient replacement for one function per level. Short; read it after Lesson 4.1 §2.
    Cited in: 01-expression-parsing

  • [Dij61] Edsger W. Dijkstra. Algol 60 translation: an Algol 60 translator for the X1 and making a translator for Algol 60. Mathematisch Centrum, Amsterdam, Report MR 35/61, 1961.
    Why and when: Where the shunting-yard algorithm (Algorithm 4.1.9) first appears, as part of a complete ALGOL 60 translator. Of historical interest; read Lesson 4.1's trace first.
    Note: Scans circulate via the E. W. Dijkstra Archive and CWI's repository.
    Cited in: 01-expression-parsing

  • [HM96] Graham Hutton and Erik Meijer. Monadic parser combinators. University of Nottingham, Technical Report NOTTCS-TR-96-4, 1996. link
    Why and when: The long tutorial on monadic combinators: >>=, choice, many, and the space leaks of backtracking. Read §2–4 alongside Algorithm 4.5.3.
    Note: Also archived as Nottingham ePrints 237 (https://eprints.nottingham.ac.uk/237/).
    Cited in: 05-parser-combinators

  • [Joh75] Stephen C. Johnson. Yacc: Yet Another Compiler-Compiler. Bell Laboratories Computing Science Technical Report 32, 1975.
    Why and when: The error token and error productions (Definition 4.6.4). Read the section on error handling after Lesson 4.6 §2 and compare with error nodes.
    Note: Reprinted in the Unix Programmer's Manual (7th ed.), vol. 2B.
    Cited in: 06-resilient-and-incremental-parsing

  • [Kas65] Tadao Kasami. An efficient recognition and syntax-analysis algorithm for context-free languages. Air Force Cambridge Research Laboratory, Bedford MA, Scientific Report AFCRL-65-758, 1965. link
    Why and when: One of the two independent origins of CYK (Algorithm 4.4.3). Hard to obtain; the textbook treatment in [HMU07 §7.4] is the practical reading.
    Note: A DTIC-distributed technical report that few libraries hold (the URL is its catalog record); the textbook treatment in HMU07 §7.4.4 is the practical source.
    Cited in: 04-cyk-and-gll

  • [LM01] Daan Leijen and Erik Meijer. Parsec: direct style monadic parser combinators for the real world. Utrecht University, Technical Report UU-CS-2001-35, 2001. link
    Why and when: Committed choice with consumed/empty replies and try (Definition 4.5.4, Algorithm 4.5.5), and why it fixes the space leak and the error messages of backtracking. Read §3 and §5.1.
    Note: The Microsoft Research page carries the PDF of the Utrecht report.
    Cited in: 05-parser-combinators

Source code (pinned versions)

  • [CHUMSKY] chumsky's error-recovery strategies — src/recovery.rs in zesterer/chumsky at 0.10. Symbols: via_parser, skip_then_retry_until, nested_delimiters.
    Why and when: Recovery inside a combinator library (Algorithm 4.5.7). Read after Lesson 4.5 §2.
    Cited in: 05-parser-combinators

  • [CLANG-OpPrec] Clang's table of C/C++ binary-operator precedence levels — clang/include/clang/Basic/OperatorPrecedence.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: prec::Level, getBinOpPrecedence.
    Why and when: The operator table \(T\) of Definition 4.1.1 for C++, in twenty lines. Compare its levels with pebble-spec §4.2 after Lesson 4.1 §2.
    Cited in: 01-expression-parsing

  • [CLANG-ParseExpr] Clang's expression parser (precedence climbing) — clang/lib/Parse/ParseExpr.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: Parser::ParseRHSOfBinaryExpression, Parser::ParseAssignmentExpression.
    Why and when: ParseRHSOfBinaryExpression is Algorithm 4.1.6 with isRightAssoc for ?: and assignment. Read it after Lesson 4.1 §7; the quiz asks which operators are right-associative.
    Cited in: 01-expression-parsing

  • [CLANG-PPMacro] Clang's macro expansion (with TokenLexer.cpp and Preprocessor.cpp) — clang/lib/Lex/PPMacroExpansion.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: Preprocessor::HandleMacroExpandedIdentifier, Token::DisableExpand, TokenLexer::Init, Preprocessor::HandleIdentifier.
    Why and when: Algorithm 4.8.2 in production: disabled macros and painted-blue tokens. Read after Lesson 4.8 §2.
    Cited in: 08-syntax-extension

  • [CLANG-Stmt] Clang's statement/expression base classes (arena-only allocation, kind field) — clang/include/clang/AST/Stmt.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: Stmt::operator new, Stmt::getStmtClass, Expr::classof.
    Why and when: The protected plain operator new and the ASTContext& one; Expr::classof in Expr.h is the interval test of Theorem 4.7.11. Read after Lesson 4.7 §2.
    Cited in: 07-syntax-tree-design

  • [CLANG-StmtNodes] Clang's TableGen list of statement and expression classes — clang/include/clang/Basic/StmtNodes.td in llvm/llvm-project at llvmorg-23.1.2. Symbols: StmtNode, Expr, BinaryOperator.
    Why and when: The node list that generates the kind enum, the ranges and the visitors (Definition 4.7.1, Lesson 4.7 §6). Compare with Pebble's ASTNodes.def.
    Cited in: 07-syntax-tree-design

  • [CPY-Gram] CPython's PEG grammar — Grammar/python.gram in python/cpython at v3.11.15. Symbols: sum, term, factor, power.
    Why and when: A production PEG with left-recursive layered expression rules and (memo) markers (Lessons 4.1 and 4.2 §7). Read the expression section.
    Cited in: 01-expression-parsing, 02-peg-and-packrat

  • [CPY-pegen] CPython's PEG parser generator (pegen) — Tools/peg_generator/pegen/parser_generator.py in python/cpython at v3.13.0. Symbols: compute_left_recursives.
    Why and when: Finds the leaders of left-recursive cycles so that seed growing handles indirect left recursion (Lesson 4.2 §7).
    Cited in: 02-peg-and-packrat

  • [GCC-CParser] GCC's C parser (operator-precedence stack for binary expressions) — gcc/c/c-parser.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: c_parser_binary_expression.
    Why and when: c_parser_binary_expression keeps an explicit stack of operands and operators: shunting-yard inside a recursive-descent parser (Lesson 4.1 §7).
    Cited in: 01-expression-parsing

  • [GCC-CPP] The GNU C preprocessor manual (Texinfo source) — gcc/doc/cpp.texi in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: Macro Pitfalls, Operator Precedence Problems, Self-Referential Macros, Argument Prescan.
    Why and when: The catalogue of token-macro pitfalls that motivate Lesson 4.8: precedence, duplicated side effects, self-reference, prescan. Read the "Macro Pitfalls" node.
    Cited in: 08-syntax-extension

  • [GCC-CPParserBin] GCC's C++ parser, binary expressions — gcc/cp/parser.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: cp_parser_binary_expression.
    Why and when: The C++ front end's version of the same stack-based algorithm, with template-argument complications (> closing a template). Read after [GCC-CParser].
    Cited in: 01-expression-parsing

  • [GO-ParseBinary] Go's parser, binary expressions — src/go/parser/parser.go in golang/go at go1.24.7. Symbols: parser.parseBinaryExpr.
    Why and when: Precedence climbing in fifteen lines with Go's five binary levels; compare with Algorithm 4.1.6 after Lesson 4.1 §2.
    Cited in: 01-expression-parsing

  • [IDRIS2-Parser] Idris 2's parser-combinator core (a compiler parsed by combinators) — src/Libraries/Text/Parser/Core.idr in idris-lang/Idris2 at v0.7.0. Symbols: Grammar, commit.
    Why and when: A self-hosting compiler whose parser is a combinator library with explicit commit (Lesson 4.5 §7).
    Cited in: 05-parser-combinators

  • [LARK-CYK] Lark's CYK parser — lark/parsers/cyk.py in lark-parser/lark at 1.3.1. Symbols: to_cnf, revert_cnf, Parser._parse.
    Why and when: CNF conversion and back-conversion of trees around a textbook CYK loop (Lesson 4.4 §7).
    Cited in: 04-cyk-and-gll

  • [LARK-Earley] Lark's Earley parser — lark/parsers/earley.py in lark-parser/lark at 1.3.1. Symbols: Parser.predict_and_complete, Parser.parse.
    Why and when: A production Earley parser with SPPF output (Lesson 4.3 §7); note that Leo items were removed in this version, which the lesson measures.
    Cited in: 03-earley

  • [LLVM-Allocator] LLVM's bump-pointer allocator — llvm/include/llvm/Support/Allocator.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: BumpPtrAllocatorImpl, BumpPtrAllocatorImpl::Allocate.
    Why and when: Algorithm 4.7.6: 4096-byte slabs, doubling every 128 slabs, custom-sized slabs for large objects. Read Allocate after Lesson 4.7 §2.
    Cited in: 07-syntax-tree-design

  • [LLVM-Casting] LLVM-style RTTI templates — llvm/include/llvm/Support/Casting.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: isa, cast, dyn_cast, CastInfo.
    Why and when: isa, cast and dyn_cast over classof (Algorithm 4.7.2); Chapter 10 studies them in depth.
    Cited in: 07-syntax-tree-design

  • [LLVM-Kaleidoscope] The Kaleidoscope tutorial's expression parser — llvm/examples/Kaleidoscope/Chapter2/toy.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: ParseBinOpRHS, BinopPrecedence.
    Why and when: The smallest production-quality precedence climber: ParseBinOpRHS with a precedence map. Read it first among the sources of Lesson 4.1 §7.
    Cited in: 01-expression-parsing

  • [NOM] nom's ordered choice (alt; many0 is in src/multi/mod.rs) — src/branch/mod.rs in rust-bakery/nom at 8.0.0. Symbols: alt, many0.
    Why and when: Single-result backtracking combinators for Rust (Lesson 4.5 §2 and §7); alt is Algorithm 4.5.3's choice.
    Cited in: 05-parser-combinators

  • [PARSEC-Prim] Parsec's core (consumed/empty replies, try) — src/Text/Parsec/Prim.hs in haskell/parsec at v3.1.16.1. Symbols: ParsecT, try, parserPlus.
    Why and when: Definition 4.5.4 and Algorithm 4.5.5 in Haskell. Read parserPlus and try after Lesson 4.5 §2.
    Cited in: 05-parser-combinators

  • [PEGEN-Parser] pegen's runtime (memoization and left-recursion decorators) — src/pegen/parser.py in we-like-parsers/pegen at v0.3.0. Symbols: memoize, memoize_left_rec.
    Why and when: Algorithm 4.2.7 and Algorithm 4.2.8 as two Python decorators; the lesson's traces came from them. Read after Lesson 4.2 §3.
    Cited in: 02-peg-and-packrat

  • [RA-Expr] rust-analyzer's expression parser (Pratt with binding-power pairs) — src/tools/rust-analyzer/crates/parser/src/grammar/expressions.rs in rust-lang/rust at 1.94.1. Symbols: expr_bp, current_op.
    Why and when: expr_bp is Algorithm 4.1.8 almost line for line, in a resilient parser. Read after Lesson 4.1 §2, then again after Lesson 4.6 for its recovery.
    Cited in: 01-expression-parsing

  • [RA-ParserCore] rust-analyzer's parser core (recovery primitives) — src/tools/rust-analyzer/crates/parser/src/parser.rs in rust-lang/rust at 1.94.1. Symbols: Parser::err_recover, Parser::err_and_bump.
    Why and when: The two recovery primitives of Algorithm 4.6.3; the recovery sets live next to the grammar functions (ITEM_RECOVERY_SET). Read after Lesson 4.6 §2.
    Cited in: 06-resilient-and-incremental-parsing

  • [RA-Reparse] rust-analyzer's incremental reparsing — src/tools/rust-analyzer/crates/syntax/src/parsing/reparsing.rs in rust-lang/rust at 1.94.1. Symbols: incremental_reparse, reparse_token, reparse_block, is_balanced.
    Why and when: Algorithm 4.6.7 in 200 lines. Read it before the lab's ★ milestone L6.
    Cited in: 06-resilient-and-incremental-parsing

  • [ROSLYN-Green] Roslyn's green nodes (red nodes in SyntaxNode.cs) — src/Compilers/Core/Portable/Syntax/GreenNode.cs in dotnet/roslyn at Visual-Studio-2022-Version-17.14.34. Symbols: GreenNode, GreenNode.FullWidth, SyntaxNode.Position.
    Why and when: The origin of red–green trees: green nodes know only widths; SyntaxNode (red) adds position and parent (Definition 4.7.7). Read after Lesson 4.7 §2.
    Cited in: 07-syntax-tree-design

  • [ROWAN] rowan's green-node cache (hash-consing of small nodes); nodes in src/green/node.rs, red cursors in src/cursor.rs — src/green/node_cache.rs in rust-analyzer/rowan at v0.15.18. Symbols: NodeCache::node, NodeCache::token.
    Why and when: Where the "at most three children" rule of Algorithm 4.7.8 lives, observed in Lesson 4.7's rowan box. Read with src/green/node.rs after Lesson 4.7 §2.
    Cited in: 07-syntax-tree-design

  • [RUSTC-AST] rustc's AST (struct plus kind enum) — compiler/rustc_ast/src/ast.rs in rust-lang/rust at 1.94.1. Symbols: Expr, ExprKind, BinOpKind.
    Why and when: A sum-type AST at production scale (Lesson 4.7 §2): compare ExprKind with Clang's StmtNodes.td.
    Cited in: 07-syntax-tree-design

  • [RUSTC-HirId] rustc's HIR node ids (owner + local index) — compiler/rustc_hir_id/src/lib.rs in rust-lang/rust at 1.94.1. Symbols: HirId, OwnerId, ItemLocalId.
    Why and when: The doc comment on HirId explains why ids are two-level: stability under edits for incremental compilation (Lesson 4.7's arena box).
    Cited in: 07-syntax-tree-design

  • [RUSTC-Hygiene] rustc's hygiene (syntax contexts and expansion marks) — compiler/rustc_span/src/hygiene.rs in rust-lang/rust at 1.94.1. Symbols: SyntaxContext, ExpnData, Transparency.
    Why and when: Marks and contexts of Definition 4.8.5, with the three transparencies. Read after the rustc hygiene box of Lesson 4.8.
    Cited in: 08-syntax-extension

  • [RUSTC-Lower] rustc's AST → HIR lowering of expressions — compiler/rustc_ast_lowering/src/expr.rs in rust-lang/rust at 1.94.1. Symbols: LoweringContext::lower_expr_for.
    Why and when: lower_expr_for is Algorithm 4.7.10's Rust template, documented in its comment. Read after Lesson 4.7's HIR box.
    Cited in: 07-syntax-tree-design

  • [RUSTC-MBE] rustc's macros by example (matching in macro_parser.rs/macro_rules.rs, transcription here) — compiler/rustc_expand/src/mbe/transcribe.rs in rust-lang/rust at 1.94.1. Symbols: transcribe_pnr, macro_rules.rs expand_macro, macro_rules.rs try_match_macro, macro_parser.rs.
    Why and when: Algorithm 4.8.4 in production: the NFA matcher and the invisible-delimiter transcription of Theorem 4.8.9. Read after Lesson 4.8 §2.
    Cited in: 08-syntax-extension

  • [RUSTC-ParseExpr] rustc's expression parser — compiler/rustc_parse/src/parser/expr.rs in rust-lang/rust at 1.94.1. Symbols: Parser::parse_expr_assoc_with.
    Why and when: Precedence climbing with AssocOp fixity, non-associative comparisons (the error Pebble's E0206 mirrors) and ranges. Read after Lesson 4.1 §7.
    Cited in: 01-expression-parsing

  • [SWIFT-Fold] Swift's operator folding after parsing — lib/Sema/TypeCheckExpr.cpp in swiftlang/swift at swift-6.1-RELEASE. Symbols: foldSequence.
    Why and when: Swift parses a flat sequence of operands and operators and folds it by declared precedence groups later, because operators are user-defined (Lesson 4.1 §6).
    Cited in: 01-expression-parsing

  • [SWIFTSYNTAX-Arena] SwiftSyntax's arena for raw (green) nodes — Sources/SwiftSyntax/SyntaxArena.swift in swiftlang/swift-syntax at 601.0.1. Symbols: SyntaxArena, RawSyntax.
    Why and when: Green nodes allocated in an arena instead of reference-counted (Lesson 4.7 §6); RawSyntax.swift holds the layout.
    Cited in: 07-syntax-tree-design

  • [SWIFTSYNTAX-Recovery] swift-syntax's precedence-based recovery for a lossless CST — Sources/SwiftParser/Recovery.swift in swiftlang/swift-syntax at 601.0.1. Symbols: canRecoverTo, RecoveryConsumptionHandle.
    Why and when: Recovery that skips tokens only when they bind more loosely than the construct being parsed (Lesson 4.6 §6).
    Cited in: 06-resilient-and-incremental-parsing

  • [TS-Reuse] tree-sitter's incremental GLR parser (subtree reuse and recovery) — lib/src/parser.c in tree-sitter/tree-sitter at v0.25.10. Symbols: ts_parser__reuse_node, ts_parser__breakdown_top_of_stack, ts_parser__can_reuse_first_leaf, ts_parser__recover.
    Why and when: Algorithm 4.6.6 in production, including the reuse checks and error recovery; ts_subtree_edit is in lib/src/subtree.c. Read after Lesson 4.6 §2.
    Cited in: 06-resilient-and-incremental-parsing

  • [V8-ParserBase] V8's JavaScript parser (recursive descent, templated over the full and pre-parser) — src/parsing/parser-base.h in v8/v8 at 12.9.1. Symbols: ParserBase<Impl>::ParseBinaryExpression, ParserBase<Impl>::ParseBinaryContinuation.
    Why and when: ParseBinaryContinuation climbs precedence levels for JavaScript's binary operators (Lesson 4.1 §7).
    Cited in: 01-expression-parsing

Official documentation and specifications

  • [BISON-Manual] GNU Bison manual: error recovery, the error token, yyerrok. Bison 3.8.2. link
    Why and when: Error productions in practice: the section "Error Recovery" is Definition 4.6.4 with the details (three tokens to resynchronize, yyerrok). Read after the Bison box of Lesson 4.6.
    Cited in: 06-resilient-and-incremental-parsing

  • [LARK-Docs] Lark documentation: parsers (Earley, LALR(1), CYK). Lark 1.3.1. link
    Why and when: Lark's own comparison of its three parsers, quoted in Lessons 4.3 and 4.4.
    Cited in: 03-earley, 04-cyk-and-gll

  • [LLVM-RTTI] How to set up LLVM-style RTTI for your class hierarchy. LLVM 23.1.2. link
    Why and when: The recipe for a kind enum plus classof, including deeper hierarchies with first/last ranges (Theorem 4.7.11). Read with Lesson 4.7 §2.
    Cited in: 07-syntax-tree-design

  • [PEP617] PEP 617: New PEG parser for CPython. Python 3.9. link
    Why and when: Why CPython moved to a PEG and how it uses memoization selectively (Lesson 4.2 §5 and §7).
    Cited in: 02-peg-and-packrat

  • [RA-SyntaxDoc] rust-analyzer: syntax trees (green nodes, red nodes, trivia, interning). rust-analyzer 2026-09-21. link
    Why and when: The design notes of rust-analyzer's red–green trees, with the alternatives (trivia on tokens, Roslyn, Swift). Read after Lesson 4.7 §2; the lesson checks one of its claims.
    Cited in: 07-syntax-tree-design

  • [RUST-RefMBE] The Rust Reference: macros by example (fragment specifiers, forwarding, hygiene). reference@52ffdc0 (September 2026). link
    Why and when: The specification of fragment specifiers, opaque forwarding and mixed-site hygiene used in Lesson 4.8. Read "Hygiene" and "Follow-set ambiguity restrictions".
    Cited in: 08-syntax-extension

  • [SE0382] Swift Evolution SE-0382: Expression macros. swift-evolution@cf74276. link
    Why and when: Swift's macros: syntax-tree in, syntax-tree out, type-checked arguments, and the explicit statement that they are not hygienic (makeUniqueName instead). Read after Lesson 4.8 §6.
    Cited in: 08-syntax-extension

Talks and videos

  • [Bru18] Max Brunsfeld. Tree-sitter: a new parsing system for programming tools. Strange Loop 2018, 2018. link
    Why and when: tree-sitter's author on incremental GLR parsing, error recovery and its use in editors (Lesson 4.6 §1). Watch after Lesson 4.6.
    Cited in: 06-resilient-and-incremental-parsing

Blog posts and articles

  • [Kla20] Aleksey Kladov. Simple but powerful Pratt parsing. 2020. link
    Why and when: Pratt parsing with pairs of binding powers, the convention of Definition 4.1.7 and of rust-analyzer's expr_bp. Read after Lesson 4.1 §2; the code is 100 lines of Rust.
    Cited in: 01-expression-parsing

  • [Kla23] Aleksey Kladov. Resilient LL parsing tutorial. 2023. link
    Why and when: Core reading. The design of rust-analyzer's resilient parser explained from scratch, with runnable code: the source of Algorithm 4.6.3. Read it after Lesson 4.6 §2, before exercise E6.
    Cited in: overview, 06-resilient-and-incremental-parsing

  • [Nor99] Theodore S. Norvell. Parsing expressions by recursive descent. 1999. link
    Why and when: The survey that named "precedence climbing" and compares it with the classic and shunting-yard solutions; a good second explanation after Lesson 4.1 §1.
    Cited in: 01-expression-parsing