Lesson 3.1 — Shift-reduce parsing, handles and the LR(0) automaton

Techniques: shift-reduce parsing with handles and viable prefixes; LR(0) items, CLOSURE/GOTO and the canonical LR(0) automaton (the characteristic finite-state machine) · Pebble implements: nothing in pebblec (its parser is recursive descent, Ch 2); the lab builds the automaton and the driver (exercises E1 and E5) · Lab: labs/ch03-lr-toolkit (SPEC, contract buildAutomaton(G, Method::LR0), parseLR; lr report --method lr0, lr parse --trace) · Prerequisites: Ch 2, Lessons 2.1–2.2 (derivations, FIRST/FOLLOW) · Time: 4 hours

A top-down parser must decide which production to use before it has seen the phrase that production derives. A bottom-up parser waits: it shifts tokens onto a stack until the top of the stack is exactly the right side of a production that belongs in the parse tree, and then reduces it to the left side. Everything in this chapter is about one question: when is the top of the stack such a phrase? This lesson answers it for the simplest case. The phrases are called handles, the stack contents that can precede a handle are the viable prefixes, and the central theorem (Knuth, 1965) is that viable prefixes form a regular language, recognized by a finite automaton built from LR(0) items.

1. Problem and motivation

Input: a context-free grammar \(G\) and a token sequence \(w\). Output: accept or reject, and for a sentence its rightmost derivation in reverse (equivalently, its parse tree built bottom-up, children before parents). A bottom-up parser is a pushdown automaton whose moves are shift a token and reduce a right side to its left side. It builds the same tree as the top-down parser of Lesson 2.5, in postorder instead of preorder.

Shift-reduce parsing

Bottom-up parsing is older than LR: precedence parsers for arithmetic expressions reduced operator phrases in the 1950s, and Floyd formalized the operator-precedence relations in 1963 [Flo63] (Lesson 3.5). The difficulty every shift-reduce parser has is the choice between shifting and reducing, and between two reductions; a wrong reduction produces a stack from which no sentence can be completed. Knuth's paper on LR(k) parsing [Knu65] (and Aho and Johnson's tutorial [AJ74] for a gentler route) turned the question into the definitions of handle and viable prefix that every bottom-up method since has used, and showed that for a large class of grammars the choice is decided by the stack contents (through a finite automaton) plus \(k\) tokens of lookahead. pebblec does not use a shift-reduce parser, but its expression grammar is exactly the kind LR generators handle with no transformation at all: \(E \to E + T\) is left-recursive and still deterministic bottom-up.

LR(0) items and the canonical LR(0) automaton

