LL vs LR: Why Production Compilers Chose the Weaker One

On grammar power the answer is not close and not disputed. LL commits to a production before reading the evidence for it, so left recursion is fatal and common prefixes need factoring. LR commits only once an entire right-hand side is on the stack, so left recursion is natural and the accepted grammar class strictly contains LL's.

If grammar power were the deciding criterion, every compiler would be LR, and for about fifteen years — roughly 1975 to 1990 — most were. Yacc shipped with Unix, the theory was elegant, and generating a parser from a grammar file was obviously better engineering than writing one by hand. The subsequent migration *away* from generated LR, by essentially every major compiler team, is the thing this lesson exists to explain.

The list is short and consistent. Clang hand-writes recursive descent, with precedence climbing over a precedence table for binary expressions. rustc's rustc_parse is hand-written descent with an AssocOp precedence table. Roslyn (C# and VB) hand-writes descent, explicitly designed for incremental, error-tolerant reparse. V8 hand-writes descent, with a separate pre-parser that skips function bodies until they are called. Go's cmd/compile/internal/syntax is hand-written descent. GCC hand-writes descent for C and C++ — it did not always, which is the most informative data point of the set.

GCC's C++ frontend was Bison-generated until GCC 3.4 in 2004; the C frontend followed in 4.1. Go's parser was yacc-generated until Go 1.6. Both migrations went in the same direction, and both were justified in the same terms: better diagnostics and easier handling of constructs the grammar could not express cleanly. Nobody migrated the other way.

The counter-examples are real and they are informative too. Ruby's reference implementation still uses a Bison grammar, and Ruby's syntax is famously hard to reimplement. PHP uses Bison. Bash uses Yacc. PostgreSQL parses SQL with Bison, which is exactly the case the technique suits: a large grammar tracking a standard, where conformance matters more than message quality and the input is usually machine-generated anyway.

A recursive-descent parser that fails is, at the moment of failure, several frames deep inside parseArgumentList called from parseCallExpression called from parseStatement. It can say: *"Expected ) after function arguments. Found { instead."* It can point at the opening ( as a secondary span. It can note that the argument list began on line 12. Every one of those facts is on the call stack.

An LR parser that fails is in state 143. State 143 is a set of items — a set of *hypotheses* — and the parser was tracking all of them simultaneously. It can enumerate the tokens the state permits, which is honest and reads as noise: syntax error, unexpected '{', expecting ')' or ',' or ';' or '->' or '::'. It cannot say "you were in an argument list", because it was in four things at once and had not chosen.

This is not a quality-of-implementation gap that a sufficiently determined team could close. It is a consequence of when each family commits. Committing early is what leaves you inside a named construct, and the same property that costs LL its grammar power is what buys it the message. [[diagnostic-quality]] develops what a good message actually contains; the point here is which architecture can produce one.

The requirement that reshaped frontend architecture is not compilation, it is editing. A language server must produce a usable tree for a file that is mid-keystroke and therefore syntactically broken, must do it in single-digit milliseconds, and must do it again on the next character.

That demands two things. Error tolerance: after an error, produce a tree with error nodes and keep going, because completion inside a function whose closing brace is not typed yet is the single most common IDE interaction there is. Incrementality: reparse the edited construct and reuse the rest, because reparsing ten thousand lines per keypress is not a budget anyone has.

Recursive descent gives both without heroics. The construct boundary is a function, so an edit inside a function body reparses that function; recovery is per-construct code you can tune; error nodes are a return value. A deterministic LR parser gives neither easily: its state is a position in a table with no correspondence to a source construct, so "reparse this function" has no natural expression, and after an error it has popped its stack to an error production and thrown away the context an IDE wanted.

The one bottom-up family that does serve editors is GLR, and it serves them by keeping every hypothesis alive rather than by knowing which is real — which is exactly what tree-sitter does, and it is why tree-sitter is a generated bottom-up parser that is nonetheless excellent in an editor. That is the honest exception to the argument, and it costs memory and the ambiguity-resolution question in exchange.

Every mainstream language has at least one construct the grammar cannot decide alone. In C and C++, T * x; is a declaration or a multiplication depending on whether T names a type — the parser must consult a symbol table. In C++, a < b > (c) may be a comparison chain or a template instantiation. In Rust, < after a path may open generic arguments, which is why the language has the turbofish ::<>. In JavaScript, / is division or the start of a regex depending on the preceding token.

In a hand-written parser each of these is an if. Ugly, localised, commented, testable. In a generated parser each is a semantic predicate, a lexer feedback channel, or a grammar contortion — machinery bolted onto a tool whose entire design premise was that the grammar decides.

It is worth being precise about the direction of causation. Languages designed after the LR era — Java, Go, Rust — were deliberately kept close to LL-parseable so that a hand-written frontend and good tooling would be possible. The parsing technique influenced the language design, not only the reverse.

The decision is not "which is better" but "which of these six properties do I need". If the answer includes user-facing error messages or an editor integration, hand-write it. If the answer is conformance to a grammar somebody else revises, generate it.

Concretely: a programming language whose users will see its errors — hand-written recursive descent plus [[pratt-parsing]] for expressions. A query or configuration language embedded in a product, where the grammar is large and churns — a generator. A tool that must parse a language it does not own, tolerantly and incrementally — tree-sitter, whose GLR foundation is the right answer to that specific problem. A one-off data format — whichever you can finish today.

And one thing that is true regardless: understand the grammar concepts independently of the tool. FIRST sets, FOLLOW sets, ambiguity, precedence and associativity are properties of the language, and you reason about them whether you write an if or a %left — see [[parser-generators]].