Skip to content

References — Chapter 2 · Grammars & Top-Down 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

  • [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: Precedence and associativity declarations instead of layered grammars: the idea behind yacc's and Bison's %left/%right, shown as a variant in Lesson 2.1 §6 and developed in Ch 3.
    Cited in: 01-grammars-and-ambiguity

  • [AP72] Alfred V. Aho and Thomas G. Peterson. A minimum distance error-correcting parser for context-free languages. SIAM Journal on Computing 1(4), 305–312, 1972. doi:10.1137/0201022
    Why and when: Core reading. Global minimum-distance repair in O(n³) for every CFG: the dynamic program behind Algorithm 2.7.6 and Theorem 2.7.11. Read the construction of the covering grammar and the parser.
    Cited in: overview, 07-error-recovery

  • [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: Bounded-window repair that tries edits near the error and keeps the one that parses furthest: the practical compromise between local and global repair (Lesson 2.7 §5–6).
    Cited in: overview, 07-error-recovery

  • [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 model of backtracking parsers with ordered choice and the tabular (memoized) linear-time algorithm that packrat parsing revived (Lesson 2.5 §1).
    Cited in: overview, 05-recursive-descent

  • [Can62] David G. Cantor. On the ambiguity problem of Backus systems. Journal of the ACM 9(4), 477–479, 1962. doi:10.1145/321138.321145
    Why and when: One of the three independent 1962 proofs that ambiguity of context-free grammars is undecidable. Three pages; read it after Theorem 2.1.12 to see the original reduction.
    Cited in: overview, 01-grammars-and-ambiguity

  • [Cho56] Noam Chomsky. Three models for the description of language. IRE Transactions on Information Theory 2(3), 113–124, 1956. doi:10.1109/TIT.1956.1056813
    Why and when: Where phrase-structure (context-free) grammars enter the literature, as the middle of three models of language. Read the section on phrase-structure grammar after Lesson 2.1 §1 for the historical framing; the linguistics can be skimmed.
    Cited in: overview, 01-grammars-and-ambiguity

  • [Cho59] Noam Chomsky. On certain formal properties of grammars. Information and Control 2(2), 137–167, 1959. doi:10.1016/S0019-9958(59)90362-6
    Why and when: The hierarchy of grammar types 0–3 by production shape (Definition 2.1.4) and the proofs that the inclusions are strict. Read the definitions of the four types; the rest is background for the Chomsky-hierarchy quiz question.
    Cited in: overview, 01-grammars-and-ambiguity

  • [Con63] Melvin E. Conway. Design of a separable transition-diagram compiler. Communications of the ACM 6(7), 396–408, 1963. doi:10.1145/366663.366704
    Why and when: Transition diagrams as coroutines for a COBOL compiler: the other early source of recursive descent. Read the design of the syntax analyzer; the coroutine idea is famous in its own right.
    Cited in: overview, 05-recursive-descent

  • [CS63] Noam Chomsky and Marcel-Paul Schützenberger. The algebraic theory of context-free languages. In P. Braffort and D. Hirschberg (eds.), Computer Programming and Formal Systems, North-Holland, 118–161, 1963.
    Why and when: Context-free languages as solutions of algebraic (power-series) equations, the viewpoint behind "L(G) is the least solution of its equations" in Lesson 2.4 (Theorem 2.4.7). Also contains an undecidability proof for ambiguity. For the mathematically curious.
    Note: Book chapter; available in university libraries (Studies in Logic and the Foundations of Mathematics series).
    Cited in: overview, 01-grammars-and-ambiguity

  • [DG84] William F. Dowling and Jean H. Gallier. Linear-time algorithms for testing the satisfiability of propositional Horn formulae. Journal of Logic Programming 1(3), 267–284, 1984. doi:10.1016/0743-1066(84)90014-1
    Why and when: The counter-per-clause algorithm that Bison's nullable computation instantiates (Algorithm 2.2.8): nullable is Horn-clause satisfiability. Read the linear-time algorithm with one counter per clause.
    Cited in: overview, 02-first-follow-fixed-points

  • [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 Digraph algorithm for "set = direct ∪ union over a relation" equations (Algorithm 2.2.9 and Theorem 2.2.14). Read the description of Digraph now and the LALR part in Ch 3.
    Cited in: overview, 02-first-follow-fixed-points

  • [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: The depth bound |N|·(n+1) that makes a backtracking parser detect left recursion (Lemma 2.5.12) and curtailment for left-recursive memoized parsing (Lesson 2.5 §6).
    Cited in: overview, 04-grammar-transformations, 05-recursive-descent

  • [Flo62] Robert W. Floyd. On ambiguity in phrase structure languages. Communications of the ACM 5(10), 526 and 534, 1962. doi:10.1145/368959.368993
    Why and when: Floyd's short note proving the same undecidability result; historically interesting because it was written for programming-language designers. Optional after Theorem 2.1.12.
    Cited in: overview, 01-grammars-and-ambiguity

  • [FMQ80] Charles N. Fischer, Donn R. Milton, and Sam B. Quiring. Efficient LL(1) error correction and recovery using only insertions. Acta Informatica 13(2), 141–154, 1980.
    Why and when: Insert-only LL(1) repair with precomputed cheapest insertion strings (Lesson 2.7 §6). Read the definition of insert-correctable grammars.
    Note: Springer, Acta Informatica 13(2); available through university libraries.
    Cited in: overview, 07-error-recovery

  • [For02] Bryan Ford. Packrat parsing: simple, powerful, lazy, linear time. ICFP 2002, 36–47, 2002. doi:10.1145/581478.581483
    Why and when: Memoizing (rule, position) to make backtracking linear, the idea of Algorithm 2.5.7. Read the introduction and the packrat construction now, the rest with Ch 4.
    Cited in: overview, 05-recursive-descent

  • [For04] Bryan Ford. Parsing expression grammars: a recognition-based syntactic foundation. POPL 2004, 111–122, 2004. doi:10.1145/964001.964011
    Why and when: Ordered choice as a grammar formalism; explains why PEG is not "backtracking CFG parsing" (the S → a | a b pitfall in Lesson 2.5 §4). Read the definition of PEGs; Ch 4 covers PEG in depth.
    Cited in: 05-recursive-descent

  • [GR75] Susan L. Graham and Steven P. Rhodes. Practical syntactic error recovery. Communications of the ACM 18(11), 639–650, 1975.
    Why and when: Phrase-level recovery made systematic: local corrections chosen by context (Lesson 2.7 §1). Read the description of the two recovery phases.
    Note: CACM 18(11); in the ACM Digital Library.
    Cited in: overview, 07-error-recovery

  • [Gre65] Sheila A. Greibach. A new normal-form theorem for context-free phrase structure grammars. Journal of the ACM 12(1), 42–52, 1965. doi:10.1145/321250.321254
    Why and when: Greibach normal form, whose construction contains direct and indirect left-recursion removal (Lesson 2.4). Read the construction's lemmas; the normal form itself is optional.
    Cited in: overview, 04-grammar-transformations

  • [Iro63] Edgar T. Irons. An error-correcting parse algorithm. Communications of the ACM 6(11), 669–673, 1963.
    Why and when: The first error-correcting parser: repair the input and continue. Historical origin of Lesson 2.7's third family.
    Note: CACM 6(11); in the ACM Digital Library.
    Cited in: overview, 07-error-recovery

  • [Kil73] Gary A. Kildall. A unified approach to global program optimization. POPL 1973, 194–206, 1973. doi:10.1145/512927.512945
    Why and when: Iterating monotone equations from the bottom of a finite lattice until nothing changes: the same argument as Lesson 2.2's round-robin proof, in its dataflow setting. Read after Lesson 2.2 §4 to see why Ch 14 will feel familiar.

  • [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: LR(k) parsing; cited here because an LR(k) grammar is unambiguous, one of the sufficient conditions for unambiguity in Lesson 2.1 (Corollary 2.1.13). The full treatment is Ch 3.
    Cited in: 01-grammars-and-ambiguity

  • [Knu71] Donald E. Knuth. Top-down syntax analysis. Acta Informatica 1(2), 79–110, 1971. doi:10.1007/BF00289517
    Why and when: Core reading. Knuth's survey-with-proofs of top-down parsing: LL(1) characterized by FIRST and FOLLOW, the parsing-machine view of recursive descent, and left-recursion elimination. The best single companion to Lessons 2.2–2.5; read the parts on LL(1) and on recursive descent.
    Cited in: overview, 01-grammars-and-ambiguity, 02-first-follow-fixed-points, 03-ll1-tables-and-conflicts, 05-recursive-descent

  • [Kur69] Reino Kurki-Suonio. Notes on top-down languages. BIT Numerical Mathematics 9(3), 225–238, 1969.
    Why and when: The strict hierarchy LL(k) ⊊ LL(k+1) of languages, quoted in Lesson 2.6 §4. Read the statement and the witness family; the proof is optional.
    Note: Springer, BIT 9(3); available through university libraries.
    Cited in: 06-llk-and-all-star

  • [LS68] Philip M. Lewis II and Richard E. Stearns. Syntax-directed transduction. Journal of the ACM 15(3), 465–488, 1968. doi:10.1145/321466.321477
    Why and when: Core reading. The origin of LL(k) grammars and of the top-down (predictive) translation that Lessons 2.3, 2.5 and 2.6 study. Read the definitions of LL(k) and of the top-down translator; the transduction results are optional.
    Cited in: overview, 02-first-follow-fixed-points, 03-ll1-tables-and-conflicts, 05-recursive-descent, 06-llk-and-all-star

  • [Luc61] Peter Lucas. Die Strukturanalyse von Formelübersetzern. Elektronische Rechenanlagen 3(4), 159–167, 1961.
    Why and when: One of the first descriptions of recursive descent: one recursive procedure per syntactic category. Historical; cited in Lesson 2.5 §1 for the origin.
    Note: In German; Oldenbourg journal, available through university libraries.
    Cited in: overview, 05-recursive-descent

  • [Moo00] Robert C. Moore. Removing left recursion from context-free grammars. NAACL 2000, 249–255, 2000. link
    Why and when: Names Paull's algorithm, measures how the variants blow up grammars, and gives a left-corner-based improvement (Lesson 2.4 §5–6). Read it after Lesson 2.4; the measurements are the point.
    Cited in: overview, 04-grammar-transformations

  • [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: Core reading. BNF's debut and the first language defined by a context-free grammar. §3.3.1 is the layered arithmetic-expression grammar (term, factor) that Lesson 2.1 generalizes into Algorithm 2.1.9; §4.5 shows how ALGOL avoided the dangling else by syntax (Lesson 2.3).
    Cited in: overview, 01-grammars-and-ambiguity, 03-ll1-tables-and-conflicts

  • [PF11] Terence Parr and Kathleen Fisher. LL(): the foundation of the ANTLR parser generator.* PLDI 2011, 425–436, 2011. doi:10.1145/1993498.1993548
    Why and when: Core reading. Lookahead DFAs built by subset construction over the grammar's ATN (Algorithm 2.6.8) and the fallback to backtracking. Read the LL() analysis sections after Lesson 2.6 §2.
    Cited in:* overview, 06-llk-and-all-star

  • [PHF14] Terence Parr, Sam Harwell, and Kathleen Fisher. Adaptive LL() parsing: the power of dynamic analysis.* OOPSLA 2014, 579–598, 2014. doi:10.1145/2660193.2660202
    Why and when: Core reading. The ALL() algorithm of ANTLR 4: SLL simulation, full-LL fallback, DFA caching, the O(n⁴) bound and the linear-in-practice measurements quoted in Lesson 2.6 §5. Readable and precise; read all of it after Lesson 2.6, then open [ANTLR4-PATN].
    Cited in:* overview, 03-ll1-tables-and-conflicts, 06-llk-and-all-star

  • [Pos46] Emil L. Post. A variant of a recursively unsolvable problem. Bulletin of the American Mathematical Society 52(4), 264–268, 1946. doi:10.1090/S0002-9904-1946-08555-9
    Why and when: Post's correspondence problem, the undecidable problem that Theorem 2.1.12 reduces to grammar ambiguity. Read the problem statement only; the proof of its undecidability is covered more accessibly in [Sip12, §5.2].
    Cited in: 01-grammars-and-ambiguity

  • [PQ95] Terence J. Parr and Russell W. Quong. ANTLR: A predicated-LL(k) parser generator. Software: Practice and Experience 25(7), 789–810, 1995. doi:10.1002/spe.4380250705
    Why and when: Syntactic and semantic predicates as a way out of LL(k) conflicts (Lesson 2.3 §6, Lesson 2.6 §6). Read the sections on predicates to see how they change what "the grammar" means.
    Cited in: 03-ll1-tables-and-conflicts, 06-llk-and-all-star

  • [Pra73] Vaughan R. Pratt. Top down operator precedence. POPL 1973, 41–51, 1973. doi:10.1145/512927.512931
    Why and when: Binding powers instead of one nonterminal per precedence level: the hand-written alternative to layering (Lesson 2.1 §6, Lesson 2.5 §6), taught in full in Ch 4.
    Cited in: 01-grammars-and-ambiguity, 05-recursive-descent

  • [RL70] Daniel J. Rosenkrantz and Philip M. Lewis II. Deterministic left corner parsing. IEEE Conference Record of the 11th Annual Symposium on Switching and Automata Theory, 139–152, 1970.
    Why and when: The left-corner transform, the polynomial-size alternative to Paull's algorithm mentioned in Lesson 2.4 §6. Background reading.
    Note: IEEE SWAT 1970 proceedings; available in IEEE Xplore.
    Cited in: 04-grammar-transformations

  • [RS70] Daniel J. Rosenkrantz and Richard E. Stearns. Properties of deterministic top-down grammars. Information and Control 17(3), 226–256, 1970. doi:10.1016/S0019-9958(70)90446-8
    Why and when: Core reading. The standard reference for LL(k) theory: strong LL(k) versus LL(k) (Theorem 2.6.12), the local-follow-set tables of full LL(k) (Algorithm 2.6.6), and the equivalence of LL(1) with conflict-free tables (Theorem 2.3.8). Read it after Lesson 2.6, starting with the definitions and the strong-vs-full example.
    Cited in: overview, 03-ll1-tables-and-conflicts, 06-llk-and-all-star

  • [Sch07] Sylvain Schmitz. Conservative ambiguity detection in context-free grammars. ICALP 2007, LNCS 4596, 692–703, 2007. doi:10.1007/978-3-540-73420-8_60
    Why and when: The approximation approach to ambiguity detection (always terminates, may report false positives), the variant contrasted with bounded search in Lesson 2.1 §6. Read the introduction and the definition of the approximation.
    Cited in: 01-grammars-and-ambiguity

  • [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: Shared packed parse forests: one polynomial-size structure for all parse trees of an ambiguous sentence (Lesson 2.1 §6). Read the SPPF definition; the Earley part belongs to Ch 4.
    Cited in: 01-grammars-and-ambiguity

  • [Tar55] Alfred Tarski. A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics 5(2), 285–309, 1955. doi:10.2140/pjm.1955.5.285
    Why and when: The Knaster–Tarski theorem: a monotone function on a complete lattice has a least fixed point. Lesson 2.2 uses it (Theorem 2.2.4) to say that nullable, FIRST and FOLLOW are well defined. Read the statement of Theorem 1; Ch 14 uses it again.
    Cited in: 02-first-follow-fixed-points

  • [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: Strongly connected components in one depth-first search, the engine of the digraph algorithm (Algorithm 2.2.9). Read the SCC section; Ch 15 reuses the paper for dominators.
    Cited in: overview, 02-first-follow-fixed-points

  • [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 sparse tables with O(1) lookup: how generated LL (and LR) tables are compressed (Lesson 2.3 §5–6). Read the row-displacement scheme.
    Cited in: 03-ll1-tables-and-conflicts, 05-recursive-descent

  • [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: Returning every successful end position instead of committing: the formulation of full backtracking in Algorithm 2.5.6 and lab exercise L3.
    Cited in: overview, 05-recursive-descent

  • [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: Seed growing for left recursion in packrat parsers, the technique CPython's pegen uses (memoize_left_rec); a variant in Lesson 2.4 §6 and Lesson 2.5 §6.
    Cited in: 04-grammar-transformations, 05-recursive-descent

  • [Wir77] Niklaus Wirth. What can we do about the unnecessary diversity of notation for syntactic definitions?. Communications of the ACM 20(11), 822–823, 1977. doi:10.1145/359863.359883
    Why and when: The one-page proposal of EBNF ({ } for repetition), the notation behind loop-shaped recursive descent (Lesson 2.4 §6, Lesson 2.5 exercise L2).
    Cited in: 04-grammar-transformations, 05-recursive-descent

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.1.3–4.1.4 (error-recovery strategies), §4.2 (context-free grammars), §4.3 (writing a grammar: ambiguity, dangling else, left recursion, Algorithm 4.19, left factoring), §4.4 (top-down parsing: FIRST/FOLLOW, LL(1), predictive parsing, §4.4.5 error recovery).
    Why and when: Core reading. The classical presentation this chapter follows for FIRST/FOLLOW, the LL(1) table and panic mode. Read §4.2–4.4 alongside Lessons 2.1–2.5; its exercises are good extra drill.
    Cited in: overview, 02-first-follow-fixed-points, 03-ll1-tables-and-conflicts, 04-grammar-transformations, 07-error-recovery

  • [AU72] Alfred V. Aho and Jeffrey D. Ullman. The Theory of Parsing, Translation, and Compiling, Vol. 1: Parsing. Prentice Hall, 1972. Read: §2.4 (context-free grammars), §5.1 (LL(k) grammars, strong LL(k), LL(k) parsing tables).
    Why and when: The rigorous textbook treatment behind Lesson 2.6's definitions and proofs (FIRST_k, ⊕_k, local follow sets, table construction). Use §5.1 when a proof in Lesson 2.6 is only sketched.
    Cited in: 05-recursive-descent, 06-llk-and-all-star

  • [EaC3] Keith D. Cooper and Linda Torczon. Engineering a Compiler, 3rd ed.. Morgan Kaufmann, 2022. Read: ch. 3 (Parsers): §3.2 (expressing syntax), §3.3 (top-down parsing: left recursion, backtrack-free grammars, recursive descent, table-driven LL(1)), §3.5 (practical issues: error recovery).
    Why and when: An engineering-first alternative to the Dragon book's chapter, with good advice on hand-written parsers and error recovery. Read §3.3 if Lessons 2.3–2.5 feel too formal.
    Cited in: overview

  • [GJ08] Dick Grune and Ceriel J. H. Jacobs. Parsing Techniques: A Practical Guide, 2nd ed.. Springer, 2008. Read: ch. 3 (introduction to parsing, ambiguity), ch. 6 (general directional top-down parsing, backtracking), ch. 8 (deterministic top-down parsing: LL(1), LL(k), strong LL(k)), ch. 16 (error handling).
    Why and when: Core reading. The most complete survey of parsing there is, with an enormous annotated bibliography. Use ch. 8 for every LL variant this chapter mentions and ch. 16 for error handling; dip into it whenever you want a second explanation.
    Cited in: overview

  • [HU79] John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979. Read: §4.6 (Greibach normal form: Lemmas 4.3–4.4, substitution and left-recursion elimination), Ch. 8 (Post's correspondence problem and the undecidable questions about CFGs, including ambiguity).
    Why and when: The textbook proofs behind Lesson 2.4 (the substitution lemma and direct removal preserve the language) and behind Theorem 2.1.12 (ambiguity is undecidable). Open it when a proof in those lessons is only sketched.
    Cited in: overview, 01-grammars-and-ambiguity, 04-grammar-transformations

  • [Sip12] Michael Sipser. Introduction to the Theory of Computation, 3rd ed.. Cengage Learning, 2012. Read: §2.1 (context-free grammars, ambiguity), §5.2 (Post's correspondence problem), Problem 5.21 (ambiguity is undecidable).
    Why and when: The gentlest complete proof path for Theorem 2.1.12: PCP's undecidability in §5.2, and the reduction to ambiguity as a guided problem. Read after Lesson 2.1 §4.

  • [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: Panic mode in recursive descent by passing "stop symbol" sets down the calls, the origin of FOLLOW-based synchronization (Lesson 2.7 §1). Short and concrete; read after Algorithm 2.7.3.
    Cited in: overview, 07-error-recovery

Theses and technical reports

  • [Joh75] Stephen C. Johnson. Yacc: Yet Another Compiler-Compiler. Bell Laboratories Computing Science Technical Report 32, 1975.
    Why and when: The origin of %left/%right precedence declarations and of "shift beats reduce" for the dangling else (Lesson 2.3 §1 and the Bison real-world boxes). Read the sections on ambiguity and conflicts and on precedence.
    Note: Bell Labs CSTR 32; reprinted in the Unix Programmer's Manual (7th ed.), vol. 2B.
    Cited in: overview, 01-grammars-and-ambiguity, 03-ll1-tables-and-conflicts

  • [Par93] Terence J. Parr. Obtaining practical variants of LL(k) and LR(k) for k > 1 by splitting the atomic k-tuple. PhD thesis, Purdue University, 1993.
    Why and when: Linear-approximate lookahead (k sets of tokens instead of sets of k-strings), the ANTLR 2 variant of strong LL(k) in Lesson 2.6 §6. Read the chapter on linear approximate lookahead for the idea and the cost argument.
    Note: Purdue University thesis; available from the author's publication list and ProQuest.
    Cited in: 06-llk-and-all-star

Source code (pinned versions)

  • [ANTLR3-NFAToDFA] ANTLR 3's LL() lookahead-DFA construction — tool/src/main/java/org/antlr/analysis/NFAToDFAConverter.java in antlr/antlr3 at 3.5.2. Symbols: NFAToDFAConverter.convert, reach.
    Why and when:* The static subset construction of Algorithm 2.6.8 with recursion limits and the fallback to predicates (Lesson 2.6 §7).
    Cited in: 06-llk-and-all-star

  • [ANTLR4-ErrorStrategy] ANTLR 4's default error strategy — runtime/Java/src/org/antlr/v4/runtime/DefaultErrorStrategy.java in antlr/antlr4 at 4.13.2. Symbols: recoverInline, singleTokenDeletion, singleTokenInsertion, recover, sync, getErrorRecoverySet.
    Why and when: Single-token deletion and insertion with a panic-mode fallback: Algorithm 2.7.5 in production. Read it after Lesson 2.7 §2 and compare with the real-world box there.
    Cited in: 07-error-recovery

  • [ANTLR4-Interp] ANTLR 4's grammar interpreter (parsing without generated code) — runtime/Java/src/org/antlr/v4/runtime/ParserInterpreter.java in antlr/antlr4 at 4.13.2. Symbols: ParserInterpreter.parse, visitState.
    Why and when: Walks the grammar's ATN with an explicit stack of rule invocations: the data-driven counterpart of Algorithm 2.5.4 that org.antlr.v4.gui.Interpreter runs in Lesson 2.5's real-world box. Read parse and visitState.
    Cited in: 05-recursive-descent

  • [ANTLR4-LeftRec] ANTLR 4's rewriting of directly left-recursive rules — tool/src/org/antlr/v4/analysis/LeftRecursiveRuleTransformer.java in antlr/antlr4 at 4.13.2. Symbols: translateLeftRecursiveRules.
    Why and when: How a tool removes direct left recursion for you by turning the rule into a precedence loop (Lesson 2.4 §7); indirect left recursion is error 119 in tool/src/org/antlr/v4/tool/ErrorType.java.
    Cited in: 04-grammar-transformations

  • [ANTLR4-LL1Analyzer] ANTLR 4's LL(1) lookahead-set computation on the ATN — runtime/Java/src/org/antlr/v4/runtime/atn/LL1Analyzer.java in antlr/antlr4 at 4.13.2. Symbols: getDecisionLookahead, LOOK.
    Why and when: FIRST/FOLLOW-style sets computed by a depth-first walk of the grammar's ATN (Lessons 2.2 and 2.3, §7).
    Cited in: 02-first-follow-fixed-points, 03-ll1-tables-and-conflicts

  • [ANTLR4-PATN] ANTLR 4's ALL() prediction engine — runtime/Java/src/org/antlr/v4/runtime/atn/ParserATNSimulator.java in antlr/antlr4 at 4.13.2. Symbols: adaptivePredict, execATN, execATNWithFullContext, computeReachSet, closure, reportAttemptingFullContext, reportAmbiguity.
    Why and when:* The production implementation of Algorithm 2.6.9: SLL simulation with a DFA cache and the full-context fallback. Read the long class comment first; then follow adaptivePredict.
    Cited in: 01-grammars-and-ambiguity, 06-llk-and-all-star

  • [ANTLR4-PredictionMode] ANTLR 4's prediction modes and conflict tests — runtime/Java/src/org/antlr/v4/runtime/atn/PredictionMode.java in antlr/antlr4 at 4.13.2. Symbols: SLL, LL, LL_EXACT_AMBIG_DETECTION, hasSLLConflictTerminatingPrediction, resolvesToJustOneViableAlt.
    Why and when: The SLL/LL distinction (Definition 2.6.7) and "the minimum alternative wins" (Lesson 2.3 §7). The comments are an excellent explanation of SLL conflicts.
    Cited in: 03-ll1-tables-and-conflicts, 06-llk-and-all-star

  • [BISON-src] Bison's counting nullable computation (with relation.c and closure.c) — src/nullable.c in akimd/bison at v3.8.2. Symbols: nullable_compute.
    Why and when: Algorithm 2.2.8 in C (rcount, squeue); src/relation.c — relation_digraph is DeRemer–Pennello's Digraph (Algorithm 2.2.9); src/closure.c — set_firsts is FIRST by reflexive–transitive closure.
    Cited in: 02-first-follow-fixed-points

  • [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 layered grammar of the C standard turned back into a table (Lesson 2.1 §7). Twenty lines; the quiz asks about it.
    Cited in: 01-grammars-and-ambiguity

  • [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.
    Why and when: Left-recursion removal written as a loop that builds left-nested ASTs, with isRightAssoc for ?: and assignment (Lessons 2.1, 2.4). Compare with lab exercise L2.
    Cited in: 01-grammars-and-ambiguity, 04-grammar-transformations

  • [CLANG-Parser] Clang's parser core (error recovery, token annotation) — clang/lib/Parse/Parser.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: Parser::SkipUntil, Parser::ExpectAndConsume, Parser::ExpectAndConsumeSemi, Parser::TryAnnotateTypeOrScopeToken.
    Why and when: Panic mode (SkipUntil with the flags declared in clang/include/clang/Parse/Parser.h), phrase-level insertion with fix-its (ExpectAndConsume), and annotation tokens that make re-parsing cheap. Read with Lesson 2.7 §7.
    Cited in: 02-first-follow-fixed-points, 05-recursive-descent, 06-llk-and-all-star, 07-error-recovery

  • [CLANG-ParseStmt] Clang's statement parser (predictive recursive descent) — clang/lib/Parse/ParseStmt.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: Parser::ParseStatementOrDeclarationAfterAttributes, Parser::ParseIfStatement.
    Why and when: A switch on the current token that is one row of an LL(1) table; ParseIfStatement is the left-factored if/else with the dangling-else warning. Read after Lesson 2.5 §7.
    Cited in: 01-grammars-and-ambiguity, 03-ll1-tables-and-conflicts, 04-grammar-transformations, 05-recursive-descent, 06-llk-and-all-star

  • [CLANG-ParseTentative] Clang's tentative (backtracking) parsing for C++ declarations vs expressions — clang/lib/Parse/ParseTentative.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: Parser::isCXXDeclarationStatement, TPResult.
    Why and when: Bounded backtracking and arbitrary lookahead at the few places C++ needs them (Lessons 2.5–2.6). Read the file comment first, then isCXXDeclarationStatement.
    Cited in: 01-grammars-and-ambiguity, 05-recursive-descent, 06-llk-and-all-star

  • [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: Left-corner SCCs and "leaders" for left recursion (Lesson 2.4 §7); the generated parsers' memoize and memoize_left_rec live in pegen/parser.py (Lesson 2.5 §7) and pegen/first_sets.py has FirstSetCalculator (Lesson 2.2 §7).
    Cited in: 02-first-follow-fixed-points, 04-grammar-transformations, 05-recursive-descent

  • [CPY38-pgen] CPython 3.8's LL(1) parser generator pgen — Parser/pgen/pgen.py in python/cpython at v3.8.0. Symbols: ParserGenerator.addfirstsets, ParserGenerator.calcfirst.
    Why and when: FIRST sets over per-rule DFAs and the "rule … is ambiguous" FIRST/FIRST check (Lessons 2.2 and 2.3); the table-driven driver is Parser/parser.c, PyParser_AddToken. The last release before the PEG switch.
    Cited in: 02-first-follow-fixed-points, 03-ll1-tables-and-conflicts, 04-grammar-transformations, 05-recursive-descent

  • [GCC-CParser] GCC's hand-written recursive-descent C parser — gcc/c/c-parser.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: c_parser_statement, c_parser_if_statement, c_parser_binary_expression, c_parser_skip_until_found.
    Why and when: The same shapes as Clang's parser in another code base: left-factored if (with -Wdangling-else), an operator-precedence stack for binary expressions, and panic mode.
    Cited in: 01-grammars-and-ambiguity, 03-ll1-tables-and-conflicts, 04-grammar-transformations, 05-recursive-descent, 07-error-recovery

  • [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_statement, cp_parser_parse_tentatively, cp_parser_parse_definitely, cp_parser_simulate_error, cp_parser_skip_to_end_of_statement.
    Why and when: Read the long header comment ("Future Improvements" discusses the cost of tentative parsing, quoted in Lesson 2.5 §5) and the tentative-parsing trio.
    Cited in: 05-recursive-descent, 07-error-recovery

  • [GO-Parser] Go's hand-written recursive-descent parser — src/go/parser/parser.go in golang/go at go1.23.0. Symbols: (*parser).advance, (*parser).parseStmt, stmtStart.
    Why and when: Panic mode that synchronizes on statement starts and bounds cascades ("avoid an endless parser loop"), quoted in Lesson 2.7 §5–7. A compact, readable production parser.
    Cited in: 05-recursive-descent, 07-error-recovery

  • [RUSTC-Parser] rustc's parser diagnostics and recovery (with stmt.rs and mod.rs next to it) — compiler/rustc_parse/src/parser/diagnostics.rs in rust-lang/rust at 1.90.0. Symbols: Parser::recover_stmt, Parser::create_snapshot_for_diagnostic, Parser::restore_snapshot, Parser::expected_one_of_not_found.
    Why and when: Snapshots for speculative recovery, panic mode to the end of a statement, and "expected one of …" messages; mod.rs has Parser::look_ahead (k-token peeks, Lesson 2.6) and stmt.rs has parse_stmt_without_recovery (Lesson 2.5).
    Cited in: 05-recursive-descent, 06-llk-and-all-star, 07-error-recovery

  • [SWIFT-ParseStmt] The Swift compiler's C++ statement parser — lib/Parse/ParseStmt.cpp in swiftlang/swift at swift-6.1-RELEASE. Symbols: Parser::parseStmt, Parser::BacktrackingScope.
    Why and when: Recursive descent with scoped backtracking (Lesson 2.5 §7). Compare its BacktrackingScope with Clang's TentativeParsingAction.
    Cited in: 05-recursive-descent

  • [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: Phrase-level recovery that keeps skipped tokens as "unexpected" nodes in the tree (Lesson 2.7 §7) and a lossless CST (Lesson 2.1 §7).
    Cited in: 01-grammars-and-ambiguity, 07-error-recovery

  • [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>::ParseStatement.
    Why and when: A fourth production recursive-descent parser (Lesson 2.5 §7); the same statement dispatch as Clang, for JavaScript.
    Cited in: 05-recursive-descent

Official documentation and specifications

  • [ANTLR4-LeftRecDoc] ANTLR 4 documentation: Left-recursive rules. ANTLR 4.13.2. link
    Why and when: The user-level statement of what ANTLR 4 accepts (direct left recursion only) and how precedence and associativity follow from alternative order (Lesson 2.4 §7).
    Cited in: 04-grammar-transformations

  • [BISON-Manual] GNU Bison manual: shift/reduce conflicts, %expect, counterexamples, GLR. Bison 3.8.2. link
    Why and when: The reference for the Bison outputs pasted in Lessons 2.1–2.3 (conflict reports, -Wcounterexamples, %expect) and for GLR ambiguity reports. Read "Shift/Reduce" and "Counterexamples".
    Cited in: 01-grammars-and-ambiguity, 03-ll1-tables-and-conflicts

  • [CLANG-Internals] Clang Internals Manual: the Lexer and Parser libraries, annotation tokens. LLVM 23.1.2. link
    Why and when: The official description of Clang's token and annotation-token design used by tentative parsing (Lesson 2.5 §7); read the "Annotation Tokens" section.
    Cited in: 05-recursive-descent

  • [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 2.5 §1): a production compiler choosing recursive descent over a generator.
    Cited in: 05-recursive-descent

  • [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 2.5 §1).
    Cited in: 05-recursive-descent

  • [PEP617] PEP 617: New PEG parser for CPython. Python 3.9. link
    Why and when: Why CPython left its LL(1) pgen parser for PEG: the LL(1) restriction forced grammar hacks. Read "Background on LL(1) parsers" after Lesson 2.3; it is the best real-world account of LL(1)'s limits.
    Cited in: 02-first-follow-fixed-points, 03-ll1-tables-and-conflicts, 05-recursive-descent