Knuth's construction builds states from sets of items with lookahead strings; DeRemer's 1969 thesis [DeR69] and 1971 paper [DeR71] separated the lookahead-free core, the LR(0) automaton (DeRemer's characteristic finite-state machine, CFSM), from the lookahead computation. Every practical LR generator (yacc, Bison, Menhir, tree-sitter, lemon) builds this automaton first; SLR(1), LALR(1) and the minimal LR(1) methods of Lessons 3.2–3.4 only differ in how they decide reductions in its states.

2. Definitions and algorithms

The grammar is \(G = (N, T, P, S)\) as in Ch 2, Definition 2.1.1. We augment it with a fresh start symbol \(S'\) and the production \((0)\ S' \to S\), so that acceptance is a reduction by production 0; productions \(1, \dots, \lvert P \rvert\) keep their numbers. \(\Rightarrow_{\mathrm{rm}}\) is a rightmost derivation step (Definition 2.1.2).

Definition 3.1.1 (Right-sentential form)

A right-sentential form of \(G\) is a string \(\gamma \in (N \cup T)^{*}\) with \(S' \Rightarrow_{\mathrm{rm}}^{*} \gamma\). Every sentence \(w \in L(G)\) is a right-sentential form, and so is every string on a rightmost derivation of \(w\).

Definition 3.1.2 (Handle)

Let \(\gamma\) be a right-sentential form. A handle of \(\gamma\) is a pair \((A \to \beta, k)\) such that \(\gamma = \alpha \beta w\) with \(\lvert \alpha \beta \rvert = k\), \(w \in T^{*}\), and \(S' \Rightarrow_{\mathrm{rm}}^{*} \alpha A w \Rightarrow_{\mathrm{rm}} \alpha \beta w\). Informally: the occurrence of \(\beta\) ending at position \(k\) that the last step of some rightmost derivation of \(\gamma\) produced. Reducing the handle replaces that \(\beta\) by \(A\).

Handles in the running example

The running example of this chapter (tests/ch03/Inputs/assign.grammar, [ALSU07, Ex. 4.48]) is

\[ (0)\ S' \to S \quad (1)\ S \to L = R \quad (2)\ S \to R \quad (3)\ L \to *\, R \quad (4)\ L \to \mathit{id} \quad (5)\ R \to L \]

The rightmost derivation \(S' \Rightarrow S \Rightarrow L = R \Rightarrow L = L \Rightarrow L = \mathit{id} \Rightarrow * R = \mathit{id} \Rightarrow * L = \mathit{id} \Rightarrow * \mathit{id} = \mathit{id}\) shows that the handle of \(*\,\mathit{id} = \mathit{id}\) is \((L \to \mathit{id}, 2)\), the first \(\mathit{id}\): the last step produced it. The second \(\mathit{id}\) is not a handle of this form, although \(L \to \mathit{id}\) matches it.

Definition 3.1.3 (Shift-reduce parser)

A configuration is a pair \((\gamma, x)\) of a stack \(\gamma \in (N \cup T)^{*}\) (top on the right) and the remaining input \(x \in T^{*}\). The moves are shift \((\gamma, a x) \vdash (\gamma a, x)\) and reduce by \(A \to \beta\): \((\alpha \beta, x) \vdash (\alpha A, x)\). The run starts in \((\varepsilon, w)\) and accepts in \((S, \varepsilon)\). A shift-reduce parser is correct if in every run on a sentence it reduces only handles: whenever it reduces by \(A \to \beta\) in \((\alpha \beta, x)\), \((A \to \beta, \lvert \alpha \beta \rvert)\) is a handle of \(\alpha \beta x\).

Definition 3.1.4 (Viable prefix)

A string \(\gamma \in (N \cup T)^{*}\) is a viable prefix of \(G\) if it is a prefix of \(\alpha \beta\) for some right-sentential form \(\alpha \beta w\) with handle \((A \to \beta, \lvert \alpha \beta \rvert)\). Equivalently: a prefix of a right-sentential form that does not extend past the right end of its handle.

Shift-reduce parsing

Algorithm 3.1.5 (Shift-reduce parsing with a handle oracle)

• Input: \(G\) (augmented), \(w \in T^{*}\), and an oracle \(H(\gamma, a)\) that, given the stack and the next token \(a\) (or \(\$\)), answers shift, reduce by \(A \to \beta\) (with \(\beta\) a suffix of \(\gamma\)), accept or error.
• Output: accept with the productions reduced, in order, or error.
• Precondition: \(H\) answers reduce by \(A \to \beta\) exactly when \(\beta\) is the handle of \(\gamma\, a \cdots\) for every continuation of the input that is a sentence; accept only in \((S, \varepsilon)\).
• Postcondition: on acceptance the output, read backwards, is the rightmost derivation of \(w\) (Theorem 3.1.13).
• Invariant: the stack is a viable prefix, and stack \(\cdot\) remaining input is a right-sentential form whenever \(w \in L(G)\) (Lemma 3.1.12).

function ShiftReduce(G, w, H):
    stack ← ε;  x ← w $;  output ← []
    loop:
        a ← first token of x
        case H(stack, a) of
            shift:            stack ← stack · a;  x ← x without a
            reduce A → β:     stack ← (stack without its suffix β) · A;  append A → β to output
            accept:           return (accept, output)
            error:            return error

Everything that follows builds \(H\) from a finite automaton and a small table.

LR(0) items and the canonical LR(0) automaton

Definition 3.1.6 (LR(0) item, validity)

An LR(0) item is a production with a dot in its right side, \([A \to \alpha \bullet \beta]\) for \(A \to \alpha \beta \in P\) (the lab writes it (p, d): production \(p\), dot before position \(d\)). It is completed if \(\beta = \varepsilon\) and a kernel item if \(\alpha \neq \varepsilon\) or it is \([S' \to \bullet S]\). The item \([A \to \alpha \bullet \beta]\) is valid for a string \(\gamma\) if there is a rightmost derivation \(S' \Rightarrow_{\mathrm{rm}}^{*} \delta A w \Rightarrow_{\mathrm{rm}} \delta \alpha \beta w\) with \(\gamma = \delta \alpha\). \(V(\gamma)\) is the set of items valid for \(\gamma\).

Definition 3.1.7 (CLOSURE and GOTO)

For a set \(I\) of items, \(\mathrm{CLOSURE}(I)\) is the least set \(J \supseteq I\) such that \([A \to \alpha \bullet B \beta] \in J\) and \(B \to \eta \in P\) imply \([B \to \bullet \eta] \in J\). For a symbol \(X\), \(\mathrm{GOTO}(I, X) \triangleq \mathrm{CLOSURE}(\{\, [A \to \alpha X \bullet \beta] \mid [A \to \alpha \bullet X \beta] \in I \,\})\); the set in braces is its kernel.

Definition 3.1.8 (Canonical LR(0) automaton)

The canonical LR(0) automaton (characteristic finite-state machine) of \(G\) is the deterministic finite automaton \(\mathcal{A}_0 = (Q, N \cup T, \delta, q_0)\) with \(q_0 = \mathrm{CLOSURE}(\{[S' \to \bullet S]\})\), \(Q\) the sets reachable from \(q_0\) by \(\mathrm{GOTO}\) with a non-empty kernel, and \(\delta(I, X) = \mathrm{GOTO}(I, X)\) when that kernel is non-empty (undefined otherwise). Every state is accepting; \(\delta^{*}\) extends \(\delta\) to strings.

Algorithm 3.1.9 (CLOSURE, worklist form)

• Input: a set of items \(I\) (a list, kernel first).
• Output: \(\mathrm{CLOSURE}(I)\) as a list: \(I\), then the added items in the order they were added.
• Precondition: none.
• Postcondition: the result is the least set of Definition 3.1.7.
• Invariant: every item in out is in \(\mathrm{CLOSURE}(I)\); every item before position i has had its nonterminal after the dot expanded.

Reference solution: solutions/labs/ch03-lr-toolkit/src/Automata.cpp (closure0); oracle tools/course/lib/lr.py (closure0).

function Closure(I):
    out ← list(I);  seen ← set(I);  i ← 0
    while i < |out|:
        [A → α • X β] ← out[i]
        if X is a nonterminal:
            for each production X → η, in grammar order:
                if [X → • η] ∉ seen:  append [X → • η] to out; add it to seen
        i ← i + 1
    return out

Algorithm 3.1.10 (The canonical LR(0) collection)

• Input: the augmented grammar \(G\).
• Output: the states \(Q = [I_0, I_1, \dots]\) numbered in discovery order, and \(\delta\).
• Precondition: none (any grammar, ambiguous or not).
• Postcondition: \(Q\) and \(\delta\) are the automaton of Definition 3.1.8; numbering is breadth first, and each state's successors are created in symbol order (terminals in order of first appearance in \(G\), then nonterminals in grammar order) — the course's canonical numbering, which Bison also uses when tokens are declared in that order.
• Invariant: every state in states is \(\delta^{*}(q_0, \gamma)\) for some \(\gamma\); index maps each kernel to its state.

function LR0Collection(G):
    states ← [Closure({[S' → • S]})];  index ← {kernel of states[0] ↦ 0};  q ← 0
    while q < |states|:
        for each symbol X in symbol order:
            K ← { [A → α X • β] : [A → α • X β] ∈ states[q] }        # the GOTO kernel
            if K = ∅: continue
            if K ∉ index: index[K] ← |states|;  append Closure(K) to states
            δ(q, X) ← index[K]
        q ← q + 1
    return (states, δ)

Definition 3.1.11 (LR(0) table and LR(0) grammars)

The LR(0) table of \(G\) has, for each state \(I\): ACTION\([I, a] \ni\) shift \(\delta(I, a)\) for every terminal \(a\) with \(\delta(I, a)\) defined; ACTION\([I, a] \ni\) reduce \(A \to \beta\) for every completed item \([A \to \beta \bullet] \in I\) with \(A \neq S'\) and every \(a \in T \cup \{\$\}\); ACTION\([I, \$] \ni\) accept if \([S' \to S \bullet] \in I\); and GOTO\([I, A] = \delta(I, A)\). A cell with two or more actions is a conflict; \(G\) is LR(0) if its table has none. (Lesson 3.2 replaces "every \(a\)" by FOLLOW sets and lookaheads; the automaton stays the same.)

3. Worked example

Running example (tests/ch03/Inputs/assign.grammar, 5 productions plus (0)): assignments whose left side can be a dereference. It is small, has a right-recursive and a left-context-dependent part, and will separate LR(0), SLR(1) and LALR(1) in Lessons 3.2–3.3.

flowchart LR
  I0((I0)) -->|*| I1((I1))
  I0 -->|id| I2((I2))
  I0 -->|S| I3((I3))
  I0 -->|L| I4((I4))
  I0 -->|R| I5((I5))
  I1 -->|*| I1
  I1 -->|id| I2
  I1 -->|L| I6((I6))
  I1 -->|R| I7((I7))
  I4 -->|=| I8((I8))
  I8 -->|*| I1
  I8 -->|id| I2
  I8 -->|L| I6
  I8 -->|R| I9((I9))

Shift-reduce parsing on the running example

For \(w = *\,\mathit{id} = \mathit{id}\) the handles, found from the rightmost derivation of §2's example read backwards, give this run (the states in the stack column are those of the LR(0) automaton below; the reductions are the handle reductions, and Theorem 3.1.19 shows that the automaton-driven parser finds exactly them):

step	stack	input	action	handle reduced
1	0	* id = id $	shift 1
2	0 * 1	id = id $	shift 2
3	0 * 1 id 2	= id $	reduce (4) L → id	\((L \to \mathit{id}, 2)\) of \(*\,\mathit{id} = \mathit{id}\)
4	0 * 1 L 6	= id $	reduce (5) R → L	\((R \to L, 2)\) of \(*\,L = \mathit{id}\)
5	0 * 1 R 7	= id $	reduce (3) L → * R	\((L \to *\,R, 2)\) of \(*\,R = \mathit{id}\)
6	0 L 4	= id $	shift 8	\(R \to L\) is not a handle here
7	0 L 4 = 8	id $	shift 2
8	0 L 4 = 8 id 2	$	reduce (4) L → id	\((L \to \mathit{id}, 3)\) of \(L = \mathit{id}\)
9	0 L 4 = 8 L 6	$	reduce (5) R → L	\((R \to L, 3)\) of \(L = L\)
10	0 L 4 = 8 R 9	$	reduce (1) S → L = R	\((S \to L = R, 3)\) of \(L = R\)
11	0 S 3	$	accept

The reductions \(4, 5, 3, 4, 5, 1\) read backwards are the rightmost derivation \(1, 5, 4, 3, 5, 4\) of the example after Definition 3.1.2. Step 6 is the interesting one: the stack \(L\) ends with the right side of \(R \to L\), but reducing would give \(R\) followed by \(=\), and no right-sentential form contains \(R =\). An LR(0) parser cannot see this (state 4 has both a completed item and a shift); Lesson 3.2 fixes it with one token of lookahead.

LR(0) items and the canonical LR(0) automaton on the running example

CLOSURE of \(\{[S' \to \bullet S]\}\) (Algorithm 3.1.9, oracle closure0):

step	scanning item	adds
1	\(S' \to \bullet S\)	\(S \to \bullet L = R\)
2	\(S' \to \bullet S\)	\(S \to \bullet R\)
3	\(S \to \bullet L = R\)	\(L \to \bullet *\,R\)
4	\(S \to \bullet L = R\)	\(L \to \bullet \mathit{id}\)
5	\(S \to \bullet R\)	\(R \to \bullet L\)
–	\(L \to \bullet *\,R\), \(L \to \bullet \mathit{id}\)	nothing (terminal after the dot)
–	\(R \to \bullet L\)	nothing new (\(L\)'s items are present)

The collection (Algorithm 3.1.10; symbol order \(=\), \(*\), \(\mathit{id}\), \(S\), \(L\), \(R\)). One row per GOTO computed:

#	from	on	kernel	to	new?
1	I0	*	\(L \to * \bullet R\)	I1	new
2	I0	id	\(L \to \mathit{id} \bullet\)	I2	new
3	I0	S	\(S' \to S \bullet\)	I3	new
4	I0	L	\(S \to L \bullet = R\); \(R \to L \bullet\)	I4	new
5	I0	R	\(S \to R \bullet\)	I5	new
6	I1	*	\(L \to * \bullet R\)	I1	seen
7	I1	id	\(L \to \mathit{id} \bullet\)	I2	seen
8	I1	L	\(R \to L \bullet\)	I6	new
9	I1	R	\(L \to * R \bullet\)	I7	new
10	I4	=	\(S \to L = \bullet R\)	I8	new
11	I8	*	\(L \to * \bullet R\)	I1	seen
12	I8	id	\(L \to \mathit{id} \bullet\)	I2	seen
13	I8	L	\(R \to L \bullet\)	I6	seen
14	I8	R	\(S \to L = R \bullet\)	I9	new
–	I2, I3, I5, I6, I7, I9	–	(only completed items: no GOTO)	–	–

The ten states (kernel items first, + closure items), exactly as lr report --method lr0 prints them:

state	items	transitions
I0	\(S' \to \bullet S\); + \(S \to \bullet L = R\), \(S \to \bullet R\), \(L \to \bullet * R\), \(L \to \bullet \mathit{id}\), \(R \to \bullet L\)	*→1, id→2, S→3, L→4, R→5
I1	\(L \to * \bullet R\); + \(L \to \bullet * R\), \(L \to \bullet \mathit{id}\), \(R \to \bullet L\)	*→1, id→2, L→6, R→7
I2	\(L \to \mathit{id} \bullet\)
I3	\(S' \to S \bullet\)
I4	\(S \to L \bullet = R\), \(R \to L \bullet\)	=→8
I5	\(S \to R \bullet\)
I6	\(R \to L \bullet\)
I7	\(L \to * R \bullet\)
I8	\(S \to L = \bullet R\); + \(L \to \bullet * R\), \(L \to \bullet \mathit{id}\), \(R \to \bullet L\)	*→1, id→2, L→6, R→9
I9	\(S \to L = R \bullet\)

The LR(0) table has one conflict, ACTION\([4, =] = \{\)s8, r5\(\}\) (shift/reduce): the grammar is not LR(0). Every other state is adequate (a single completed item and nothing else, or no completed item).

Try it

./course drill lr0-closure --seed 4 --difficulty medium --solution closes a later state and computes its GOTO kernels; build/linux/bin/lr report tests/ch03/Inputs/assign.grammar --method lr0 prints the whole collection and table.

4. Invariants and correctness

Shift-reduce parsing

Lemma 3.1.12 (Handles are unique in unambiguous grammars; stacks are viable prefixes)

(a) If \(G\) is reduced and unambiguous, every right-sentential form other than \(S'\) has exactly one handle. (b) In every accepting run of a correct shift-reduce parser, every stack is a viable prefix, and stack \(\cdot\) remaining input is a right-sentential form.

Proof

(a) A right-sentential form \(\gamma \neq S'\) has a handle: take any rightmost derivation of \(\gamma\) and its last step. If \(\gamma\) had two handles, the two last steps would extend to two rightmost derivations \(S' \Rightarrow_{\mathrm{rm}}^{*} \gamma\) that differ; completing both with the same rightmost derivation \(\gamma \Rightarrow_{\mathrm{rm}}^{*} w\) of a sentence (every symbol of a reduced grammar derives a terminal string) gives two different rightmost derivations of \(w\), hence (Lemma 2.1.10) two parse trees, contradicting unambiguity.

(b) Consider an accepting run on a sentence \(w\) and any configuration \((\gamma, x)\) in it. Stack \(\cdot\) input is a right-sentential form: initially it is \(w\); a shift does not change it; a reduction of a handle \((A \to \beta, \lvert \alpha\beta \rvert)\) turns \(\alpha \beta x\) into \(\alpha A x\), which by Definition 3.1.2 is the previous form of a rightmost derivation. If the run reduces again later, let \((\alpha\beta, x')\) be the configuration of the next reduction; only shifts happen in between, so \(\gamma\) is a prefix of \(\alpha\beta\), and \(\alpha\beta x'\) has the handle \((A \to \beta, \lvert\alpha\beta\rvert)\) because the parser is correct: \(\gamma\) is a viable prefix. If no reduction follows, the next move is accept, so \(\gamma = S\), which is viable (the handle of the form \(S\) is \((S' \to S, 1)\) in the augmented grammar).

Theorem 3.1.13 (Shift-reduce parsing reverses the rightmost derivation)

If a correct shift-reduce parser accepts \(w\) with reductions \(p_1, \dots, p_m\), then \(p_m, \dots, p_1\) applied to \(S\) (always to the rightmost nonterminal) is the rightmost derivation \(S \Rightarrow_{\mathrm{rm}}^{*} w\). Conversely, every rightmost derivation of \(w\) is found this way when the oracle \(H\) of Algorithm 3.1.5 returns its handles.

Proof

Let \(\gamma_j\) be stack \(\cdot\) input just before the \(j\)-th reduction (\(\gamma_1 = w\)). Between reductions only shifts happen, which do not change stack \(\cdot\) input, so the \(j\)-th reduction maps \(\gamma_j\) to \(\gamma_{j+1}\) by replacing the handle \(\beta\) of production \(p_j = A \to \beta\) with \(A\). By Definition 3.1.2 this is exactly one rightmost step backwards: \(\gamma_{j+1} \Rightarrow_{\mathrm{rm}} \gamma_j\), where \(A\) is the rightmost nonterminal of \(\gamma_{j+1}\) (everything after the handle is terminal). Accepting means \(\gamma_{m+1} = S\), so \(S = \gamma_{m+1} \Rightarrow_{\mathrm{rm}} \gamma_m \Rightarrow_{\mathrm{rm}} \cdots \Rightarrow_{\mathrm{rm}} \gamma_1 = w\) uses \(p_m, \dots, p_1\). Conversely, given a rightmost derivation, reduce at each step the handle its last step created; shifting until the handle's right end is on the stack is always possible because the handle lies entirely left of the unread input.

LR(0) items and the canonical LR(0) automaton

Lemma 3.1.14 (A valid item for every viable prefix)

Let \(\alpha\beta w\) be a right-sentential form with handle \((A \to \beta, \lvert\alpha\beta\rvert)\) and let \(\gamma\) be a prefix of \(\alpha\beta\). Then \(V(\gamma) \neq \emptyset\); moreover, if \(\gamma X\) is also a prefix of \(\alpha\beta\), some item \([C \to \mu \bullet X \nu] \in V(\gamma)\) has \(X\) after its dot.

Proof

Fix a rightmost derivation \(\gamma_0 = S' \Rightarrow_{\mathrm{rm}} \gamma_1 \Rightarrow_{\mathrm{rm}} \cdots \Rightarrow_{\mathrm{rm}} \gamma_{m+1} = \alpha\beta w\) whose last step creates the handle. Write step \(i\) as \(\gamma_i = \alpha_i A_i w_i \Rightarrow_{\mathrm{rm}} \alpha_i \beta_i w_i\) with \(w_i \in T^{*}\) (so \(\alpha_m = \alpha\), \(\beta_m = \beta\), \(\alpha_0 = \varepsilon\)). Because \(w_i\) is terminal, the next rewritten nonterminal \(A_{i+1}\) lies in \(\alpha_i\beta_i\), so \(\alpha_{i+1}\) is a prefix of \(\alpha_i \beta_i\). Let \(i^{*}\) be the largest \(i\) with \(\lvert \alpha_i \rvert \le \lvert \gamma \rvert\) (it exists: \(\alpha_0 = \varepsilon\)). For every \(j > i^{*}\), \(\lvert\alpha_j\rvert > \lvert\gamma\rvert\) and \(\alpha_j\) is a prefix of \(\alpha_{j-1}\beta_{j-1}\), so the first \(\lvert\gamma\rvert + 1\) symbols (as many as exist) of \(\alpha_j\beta_j\) and of \(\alpha_{j-1}\beta_{j-1}\) agree; by induction they agree with those of \(\alpha_{i^{*}}\beta_{i^{*}}\). Hence \(\gamma\) (and \(\gamma X\), when it is a prefix of \(\alpha\beta = \alpha_m\beta_m\)) is a prefix of \(\alpha_{i^{*}}\beta_{i^{*}}\) with \(\lvert\alpha_{i^{*}}\rvert \le \lvert\gamma\rvert\). Split \(\beta_{i^{*}} = \beta'\beta''\) with \(\alpha_{i^{*}}\beta' = \gamma\): step \(i^{*}\) shows that \([A_{i^{*}} \to \beta' \bullet \beta''] \in V(\gamma)\), and \(\beta''\) starts with \(X\) when \(\gamma X\) is a prefix.

Lemma 3.1.15 (CLOSURE and GOTO compute valid items)

For every \(\gamma\) and symbol \(X\): (a) \(V(\gamma) = \mathrm{CLOSURE}(K)\) where \(K\) is the set of kernel items of \(V(\gamma)\); (b) \(V(\gamma X) = \mathrm{GOTO}(V(\gamma), X)\); (c) \(V(\varepsilon) = \mathrm{CLOSURE}(\{[S' \to \bullet S]\})\).

Proof

(\(V(\gamma)\) is closed.) If \([A \to \alpha \bullet B \beta] \in V(\gamma)\), there is \(S' \Rightarrow_{\mathrm{rm}}^{*} \delta A w \Rightarrow_{\mathrm{rm}} \delta \alpha B \beta w\) with \(\gamma = \delta \alpha\). \(G\) is reduced, so \(\beta \Rightarrow_{\mathrm{rm}}^{*} y\) for some \(y \in T^{*}\); continuing rightmost, \(\delta \alpha B \beta w \Rightarrow_{\mathrm{rm}}^{*} \delta\alpha B y w \Rightarrow_{\mathrm{rm}} \delta \alpha \eta y w\) for any \(B \to \eta\), so \([B \to \bullet \eta] \in V(\gamma)\). Hence \(\mathrm{CLOSURE}(K) \subseteq V(\gamma)\).

(Every non-kernel valid item is in \(\mathrm{CLOSURE}(K)\).) Let \([B \to \bullet \eta] \in V(\gamma)\) via \(S' \Rightarrow_{\mathrm{rm}}^{*} \gamma B w \Rightarrow_{\mathrm{rm}} \gamma \eta w\). \(B\) is the rightmost nonterminal of \(\gamma B w\). Let \(\zeta C u \Rightarrow_{\mathrm{rm}} \zeta \mu B \nu u\) be the step that introduced this occurrence of \(B\) (\(u \in T^{*}\)). Afterwards the derivation only rewrites nonterminals right of \(B\) (it is rightmost and ends with \(B\) rightmost), so \(\zeta\mu = \gamma\) and \(\nu\) derives a terminal string: \([C \to \mu \bullet B \nu] \in V(\gamma)\), and one closure step from it adds \([B \to \bullet \eta]\). If \(\mu \neq \varepsilon\) (or \(C = S'\)) that item is a kernel item; otherwise it is \([C \to \bullet B \nu]\), valid for \(\zeta = \gamma\), and we repeat the argument for this occurrence of \(C\), which was introduced at an earlier step. The derivation is finite, so the chain ends at a kernel item, and \([B \to \bullet\eta]\) is reached from it by closure steps. This proves (a); (c) is (a) for \(\gamma = \varepsilon\), whose only kernel item is \([S' \to \bullet S]\).

(b) \([A \to \alpha X \bullet \beta] \in V(\gamma X)\) iff some \(S' \Rightarrow_{\mathrm{rm}}^{*} \delta A w \Rightarrow_{\mathrm{rm}} \delta \alpha X \beta w\) has \(\delta\alpha = \gamma\), iff \([A \to \alpha \bullet X \beta] \in V(\gamma)\). So the kernel of \(V(\gamma X)\) is the GOTO kernel of \(V(\gamma)\) on \(X\) (every kernel item of \(V(\gamma X)\) has a symbol before its dot, which must be \(X\)), and by (a) \(V(\gamma X)\) is its closure.

Theorem 3.1.16 (Correctness of the LR(0) automaton [Knu65, DeR71])

For every \(\gamma \in (N \cup T)^{*}\): \(\delta^{*}(q_0, \gamma)\) is defined iff \(\gamma\) is a viable prefix, and then \(\delta^{*}(q_0, \gamma) = V(\gamma)\).

Proof

First, \(\gamma\) is viable iff \(V(\gamma) \neq \emptyset\): Lemma 3.1.14 gives (\(\Rightarrow\)); conversely a valid item \([A \to \alpha \bullet \beta]\) for \(\gamma = \delta\alpha\) exhibits the right-sentential form \(\delta \alpha \beta w\) with handle \((A \to \alpha\beta, \lvert \delta\alpha\beta \rvert)\) of which \(\gamma\) is a prefix.

Now induct on \(\lvert \gamma \rvert\). For \(\gamma = \varepsilon\): \(\delta^{*}(q_0, \varepsilon) = q_0 = V(\varepsilon)\) by Lemma 3.1.15(c), and \(\varepsilon\) is viable. For \(\gamma X\): if \(\gamma\) is not viable, neither is \(\gamma X\) (viable prefixes are closed under prefixes by Definition 3.1.4), and \(\delta^{*}(q_0, \gamma)\) is undefined by induction. Otherwise \(\delta^{*}(q_0, \gamma) = V(\gamma)\) and, by Lemma 3.1.15(b), \(\mathrm{GOTO}(V(\gamma), X) = V(\gamma X)\). The closure of an empty kernel is empty, so the GOTO kernel is non-empty iff \(V(\gamma X) \neq \emptyset\) iff \(\gamma X\) is viable; \(\delta(V(\gamma), X)\) is defined exactly then, and equals \(V(\gamma X)\).

Corollary 3.1.17 (Viable prefixes form a regular language [Knu65])

For every context-free grammar \(G\), the set of viable prefixes of \(G\) is a regular language over \(N \cup T\): it is the language of the finite automaton \(\mathcal{A}_0\) with every state accepting.

Proof

By Theorem 3.1.16, \(\gamma\) is viable iff \(\delta^{*}(q_0, \gamma)\) is defined, i.e. iff \(\mathcal{A}_0\) (all states accepting, missing transitions going to an implicit dead state) accepts \(\gamma\). \(\mathcal{A}_0\) is finite because its states are sets of items and there are \(\lvert G \rvert\) items.

Why regularity matters

\(L(G)\) need not be regular (\(L \to *\,R\) nests arbitrarily deep), yet deciding "can this stack still be completed?" needs only a DFA. In the running example the viable prefixes are exactly the strings spelled by paths from I0 in the diagram of §3, e.g. \(* * L\) (I0 → I1 → I1 → I6) but not \(L = L =\) (I6 has no = transition). The oracle test ViablePrefixes in tools/course/tests/test_ch03_lr.py checks Theorem 3.1.16 on 40 random grammars against Knuth's independent right-linear grammar of viable prefixes [Knu65].

Algorithm 3.1.18 (The LR driver)

• Input: an ACTION/GOTO table (any method of this chapter), \(w\).
• Output: accept with the reductions, or the first syntax error (position, token, expected tokens).
• Precondition: if the table has conflicts, each cell's first action is used (shift before reduce, then the lowest production: yacc's default).
• Postcondition: for a conflict-free table built from \(\mathcal{A}_0\), accepts exactly \(L(G)\) and outputs the reversed rightmost derivation (Theorem 3.1.19).
• Invariant: the stack holds states \(s_0 s_1 \cdots s_m\) and symbols \(X_1 \cdots X_m\) with \(s_0 = q_0\) and \(s_i = \delta^{*}(q_0, X_1 \cdots X_i)\); so \(X_1 \cdots X_m\) is a viable prefix and \(s_m = V(X_1 \cdots X_m)\).

Reference solution: solutions/labs/ch03-lr-toolkit/src/Driver.cpp (contract lr::parseLR).

function LRParse(ACTION, GOTO, w):
    states ← [0];  symbols ← [];  i ← 0;  a ← w[0] (or $)
    loop:
        act ← first action of ACTION[top(states), a]         # empty cell ⇒ error
        if act = none:  return error(i, a, { t : ACTION[top(states), t] ≠ ∅ })
        if act = shift s:  push s on states; push a on symbols; i ← i + 1; a ← w[i] (or $)
        if act = reduce A → β:
            pop |β| entries from states and from symbols
            push A on symbols; push GOTO[top(states), A] on states; output A → β
        if act = accept:  return accept(output)

Theorem 3.1.19 (The LR(0) parser is correct for LR(0) grammars)

If \(G\) is reduced and LR(0), Algorithm 3.1.18 with the LR(0) table accepts exactly \(L(G)\), reduces only handles, and detects every error at the first token that cannot extend the input read so far to a sentence (the correct-prefix property, Definition 2.5.2).

Proof

Invariant. Shifting \(a\) from \(s_m\) pushes \(\delta(s_m, a)\); reducing by \(A \to \beta\) pops \(\lvert \beta \rvert\) states, exposing \(s_{m - \lvert \beta \rvert} = \delta^{*}(q_0, X_1 \cdots X_{m-\lvert\beta\rvert})\), and pushes its GOTO on \(A\), i.e. \(\delta^{*}(q_0, X_1 \cdots X_{m-\lvert\beta\rvert} A)\). So the invariant of Algorithm 3.1.18 holds, and by Theorem 3.1.16 the top state is \(V(s)\) for the stack string \(s\).

Only handles are reduced (on a sentence). Induct on the moves: assume every reduction so far reduced a handle, so stack \(\cdot\) input \(= s\,x\) is a right-sentential form (as in Lemma 3.1.12(b)). Let the parser reduce by \(A \to \beta\) in state \(V(s)\), and let \((B \to \eta, k)\) be a handle of \(s\,x\). If \(k > \lvert s \rvert\), the handle ends inside \(x\); then \(s\,a\) (\(a\) the next token) is a prefix of the form up to the handle's end, and Lemma 3.1.14 puts an item with \(a\) after its dot into \(V(s)\): the LR(0) table has shift on \(a\) next to the reduction on \(a\), a conflict. If \(k < \lvert s \rvert\), consider the last moment the stack had height \(k\): it was the first \(k\) symbols of \(s\), with \([B \to \eta \bullet]\) valid (it is the handle), and the parser shifted next: everything after a handle is terminal, so position \(k + 1\) of \(s\) holds a terminal, whereas a reduction landing above height \(k\) would have left a nonterminal there that no later move (the stack never shrank to \(k\) again) could replace by a terminal. So its state had a completed item and a shift, a conflict. So \(k = \lvert s \rvert\) and \([B \to \eta \bullet] \in V(s)\); the LR(0) cell has exactly one reduction, so \(A \to \beta = B \to \eta\).

Acceptance and completeness. By Theorem 3.1.13 an accepting run spells a rightmost derivation, so the parser accepts only sentences. On a sentence the parser never errs: at every configuration the handle of \(s\,x\) either ends at the top (its completed item is in \(V(s)\) and the cell reduces) or later, and then Lemma 3.1.14 gives a shift on the next token; since the parser reduces only handles, it follows the rightmost derivation to \(S\) and accepts on \(\$\).

Correct prefix. The parser shifts \(a\) only if \(\delta(s_m, a)\) is defined, i.e. \(s\,a\) is viable, and every viable prefix is a prefix of a right-sentential form, which derives a sentence; so the tokens shifted so far always form a prefix of some sentence. It reports an error only in an empty cell; there, by the completeness argument applied to any sentence extending the tokens read, the next token cannot come next.

When it breaks. For a grammar that is not LR(0), the table has a conflict and the default resolution may reduce a non-handle, so correctness needs the lookahead of Lesson 3.2. For an ambiguous grammar no deterministic table exists at all (Theorem 3.2.13 in Lesson 3.2); GLR (Lesson 3.6) follows every action instead.

5. Complexity

Variables: \(\lvert G \rvert = \sum_{A \to \beta} (1 + \lvert \beta \rvert)\) the grammar size (so the number of items is \(\lvert G \rvert\)), \(\lvert Q \rvert\) the number of LR(0) states, \(\lvert N \rvert\), \(\lvert T \rvert\) as usual, \(n = \lvert w \rvert\).

Technique	Time (worst)	Time (typical)	Space	Notes
Shift-reduce driver	\(O(n)\) moves for a fixed grammar	a few table lookups per token	stack \(O(n)\)	needs a handle oracle; with an LR table it is Algorithm 3.1.18
LR(0) automaton	\(O(\lvert Q \rvert \cdot \lvert G \rvert \cdot (\lvert N \rvert + \lvert T \rvert))\) with hashing; \(\lvert Q \rvert \le 2^{\lvert G \rvert}\)	linear-ish in \(\lvert G \rvert\): 6 458 states for PostgreSQL's 3 408 rules (Lesson 3.8)	\(O(\lvert Q \rvert \cdot \lvert G \rvert)\) items	exponential family below

Proposition 3.1.20 (The driver makes a linear number of moves)

For a fixed grammar without cycles \(A \Rightarrow^{+} A\) and a conflict-free LR table, Algorithm 3.1.18 makes \(O(n)\) moves on an input of length \(n\).

Proof

There are exactly \(n + 1\) shifts or fewer (each consumes a token; accept consumes \(\$\)). Each reduction corresponds to a node of the parse tree it is building (Theorem 3.1.13), and a parse tree of a cycle-free grammar has \(O(n)\) nodes: at most \(c \cdot n\) where \(c\) depends only on \(G\) (a chain of unit or \(\varepsilon\)-productions without repeating a nonterminal has length \(< \lvert N \rvert\), so every node with a single non-leaf child starts a chain of bounded length, and there are \(O(n)\) nodes with \(\ge 2\) children or a terminal child, plus \(\varepsilon\)-subtrees of bounded size hanging off them). Each move is \(O(1)\) table work plus popping \(\lvert \beta \rvert \le r\) entries.

Proposition 3.1.21 (The LR(0) automaton can be exponential)

For \(n \ge 1\) let \(G_n\) have the productions \(S \to A_i\) (\(1 \le i \le n\)), \(A_i \to a_j\, A_i\) for all \(j \neq i\), and \(A_i \to b_i\). Then \(G_n\) has \(n^2 + n\) productions and its LR(0) automaton has exactly \(n\, 2^{n-1} + n^2 + 2\) states.

Proof

Count the reachable kernels. \(I_0\); \(\{S' \to S \bullet\}\); \(\{S \to A_i \bullet\}\) and \(\{A_i \to b_i \bullet\}\) for each \(i\) (\(2n\) states). After a non-empty string of \(a\)'s ending in \(a_j\), the kernel is \(K_{j,Y} = \{[A_i \to a_j \bullet A_i] : i \in Y\}\) where \(Y\) is the set of \(i \ne j\) such that \(a_i\) was never read: an item \(A_i \to a_k \bullet A_i\) survives a transition on \(a_j\) iff \(j \neq i\) (its closure offers \(A_i \to \bullet a_j A_i\) for exactly those \(j\)). Every non-empty \(Y \subseteq \{1..n\} \setminus \{j\}\) is reached (read the complement of \(Y \cup \{j\}\) in any order, then \(a_j\)), giving \(n (2^{n-1} - 1)\) states. Finally \(\mathrm{GOTO}(K_{j,Y}, A_i) = \{A_i \to a_j A_i \bullet\}\) gives \(n(n-1)\) more (one per pair \(i \ne j\)). Total \(2 + 2n + n(2^{n-1} - 1) + n(n-1) = n 2^{n-1} + n^2 + 2\). The oracle confirms \(10, 23, 50, 107, 230\) states for \(n = 2, \dots, 6\) (lr.state_counts).

So the automaton can be exponential in \(\sqrt{\lvert G \rvert}\) (here \(\lvert G \rvert = \Theta(n^2)\)); Ukkonen proves exponential lower bounds on the size of any deterministic LR-style parser for suitable grammar families [Ukk83]. At scale this does not happen for programming languages: Bison builds PostgreSQL 17's 3 408-rule grammar into 6 458 states in about 2 s (Lesson 3.8's real-world box), fewer than two states per rule.

6. Variants and refinements

Shift-reduce parsing

• Precedence parsing (simple precedence [WW66], operator precedence [Flo63]) finds handles with relations between adjacent symbols instead of an automaton — trade-off: tiny tables and no items, but only for restricted grammars and with weak error detection (Lesson 3.5).
• Bounded-context parsing (Floyd's bounded context, Wirth–Weber) looks at a fixed number of symbols on both sides of a candidate handle — trade-off: historically simpler to explain, strictly weaker than LR(k) [AU72].
• Generalized shift-reduce (GLR, Lesson 3.6) follows every action when the oracle has several answers — trade-off: all context-free grammars, at a cost up to \(O(n^3)\).

LR(0) items and the canonical LR(0) automaton

• Kernel-only states and default reductions: store only kernels and recompute closures on demand; reduce in a state with one completed item without looking at the token (Bison's $default above) — trade-off: smaller tables, errors detected a few reductions later (never after a shift, so the correct-prefix property survives).
• Table compression: row displacement and "default reduction" rows [TY79, DDH84] — trade-off: an extra check array and one indirection per lookup.
• Recursive ascent [Pen86]: compile each state into a function, like recursive descent for LR — trade-off: faster, no table interpretation, but code size grows with the automaton (the --code back end of Menhir compiles states to OCaml code [MENHIR-Manual]).

7. In real compilers

Shift-reduce parsing

• Bison (3.8.2) data/skeletons/yacc.c — the yyparse loop with the labels yybackup (consult the table), yyreduce and yydefault is Algorithm 3.1.18 generated as C [BISON-src]; the real-world box below traces it.
• PostgreSQL (REL_17_0) src/backend/parser/gram.y — every SQL statement is parsed by a Bison-generated shift-reduce parser [PG-gram] (Lesson 3.8).

A Bison parser's shift-reduce trace for *x=y

Reproduce (bison 3.8.2, clang 23.1.2; any OS):

cat > run.y <<'EOF'
%{
#include <stdio.h>
int yylex(void);
void yyerror(const char *s) { fprintf(stderr, "%s\n", s); }
%}
%define parse.trace
%token '=' '*' ID
%%
s: l '=' r | r ;
l: '*' r | ID ;
r: l ;
%%
static const char *in;
int yylex(void) { char c = *in ? *in++ : 0; return c >= 'a' && c <= 'z' ? ID : c; }
int main(int argc, char **argv) { in = argv[1]; yydebug = 1; return yyparse(); }
EOF
bison -o run.c run.y
clang-23 -w -o run run.c
./run '*x=y' 2>&1 | grep -E '^(Entering state|Reducing stack|Shifting token|Stack now)'

Output (complete):

Entering state 0
Stack now 0
Shifting token '*' ()
Entering state 1
Stack now 0 1
Shifting token ID ()
Entering state 2
Stack now 0 1 2
Reducing stack by rule 4 (line 10):
Entering state 6
Stack now 0 1 6
Reducing stack by rule 5 (line 11):
Entering state 7
Stack now 0 1 7
Reducing stack by rule 3 (line 10):
Entering state 4
Stack now 0 4
Shifting token '=' ()
Entering state 9
Stack now 0 4 9
Shifting token ID ()
Entering state 2
Stack now 0 4 9 2
Reducing stack by rule 4 (line 10):
Entering state 6
Stack now 0 4 9 6
Reducing stack by rule 5 (line 11):
Entering state 10
Stack now 0 4 9 10
Reducing stack by rule 1 (line 9):
Entering state 3
Stack now 0 3
Shifting token "end of file" ()
Entering state 8
Stack now 0 3 8
Stack now 0 3 8

What to notice: the reductions are \(4, 5, 3, 4, 5, 1\), the table of §3 row for row (Theorem 3.1.13); the state stacks are ours with Bison's 9, 10 for our I8, I9. In state 2 Bison reduces without reading the next token ("Reducing" follows "Entering state 2" directly): a default reduction, legal because I2 holds a single completed item.

LR(0) items and the canonical LR(0) automaton

• Bison (3.8.2) src/lr0.c — generate_states, new_itemsets (the GOTO kernels), get_state (kernel lookup by hash), and src/closure.c closure (Algorithm 3.1.9 with precomputed bitsets of "first derives") [BISON-src]. The real-world box below prints its trace.
• Menhir (20231231) src/lr0.ml — builds the LR(0) automaton (and the symbolic lookahead sets) on which its LALR (src/LALR.ml), Pager (src/LR1Pager.ml) and canonical (src/LR1Canonical.ml) constructions are layered [MENHIR-src].
• tree-sitter (0.27.0) crates/generate/src/build_tables/build_parse_table.rs — ParseTableBuilder::add_parse_state interns each item set (ParseItemSet) as a state, numbered as discovered, and add_actions fills its row [TS-build].

Bison computes the same closure and GOTO kernels

Reproduce (bison 3.8.2; any OS):

export LC_ALL=C   # plain '.' and '`->' in Bison's output; UTF-8 locales print '•' and '↳'
cat > assign.y <<'EOF'
%token '=' '*' ID
%%
s: l '=' r | r ;
l: '*' r | ID ;
r: l ;
EOF
bison --trace=automaton -o /dev/null assign.y 2>&1 \
  | sed -n '/^new_itemsets: begin: state = 0/,/^new_itemsets: end: state = 0/p'
bison --report=itemset --report-file=assign.output -o /dev/null assign.y
sed -n '/^State 4$/,/^State 5$/p' assign.output

Output (complete):

new_itemsets: begin: state = 0
initial kernel:
working on:     0 $accept: . s $end
working on:     1 s: . l '=' r
working on:     2 s: . r
working on:     3 l: . '*' r
working on:     4 l: . ID
working on:     5 r: . l
final kernel:
kernel['*'] =
    3 l: '*' . r
kernel[ID] =
    4 l: ID .
kernel[s] =
    0 $accept: s . $end
kernel[l] =
    1 s: l . '=' r
    5 r: l .
kernel[r] =
    2 s: r .
new_itemsets: end: state = 0
State 4

    1 s: l . '=' r
    5 r: l .

    '='  shift, and go to state 9

    $default  reduce using rule 5 (r)


State 5

What to notice: "working on" lists \(\mathrm{CLOSURE}(\{[S' \to \bullet S]\})\) in the order of Algorithm 3.1.9, and the five kernels are the GOTO kernels of rows 1–5 above, in the same symbol order (Bison augments with $accept: s $end, so its accept item has $end after the dot). State 4 is our I4 with its shift/reduce choice; Bison decides it with a default reduction on every token except =, a lookahead refinement (Lesson 3.3). With the tokens declared in first-appearance order, Bison's states 0–7 are our I0–I7; it inserts one extra state (8, after shifting $end) before our I8 and I9 [BISON-Manual].

Find where LLVM does it. LLVM contains no LR parser generator; its parsers (Clang, the .ll reader) are hand-written. Open llvm/lib/AsmParser/LLParser.cpp (LLVM 23.1.2) and find LLParser::parseTopLevelEntities [LLVM-LLParser]: which token-kind switch does it use to pick the next top-level entity, i.e. which technique is it? (quiz llparser-technique)

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Shift-reduce parsing (with a handle oracle)	Any grammar for which the oracle exists; reverse rightmost derivation	\(O(n)\) moves · a table lookup per move	Depends on the oracle; LR oracles detect errors at the first bad token	The driver is 30 lines; the oracle is the work	Every LR, precedence and GLR parser
LR(0) automaton	Exactly the viable prefixes (Theorem 3.1.16); alone, only LR(0) grammars are deterministic	\(O(\lvert Q\rvert \lvert G\rvert)\), worst case exponential · 6 458 states for PostgreSQL in ~2 s	Items name every production that could be in progress (Menhir .messages, Lesson 3.7)	Moderate: closure, GOTO, hashing kernels	The core of every LR generator (yacc, Bison, Menhir, tree-sitter)

Choose shift-reduce parsing when the grammar is naturally left-recursive or the language is designed around a generated parser (SQL, config languages, many DSLs): the stack defers every decision until the whole phrase has been seen. Choose the LR(0) automaton as your foundation when you build any LR generator: every method in Lessons 3.2–3.4 starts from it, and its items are the vocabulary of conflict reports and error messages.

9. Assessment

Technique	Quiz ids (solutions/quizzes/ch03.yaml)	Drill	Flashcard tag	Exercises
Shift-reduce parsing, handles, viable prefixes	handle-of-form, sr-trace-running	./course drill shift-reduce-trace	shift-reduce	E5
LR(0) items and automaton	closure-state0, llparser-technique	./course drill lr0-closure	lr0	E1

A reducible right side is not always a handle

In step 6 of §3 the stack ends with \(L\), the whole right side of \(R \to L\), and reducing it would be wrong: the handle is determined by the rightmost derivation, not by pattern matching. The LR(0) automaton knows this (both \(S \to L \bullet = R\) and \(R \to L \bullet\) are valid for \(L\)); it needs lookahead to decide.

References

See the chapter references.