Skip to content

References — Chapter 3 · Bottom-Up Parsing

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

  • [AEH73] T. Anderson, J. Eve, and J. J. Horning. Efficient LR(1) parsers. Acta Informatica 2(1), 12–39, 1973. doi:10.1007/BF00571461
    Why and when: How to make LR(1) parsers practical: compact encodings of the tables and space optimizations such as default reductions (Lessons 3.1 §6, 3.3 §1). Read it for the engineering side of table construction; optional.
    Cited in: 03-lalr

  • [AJU75] Alfred V. Aho, Stephen C. Johnson, and Jeffrey D. Ullman. Deterministic parsing of ambiguous grammars. Communications of the ACM 18(8), 441–452, 1975. doi:10.1145/360933.360969
    Why and when: Core reading. Precedence and associativity rules as a way to parse ambiguous expression grammars deterministically, with smaller and faster parsers than layered grammars (Theorem 3.5.10, Proposition 3.5.12). Read after Lesson 3.5.
    Cited in: 05-conflicts-and-precedence

  • [Bea82] John C. Beatty. On the relationship between the LL(1) and LR(1) grammars. Journal of the ACM 29(4), 1007–1022, 1982. doi:10.1145/322344.322350
    Why and when: Every p-reduced LL(1) grammar is LALR(1), and every ε-free LL(1) grammar is SLR(1): the precise boundary behind Proposition 3.3.14's counterexample (which is not p-reduced).
    Cited in: 02-slr-and-canonical-lr1, 03-lalr

  • [BF87] Michael G. Burke and Gerald A. Fisher. A practical method for LR and LL syntactic error diagnosis and recovery. ACM TOPLAS 9(2), 164–197, 1987. doi:10.1145/22719.22720
    Why and when: Core reading. Deferred-window repair by single-token edits plus scope recovery (Lesson 3.7), implemented by ML-Yacc. Read the description of simple repair and the deferral mechanism.
    Cited in: 07-lr-error-recovery

  • [BL89] Manuel E. Bermudez and George Logothetis. Simple computation of LALR(1) lookahead sets. Information Processing Letters 31(5), 233–238, 1989. doi:10.1016/0020-0190(89)90079-3
    Why and when: LALR(1) lookaheads as ordinary FOLLOW sets of a transformed grammar: a variant of DeRemer–Pennello (Lesson 3.3 §6) that reuses your Chapter 2 FOLLOW code.
    Cited in: 03-lalr

  • [DDH84] Peter Dencker, Karl Dürre, and Johannes Heuft. Optimization of parser tables for portable compilers. ACM TOPLAS 6(4), 546–572, 1984. doi:10.1145/1780.1802
    Why and when: Measured comparison of LR table compression schemes (Lesson 3.1 §6). Skim the results tables.
    Cited in: 01-shift-reduce-and-lr0

  • [DeR71] Frank DeRemer. Simple LR(k) grammars. Communications of the ACM 14(7), 453–460, 1971. doi:10.1145/362619.362625
    Why and when: Core reading. The origin of SLR(k): the LR(0) automaton plus FOLLOW sets. Short and readable; read it with Lesson 3.2 and compare its examples with the running example's SLR conflict.
    Cited in: 01-shift-reduce-and-lr0, 02-slr-and-canonical-lr1

  • [DM10] Joel E. Denny and Brian A. Malloy. The IELR(1) algorithm for generating minimal LR(1) parser tables for non-LR(1) grammars with conflict resolution. Science of Computer Programming 75(11), 943–979, 2010. doi:10.1016/j.scico.2009.08.001
    Why and when: Core reading. IELR(1) as implemented in Bison: annotations, compatibility, state splitting, and why LALR and Pager differ from canonical LR(1) in the presence of precedence declarations. Read §1–3 after Lesson 3.4; §4 has the proofs behind Theorem 3.4.10.
    Cited in: overview, 04-minimal-lr1

  • [DP82] Frank DeRemer and Thomas Pennello. Efficient computation of LALR(1) look-ahead sets. ACM TOPLAS 4(4), 615–649, 1982. doi:10.1145/69622.357187
    Why and when: Core reading. The reads/includes/lookback relations and the Digraph algorithm of Lesson 3.3, with the proofs of Lemma 3.3.11 and Theorem 3.3.12. Read §3–4 after the worked example; Bison's lalr.c follows it closely.
    Cited in: overview, 03-lalr

  • [DT20] Lukas Diekmann and Laurence Tratt. Don't Panic! Better, Fewer, Syntax Errors for LR Parsers. ECOOP 2020, LIPIcs 166, 6:1–6:32, 2020. doi:10.4230/LIPIcs.ECOOP.2020.6
    Why and when: CPCT+: all minimum-cost repair sequences within a time budget, in the grmtools Rust LR library — the modern successor of Burke–Fisher (Lesson 3.7 §6).
    Cited in: 07-lr-error-recovery

  • [Flo63] Robert W. Floyd. Syntactic analysis and operator precedence. Journal of the ACM 10(3), 316–333, 1963. doi:10.1145/321172.321179
    Why and when: Core reading. The origin of operator-precedence relations and parsing (Lesson 3.5) and a precursor of bounded-context and LR methods. Read the definitions of the three relations and the parsing algorithm.
    Cited in: 01-shift-reduce-and-lr0, 05-conflicts-and-precedence

  • [IM15] Chinawat Isradisaikul and Andrew C. Myers. Finding counterexamples from parsing conflicts. PLDI 2015, 555–564, 2015. doi:10.1145/2737924.2737961
    Why and when: Unifying and nonunifying counterexamples for LR conflicts, the algorithm behind Bison's -Wcounterexamples (Lesson 3.5). Read §2–3 for the definitions and the search.
    Cited in: 05-conflicts-and-precedence

  • [Jef03] Clinton L. Jeffery. Generating LR syntax error messages from examples. ACM TOPLAS 25(5), 631–640, 2003. doi:10.1145/937563.937566
    Why and when: merr: per-state error messages derived from example erroneous inputs, the idea Menhir's .messages files systematize (Lesson 3.7).
    Cited in: 07-lr-error-recovery

  • [JPL12] Jacques-Henri Jourdan, François Pottier, and Xavier Leroy. Validating LR(1) parsers. European Symposium on Programming (ESOP 2012), LNCS 7211, 397–416, 2012. doi:10.1007/978-3-642-28869-2_20
    Why and when: A Coq validator certifies that a Menhir-generated LR(1) automaton is correct for its grammar; used for CompCert's C parser (Lessons 3.7–3.8).
    Cited in: 07-lr-error-recovery, 08-lr-in-practice

  • [Knu65] Donald E. Knuth. On the translation of languages from left to right. Information and Control 8(6), 607–639, 1965. doi:10.1016/S0019-9958(65)90426-2
    Why and when: Core reading. The origin of LR(k): handles, viable prefixes, the item construction, and the theorems that LR(k) grammars are unambiguous and characterized by a conflict-free table. Read it after Lessons 3.1–3.2; the definitions of §II are the ones Definitions 3.1.2 and 3.2.5 follow.
    Cited in: overview, 01-shift-reduce-and-lr0, 02-slr-and-canonical-lr1

  • [Knu71] Donald E. Knuth. Top-down syntax analysis. Acta Informatica 1(2), 79–110, 1971. doi:10.1007/BF00289517
    Why and when: Knuth's study of top-down (LL(k)) analysis, the historical background of the relation between LL and LR grammars in Theorem 3.2.14. The LL half of the chapter is Ch 2.
    Cited in: 02-slr-and-canonical-lr1

  • [Lan74] Bernard Lang. Deterministic techniques for efficient non-deterministic parsers. ICALP 1974, LNCS 14, 255–269, 1974. doi:10.1007/978-3-662-21545-6_18
    Why and when: The first shared-stack simulation of a nondeterministic LR parser, the idea Tomita made practical (Lesson 3.6 §1). For historical depth.
    Cited in: 06-glr

  • [LLH71] Wilf R. LaLonde, E. S. Lee, and James J. Horning. An LALR(k) parser generator. Proceedings of IFIP Congress 71, 513–518, North-Holland, 1971.
    Why and when: One of the first practical LALR generators, computing lookaheads on the LR(0) automaton without building LR(1) (Lesson 3.3 §1). Of historical interest.
    Note: IFIP Congress proceedings (North-Holland, 1972); no DOI; available in university libraries.
    Cited in: 03-lalr

  • [MN04] Scott McPeak and George C. Necula. Elkhound: A fast, practical GLR parser generator. Compiler Construction (CC 2004), LNCS 2985, 73–88, 2004. doi:10.1007/978-3-540-24723-4_6
    Why and when: A deterministic LR core that switches to GLR only at conflicts, and a C++ front end built on it: the engineering answer to "GLR is slow" (Lesson 3.6 §6–7).
    Cited in: 06-glr

  • [NF91] Rahman Nozohoor-Farshi. GLR parsing for ε-grammars. In M. Tomita (ed.), Generalized LR Parsing, Kluwer, 61–75, 1991.
    Why and when: The fix for Tomita's algorithm on grammars with ε-rules and hidden left recursion (Lesson 3.6 §1 and §6).
    Note: Chapter of the edited volume [Tom91]; no DOI.
    Cited in: 06-glr

  • [Nij82] Anton Nijholt. On the relationship between the LL(k) and LR(k) grammars. Information Processing Letters 15(3), 97–101, 1982. doi:10.1016/0020-0190(82)90038-2
    Why and when: A short proof that every LL(k) grammar is LR(k), via Beatty's left-part theorem: the full proof of Theorem 3.2.14.
    Cited in: 02-slr-and-canonical-lr1

  • [Pag77] David Pager. A practical general method for constructing LR(k) parsers. Acta Informatica 7(3), 249–268, 1977. doi:10.1007/BF00290336
    Why and when: Core reading. Weak compatibility and the PGM construction of Lesson 3.4, with the proof that merging weakly compatible states preserves LR(1)-ness (Theorem 3.4.8). Read the definitions and the main theorem.
    Cited in: 04-minimal-lr1

  • [PCC85] Joseph C. H. Park, K. M. Choe, and C. H. Chang. A new analysis of LALR formalisms. ACM TOPLAS 7(1), 159–175, 1985.
    Why and when: An alternative relational formulation of LALR lookaheads, compared in Lesson 3.3 §6. Optional.
    Note: ACM TOPLAS 7(1), 1985; available from the ACM Digital Library.
    Cited in: 03-lalr

  • [Pen86] Thomas J. Pennello. Very fast LR parsing. SIGPLAN '86 Symposium on Compiler Construction, SIGPLAN Notices 21(7), 145–151, 1986. doi:10.1145/12276.13326
    Why and when: Compiling LR tables into machine code (recursive ascent style), the speed argument of Lesson 3.1 §6. Optional.
    Cited in: 01-shift-reduce-and-lr0

  • [Pot16] François Pottier. Reachability and error diagnosis in LR(1) parsers. Compiler Construction (CC 2016), 88–98, 2016. doi:10.1145/2892208.2892224
    Why and when: Core reading. The algorithm behind menhir --list-errors: which error states are reachable and by which shortest inputs (Theorem 3.7.11). Read §1–3; the ✗ rows of Lesson 3.7 §3 are its motivating problem.
    Cited in: 07-lr-error-recovery

  • [SJ06] Elizabeth Scott and Adrian Johnstone. Right nulled GLR parsers. ACM TOPLAS 28(4), 577–618, 2006. doi:10.1145/1146809.1146810
    Why and when: Core reading. RNGLR: right-nullable reductions make Tomita's algorithm correct for all context-free grammars (Theorem 3.6.9). Read §2–4.
    Cited in: overview, 06-glr

  • [SJE07] Elizabeth Scott, Adrian Johnstone, and Rob Economopoulos. BRNGLR: a cubic Tomita-style GLR parsing algorithm. Acta Informatica 44(6), 427–461, 2007. doi:10.1007/s00236-007-0054-z
    Why and when: Binarized reductions bring GLR's worst case to O(n^3) (Theorem 3.6.9, Lesson 3.6 §5). Read the introduction and the complexity section.
    Cited in: 06-glr

  • [Spe88] David Spector. Efficient full LR(1) parser generation. ACM SIGPLAN Notices 23(12), 143–150, 1988.
    Why and when: Splitting LALR states on demand where conflicts appear — a simpler predecessor of IELR (Lesson 3.4 §6). Optional.
    Note: SIGPLAN Notices 23(12), 1988; ACM Digital Library.
    Cited in: 04-minimal-lr1

  • [Tar72] Robert E. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing 1(2), 146–160, 1972. doi:10.1137/0201010
    Why and when: The strongly connected components algorithm inside Digraph (Theorem 3.3.10). Read the SCC section; LLVM's scc_iterator is the same algorithm.
    Cited in: 03-lalr

  • [TY79] Robert Endre Tarjan and Andrew Chi-Chih Yao. Storing a sparse table. Communications of the ACM 22(11), 606–611, 1979. doi:10.1145/359168.359175
    Why and when: Row displacement for LR tables (Lesson 3.1 §6). Read the row-displacement scheme.
    Cited in: 01-shift-reduce-and-lr0

  • [Ukk83] Esko Ukkonen. Lower bounds on the size of deterministic parsers. Journal of Computer and System Sciences 26(2), 153–170, 1983. doi:10.1016/0022-0000(83)90010-7
    Why and when: Families of LR(0) and LL(2) grammars whose deterministic parsers must be exponentially larger than the grammar; the theory behind Proposition 3.1.21's blow-up. Skim the statements of the main theorems.
    Cited in: 01-shift-reduce-and-lr0

  • [WW66] Niklaus Wirth and Helmut Weber. EULER: a generalization of ALGOL, and its formal definition: Part I. Communications of the ACM 9(1), 13–25, 1966. doi:10.1145/365153.365162
    Why and when: Simple precedence parsing (relations between all grammar symbols), the variant of Floyd's method in Lessons 3.1 §6 and 3.5 §6. Read the parsing section.
    Cited in: 01-shift-reduce-and-lr0, 05-conflicts-and-precedence

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.5 (bottom-up parsing, handles, shift-reduce), §4.6 (LR(0) items, SLR), §4.7 (canonical LR(1), LALR, §4.7.5 lookahead propagation), §4.8 (ambiguous grammars, precedence, LR error recovery); Examples 4.48, 4.54, 4.58.
    Why and when: Core reading. The classical presentation Lessons 3.1–3.3 and 3.5 follow; the running example (Ex. 4.48) and the non-LALR grammar (Ex. 4.58) come from it. Work its exercises after each lesson.
    Cited in: overview, 02-slr-and-canonical-lr1, 03-lalr

  • [ASU86] Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools, 1st ed.. Addison-Wesley, 1986. Read: §4.6 (operator-precedence parsing), §4.7 (LR parsers), §4.8 (using ambiguous grammars).
    Why and when: The first edition keeps operator-precedence parsing (dropped in the 2nd edition): the textbook proof behind Theorem 3.5.11 and the precedence-function variant.
    Cited in: 05-conflicts-and-precedence

  • [AU72] Alfred V. Aho and Jeffrey D. Ullman. The Theory of Parsing, Translation, and Compiling, Vol. 1: Parsing. Prentice Hall, 1972. Read: §5.2 (deterministic bottom-up parsing: LR(k) grammars and parsers), §5.3 (precedence grammars), §5.4 (other classes of shift-reduce parsable grammars).
    Why and when: The rigorous textbook theory of LR(k), precedence and bounded-context parsing; consult §5.2 when a proof of Lessons 3.1–3.2 feels compressed.
    Cited in: 01-shift-reduce-and-lr0

  • [EaC3] Keith D. Cooper and Linda Torczon. Engineering a Compiler, 3rd ed.. Morgan Kaufmann, 2022. Read: ch. 3 (Parsers): §3.4 (bottom-up parsing: LR(1) items, the canonical collection, table construction, conflicts), §3.5 (practical issues: error recovery, unary operators).
    Why and when: An engineering-first treatment built directly on canonical LR(1) sets; read §3.4 as an alternative to Lessons 3.1–3.2.
    Cited in: overview

  • [GJ08] Dick Grune and Ceriel J. H. Jacobs. Parsing Techniques: A Practical Guide, 2nd ed.. Springer, 2008. Read: ch. 9 (deterministic bottom-up parsing: precedence, LR(0), SLR, LR(1), LALR, conflict resolution), ch. 11 (generalized deterministic parsers: GLR), ch. 16 (error handling).
    Why and when: Core reading. The most complete survey: every LR variant of this chapter and many more, with an enormous annotated bibliography. Use ch. 9 for Lessons 3.1–3.5, ch. 11 for Lesson 3.6.
    Cited in: overview

  • [Tom85] Masaru Tomita. Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems. Kluwer Academic Publishers, 1985. Read: the chapters presenting the algorithm, the graph-structured stack and the shared packed forest (the first half of the book).
    Why and when: The origin of GLR with a graph-structured stack and packed forests (Lesson 3.6). Read the algorithm description with the worked example of Lesson 3.6 §3 at hand.
    Cited in: 06-glr

  • [Tom91] Masaru Tomita. Generalized LR Parsing. Kluwer Academic Publishers (edited volume), 1991. Read: ch. 1 (Tomita and Ng, the GLR algorithm), the chapter by Nozohoor-Farshi on ε-grammars.
    Why and when: The standard reference collection on GLR; its first chapter restates the algorithm used in Theorem 3.6.7, and Nozohoor-Farshi's chapter [NF91] treats ε-rules.
    Cited in: 06-glr

