SLR Parsing
The
LR(0) automaton
tells us, for any stack, which state we are in and which items are live. That is almost a parser — but
not quite. When a state contains a complete item A \to \beta{\cdot},
the automaton says "you could reduce here", and when the state also has a shift available, or a
second complete item, LR(0) alone cannot choose. It has no lookahead: it would reduce on
every input symbol, causing conflicts.
SLR parsing — "Simple LR", due to Frank DeRemer — is the smallest sensible fix. Keep the
exact same LR(0) automaton, but reduce by A \to \beta only when the next
input token is in \text{FOLLOW}(A). If a token could never legally follow
an A, then reducing to A now would be pointless, so
we don't. That one guard — a
FOLLOW set
on each reduction — turns the LR(0) automaton into a genuine, deterministic parser for a large and useful
class of grammars, at essentially no extra cost in table size.
From automaton to table
An LR parser is table-driven. Two tables, indexed by the current state:
- ACTION[i, a] for a terminal
a:
- if \text{GOTO}(I_i, a) = I_j, set shift j (
sj);
- if I_i contains the complete item A \to \beta{\cdot} (with A \ne S'), set reduce A\to\beta (
rk) for every a \in \text{FOLLOW}(A);
- if I_i contains S' \to S{\cdot}, set accept on \$.
- GOTO[i, A] for a nonterminal
A: copy the automaton's \text{GOTO}(I_i, A) = I_j
straight in. This is the state the parser jumps to after a reduction pushes an
A.
- Every blank entry is an error.
If following these rules ever asks you to write two different actions in one cell, the grammar is
not SLR(1) — a conflict. Otherwise the table is a complete, deterministic parser.
The SLR table for S \to AA,\ A \to aA \mid b
Reuse the seven-state automaton from the previous page (augmented grammar
S' \to S, and productions
(1) S \to AA,
(2) A \to aA,
(3) A \to b). We need the FOLLOW sets:
\text{FOLLOW}(S) = \{\$\}, \qquad \text{FOLLOW}(A) = \{a,\, b,\, \$\}.
\text{FOLLOW}(A) is everything, because an A can be
followed by the start of another A (an a or a
b) or by end-of-input. Now fill the table. State
I_4 reduces by A\to b on all of
\{a,b,\$\}; I_6 reduces by
A\to aA on the same set; but I_5
(S\to AA{\cdot}) reduces by S\to AA only on
\$ — because that is all of \text{FOLLOW}(S).
| State | ACTION | GOTO |
|---|
| a | b | \$ | S | A |
|---|
| 0 | s3 | s4 | | 1 | 2 |
| 1 | | | acc | | |
| 2 | s3 | s4 | | | 5 |
| 3 | s3 | s4 | | | 6 |
| 4 | r3 | r3 | r3 | | |
| 5 | | | r1 | | |
| 6 | r2 | r2 | r2 | | |
Read s3 as "shift and go to state 3", r2 as "reduce by production 2
(A\to aA)", and acc as accept. No cell holds two actions, so this
grammar is SLR(1).
Running the parser: a full stack trace of abab
The LR driver keeps a stack of states (we show the grammar symbols beside them for
readability). On a shift j it pushes the token and state
j. On a reduce A\to\beta it pops
|\beta| state-symbol pairs, then pushes A and the
state \text{GOTO}[\,\text{top},A\,]. Here is the entire parse of
abab — read the string as two As, each an
ab:
| Step | State stack | Symbols | Input | Action |
|---|
| 1 | 0 | | abab\$ | shift 3 |
| 2 | 0 3 | a | bab\$ | shift 4 |
| 3 | 0 3 4 | a\,b | ab\$ | reduce A\to b |
| 4 | 0 3 6 | a\,A | ab\$ | reduce A\to aA |
| 5 | 0 2 | A | ab\$ | shift 3 |
| 6 | 0 2 3 | A\,a | b\$ | shift 4 |
| 7 | 0 2 3 4 | A\,a\,b | \$ | reduce A\to b |
| 8 | 0 2 3 6 | A\,a\,A | \$ | reduce A\to aA |
| 9 | 0 2 5 | A\,A | \$ | reduce S\to AA |
| 10 | 0 1 | S | \$ | accept |
Look at step 3: the state on top is I_4 and the lookahead is
a. Because a \in \text{FOLLOW}(A), the SLR rule
permits the reduce A\to b — and it is correct. That FOLLOW check is the only
thing SLR adds beyond LR(0), and it is exactly what lets the parser reduce confidently instead of
blindly.
One driver runs any LR table
The beautiful part of table-driven parsing: the driver never changes. Swap in an SLR, LALR, or
canonical-LR(1) table and the same twelve-line loop parses the language. Below is the generic LR driver
running the SLR table above on abab; it prints the same trace.
type Act = string; // "sN" shift, "rN" reduce, "acc", or "" = error
// ACTION[state][terminal]
const ACTION: Record<number, Record<string, Act>> = {
0: { a: "s3", b: "s4" },
1: { $: "acc" },
2: { a: "s3", b: "s4" },
3: { a: "s3", b: "s4" },
4: { a: "r3", b: "r3", $: "r3" },
5: { $: "r1" },
6: { a: "r2", b: "r2", $: "r2" },
};
// GOTO[state][nonterminal]
const GOTO: Record<number, Record<string, number>> = {
0: { S: 1, A: 2 },
2: { A: 5 },
3: { A: 6 },
};
// Productions: 1..3 (0 = S'->S handled by "acc").
const PROD: Record<number, { lhs: string; len: number; name: string }> = {
1: { lhs: "S", len: 2, name: "S->AA" },
2: { lhs: "A", len: 2, name: "A->aA" },
3: { lhs: "A", len: 1, name: "A->b" },
};
function parse(input: string[]): boolean {
const tokens = [...input, "$"];
const states: number[] = [0];
const syms: string[] = [];
let ip = 0;
for (let guard = 0; guard < 1000; guard++) {
const s = states[states.length - 1];
const a = tokens[ip];
const act = ACTION[s]?.[a] ?? "";
const view = `[${states.join(" ")}] ${syms.join("")}`.padEnd(22);
if (act.startsWith("s")) {
const j = Number(act.slice(1));
console.log(`${view} shift ${a}`);
syms.push(a); states.push(j); ip++;
} else if (act.startsWith("r")) {
const p = PROD[Number(act.slice(1))];
for (let k = 0; k < p.len; k++) { states.pop(); syms.pop(); }
const t = states[states.length - 1];
syms.push(p.lhs); states.push(GOTO[t][p.lhs]);
console.log(`${view} reduce ${p.name}`);
} else if (act === "acc") {
console.log(`${view} ACCEPT`);
return true;
} else {
console.log(`${view} ERROR on '${a}'`);
return false;
}
}
return false;
}
parse(["a", "b", "a", "b"]); // try ["b","b"], or ["a","b"] (should error: only one A)
Try editing the input. ["b","b"] parses (two As, each a lone
b); ["a","b"] fails, because
S \to AA demands two As and only one is
present — the driver reports an error exactly where the second A should begin.
A subtlety worth pinning down: the LR stack holds states, not just symbols, and the symbols are
really only there for our eyes. After a reduce, the parser has popped back to some older state
t and pushed a nonterminal A; the new state is
\text{GOTO}[t, A], read from the table. In other words the stack of states is
a running record of "where the LR(0) automaton would be if you replayed the current stack of symbols from
the start" — but maintained incrementally, without any replay. That is the whole efficiency
trick: each parsing action is O(1), so the parser runs in time linear in the
input plus the number of reductions.
SLR's one idea — "reduce by A\to\beta whenever the lookahead is in
\text{FOLLOW}(A)" — is also its weakness. \text{FOLLOW}(A)
pools together every token that can follow any A anywhere in
the grammar. But in a particular state, the tokens that can legitimately follow this
reduction may be a strict subset. When SLR reduces on a FOLLOW token that is not valid in this
context, it can collide with a shift and manufacture a conflict that a smarter parser would avoid.
The classic witness is the grammar
S \to L=R \mid R,
L \to *R \mid \texttt{id},
R \to L (pointers and assignment). One LR(0) state contains both
R \to L{\cdot} (reduce) and S \to L{\cdot}=R
(shift on =). Since = \in \text{FOLLOW}(R), SLR
writes both "reduce R\to L" and "shift ="
into the same cell — a shift-reduce conflict — even though the grammar is perfectly
unambiguous. The trouble is that = follows R
globally but not right here. The cure is to attach a precise, per-item lookahead
instead of a global FOLLOW — which is exactly what
canonical LR(1) and LALR
do.