LL and LR Parsing

Every time you hit compile, something quietly extraordinary happens before a single instruction executes. Your source code — a flat river of characters — must be read, understood, and restructured into a parse tree: a nested shape that captures which expressions contain which sub-expressions, which statements belong to which blocks, which operators bind more tightly than others.

That act of restructuring is parsing, and it is governed by the language's context-free grammar (CFG). A CFG is a set of production rules that says things like "an expression is a term, or an expression followed by + and a term." The parser's job is to find which sequence of rule applications produces the exact token stream it sees.

Two great families of algorithms have dominated this space since the 1960s:

• LL (Left-to-right, Leftmost-derivation) parsers build the tree top-down, predicting which rule to apply next by peeking at the next token.
• LR (Left-to-right, Rightmost-derivation in reverse) parsers build the tree bottom-up, using a stack to accumulate tokens and reduce them to grammar symbols whenever a rule's right-hand side is complete.

The letters encode the strategy: L = scan left-to-right, L/R = leftmost vs rightmost derivation, and the optional number k in LL(k) or LR(k) says how many tokens the parser peeks ahead. Most real grammars are handled by LALR(1) or LR(1) — looking just one token ahead — which is both sufficient and efficient.

Below is a live LR(0) shift-reduce parser for a tiny arithmetic grammar. Type an expression using numbers, +, *, and parentheses (e.g. 3+2*4 or (1+2)*3), then step through the parse one action at a time or let it run to the end.

<div class="controls">
  <label for="expr">{{label_expression}}</label>
  <input id="expr" type="text" value="3+2*4" spellcheck="false" autocomplete="off" />
  <button id="btn-parse" type="button">{{btn_parse}}</button>
</div>
<div class="steps-header">
  <span class="col-stack">{{col_stack}}</span>
  <span class="col-input">{{col_input}}</span>
  <span class="col-action">{{col_action}}</span>
</div>
<div id="steps-list"></div>
<div class="nav-row">
  <button id="btn-prev" type="button" disabled>{{btn_prev}}</button>
  <span id="step-counter">—</span>
  <button id="btn-next" type="button" disabled>{{btn_next}}</button>
  <button id="btn-end" type="button" disabled>{{btn_end}}</button>
</div>
<div id="msg" class="msg"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; font-size: 14px; color: #222; margin: 0; }
.controls { display: flex; gap: .5rem; align-items: center; flex-wrap: wrap; margin-bottom: .7rem; }
label { font-weight: 600; }
#expr { font: 600 15px ui-monospace, monospace; border: 1.5px solid #adb1b8; border-radius: 6px;
        padding: .35rem .6rem; width: 170px; }
