Parsing: Concepts & Vocabulary
The shared glossary for the parsing catalog — the page every deep-dive and theory leaf links back to for definitions. It fixes the load-bearing terms — grammar, terminal/nonterminal, derivation, recognition vs parsing, parse tree / AST / CST, lexing vs scannerless, ambiguity and disambiguation, lookahead / backtracking / determinism, memoization / incrementality / error recovery — and grounds each in a textbook, a seminal paper, or a real source tree, so the algorithm deep-dives (top-down, bottom-up, general, PEG/packrat, Pratt, derivatives) and the tool deep-dives can use the words without re-defining them. The deep theoretical development — the Chomsky hierarchy, automata, pumping lemmas, decidability, and the cubic complexity wall — lives one level down in Formal Languages & the Parsing Problem; this page is the practitioner's vocabulary that sits on top of it. The whole field is laid out side-by-side in the at-a-glance landscape table at the bottom, and synthesized in the capstone comparison.
NOTE
Two companion glossaries. This file defines the operational vocabulary a reader needs to follow any deep-dive; theory/formal-languages.md develops the formal machinery (the four-tuple G = (N, Σ, P, S), the recognizing automata, the Valiant/Lee O(n³) frontier, the closure and pumping lemmas). Where a term has a precise theoretical home, this page links there rather than re-deriving it. The theory index is the map of that lower level.
Grammars and the Chomsky hierarchy
A grammar is a finite set of rewrite rules (productions) that generates a (usually infinite) set of strings — its language. Parsing is the inverse problem: given a string, recover the structure the grammar would have used to generate it. Grune & Jacobs open Parsing Techniques with the definition this whole catalog inherits:
"Parsing is the process of structuring a linear representation in accordance with a given grammar." — Grune & Jacobs, Parsing Techniques: A Practical Guide, 2nd ed. (source)
Grammars are ranked by expressive power along the Chomsky hierarchy, Noam Chomsky's 1956 classification of four nested grammar classes, each defined by a restriction on the shape of its productions and each recognized by a strictly weaker machine (Chomsky 1956; full development in formal-languages). The four levels, from most to least restrictive:
| Type | Grammar class | Production form | Recognizer | Membership cost | Role in parsing |
|---|---|---|---|---|---|
| 3 | Regular | A → a, A → aB (right-linear) | finite automaton (DFA/NFA) | O(n), O(1) space | the lexer layer; the SIMD classifier in simdjson |
| 2 | Context-free (CFG) | A → γ (one nonterminal LHS, any RHS) | pushdown automaton (a stack) | O(n³) general, O(n) deterministic | the backbone of every parser here |
| 1 | Context-sensitive (CSG) | αAβ → αγβ, γ ≠ ε | linear-bounded automaton | PSPACE-complete | a foil — too costly to parse with; handled out-of-band |
| 0 | Unrestricted (recursively enumer.) | γ → α, any rewrite | Turing machine | undecidable in general | out of scope (general computation) |
Practical parsing lives almost entirely in Type 2 and Type 3. A regular language cannot count nesting depth — it has "no memory but its current state" — so it cannot balance (/) or if/end; that demands at least a stack, i.e. a context-free grammar parsed by a pushdown automaton. But you do not climb higher than you must: Type 1 recognition is PSPACE-complete and Type 0 is undecidable. The Dragon Book frames syntax analysis around precisely this choice — context-free grammars are expressive enough for nesting yet cheap enough to parse:
"By design, every programming language has precise rules that prescribe the syntactic structure of well-formed programs. … The syntax of programming language constructs can be specified by context-free grammars or BNF (Backus-Naur Form) notation." — Aho, Lam, Sethi & Ullman, Compilers: Principles, Techniques, and Tools (the "Dragon Book"), 2nd ed. (source)
The single most consequential fact for this catalog is the split inside Type 2: the deterministic context-free languages (those a deterministic pushdown automaton accepts) are exactly the languages with an LR(1) grammar (Knuth, 1965), and they parse in O(n). Every top-down and bottom-up technique is a strategy for staying in — or near — that linear-time deterministic subset; the general parsers are what you reach for when the grammar genuinely escapes it. The grammar classes the real families occupy:
recognizing machine parsing in this catalog
Type 0 recursively enumerable ── Turing machine (out of scope)
⊋
Type 1 context-sensitive ── linear-bounded automaton (foil; "context-sensitive patches")
⊋
Type 2 context-free ── pushdown automaton ← THE parsing level
│ ⊋ deterministic CF (DPDA) ── LR(1)/LALR/LL ← linear-time subset
⊋
Type 3 regular ── finite automaton ← lexers, the SIMD classifierIMPORTANT
"Context-free" is an almost-truth for real languages. Production grammars are context-free in the large but carry a few context-sensitive patches — C's typedef-vs-identifier ambiguity (the lexer hack), Python's significant indentation (INDENT/DEDENT), here-documents — each a tiny instance of the {aⁿbⁿcⁿ} phenomenon a CFG provably cannot express. The universal move is to push the context-sensitive bit into a stateful lexer or a semantic side-table so the core grammar stays context-free; the gory details are in formal-languages.
Terminals, nonterminals, and derivations
Formally a grammar is a 4-tuple G = (N, Σ, P, S) (formal-languages):
- Terminals (
Σ) — the alphabet of atomic symbols the grammar's strings are made of. For a programming language these are the tokens the lexer emits (if,+, an identifier, a number literal), not raw characters. They are "terminal" because no production rewrites them; they are the leaves of every parse tree. - Nonterminals (
N) — the syntactic variables (Expr,Statement,Decl). Each names a sub-language and appears on the left-hand side of one or more productions. By convention nonterminals are capitalized or angle-bracketed (<expr>), terminals quoted or lowercase. - Productions (
P) — the rewrite rulesA → γ. A context-free production has a single nonterminal on the left and any string of terminals and nonterminals on the right. - Start symbol (
S ∈ N) — the distinguished nonterminal a whole input must reduce to (CompilationUnit,Program).
A grammar of balanced parentheses, written in bnf, has one nonterminal (S), two terminals ((, )), and a recursive production plus an empty alternative:
; Context-free, not regular: matching depth needs a stack.
S ::= "(" S ")" S
| ε ; the empty string (epsilon)A derivation is a sequence of rewrites S ⇒ … ⇒ w that produces a terminal string w by repeatedly replacing a nonterminal with the right-hand side of one of its productions. The grammar's language is every string so derivable: L(G) = { w ∈ Σ* | S ⇒* w } where ⇒* is the reflexive-transitive closure of the single-step rewrite.
Two derivation orders name the two great algorithm families:
- A leftmost derivation always expands the leftmost remaining nonterminal first. This is the order a top-down / recursive-descent /
LLparser follows — the firstLinLLstands for the Leftmost derivation it traces. - A rightmost derivation expands the rightmost nonterminal first. A bottom-up /
LRparser builds a rightmost derivation in reverse — theRinLRis the Rightmost derivation it reconstructs as it reduces handles back toS.
Leftmost derivations are in bijection with parse trees, so "two leftmost derivations" and "two parse trees" are the same phenomenon — the formal definition of ambiguity.
NOTE
EBNF, BNF, and the metasyntax. Grammars in this catalog are written in BNF (Backus–Naur Form: ::=, |, recursion) or EBNF (Extended BNF, which adds regular-expression sugar — ? optional, */+ repetition, ( ) grouping). The sugar is convenience, not extra power: an EBNF rule desugars to plain BNF productions. Each parser-generator deep-dive (Bison, ANTLR, Menhir, pest) defines its own concrete grammar DSL on top of this shared metasyntax.
Recognition vs parsing
Two questions hide under the word "parse", and keeping them apart is the first discipline of the field:
| Stage | Question answered | Output | Cost (CFG) |
|---|---|---|---|
| Recognition | Is w ∈ L(G)? (yes / no) | a boolean | O(n³) general, O(n) det. |
| Parsing | What structure did G use for w? | a parse tree (or actions/AST built on the fly) | same asymptotics |
Recognition is the membership decision: does the string belong to the language at all? Parsing additionally builds the witness — the tree (or the sequence of semantic actions) that shows how the grammar generated the string. Many algorithms are first specified as recognizers and then extended to parsers: CYK fills a table of which nonterminals derive which substrings (recognition) and reconstructs the tree by back-pointers (parsing); a regex matcher recognizes without ever building a tree. The asymptotic cost is the same either way — building the tree is not the expensive part; deciding membership is.
A third, distinct stage sits beyond parsing: semantic analysis answers is w well-formed beyond syntax? (types agree, names are declared before use). This is where the context-sensitive constraints a CFG provably cannot express — the typedef-vs-identifier decision, declaration-before-use — are enforced, via a symbol table and attribute evaluation rather than a grammar. The clean layering recognition → parsing → semantics is the architecture the lexer hack deliberately violates (it feeds the symbol table backwards into the lexer) and Clang deliberately restores.
NOTE
"Parser" in tool names is loose. A "JSON parser" like simdjson both validates (recognizes) and produces a navigable document (parses); a "validator" recognizes only. When a deep-dive says a tool is O(n³), that is the recognition bound. Building one tree, or a compact shared-packed parse forest, stays within that bound; explicitly enumerating every tree in an ambiguous grammar can still be exponential in the number of parses.
Parse trees, ASTs, and CSTs
Three tree shapes, distinguished by how much of the concrete syntax they keep:
A parse tree (a.k.a. concrete syntax tree, CST, derivation tree) is the direct image of a derivation:
Sat the root, every interior node a nonterminal whose children are exactly the right-hand side of the production applied, leaves spelling out the input terminals left to right. It records every token, including punctuation and grouping. A lossless CST additionally retains whitespace and comments — the property tree-sitter needs to round-trip and re-render edited source.An abstract syntax tree (AST) is the parse tree with the syntactic noise stripped out — the shape a compiler back-end actually consumes. Wikipedia's definition pins the distinction:
"An abstract syntax tree (AST) … does not represent every detail appearing in the real syntax, but rather just the structural or content-related details. For instance, grouping parentheses are implicit in the tree structure, so these do not have to be represented as separate nodes. … Compared to the source code, an AST does not include nonessential punctuation and delimiters (braces, semicolons, parentheses, etc.). … This distinguishes abstract syntax trees from concrete syntax trees, traditionally designated parse trees." — Wikipedia: AST
The contrast, on the same input (1 + 2):
CST / parse tree AST
---------------- ---
Expr (+)
└─ "(" Expr ")" ├─ 1
└─ Expr "+" Expr └─ 2
├─ Num "1"
└─ Num "2"
(keeps the parens and the (parens implied by structure;
Expr-wrapping nonterminals) only the operator and operands)Which one a tool builds is a defining design choice. Most parser-generators (Bison, Menhir, ANTLR) let semantic actions build an AST directly during the parse, never materializing a full CST. Parser combinators (nom, Parsec, chumsky) return whatever value the combinator code constructs — usually an AST, since the combinator is the tree-builder. tree-sitter is the outlier: it deliberately produces a lossless CST because an editor must re-render and incrementally re-parse the exact bytes, comments and all. General parsers (Earley, GLR) facing an ambiguous grammar return not one tree but a parse forest — a shared, packed representation of all trees (an SPPF; see general parsing).
Lexing vs scannerless parsing
The classical pipeline splits syntax analysis into two phases: a lexer (a.k.a. scanner, tokenizer) first chops the raw character stream into a stream of tokens using a regular (Type 3) grammar, then a parser consumes that token stream with a context-free grammar. The lexer is a finite automaton; the parser is a pushdown automaton. The split is licensed by a closure property — a context-free language intersected with a regular language is still context-free — so running a regular lexer in front of a CF parser keeps the composite context-free (formal-languages). The Dragon Book gives three reasons to separate them:
"There are a number of reasons why the analysis portion of a compiler is normally separated into lexical analysis and parsing (syntax analysis) phases. 1. Simplicity of design … 2. Compiler efficiency is improved [a specialized buffering technique for reading characters speeds up the compiler] … 3. Compiler portability is enhanced [input-device-specific peculiarities can be restricted to the lexical analyzer]." — Dragon Book, §3.1 (source)
The lexer's job is more than splitting: it classifies each token (keyword? operator? literal?), discards whitespace and comments, and resolves the longest-match / maximal-munch rule (>= is one token, not > then =). Crucially, it is also where the context-sensitive patches are smuggled in — Python's indentation-driven INDENT/DEDENT tokens, C's typedef back-channel, here-document terminators — precisely because a stateful lexer can carry side data a pure CFG cannot.
Scannerless parsing collapses the two phases: there is no separate token stream; the parser works directly over characters (or bytes), with the lexical rules folded into the same grammar as the syntactic rules. This is the natural mode for parser combinators (nom is byte-oriented and scannerless; Parsec, chumsky) and for PEG tools (pest), where the ordered-choice operator and the absence of a separate lexical grammar make a single unified grammar both possible and idiomatic. simdjson is scannerless in a different sense — its SIMD stage-1 classifies bytes directly into structural and non-structural roles with no token objects at all.
| Axis | Lexer + parser (two-phase) | Scannerless (one phase) |
|---|---|---|
| Lexical grammar | separate (regular); a flex/hand-written scanner | folded into the main grammar |
| Parser sees | a stream of tokens | raw characters / bytes |
| Whitespace & comments | discarded by the lexer before the parser | matched explicitly in the grammar (a recurring chore) |
| Token disambiguation | maximal-munch in the lexer; keyword tables | handled by ordered choice / longest-match in the grammar |
| Typical homes | Bison, Menhir, ANTLR, classic LR/LL | nom, Parsec, pest, chumsky (PEG/combinators) |
| Context-sensitive patches | smuggled into the stateful lexer | expressed via predicates / context-sensitive combinators |
WARNING
Scannerless parsing re-introduces lexical ambiguity into the parser: without a separate maximal-munch lexer, the grammar must itself ensure that interface is a keyword and not the identifier inter followed by face, and must thread whitespace handling through every rule. PEG's ordered choice and greedy repetition make this tractable (try the keyword alternative first); plain CFG combinators rely on the author's discipline. The convenience of one grammar is paid for in vigilance over token boundaries.
Ambiguity and disambiguation
A grammar is ambiguous when some string has more than one parse tree (equivalently, more than one leftmost derivation):
"[An ambiguous grammar is] a context-free grammar for which there exists a string that can have more than one … parse tree." — Wikipedia: ambiguous grammar
The textbook witness is unparenthesized arithmetic, which leaves operator precedence and associativity unresolved:
; Ambiguous: "1 - 2 - 3" has two parse trees —
; (1 - 2) - 3 and 1 - (2 - 3) — with different values.
E ::= E "-" E
| digitTwo finer distinctions matter. Grammar ambiguity is a property of the grammar and is often fixable by rewriting. Inherent ambiguity is a property of the language: one for which every grammar is ambiguous — no rewriting can help, so no deterministic parser exists for it (formal-languages). And, decisively for tooling, "is this grammar ambiguous?" is undecidable in general (it reduces to the Post Correspondence Problem) — which is why no generator can warn you definitively; it can only report grammar-class-specific conflicts (formal-languages).
The three families cope with ambiguity in fundamentally different ways:
Deterministic parsers reject it at construction time. An LL or LR/LALR generator that finds two viable actions for the same state reports a shift/reduce or reduce/reduce conflict — its way of saying "your grammar is not in my deterministic class." Bison resolves such conflicts via precedence and associativity declarations (
%left,%right,%prec) or a default (shift), trading a clean error for a silent choice.PEG / ordered-choice parsers dissolve it by fiat. A PEG's choice operator
e1 / e2is prioritized: it commits to the first alternative that matches. So a PEG is unambiguous by definition — at the cost of possibly hiding the alternative you meant. Ford's contrast:"Unlike CFGs, PEGs cannot be ambiguous; a string has exactly one valid parse tree or none." — Wikipedia: parsing expression grammar, on Ford's PEG (POPL 2004)
General parsers embrace it. Earley and GLR return a parse forest — all trees at once — which is the only honest answer for an inherently or deliberately ambiguous grammar (natural language, tooling grammars). tree-sitter is GLR-based and resolves residual ambiguity with static
precrules and a runtime error-cost metric.
Disambiguation is the act of choosing one tree. The principled techniques, in roughly increasing intrusiveness:
| Technique | Where it lives | Example |
|---|---|---|
| Encode precedence in grammar shape | the grammar itself (a rule layer per level) | one nonterminal for +/-, one for *//; left-recursive for left-assoc |
| Precedence/associativity declarations | generator directives | Bison %left '+'; Menhir %left |
| Pratt / precedence climbing | the parser's expression core | a binding-power number per operator; the dominant hand-written technique |
Ordered choice (/) | PEG grammars | "try the keyword rule before the identifier rule" |
| Semantic predicates / dynamic precedence | parse-time guards | ANTLR {...}? predicates; tree-sitter prec.dynamic |
IMPORTANT
The dangling-else is the canonical ambiguity every language designer meets: in if a then if b then s1 else s2, does the else bind to the inner or outer if? The grammar is genuinely ambiguous; the universal resolution ("else binds to the nearest unmatched then") is imposed by a disambiguation rule — a Bison shift-default, a PEG ordered choice, or a grammar rewrite — not by the bare CFG.
Lookahead, backtracking, and determinism
Three intertwined notions decide how a parser chooses its next move and how much it can see or undo while choosing.
Lookahead is how many tokens of upcoming input the parser may inspect before committing to a production. The classical classes are named by it:
LL(k)/LR(k)— fixed k tokens of lookahead.LL(1)andLALR(1)(one token) are the workhorses: a parse decision is a table lookup keyed on the current state and the next token. TheLLfamily is developed in top-down, theLRfamily in bottom-up.LL(*)/ALL(*)— unbounded but regular lookahead. ANTLR'sALL(*)does a mini-DFA simulation at parse time to choose among alternatives that share an arbitrarily long common prefix — the central trick of ANTLR:"The critical innovation is to move grammar analysis to parse-time … ALL(*) is O(n⁴) in theory but consistently performs linearly on grammars used in practice." — Parr, Harwell & Fisher, "Adaptive LL(*) Parsing" (OOPSLA 2014) (source)
Backtracking is the parser's ability to undo a wrong choice — abandon a partially matched alternative and try the next. Deterministic LL/LR parsers do not backtrack: the table tells them the one correct move, so they never speculate. PEG / packrat parsers (peg) and most parser combinators (nom, Parsec) do backtrack: ordered choice e1 / e2 tries e1, and on failure rewinds the input and tries e2. Backtracking buys unbounded lookahead and a simpler grammar at the risk of exponential blowup — which is exactly the cost packrat memoization exists to defuse.
WARNING
Backtracking in combinators is opt-in, and getting it wrong silently breaks the parser. In Parsec, choice p <|> q only tries q if p consumed no input; once p consumes a token it commits, and you must wrap it in try p to make the alternative reachable. This "consumed-input" rule is what keeps Parsec near-linear by default, but it makes accidental commitment a classic bug — see Parsec.
Determinism is the property that the parser's next action is uniquely determined by its state and bounded lookahead — no speculation, no backtracking, no parallel parses. A deterministic parser runs in O(n) and detects errors at the earliest possible token (the viable-prefix property for LR; an analogous early-detection property for LL). The deterministic CF languages are exactly the LR(1) languages (Knuth 1965), and chasing that linear-time sweet spot is what the whole LL/LR enterprise is about. When a grammar is not deterministic, you have three escapes, each trading the determinism for something:
| Escape from determinism | Buys | Pays | Realized by |
|---|---|---|---|
| Backtracking + ordered choice | a simpler grammar; unbounded lookahead | exponential time without memoization; hidden alternatives | PEG, combinators (nom, Parsec) |
Parse-time analysis (ALL(*)) | any non-left-recursive CFG, no manual factoring | O(n⁴) worst case (linear in practice) | ANTLR |
| Generalized parsing (GLR/GLL/Earley) | any CFG, ambiguity and all | O(n³) worst case; a forest, not a tree | GLR, Earley/GLL |
Memoization, incrementality, and error recovery
Three engineering concerns that separate a textbook algorithm from a production parser.
Memoization caches the result of "did nonterminal A match at position i?" so a backtracking parser never re-evaluates the same (rule, position) pair twice. This is the heart of packrat parsing: it turns a PEG's exponential-in-the-worst-case backtracking into guaranteed linear time by trading time for a memo table. Ford's functional pearl introduced it:
"Packrat parsing is a novel technique for implementing parsers in a lazy functional programming language. A packrat parser provides the power and flexibility of top-down parsing with backtracking and unlimited lookahead, but nevertheless guarantees linear parse time." — Ford, "Packrat Parsing: Simple, Powerful, Lazy, Linear Time" (ICFP 2002) (source)
The trade is space: the memo table is O(n × |grammar|), so packrat parsers use far more memory than a streaming LL/LR parser — which is exactly why pest deliberately does not memoize (it is a "non-packrat" PEG), and why nom/chumsky make memoization opt-in. The same (rule, position) table reappears, transposed, as the chart in Earley and the GSS in GLL/GLR — memoization is the single idea that tames every backtracking or generalized parser.
Incrementality is the ability to re-parse a small edit in time proportional to the edit, not to the whole file — the contract an editor demands. A batch parser may recover from syntax errors, but its unit of work is still a complete input; that contract is wrong for a buffer that is constantly half-typed and re-parsed on every keystroke. tree-sitter is the canonical incremental parser; its self-description states the contract directly:
"Tree-sitter is a parser generator tool and an incremental parsing library. It can build a concrete syntax tree for a source file and efficiently update the syntax tree as the source file is edited." — tree-sitter documentation
Incrementality requires keeping the CST around between edits (you re-use unchanged subtrees), which is one reason tree-sitter produces a lossless CST rather than a throwaway AST.
Error recovery is producing a useful result despite a syntax error rather than aborting at the first one — the difference between a compiler (which may stop) and an IDE (which must not). The theory guarantees only where the first error is (the viable-prefix property); how to continue past it is heuristic engineering:
| Recovery strategy | Mechanism | Where it lives |
|---|---|---|
| Panic mode | skip tokens until a synchronizing token (;, }) is found | classic LL/LR; Bison |
| Error productions | grammar rules that match common mistakes and emit a diagnostic | Bison error token; Menhir |
| Error nodes in the tree | insert/skip tokens and record an ERROR node, keep parsing | tree-sitter (GLR error cost) |
| Partial-AST recovery | a failed parse yields a partial AST plus a list of errors | chumsky (recovery is a first-class combinator) |
| Formal/verified parsing | a machine-checked correctness proof of the parser itself | Menhir's Coq/Rocq back-end |
NOTE
Error recovery and incrementality are why the catalog's two most "modern" tools — tree-sitter and chumsky — exist at all. A 1970s LALR generator was built for the batch compiler contract: one pass, first error fatal, AST or nothing. The shift toward IDE/LSP tooling re-prioritized tolerance and incrementality over raw single-pass throughput, and the algorithm choices (GLR, recovering combinators) follow from that contract change. The opposite extreme — maximal throughput, no recovery — is simdjson.
The parser landscape at a glance
Every family this catalog surveys, mapped to its typical grammar class, worst-case time (for recognition — see recognition vs parsing), how it handles ambiguity, its error-recovery posture, and a representative tool. Each family links to the theory deep-dive that develops it; the capstone comparison places these side-by-side on shared axes.
| Family | Typical grammar class | Worst-case time | Ambiguity handling | Error-recovery posture | Representative tool |
|---|---|---|---|---|---|
| Recursive descent / LL(k) (top-down) | LL(k) deterministic CF | O(n) | rejected at construction (conflict) or by rule order | panic-mode; hand-written recovery is easy and local | hand-written RD; many compilers |
| LL(*) / ALL(*) (top-down) | non-left-recursive CF (adaptive lookahead) | O(n⁴) (linear in practice) | not handled; resolved by alternative order | single-token recovery + sync sets | ANTLR |
| LR(0) / SLR / LALR(1) (bottom-up) | deterministic CF (subsets of LR(1)) | O(n) | rejected as shift/reduce or reduce/reduce conflict | panic-mode; error productions; error token | Bison / yacc |
| Canonical LR(1) (bottom-up) | full deterministic CF (the LR(1) languages) | O(n) | rejected as a conflict (fewer than LALR) | error productions; verified recovery option | Menhir |
| GLR (generalized LR) (bottom-up) | any CFG (ambiguous included) | O(n³) (cubic) | embraced — splits the stack, returns a parse forest | error cost + tree error nodes (tree-sitter) | tree-sitter; Bison %glr |
| Earley (general) | any CFG | O(n³); O(n²) unambig.; O(n) LR-class | embraced — chart yields a parse forest | chart survives errors; recovery is grammar-driven | Marpa; nearley.js |
| CYK (general) | any CFG (Chomsky normal form) | O(n³ · grammar-size) | embraced — table records all derivations | mostly a recognizer; recovery is bolt-on | teaching / NLP toolkits |
| GLL (general) | any CFG (generalized recursive descent) | O(n³) | embraced — GSS + shared packed parse forest | descends well into partial input; tooling-dependent | instaparse |
| PEG / packrat (PEG/packrat) | PEG (ordered choice; CF-incomparable) | O(n) packrat; O(n)/exp. non-memo | dissolved — unambiguous by fiat (first match wins) | by construction continues; recovery is the weak spot | pest (non-packrat PEG) |
| Parser combinators (top-down) | PEG-like / predictive LL with backtracking | O(n)–exponential (opt-in memo) | dissolved via left-biased ordered choice | first-class recovering combinators (chumsky) | nom, Parsec, chumsky |
| Parsing with derivatives (derivatives) | any CFG (Brzozowski derivative, lifted) | O(n³) (cubic, w/ compaction) | embraced — produces a parse forest | research-grade; not a recovery-focused technique | Adams/Might parsing-with-derivatives |
| Pratt / operator-precedence (Pratt) | operator grammars (expression sublanguage) | O(n) | resolved by binding power (precedence as a number) | local; pairs with a host recursive-descent recovery | embedded in many hand-written parsers |
| SIMD / ad-hoc data-parallel (simdjson) | one fixed grammar (regular stage-1 + CF stage-2) | O(n) (branchless, vectorized) | n/a — a single unambiguous grammar (JSON) | validate-or-reject (no partial recovery) | simdjson |
NOTE
The "worst-case time" column is the asymptotic recognition bound, not the constant factor. simdjson and a LALR(1) parser are both O(n), yet simdjson is often an order of magnitude faster in wall-clock terms because it is branchless and vectorized — it processes 64 bytes per step instead of one token per table lookup. Conversely a cubic-worst-case Earley or GLR parser runs in linear time on the deterministic grammars that dominate real languages; the cubic wall only bites on genuinely ambiguous input. Asymptotic class is necessary but never sufficient for picking a parser — see the comparison for the constant-factor and ergonomics axes.
The families are not disjoint. Parser combinators are recursive descent expressed as composable host-language values, so they share top-down's grammar class while adopting PEG's ordered choice. GLR is LR with the determinism requirement dropped, so it sits in both the bottom-up and the general-parsing families. Pratt parsing is an expression sublanguage technique embedded inside a recursive-descent or LR parser, not a standalone family. And tree-sitter layers incrementality and error recovery on top of GLR — a reminder that the memoization / incrementality / error recovery concerns cut across the algorithm taxonomy rather than partitioning it.
Sources
The definitions above are grounded in the field's primary literature and authoritative references; the deep theory is developed in formal-languages, which carries its own citations.
- Aho, Lam, Sethi & Ullman. Compilers: Principles, Techniques, and Tools (the "Dragon Book"), 2nd ed. — CFGs as the formalism for programming-language syntax (§4), the lexer/parser separation rationale (§3.1). (PDF)
- Grune, D. & Jacobs, C. Parsing Techniques: A Practical Guide, 2nd ed. — the operational definition of parsing and a survey of every algorithm family. (1st-ed. PDF)
- Hopcroft, Motwani & Ullman. Introduction to Automata Theory, Languages, and Computation — the canonical reference for the Chomsky hierarchy, automata, and decidability.
- Chomsky, N. (1956). "Three Models for the Description of Language." — introduces the hierarchy. (Semantic Scholar record)
- Ford, B. (2004). "Parsing Expression Grammars: A Recognition-Based Syntactic Foundation." POPL — PEGs, ordered choice, syntactic predicates, unambiguity by construction. (paper)
- Ford, B. (2002). "Packrat Parsing: Simple, Powerful, Lazy, Linear Time." ICFP — memoization → linear-time backtracking. (PDF)
- Parr, Harwell & Fisher. (2014). "Adaptive LL(*) Parsing: The Power of Dynamic Analysis." OOPSLA —
ALL(*), parse-time grammar analysis. (paper) - Reference encyclopedia entries (definitions cross-checked): abstract syntax tree, ambiguous grammar, parsing expression grammar, parser combinator.
- In-tree deep-dives carry the per-tool primary sources: tree-sitter, simdjson, ANTLR, Bison/yacc, Menhir, Parsec, nom, chumsky, pest.