Parsing Theory
The classical computer-science foundations under every parser in this survey, from the Chomsky hierarchy to the algorithm families that production tools reify. This is the theory subtree of the parsing survey; the concepts glossary sits above it with the operational vocabulary, and the systems deep-dives (simdjson, ANTLR, Bison, …) are where these algorithms ship. Where a deep-dive here names a real tool, it links to that tool's page.
Last reviewed: June 29, 2026
The one organizing question: what grammars can you parse, and how fast?
Every parsing algorithm is a point on a trade-off between generality (which grammars it accepts), time/space cost, and determinism (whether it commits to one parse or pursues many). Formal-language theory fixes the outer walls:
IMPORTANT
The cubic wall. General context-free recognition is pinned to the complexity of Boolean matrix multiplication from both sides — Valiant (1975) reduces parsing to BMM, and Lee (2002) proves the converse — so genuinely sub-cubic general parsing is effectively impossible. Every fast production parser escapes the wall the same way: by restricting the grammar to a deterministic subclass (LL, LR, PEG) that runs in linear time. See formal-languages.
The deep-dives split along the two classical descent directions plus the general and expression-specific families:
- Top-down (top-down) — predict from the root downward; the LL family, recursive descent, and ANTLR's adaptive ALL(*).
- Bottom-up (bottom-up) — shift and reduce upward; the LR family (SLR/LALR/canonical) and Tomita's generalized GLR.
- General (general-parsing) — parse every CFG, ambiguity and all: Earley, CYK, GLL, and the shared-packed-parse-forest representation.
- PEG & packrat (peg-packrat) — swap CFG nondeterminism for ordered choice; unambiguous and scannerless, linear-time by memoization.
- Operator-precedence & Pratt (pratt-precedence) — the linear expression sub-engine recursive descent embeds.
- Derivatives (derivatives) — one self-similar operation from regex→DFA up to full CFG parsing.
- Incremental & query-based (incremental) — the editor contract: reuse the parse tree (node reuse) and reuse the computation (demand-driven, memoized queries) so an edit costs
O(edit), notO(file).
Catalog
| Deep-dive | Grammar class / scope | Worst-case time | Resolves ambiguity by | Representative tools |
|---|---|---|---|---|
| Formal languages | Chomsky hierarchy; the parse/recognition problem & complexity walls | Θ(n³) general / O(n) det. | (theory) — ambiguity is undecidable | — |
| Top-down | LL(1) ⊊ LL(k) ⊊ LL(*) ⊊ non-left-recursive CFG | O(n) fixed-k; O(n⁴) ALL(*) | First match / production order | ANTLR, combinators (Parsec, nom, chumsky) |
| Bottom-up | LR(0) ⊊ SLR(1) ⊊ LALR(1) ⊊ LR(1); GLR = all CFGs | O(n) det.; O(n³) GLR | Declared precedence; GLR keeps all parses | Bison, Menhir, tree-sitter (GLR) |
| General parsing | All CFGs (ambiguous, left-recursive) | O(n³); O(n) on LR(k) (Leo) | Returns a forest (SPPF) of all parses | Marpa, nearley, NLTK; cf. tree-sitter |
| PEG & packrat | PEG — superset of LL/LR reaching some non-CFLs | O(n) packrat (O(n) space) | Ordered choice — unambiguous by definition | pest, nom, chumsky; LPeg, Peggy |
| Operator-precedence & Pratt | Operator grammars (expressions only) | O(n) | Binding power (implicit, global) | embedded in GCC/Clang, chumsky, pest |
| Parsing with derivatives | Regular (Brzozowski) up to all CFGs (PWD) | O(G·n³) PWD; O(n) lexers | Returns a forest; nullability fixpoints | ml-ulex (lexers); derp (research) |
| Incremental & query-based | Any base parser + a persistent tree / query graph | O(edit) re-parse (Wagner O(t+s·lg N)) | (orthogonal — reuses the chosen parser's tree) | tree-sitter, rust-analyzer, Roslyn, Lezer, rustc |
Two cross-cutting splits
Deterministic vs general
The decisive engineering choice. Deterministic parsers (LL, LR, PEG) commit to a single parse and run in linear time, but reject grammars outside their subclass with a conflict at build time. General parsers (Earley, GLR, GLL, PWD) accept every CFG and surface ambiguity as a runtime parse forest — powerful for natural language, ambiguous DSLs, and grammar prototyping, but with a cubic worst case and no static determinism guarantee.
| Deterministic (LL / LR / PEG) | General (Earley / GLR / GLL / PWD) | |
|---|---|---|
| Grammars accepted | a decidable subclass; the rest is a build-time conflict | every CFG (PWD/GLR also handle ambiguity & left-rec.) |
| Output | one parse tree | a shared packed parse forest of all parses |
| Time | O(n) | O(n³) worst; O(n)–O(n²) on tame grammars |
| Ambiguity | rejected as a conflict (LL/LR) or hidden (PEG) | reported as multiple derivations |
| Where it ships | Bison, Menhir, ANTLR, pest | tree-sitter (GLR), Marpa, nearley |
Generated vs hand-written vs combinator
The same algorithm reaches code three ways: a generator compiles a grammar file to tables (Bison, Menhir, ANTLR, pest); a hand-written recursive-descent parser codes one procedure per rule (GCC, Clang, rustc) — usually with a Pratt expression loop; and a combinator library (Parsec, nom, chumsky) reifies recursive descent as composable host-language values. The comparison weighs these in the capstone.
Suggested reading paths
- "Ground up." concepts → formal-languages → top-down → bottom-up → general-parsing.
- "Why is everything PEG now?" peg-packrat → top-down (combinators as recursive descent) → the comparison.
- "Just the expression parser." pratt-precedence.
- "The elegant outlier." derivatives → general-parsing.
- "How editors parse on every keystroke." incremental → tree-sitter → rust-analyzer (query-based) → the comparison.
Sources
Each deep-dive carries its own primary citations; the spine here rests on Chomsky 1956, Knuth 1965 (LR), Lewis & Stearns 1968 (LL), Earley 1970, Pratt 1973, Valiant 1975 / Lee 2002 (the complexity wall), Ford 2002/2004 (packrat/PEG), and Might et al. 2011 (derivatives), together with the Dragon Book (Aho, Lam, Sethi & Ullman) and Grune & Jacobs, Parsing Techniques. See the individual pages and the concepts glossary.