Surveys and tutorials

  • [AJ74] Alfred V. Aho and Stephen C. Johnson. LR parsing. ACM Computing Surveys 6(2), 99–124, 1974. doi:10.1145/356628.356629
    Why and when: Core reading. The tutorial that taught a generation LR(0) items, SLR and LALR, conflict resolution and table compression, written by yacc's author. Read it as a second explanation of Lessons 3.1–3.3 and 3.5.
    Cited in: overview, 01-shift-reduce-and-lr0

Theses and technical reports

  • [Che09] Xin Chen. Measuring and extending LR(1) parser generation. PhD thesis, University of Hawaii, 2009.
    Why and when: Implements and measures Pager's PGM and lane-tracing (Hyacc); useful state-count data for Lesson 3.4's comparison. Skim the experimental chapter.
    Note: University of Hawaii at Manoa, 2009; the Hyacc parser generator implements its algorithms.
    Cited in: 04-minimal-lr1

  • [DeR69] Franklin L. DeRemer. Practical translators for LR(k) languages. PhD thesis, MIT (Project MAC TR-65), 1969.
    Why and when: Separates the LR(0) automaton (the characteristic finite-state machine) from the lookahead computation and defines LALR(k) as merged LR(k) states — the origin of Lessons 3.1 and 3.3.
    Note: MIT Project MAC Technical Report MAC-TR-65; scanned copies are in MIT's DSpace.
    Cited in: 01-shift-reduce-and-lr0, 02-slr-and-canonical-lr1, 03-lalr

  • [Joh75] Stephen C. Johnson. Yacc: Yet Another Compiler-Compiler. Bell Laboratories Computing Science Technical Report 32, 1975.
    Why and when: yacc: LALR(1) tables, default conflict resolution, %left/%right/%nonassoc, and the error token (Lessons 3.3, 3.5, 3.7). Read the sections on ambiguity, precedence and error handling.
    Note: Bell Labs CSTR 32; reprinted in the Unix Programmer's Manual (7th ed.), vol. 2B.
    Cited in: 03-lalr, 05-conflicts-and-precedence, 07-lr-error-recovery

  • [Rek92] Jan Rekers. Parser Generation for Interactive Environments. PhD thesis, University of Amsterdam, 1992.
    Why and when: A careful GLR with shared packed parse forests and ε-handling, and a proof of correctness (Theorem 3.6.7). Read ch. 1 after Lesson 3.6.
    Note: University of Amsterdam, 1992; the basis of the SGLR parser of ASF+SDF and Spoofax.
    Cited in: 06-glr

