Parsingimplementation

Parser Generators

ANTLR, Bison, tree-sitter and LALRPOP turn a grammar file into a parser. What you buy is a machine-checked grammar and cheap change; what you pay is diagnostics, debuggability and a build step.

The question

Should I write a grammar file and generate a parser, or write the parser myself?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

The grammar file is the source of truth, and the parser becomes a build artifact. That inverts the usual relationship: the thing under review is a declarative description of the language, and the thing that runs is generated code plus a state table that nobody reads. The representation the generator works on internally is an automaton — an LL decision table, an LR item-set machine, or a PEG memo structure — and every property of the result, good and bad, follows from which one.

What this phase may assume or do

A generator is entitled to assume the grammar is unambiguous for its algorithm class, and it verifies that assumption mechanically: a conflict report is the tool refusing to proceed on an assumption it could not establish. That check is the single largest thing a generator buys, and it is why a conflict silenced by a default is a piece of the language definition that has quietly moved from your grammar file into the tool's tie-breaking rule.

Key points

A generator turns the grammar into the source of truth and the parser into a build artifact.
What it buys: a mechanical proof the grammar is unambiguous for its class, cheap change, and uniform handling of every construct.
What it costs: diagnostics derived from automaton state, debugging against generated code and state numbers, a build dependency, and usually no incremental reparse.
ANTLR (ALL(*)) is the strongest classic generator for DSLs and multi-language targets; Bison is for standards-tracking and legacy grammars; LALRPOP is Bison-shaped for Rust.
tree-sitter is a different category: GLR, error-tolerant by construction, incremental, and built for editors parsing languages they do not own.
In Bison-style grammars a real part of the language definition lives in %left/%right declarations outside the productions, which is a documentation hazard.
A conflict report is the tool doing its job; permuting productions until it disappears silently changes what the language means.
Learn grammars, ambiguity, precedence and FIRST/FOLLOW as concepts — the generator changes which understanding it demands, not whether you need one.

What is actually being bought

Three things, and they are worth stating precisely because they are often undersold as "convenience".

A machine-checked grammar. The generator proves your grammar is unambiguous for its class, or names the exact place it is not. No amount of testing a hand-written parser gives you that. For a language whose grammar is a published artifact, this is the whole argument.

Cheap change. Adding a construct is a production, not an edit across several mutually recursive functions. When the grammar churns weekly — a SQL dialect tracking a vendor, a config language under design — regeneration is dramatically cheaper than re-deriving hand-written code, and much harder to get subtly wrong.

Uniformity. Every construct is handled by the same machinery, so there is no construct that was parsed slightly differently because someone was in a hurry. Generated parsers do not have that class of bug at all.

What is actually being paid

implementationCurrent as of the 2024–2025 releases of each tool. ANTLR 4's ALL(*) is materially more powerful than LL(k) — it simulates the grammar over the actual remaining input — so do not read its capabilities back onto the LL family. tree-sitter's incremental reparse and error tolerance are properties of that tool's design, not of GLR in general; Bison's %glr-parser gives you GLR without either.

Diagnostics. Covered at length in [[ll-vs-lr]], and it is the dominant cost for anything user-facing. A deterministic LR parser can enumerate the tokens its state permits and nothing more; getting past that means writing error productions per construct, which is most of the hand-written parser you were trying to avoid.

Debuggability. When the generated parser misbehaves, you are debugging code you did not write against a state number that corresponds to nothing in your grammar file. Reading a Bison conflict requires --report=all and the ability to read item sets. This is a genuine skill barrier, and on a team it means one person owns the grammar.

