Canonical LR(1) and LALR
SLR
failed on a perfectly unambiguous grammar because it decided reductions with a global
\text{FOLLOW} set — the tokens that can follow a nonterminal anywhere
— when what it needed was the tokens that can follow this reduction, in this state. The
fix is to stop guessing and carry the exact lookahead inside each item. That single upgrade produces the
most powerful class of parser that still uses one token of lookahead: canonical LR(1),
Knuth's original 1965 construction. Its only sin is size — the tables can be enormous — so in practice we
shrink them back down with a clever compromise called LALR, the method that powers
yacc and bison.
The LR(1) item: an item with a lookahead
An LR(1) item is an LR(0) item paired with a single terminal called its
lookahead:
[\,A \to \alpha\,{\cdot}\,\beta,\; a\,].
The lookahead only matters for complete items. The item
[A \to \alpha{\cdot},\, a] says: "reduce by
A \to \alpha — but only if the next input token is exactly
a." Where SLR would reduce on all of
\text{FOLLOW}(A), an LR(1) state reduces on just the lookaheads that are
genuinely valid for the path that reached it. Different routes to the same core of items can now carry
different lookaheads, and that context-sensitivity is exactly the extra power.
CLOSURE gains a lookahead-propagation rule. For an item
[A \to \alpha{\cdot}B\beta,\, a], when we add the fresh items
B \to {\cdot}\gamma, their lookaheads are everything in
\text{FIRST}(\beta a) — the symbols that can appear right after this
B. GOTO is unchanged except that it carries the lookahead along with the dot.
A worked LR(1) closure
Take the compact grammar (augmented with S' \to S):
S \to C\,C, \qquad C \to c\,C \;\mid\; d.
(It generates c^{*}d\,c^{*}d.) The start state is
\text{CLOSURE}\big(\{[S' \to {\cdot}S,\ \$]\}\big). Work the propagation
through:
| Item added | Lookahead | Why |
|---|
| S' \to {\cdot}S | \$ | the seed (end of input) |
| S \to {\cdot}CC | \$ | from [S'\to{\cdot}S,\$]: \text{FIRST}(\$)=\{\$\} |
| C \to {\cdot}cC | c,\ d | from [S\to{\cdot}CC,\$]: \text{FIRST}(C\,\$)=\{c,d\} |
| C \to {\cdot}d | c,\ d | same reason |
So the first C in S\to CC may be followed by the
start of the second C (a c or a
d), giving the lookahead set \{c,d\}. Follow the
automaton to the end and you find the state reached after the second
C carries the lookahead \$ instead — the very
distinction SLR could not make, because it lumped both into
\text{FOLLOW}(C)=\{c,d,\$\}.
type Prod = { lhs: string; rhs: string[] };
// 0: S'->S 1: S->C C 2: C->c C 3: C->d
const G: Prod[] = [
{ lhs: "S'", rhs: ["S"] },
{ lhs: "S", rhs: ["C", "C"] },
{ lhs: "C", rhs: ["c", "C"] },
{ lhs: "C", rhs: ["d"] },
];
const NONTERM = new Set(["S'", "S", "C"]);
// FIRST of a sequence (this grammar is ε-free).
function firstSeq(seq: string[], fallback: string): string[] {
if (seq.length === 0) return [fallback];
const x = seq[0];
if (!NONTERM.has(x)) return [x];
const out = new Set<string>();
for (const prod of G) if (prod.lhs === x) for (const t of firstSeq(prod.rhs, fallback)) out.add(t);
return [...out];
}
type Item = { p: number; dot: number; look: string };
const key = (it: Item) => `${it.p}:${it.dot}:${it.look}`;
function closure(seed: Item[]): Item[] {
const out = [...seed];
const seen = new Set(out.map(key));
for (let i = 0; i < out.length; i++) {
const { p, dot, look } = out[i];
const B = G[p].rhs[dot];
if (B !== undefined && NONTERM.has(B)) {
const beta = G[p].rhs.slice(dot + 1);
const looks = firstSeq(beta, look); // FIRST(β a)
G.forEach((prod, q) => {
if (prod.lhs === B) for (const b of looks) {
const ni = { p: q, dot: 0, look: b };
if (!seen.has(key(ni))) { seen.add(key(ni)); out.push(ni); }
}
});
}
}
return out;
}
const show = (it: Item) => {
const body = [...G[it.p].rhs];
body.splice(it.dot, 0, ".");
return `[${G[it.p].lhs} -> ${body.join(" ")}, ${it.look}]`;
};
console.log("I0 = CLOSURE({ [S' -> .S, $] }):");
for (const it of closure([{ p: 0, dot: 0, look: "$" }])) console.log(" " + show(it));
LALR: merge states with the same core
Canonical LR(1) is precise but wasteful. Across the automaton you find many pairs of states whose
cores are identical — the same set of LR(0) items (dot positions) — differing
only in their lookahead sets. For our grammar
S\to CC,\ C\to cC\mid d, the two states built around
C \to c{\cdot}C are twins: one arose while expecting
\{c,d\} ahead, the other while expecting \$.
LALR ("LookAhead LR") does the obvious thing: merge any two states with the same
core, taking the union of their lookahead sets. The merged automaton has exactly as many states as
the LR(0)/SLR automaton — for this grammar, the ten canonical LR(1) states collapse back to
seven — yet it keeps far more of LR(1)'s lookahead precision than SLR's blunt FOLLOW
sets. This is the sweet spot the whole industry settled on.
- Every LR(0) grammar is SLR(1); every SLR(1) grammar is LALR(1); every LALR(1) grammar is
LR(1):
\text{LR}(0) \subsetneq \text{SLR}(1) \subsetneq \text{LALR}(1) \subsetneq \text{LR}(1).
- LALR(1) and canonical LR(1) build the same number of states — LALR just merges
cores — so LALR's table is the size of SLR's but its language power is nearly LR(1)'s.
- All of these are strictly weaker than unrestricted context-free parsing (which needs
GLR or other general methods).
Four parsers, one automaton skeleton
All four LR variants share the same driver and, except for canonical LR(1), the same
number of states. They differ only in where the reduce-lookaheads come from — which is
the entire story of their relative power and cost.
| Method | Reduce lookahead | # states | Power |
|---|
| LR(0) | none — reduce on every token | base (call it N) | weakest; most grammars conflict |
| SLR(1) | global \text{FOLLOW}(A) | N | modest; coarse lookahead |
| LALR(1) | per-state, merged from LR(1) | N | strong; yacc/bison default |
| LR(1) | exact per-item lookahead | up to many× N | strongest 1-token parser |
The middle two columns are the punchline: LALR gets LR(1)-grade lookahead at SLR-grade table
size. For a real programming language, canonical LR(1) might need tens of thousands of states
where LALR needs a few hundred — the difference between a table you can ship and one you cannot.
Purely table size, and it is not close. In the 1970s, when yacc was written, a canonical-LR(1) table for
a language like C could easily need ten to twenty times the states of the LALR table — thousands
versus hundreds — and memory was measured in kilobytes. LALR delivers almost all of LR(1)'s expressive
power for the cost of SLR, so it was an easy call, and it stuck: bison, byacc, and the ML/OCaml yacc
derivatives are all LALR by default. The grammars that are LR(1) but not LALR are rare and
usually a symptom of an awkwardly written grammar that is easily massaged. In the handful of cases where
it truly matters, modern bison offers an explicit %glr-parser or an IELR(1) mode that
recovers full LR(1) power — but the everyday default remains LALR precisely because its tables are
small.
Merging is not free. When you union the lookahead sets of two same-core states, two reduce items that had
disjoint lookaheads in their separate states can suddenly overlap, producing a
reduce-reduce conflict that neither original state had. A grammar can therefore be
canonical-LR(1) yet fail to be LALR(1) — this is the one place where the merge loses power.
The reassuring half of the theorem: LALR merging can never introduce a shift-reduce
conflict. Here is the argument. Whether a state shifts on token a
depends only on its core (is there an item with the dot before a?),
and merged states share a core by definition — so the shift actions are identical before and after the
merge. A shift-reduce conflict needs a shift on a to collide with a reduce on
a; if the merged state had that collision, then one of the pre-merge states —
having the same shift on a and already containing that reduce item with
a in its lookahead — would already have had the conflict, contradicting
that it was LR(1). So only reduce-reduce conflicts can be born from a merge. In practice these
are rare, and bison flags them loudly.