Source code (pinned versions)

  • [BISON-src] Bison's LALR(1) lookaheads (DeRemer–Pennello); see also src/lr0.c, src/relation.c, src/ielr.c, src/conflicts.c, data/skeletons/yacc.c and glr.c — src/lalr.c in akimd/bison at v3.8.2. Symbols: initialize_goto_follows, build_relations, add_lookback_edge, compute_follows, compute_lookaheads.
    Why and when: The production implementation of Lessons 3.1–3.7: lr0.c (generate_states, new_itemsets), relation.c (relation_digraph), ielr.c (the IELR phases), conflicts.c (resolve_sr_conflict), yacc.c (the driver and yyerrlab), glr.c (yyglrReduce, yysplitStack). Start with lalr.c.
    Cited in: 01-shift-reduce-and-lr0, 02-slr-and-canonical-lr1, 03-lalr, 04-minimal-lr1, 05-conflicts-and-precedence, 06-glr, 07-lr-error-recovery

  • [CLANG-Parser] Clang's parser core, including SkipUntil (panic-mode recovery) — clang/lib/Parse/Parser.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: Parser::SkipUntil.
    Why and when: The recursive-descent counterpart of yacc's error recovery (Lesson 3.7's find-it task).
    Cited in: 07-lr-error-recovery

  • [CLANG-ParseTentative] Clang's tentative parsing for C++ declarations vs expressions — clang/lib/Parse/ParseTentative.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: Parser::isCXXDeclarationStatement, Parser::isCXXSimpleDeclaration.
    Why and when: How a recursive-descent parser handles the ambiguity that defeats LR(k) (Lesson 3.8); compare with GLR (Lesson 3.6).
    Cited in: 08-lr-in-practice

  • [COMPCERT-msgs] CompCert's hand-written syntax error messages for its Menhir C parser — cparser/handcrafted.messages in AbsInt/CompCert at v3.15. Symbols: error sentences and messages.
    Why and when: A real .messages file (Lesson 3.7): sentences from --list-errors with a hand-written message each.
    Cited in: 07-lr-error-recovery

  • [GCC-CParser] GCC's hand-written 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: The comment quoted in Lesson 3.5 describes Floyd-style operator-precedence parsing inside recursive descent. Read c_parser_binary_expression.
    Cited in: 05-conflicts-and-precedence, 08-lr-in-practice

  • [GCC-CPChangeLog] The GCC C++ ChangeLog entry removing the yacc grammar — gcc/cp/ChangeLog.3 in gcc-mirror/gcc at releases/gcc-3.4.0. Symbols: 2002-12-30 parse.y: Remove..
    Why and when: Primary evidence for the switch from a yacc-generated to a hand-written C++ parser (Lesson 3.8).
    Cited in: 08-lr-in-practice

  • [GCC-CPParser] GCC's hand-written recursive-descent C++ parser — gcc/cp/parser.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: cp_parser_binary_expression, cp_parser_parse_tentatively.
    Why and when: The "Methodology" comment quoted in Lesson 3.8 and the tentative-parsing functions; the parser that replaced the yacc grammar.
    Cited in: 05-conflicts-and-precedence, 08-lr-in-practice

  • [LLVM-AsmParser] LLVM's assembler expression parser (precedence climbing with two tables) — llvm/lib/MC/MCParser/AsmParser.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: AsmParser::parseBinOpRHS, getGNUBinOpPrecedence, getDarwinBinOpPrecedence.
    Why and when: Two precedence tables for one parser (Lesson 3.5's box and find-it task).
    Cited in: 05-conflicts-and-precedence

  • [LLVM-LLParser] LLVM's textual IR parser (hand-written recursive descent) — llvm/lib/AsmParser/LLParser.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: LLParser::parseTopLevelEntities.
    Why and when: A switch on the token kind per construct: the technique LLVM uses instead of a generated LR parser (Lesson 3.1's find-it task).
    Cited in: 01-shift-reduce-and-lr0

  • [LLVM-SCCIterator] LLVM's Tarjan SCC iterator — llvm/include/llvm/ADT/SCCIterator.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: scc_iterator::DFSVisitChildren, StackElement::MinVisited.
    Why and when: The same SCC bookkeeping as Digraph (Theorem 3.3.10): MinVisited plays the role of N[x] (Lesson 3.3's find-it task).
    Cited in: 03-lalr

  • [MENHIR-src] Menhir's Pager construction (GitHub mirror of the Inria repository); see also src/lr0.ml, src/LALR.ml, src/LR1Canonical.ml, src/LRijkstra.ml — src/LR1Pager.ml in LexiFi/menhir at 20231231. Symbols: Run.
    Why and when: Menhir's LR constructions and error-site search, each with an explanatory header comment (Lessons 3.1, 3.3, 3.4, 3.7). Read the header of LR1Pager.ml and of LRijkstra.ml.
    Cited in: 01-shift-reduce-and-lr0, 02-slr-and-canonical-lr1, 03-lalr, 04-minimal-lr1, 07-lr-error-recovery

  • [MLYACC-parser] ML-Yacc's parser driver with Burke–Fisher error correction — ml-yacc/lib/parser2.sml in smlnj/legacy at v110.99.9. Symbols: CHANGE, parse.
    Why and when: The implementation behind Lesson 3.7's ML-Yacc box; the header describes the partial, deferred method of [BF87].
    Cited in: 07-lr-error-recovery

  • [OCAML-parser] OCaml's grammar for Menhir — parsing/parser.mly in ocaml/ocaml at 5.2.0. Symbols: implementation, expr.
    Why and when: A production compiler whose parser is generated by Menhir (Lesson 3.8).
    Cited in: 08-lr-in-practice

  • [PG-gram] PostgreSQL's SQL grammar for Bison — src/backend/parser/gram.y in postgres/postgres at REL_17_0. Symbols: %expect 0, precedence declarations.
    Why and when: A 19 513-line conflict-free LALR grammar with 23 precedence lines (Lessons 3.5 and 3.8's boxes). Read the precedence block and its comments.
    Cited in: 01-shift-reduce-and-lr0, 05-conflicts-and-precedence, 07-lr-error-recovery, 08-lr-in-practice

  • [PHP-parser] PHP's language grammar for Bison — Zend/zend_language_parser.y in php/php-src at php-8.3.0. Symbols: %expect 0, %define api.pure full.
    Why and when: A general-purpose language parsed by a Bison LALR parser (Lesson 3.8). Look at the precedence declarations at the top.
    Cited in: 08-lr-in-practice

  • [RUBY-news33] Ruby 3.3 release notes (Bison replaced by Lrama) — NEWS.md in ruby/ruby at v3_3_0. Symbols: Replace Bison with Lrama LALR parser generator.
    Why and when: Why a language project wrote its own LALR generator (Lesson 3.8 §6).
    Cited in: 08-lr-in-practice

  • [RUBY-news34] Ruby 3.4 release notes (Prism becomes the default parser) — NEWS.md in ruby/ruby at v3_4_0. Symbols: The default parser is now Prism.
    Why and when: A language moving from a generated LALR parser to a hand-written one in 2024 (Lesson 3.8); prism/prism.c is the parser.
    Cited in: 08-lr-in-practice

  • [SQLITE-parse] SQLite's grammar for the Lemon LALR(1) generator (tool/lemon.c) — src/parse.y in sqlite/sqlite at version-3.46.0. Symbols: cmd, expr.
    Why and when: An LR grammar in a very widely deployed system, with Lemon's own syntax for precedence and destructors (Lesson 3.8).
    Cited in: 08-lr-in-practice

  • [TS-build] tree-sitter's parse-table construction (item sets with lookaheads, conflict reports) — crates/generate/src/build_tables/build_parse_table.rs in tree-sitter/tree-sitter at v0.27.0. Symbols: ParseTableBuilder::add_parse_state, ParseTableBuilder::add_actions, ParseTableBuilder::handle_conflict.
    Why and when: How tree-sitter builds LR(1)-style item sets, reports conflicts with interpretations and suggested resolutions (Lesson 3.6's box), and merges states afterwards (minimize_parse_table.rs).
    Cited in: 01-shift-reduce-and-lr0, 03-lalr, 04-minimal-lr1

  • [TS-parser] tree-sitter's runtime GLR-style parser and error recovery — lib/src/parser.c in tree-sitter/tree-sitter at v0.27.0. Symbols: ts_parser__advance, ts_parser__condense_stack, ts_parser__select_tree, ts_parser__recover.
    Why and when: Stack versions, merging and tree selection by dynamic precedence and error cost (Lesson 3.6 §7); stack.c holds the graph-structured stack.
    Cited in: 06-glr

Official documentation and specifications

  • [BISON-Manual] GNU Bison manual: LR table construction (lr.type), conflicts, counterexamples, precedence, error recovery, GLR. Bison 3.8.2. link
    Why and when: Core reading. The reference for every Bison box of this chapter: "Mysterious Conflicts", "LR Table Construction" (lalr, ielr, canonical-lr), "Counterexamples", "Precedence", "Error Recovery" and "GLR Parsers". Read the sections as the lessons point to them.
    Cited in: 01-shift-reduce-and-lr0, 02-slr-and-canonical-lr1, 03-lalr, 04-minimal-lr1, 05-conflicts-and-precedence, 06-glr, 07-lr-error-recovery, 08-lr-in-practice

  • [GCC34] GCC 3.4 Release Series, Changes, New Features, and Fixes (C++ section). GCC 3.4. link
    Why and when: Records that a hand-written recursive-descent C++ parser replaced the yacc-derived one (Lesson 3.8).
    Cited in: 08-lr-in-practice

  • [GCC41] GCC 4.1 Release Series, Changes, New Features, and Fixes (C family). GCC 4.1. link
    Why and when: Records that the Bison-based C and Objective-C parser was replaced by a hand-written recursive-descent parser (Lesson 3.8).
    Cited in: 08-lr-in-practice

  • [MENHIR-Manual] Menhir reference manual. Menhir 20231231. link
    Why and when: Construction modes (--lalr, default Pager, --canonical), conflict explanations, and the .messages workflow (--list-errors, --compile-errors, --compare-errors) of Lesson 3.7.
    Cited in: 01-shift-reduce-and-lr0, 02-slr-and-canonical-lr1, 04-minimal-lr1, 05-conflicts-and-precedence, 07-lr-error-recovery

  • [TS-docs] tree-sitter documentation: creating parsers (precedence, conflicts, dynamic precedence). tree-sitter 0.27. link
    Why and when: The grammar DSL used in Lesson 3.6's box: prec.left/right, prec.dynamic and the conflicts field that turns on GLR forking.
    Cited in: 05-conflicts-and-precedence, 06-glr, 08-lr-in-practice