LR(0) Items and the Canonical Automaton
Shift-reduce parsing
left us with one hard question: at each step, is the top of the stack a complete handle ready to
reduce, or merely a prefix of one that still needs more symbols shifted? Answering that
deterministically — no guessing, no backtracking — is the whole game. Knuth's insight was that a
finite automaton, run over the parse stack, can track "how far into some production body
we currently are" and thus recognise exactly when a handle is complete. Building that automaton starts
with a tiny, elegant object: the LR(0) item.
An LR(0) item is a production with a dot marking how much of the right-hand side we have
already seen on the stack. The production A \to XYZ yields four items:
A \to {\cdot}\,XYZ, \qquad A \to X\,{\cdot}\,YZ, \qquad A \to XY\,{\cdot}\,Z, \qquad A \to XYZ\,{\cdot}
Read the dot as a cursor. A \to {\cdot}XYZ means "I hope to build an
A here and have seen none of it yet"; A \to XY{\cdot}Z
means "I've seen XY, I still need a Z"; and the
complete item A \to XYZ{\cdot} means "the entire body is on
the stack — this is a handle, reduce now". A production of length n gives
n+1 items (the empty production A\to\varepsilon
gives just A\to{\cdot}).
Augment the grammar first
Before anything else, add a fresh start symbol. If S is the old start, invent
S' and the production S' \to S. This
augmented grammar gives the parser a single, unambiguous way to say "I'm done": a
reduction by S' \to S is the accept action, and nothing is ever
reduced past the real start symbol by accident. It costs one extra production and buys a clean
acceptance condition.
Two operations: CLOSURE and GOTO
States of the automaton are sets of items, and two operations generate them all.
-
\text{CLOSURE}(I) — start with the items in
I, and whenever an item has its dot immediately before a
nonterminal B (i.e. A \to \alpha{\cdot}B\beta),
add every item B \to {\cdot}\gamma for each production of
B. Repeat until nothing new appears. Intuition: "if I'm expecting a
B next, then I'm equally ready to start any way of building a
B."
-
\text{GOTO}(I, X) — for every item
A \to \alpha{\cdot}X\beta in I (dot before the
grammar symbol X), advance the dot past X to get
A \to \alpha X{\cdot}\beta; then take the CLOSURE of all such moved items.
This is the transition of the automaton on symbol X.
The canonical collection of LR(0) item sets is then just: start from
\text{CLOSURE}(\{S' \to {\cdot}S\}) and keep applying GOTO on every grammar
symbol until no new item set is produced. Those item sets are the automaton's states; the GOTO edges are
its transitions. This is a worklist/BFS exactly like the
subset construction
for NFA→DFA — and for the same reason it must terminate: there are only finitely many subsets of the
(finite) set of items.
The automaton for a tiny grammar
Take the augmented grammar
S' \to S, \qquad S \to A\,A, \qquad A \to a\,A \;\mid\; b.
(It generates strings of the form a^{*}b\,a^{*}b — two "runs of
as ending in b".) Running CLOSURE and GOTO to
exhaustion produces seven item sets, I_0 through
I_6. Reveal the automaton one state at a time:
Each state is the full set of items listed below. States with a complete item (dot at the far
right) are where reductions happen: I_4
(A \to b{\cdot}), I_5
(S \to AA{\cdot}), I_6
(A \to aA{\cdot}), and I_1
(S' \to S{\cdot}, the accept state).
| State | Items | GOTO / shift edges |
|---|
| I_0 | S'\!\to{\cdot}S,\; S\to{\cdot}AA,\; A\to{\cdot}aA,\; A\to{\cdot}b | S→I₁, A→I₂, a→I₃, b→I₄ |
| I_1 | S'\!\to S{\cdot} — accept | — |
| I_2 | S\to A{\cdot}A,\; A\to{\cdot}aA,\; A\to{\cdot}b | A→I₅, a→I₃, b→I₄ |
| I_3 | A\to a{\cdot}A,\; A\to{\cdot}aA,\; A\to{\cdot}b | A→I₆, a→I₃, b→I₄ |
| I_4 | A\to b{\cdot} — reduce A\to b | — |
| I_5 | S\to AA{\cdot} — reduce S\to AA | — |
| I_6 | A\to aA{\cdot} — reduce A\to aA | — |
Computing it yourself
CLOSURE and GOTO are short set operations, and the canonical collection is a BFS over them. Here is the
whole construction for the grammar above — it prints the seven item sets and every transition, matching
the table exactly.
type Prod = { lhs: string; rhs: string[] };
// 0: S'->S 1: S->A A 2: A->a A 3: A->b
const G: Prod[] = [
{ lhs: "S'", rhs: ["S"] },
{ lhs: "S", rhs: ["A", "A"] },
{ lhs: "A", rhs: ["a", "A"] },
{ lhs: "A", rhs: ["b"] },
];
const NONTERM = new Set(["S'", "S", "A"]);
const SYMBOLS = ["S", "A", "a", "b"];
type Item = { p: number; dot: number };
const itemKey = (it: Item) => `${it.p}:${it.dot}`;
const setKey = (its: Item[]) => its.map(itemKey).sort().join("|");
function closure(seed: Item[]): Item[] {
const out = [...seed];
const seen = new Set(out.map(itemKey));
for (let i = 0; i < out.length; i++) { // worklist grows in place
const { p, dot } = out[i];
const sym = G[p].rhs[dot];
if (sym !== undefined && NONTERM.has(sym)) {
G.forEach((prod, q) => {
if (prod.lhs === sym) {
const ni = { p: q, dot: 0 };
if (!seen.has(itemKey(ni))) { seen.add(itemKey(ni)); out.push(ni); }
}
});
}
}
return out;
}
function goto(items: Item[], X: string): Item[] {
const moved: Item[] = [];
for (const it of items) if (G[it.p].rhs[it.dot] === X) moved.push({ p: it.p, dot: it.dot + 1 });
return moved.length ? closure(moved) : [];
}
// Canonical collection of LR(0) item sets.
const start = closure([{ p: 0, dot: 0 }]);
const states: Item[][] = [start];
const index = new Map<string, number>([[setKey(start), 0]]);
const edges: [number, string, number][] = [];
for (let i = 0; i < states.length; i++) {
for (const X of SYMBOLS) {
const g = goto(states[i], X);
if (g.length === 0) continue;
const k = setKey(g);
let j = index.get(k);
if (j === undefined) { j = states.length; index.set(k, j); states.push(g); }
edges.push([i, X, j]);
}
}
const show = (it: Item) => {
const body = [...G[it.p].rhs];
body.splice(it.dot, 0, ".");
return `${G[it.p].lhs} -> ${body.join(" ")}`;
};
states.forEach((s, i) => console.log(`I${i}: { ${s.map(show).join(", ")} }`));
console.log("--- transitions ---");
for (const [i, X, j] of edges) console.log(`I${i} --${X}--> I${j}`);
Notice I_3 has a self-loop on a: from
A \to a{\cdot}A the closure re-introduces A\to{\cdot}aA,
so another a keeps you in the same state. That single loop is the automaton's
way of counting an arbitrarily long run of as with a finite number of states —
precisely why a regular device can police a stack.
What the automaton actually recognises
The states are not "the state of the parse" and they are not stack contents. They answer a subtler
question about the string of grammar symbols currently on the stack.
- Feed the automaton the sequence of grammar symbols on the parse stack, starting from
I_0. The state you end in is
\text{GOTO}(I_0, \text{stack}), and it is defined for exactly those stack
contents that are viable prefixes — prefixes of some right-sentential form that do
not extend past the right end of a handle.
- A state that contains a complete item
A \to \beta{\cdot} announces that \beta is a
handle on top of the stack: a reduction by A \to \beta is legal here.
- The set of viable prefixes of any context-free grammar is a regular language — a
surprising and load-bearing fact, since it is what lets a finite automaton do the handle-spotting.
This is the payoff. The stack can grow without bound, but "everything about the stack that could matter
for the next parsing decision" is captured by a single automaton state. The parser never re-scans the
stack; it just remembers the state it is in, which is why LR parsing runs in linear time.
It feels like cheating: parsing is more powerful than regular-language recognition, yet here is a mere
DFA at the heart of it. The resolution is that the automaton does not recognise the language of
the grammar. It recognises the viable prefixes — the legal stack contents — and
that set really is regular, even when the language itself is not. The context-free power comes
from the second ingredient: when the automaton reports a complete item, the parser pops the handle and
consults GOTO to jump to the state for the shortened stack. The stack supplies the unbounded memory; the
automaton supplies the finite, instant decision. Neither alone is enough; together they are exactly a
deterministic pushdown automaton.
The commonest conceptual error is to picture each state as "the parser is at
A \to a{\cdot}A". A state is the whole set the closure produced —
I_3 = \{\,A \to a{\cdot}A,\; A \to {\cdot}aA,\; A \to {\cdot}b\,\} — and it
must be, because the parser genuinely does not yet know which production it is in the middle of.
The kernel item A \to a{\cdot}A says "I've committed to
A \to aA and consumed the a", while the closure
items A \to {\cdot}aA and A \to {\cdot}b say "…and
the next A could itself start with either an a or a
b." All of those possibilities are live at once. Collapse the set to one item
and you have thrown away the very superposition that makes the parser deterministic without backtracking —
the same lesson as
subset construction,
where a DFA state is a set of NFA states, never a single one.