button { font: 600 13px system-ui; padding: .38rem .85rem; border: 1.5px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button:disabled { opacity: .4; cursor: default; }
button#btn-parse { background: #2a6eb5; border-color: #2a6eb5; }
.steps-header { display: grid; grid-template-columns: 1fr 1fr 1.2fr;
                gap: 4px; font-weight: 700; font-size: 12px; color: #555;
                border-bottom: 2px solid #dde3ea; padding: 0 0 4px; margin-bottom: 4px; }
#steps-list { max-height: 240px; overflow-y: auto; }
.step-row { display: grid; grid-template-columns: 1fr 1fr 1.2fr; gap: 4px;
            padding: 4px 2px; border-radius: 5px; transition: background .15s; }
.step-row.active { background: #e6f0fb; }
.step-row.done { background: #e8f7ee; }
.step-row.err { background: #fdecea; }
.col-stack, .col-input, .col-action { font: 13px ui-monospace, monospace; word-break: break-all; }
.col-action { font-family: system-ui, sans-serif; font-size: 12px; color: #1d3557; }
.col-action.shift { color: #2a6eb5; font-weight: 700; }
.col-action.reduce { color: #a0522d; font-weight: 700; }
.col-action.accept { color: #0a7d33; font-weight: 700; }
.col-action.error { color: #c92f3c; font-weight: 700; }
.nav-row { display: flex; gap: .5rem; align-items: center; margin: .6rem 0 .4rem; flex-wrap: wrap; }
#step-counter { font-size: 13px; color: #555; min-width: 60px; text-align: center; }
.msg { font-weight: 700; font-size: 13px; min-height: 1.4em; }
.msg.ok { color: #0a7d33; } .msg.err { color: #c92f3c; }
.col-stack, .col-input, .col-action { overflow: hidden; text-overflow: ellipsis; white-space: nowrap; }

// Code not found

Notice the two operations the parser alternates between: shift (move the next token from input onto the stack) and reduce (pop a matched right-hand side and push the non-terminal it produces). The stack grows left to right, and when the grammar symbol on top matches the start symbol with an empty input, parsing succeeds. Each reduce step is one node being added to the parse tree.

Parsing is one of the few places in computer science where theory and practice align almost perfectly.

• LL(k) and LR(k) parsers run in $O(n)$ time — linear in the length of the input. One pass, no backtracking, no revisiting tokens. This is why even million-line codebases compile quickly.
• LL grammars are a strict subset of LR grammars. Every grammar an LL(k) parser can handle, an LR(k) parser can also handle, but not vice versa. LR parsers see more context: they defer decisions until they have accumulated enough tokens on the stack.
• LALR(1) (Lookahead LR, 1 token) is the sweet spot used by tools like yacc and GNU Bison. It merges the states of a canonical LR(1) automaton to save space, and almost all practical programming languages fit within it.
• LR(1) parsers handle strictly more grammars than LALR(1), at the cost of a potentially much larger set of parser states (exponential in the worst case). ANTLR and many hand-written parsers use LL(k) or LL(*) — unbounded lookahead — for readability and ease of error reporting.
• General context-free parsing (e.g. the CYK algorithm, 1961–1965) handles any CFG in $O(n^{3})$ time — cubic, not linear. It is used when speed is not critical and the grammar is ambiguous or doesn't fit the LL/LR hierarchy.
• Some grammars are ambiguous: they produce two different parse trees for the same input. Ambiguous grammars cannot be LL or LR; resolving ambiguity requires grammar refactoring or explicit precedence rules (as C, Java and Python all do for arithmetic).

The status of parsing is thus solved: for the grammars real languages use, linear-time deterministic parsing exists and is efficient. The theoretical limits — which grammars are inherently ambiguous, which require the full $O(n^{3})$ — are also fully understood. Parsing is one of the most beautiful success stories of formal language theory.

Curious about the deeper hierarchy? See P vs NP for why "can we solve this quickly?" is the central question in all of computing, and pattern matching for a related problem where the string and the pattern interact differently.

LL and LR parsing are not academic curiosities. They are the front end of nearly every tool that processes structured text:

• Compilers and interpreters: GCC, Clang, CPython, the Java compiler, Rust's rustc — all have a parser in their front end. Most use a hand-written recursive-descent LL parser or a generated LALR(1) parser.
• IDE language servers: the Language Server Protocol (LSP) powering code completion, go-to-definition and inline errors in VS Code and JetBrains relies on fast incremental parsers (often LL or tree-sitter, a GLR variant).
• Parser generators: yacc (1975, Stephen Johnson), GNU Bison, ANTLR (Terence Parr), tree-sitter — these tools accept a grammar and emit a working parser. They are built on the same LL/LR theory.
• Query languages: SQL parsers are almost universally LALR(1) or LL(k).
• Configuration and data formats: JSON, TOML, YAML, HTML — every structured document format needs a parser. JSON's grammar is LL(1).
• Network protocols: protocol dissectors in tools like Wireshark parse binary and text protocols using finite automata and small grammars related to LL/LR.
• Template engines: Jinja2, Handlebars, ERB — all parse their own mini-languages to interpolate values into output.

Understanding LL and LR parsing means understanding the first step every language tool takes — and why some grammars are easier to work with than others.

Parsing is one of computer science's great completed chapters. For every programming language grammar that avoids ambiguity, a deterministic parser exists that reads the input in linear time, one token at a time, building the syntax tree as it goes.

LL parsers predict; LR parsers reduce. LL grammars are a strict subset of LR grammars. LALR(1) — one token of lookahead, merged states — is practical enough for almost every language ever designed, and it runs in $O(n)$. When you write 3 + 2 * 4 and your compiler correctly evaluates multiplication before addition, you are benefiting from decades of formal language theory made practical in yacc, Bison, ANTLR and their descendants.

The next time you get a "syntax error" at line 42, remember: a deterministic automaton read your entire file in one pass and pinpointed exactly where the grammar was violated. That's parsing — fast, principled, and completely understood.