A build step. A tool dependency with a version, a generated artifact that is either committed (and goes stale) or regenerated (and must be installed everywhere, including CI and every contributor's machine), and a build graph edge. Small, and it is a real cost that hand-written parsers do not have.

Incrementality, usually. Deterministic generated parsers do not reparse a single edited function; the state is a table position with no construct boundary. tree-sitter is the exception and it is built around this requirement specifically.

Semantic actions. Tree building is code interleaved into the grammar file, in a host language, running in an order the automaton chooses. It is hard to test in isolation and it makes the grammar file less readable as a grammar — which was the artifact you were paying for.

The four generators worth knowing, and what each is actually forimplementation

Tool	Algorithm	Output	Error handling	Where it is the right answer
ANTLR 4	ALL(*) — adaptive top-down	Java, C#, Python, Go, JS, C++	Best of the classic generators: automatic single-token insert/delete recovery and construct-aware messages	DSLs, query languages, data formats; multi-target projects that need one grammar in several languages
Bison / Yacc	LALR(1) by default; LR(1), IELR, GLR available	C, C++	Weakest: state-derived token lists, plus `error` productions you write	Standards-tracking grammars, large stable languages, existing Yacc grammars — Ruby, PHP, Bash, PostgreSQL
tree-sitter	GLR over a generated LR table	C library with bindings everywhere	Error-tolerant by construction: always returns a tree, with ERROR and MISSING nodes	Editor tooling, syntax highlighting, structural search over languages you do not own
LALRPOP	LR(1) by default, LALR opt-in	Rust	Conflicts are build errors; messages are ordinary Rust errors	Rust projects wanting a checked grammar with modern ergonomics

The grammar file, and where the language definition leaks out of it

Here is the same expression language in three notations. The Bison version is the shortest and the most misleading: read the productions alone and 1 + 2 * 3 is ambiguous, because the precedence lives in the %left declarations above them. That is a real property of most production Yacc grammars — a meaningful part of the language definition sits outside the productions, and a reader who skims the declarations infers the wrong tree.

The ANTLR version puts precedence back into the grammar by rule order, which is more honest as a document and is why ANTLR grammars read well. The tree-sitter version declares precedence and associativity per rule as data, which is the same idea again in JavaScript.

One expression language, three grammar files

1/* ─── Bison / Yacc (LALR(1)) ─────────────────────────────────────── */
2%left  '+' '-'          /* the precedence lives HERE, not in the rules */
3%left  '*' '/'
4%right UMINUS
5%%
6expr : expr '+' expr           { $$ = mkBin('+', $1, $3); }
7     | expr '*' expr           { $$ = mkBin('*', $1, $3); }
8     | '-' expr %prec UMINUS   { $$ = mkNeg($2); }
9     | '(' expr ')'            { $$ = $2; }
10     | NUMBER                  { $$ = mkNum($1); }
11     ;
12/* Without the %left lines this grammar is ambiguous and reports
13   4 shift/reduce conflicts. The productions alone do not define
14   the language.                                                  */
15 
16 
17// ─── ANTLR 4 (ALL(*)) ─────────────────────────────────────────────
18// Precedence is rule order; left-recursion is handled by the tool.
19expr : expr ('*'|'/') expr    # MulDiv
20     | expr ('+'|'-') expr    # AddSub
21     | '-' expr               # Negate
22     | '(' expr ')'           # Paren
23     | NUMBER                 # Number
24     ;
25 
26 
27// ─── tree-sitter (GLR, grammar.js) ────────────────────────────────
28// Precedence and associativity are per-alternative data.
29expr: ($) => choice(
30  prec.left(2, seq($.expr, choice('*', '/'), $.expr)),
31  prec.left(1, seq($.expr, choice('+', '-'), $.expr)),
32  prec(3, seq('-', $.expr)),
33  seq('(', $.expr, ')'),
34  $.number,
35),

All three describe the same language and all three handle left recursion without the rewrite [[recursive-descent]] requires — that is the generator earning its keep. The difference worth noticing is where precedence is written: outside the rules in Bison, in rule order in ANTLR, as per-alternative data in tree-sitter. Only the first can be misread by someone reading the productions.

Concepts first, tools second

A generator does not remove the need to understand grammars; it changes which understanding it demands. A conflict report is unreadable without items and states. A FIRST/FOLLOW problem shows up as an ANTLR ambiguity warning. Precedence declarations are exactly the binding powers of [[pratt-parsing]], applied at table-construction time. Left factoring, ambiguity and associativity are properties of the language and you reason about them whether you write an if or a %left.

The failure mode this produces is specific and common: a team adopts a generator to avoid learning parsing, hits a conflict in month three, and resolves it by permuting productions until the warning goes away. That works — the warning does go away — and the language now means something nobody chose. The tool did its job by reporting; the report needed a reader.

The other direction is worth saying too. Learning to read a grammar file is a transferable skill in a way that reading one compiler's hand-written parser is not. A .g4 or .y file is a specification you can review, diff and reason about, which is why standards bodies publish grammars and not parsers.

Choosing

The decision is the same shape as [[ll-vs-lr]], with one addition: the generator is also a dependency and a skill commitment, and those are organisational costs rather than technical ones.

Generate when the grammar is large, changes often, is owned by someone else, or is itself a deliverable that must be proved unambiguous. Hand-write when the error messages face humans, when an editor will consume the frontend, or when the language has context-sensitive constructs. Use tree-sitter when you need a tolerant, incremental parser for a language you do not own — that is a category of its own and it is not really competing with the other three.

And note the hybrid that several projects run: a hand-written parser for the shipping compiler plus a generated parser from the reference grammar, cross-checked by differential testing. It buys the mechanical ambiguity guarantee and the good messages, and it costs two parsers and a harness. That is expensive and it is the honest answer when both requirements are real.

How it works

The steps, in the order the compiler takes them.

Write the grammar in the tool's notation, with terminals coming either from a declared lexer or from inline literals.
The generator computes the decision structure for its class — an LL decision procedure, an LR item-set automaton, or a PEG memo layout.
It reports every place the structure is not deterministic: LL ambiguities, shift/reduce and reduce/reduce conflicts, or unreachable rules.
You resolve each: rewrite the grammar, add a precedence or associativity declaration, declare an expected conflict count, or declare an explicit GLR fork point.
The generator emits source code — a table plus a driver loop, or a set of mutually recursive functions — into a file the build compiles.
Semantic actions attached to productions run at reduction or rule-exit time and construct the tree; ANTLR alternatively emits a listener or visitor interface over a generated parse tree.
The build regenerates when the grammar changes, so the generated file is either a build product or a committed artifact that must be kept in sync.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

Conflict warnings accumulate until nobody reads them, and a new construct is silently resolved by the tool's default in a way the language reference does not describe.
A grammar is permuted until the conflict count reaches zero; the language now accepts a slightly different set of programs, and no test covers the difference.
A user reports "syntax error, unexpected '}', expecting ')' or ','" and there is no straightforward way to improve it, because improving it means writing per-construct error productions.
The generated parser file is committed and drifts out of sync with the grammar; a change to the grammar has no effect until someone notices the build is not regenerating.
The tool is not installed in CI or on a new contributor's machine, and the build fails in a way whose message is about a missing binary rather than about the grammar.
One engineer becomes the only person who can read the conflict reports, and grammar changes queue behind their availability.
A semantic action has a side effect and a later grammar change alters the reduction order; the parser still accepts the same language and the action now runs at the wrong time.

When it helps

A grammar that is a published artifact and must be provably unambiguous — a language standard, a wire format, a query language specification.
A grammar under weekly churn, or maintained by people who are not compiler engineers.
Multi-target projects: one ANTLR grammar generating parsers in Java, Python, Go and C# is a real and substantial saving.
Editor tooling for a language you do not own, where tree-sitter's tolerance and incrementality are the requirement and hand-writing a parser for someone else's evolving language is not viable.
Prototyping a language, where the grammar will change many times before anyone sees an error message.

When it hurts

Anything whose error messages are part of the product. The structural handicap is real and closing it costs roughly what hand-writing would have.
Frontends shared with a language server, where error tolerance and incremental reparse are requirements a deterministic generated parser does not meet.
Languages with genuine context sensitivity, where semantic predicates and lexer feedback channels are working against the tool's design premise.
Small grammars. A two-hundred-line hand-written parser with no build dependency beats a generator plus a toolchain for a config format, and it will still be readable in five years.

What it costs

Every one of these is paid by something.

A machine-checked grammar buys a guarantee of unambiguity that testing cannot provide, and pays with conflict reports that require reading item sets to action — a skill barrier that concentrates grammar ownership in one person.
Declarative rules buy cheap change and uniform handling, and pay in diagnostics: the parser has no per-construct code, so it has nowhere to put a message better than a token list.
A generated artifact buys regenerability, and pays a build-time tool dependency plus the committed-or-generated question, which is a real operational cost in CI and for new contributors.
Precedence declarations buy a compact expression grammar, and pay by moving part of the language definition outside the productions, so the grammar file no longer specifies the language on its own.
Semantic actions buy tree construction without a separate pass, and pay readability of the grammar file — the artifact you adopted the tool to get — plus code that only runs in the order the automaton chooses and is therefore hard to test.

What else you could do

What a different compiler or language does instead, and when that is better.

Hand-written [[recursive-descent]] plus [[pratt-parsing]]: no build step, arbitrary diagnostics, per-construct recovery, and no machine-checked grammar. The choice of essentially every production compiler.
Parser combinators — Parsec, nom, chumsky — express the grammar as ordinary composable code, so there is no build step and the grammar is still declarative-ish. Error messages and backtracking behaviour are the library's to define, and vary enormously between libraries.
PEG generators — pest, peg, and CPython's own since 3.9 — replace conflicts with ordered choice, which makes ambiguity unrepresentable rather than reported. Convenient, and it removes the check that was a generator's main selling point.
A hand-written parser plus a generated reference parser, cross-checked by differential testing. Both guarantees, double the cost, and the honest answer when a language has both users and a specification.

See it for yourself

The flag, dump or tool that shows you this directly.

bison --report=all -o parser.c grammar.y writes parser.output with every state and conflict; bison -Wcounterexamples (3.8+) prints an input string that exhibits each conflict, which is the fastest conflict-debugging tool in any generator.
ANTLR: antlr4 Grammar.g4 && javac *.java && grun Grammar startRule -gui renders the parse tree for input you type; -Xlog reports where it needed adaptive lookahead.
tree-sitter generate reports conflicts and requires you to declare intentional ones; tree-sitter parse --debug shows the shift/reduce actions and where the GLR parser forked.
Read a real one: PostgreSQL's src/backend/parser/gram.y is about twenty thousand lines of Bison and is the best available argument for generators at scale. Ruby's parse.y is the best available argument against.
Count the cost yourself on a small language: implement it once by hand and once with a generator, then introduce a deliberate syntax error and compare the two messages. That comparison decides most real projects.

Plausible wrong readings

Stated the way a confident engineer states them.

"Using a generator means I do not need to understand parsing." It means you need to understand grammars, ambiguity and the tool's conflict reports instead of control flow. The total amount to learn is not smaller.
"A generator produces a slower parser." Generated table-driven parsers are fast. The performance difference between families is small and usually favours hand-written descent slightly, for locality reasons, not by enough to decide anything.
"tree-sitter is a parser generator like Bison." It generates a parser, and it is built for a different job: tolerant, incremental parsing for editors, always returning a tree. Comparing it to Bison on grammar power misses what it is for.
"If the conflict count is zero the grammar is correct." It is unambiguous for that algorithm class. Whether it describes the language you meant is a separate question no tool checks.
"ANTLR is an LL(k) tool, so it is strictly weaker than Bison." ALL(*) simulates the grammar against the actual input and accepts many grammars no fixed k handles. The classic family comparison does not transfer.

Misconceptions

The claim, and what is actually true.

Parser generators are obsolete because compilers hand-write parsers.

Compiler frontends moved away; query languages, DSLs, data formats and editor tooling did not. PostgreSQL, Ruby, PHP and Bash all ship generated parsers today, and tree-sitter made generated parsing the default for editor tooling.

The grammar file is the specification, so the parser matches the specification.

The grammar file plus the precedence declarations plus the tool's conflict-resolution defaults is the specification. In a Bison grammar with tolerated conflicts, part of your language is defined by Bison's tie-breaking rules.

Choosing a generator is a technical decision.

It is also an organisational one. Someone has to be able to read conflict reports, and the tool has to exist in CI and on every contributor machine. Those costs are small individually and they are the ones that actually bite.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

A parser generator reads a grammar file and writes the parser for you. You get a grammar the tool has checked for ambiguity and that is easy to change; you give up good error messages, easy debugging, and add a build step. For a language whose errors users read, most compiler teams decide that trade is not worth it. For a query language, a config format, or editor tooling, it usually is.

practical

If you adopt one: turn on the strongest conflict reporting from day one and treat conflicts as build failures, not warnings — %expect 0 in Bison, and let LALRPOP and tree-sitter fail as they already do. Never resolve a conflict by permuting productions until the warning stops; get a counterexample input, understand what the two parses mean, and choose deliberately. Decide once whether the generated file is committed, and put the tool version in your build config. And write the error-message test cases early, because that is where you will find out whether you chose the right tool while it is still cheap to change.

advanced

The most interesting thing generators expose is that a grammar is a *specification artifact*, separable from any implementation, reviewable and diffable in a way a hand-written parser is not. That is why standards bodies publish grammars and why the strongest real-world configuration is often the expensive one: a hand-written frontend for the shipping compiler plus a generated parser from the reference grammar, differentially tested against each other on a corpus. The generated parser is not there to run in production — it is there as an executable specification that catches the hand-written parser drifting. Framing the tool as "how do I get a parser" underuses it; framing it as "how do I get a checkable definition of my language" is what the mature projects do.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

implementationTool behaviour cited here is for current major versions: Bison 3.8+ for -Wcounterexamples, ANTLR 4 for ALL(*), tree-sitter as of its 0.2x releases. Bison before 3.8 has no counterexample generation, which materially changes how hard conflicts are to debug; ANTLR 3 used LL(*) rather than ALL(*) and had different capabilities. Pin the version when the claim matters.

typicalThat generated parsers have worse diagnostics is true of deterministic LR generators as a family and is the dominant experience with Yacc and Bison. ANTLR 4 is substantially better — it has automatic single-token insertion and deletion recovery and construct-aware messages — and tree-sitter always returns a tree. The handicap is structural but its severity varies by an order of magnitude across tools.

simplifiedThe three grammar files shown omit the lexer entirely. Bison needs a separate Flex specification or a hand-written yylex; ANTLR grammars usually declare lexer rules in the same file or a separate .g4; tree-sitter derives its lexer from the grammar with an externals escape hatch for context-sensitive tokens. That lexer interface is a meaningful part of the adoption cost and none of it is visible above.

If you were asked this in an interview

When would you reach for a parser generator over hand-writing, and what would you be accepting?
Your Bison build reports three shift/reduce conflicts. Walk me through what you do, in order.
Why is tree-sitter used for editor tooling when Bison is not?

Connections

DSAstack dp-state-machine

API Designschema-first-vs-code-first

Domains that do not exist yet

DevOps / Production Engineering — Generated artifacts in a build: commit or regenerate
A generated parser is a build product with a tool dependency and a staleness question. Whether it is committed, how the tool version is pinned, and how CI gets it are build-system concerns owned there, and they are a real part of the cost of adopting a generator.
Testing & Reliability Engineering — Differential testing between two implementations of one specification
The mature configuration — a hand-written parser plus a generated reference parser, cross-checked on a corpus — is differential testing. The general technique is owned there; [[differential-testing]] is our compiler-specific treatment.