Simple LR uses the same DFA as LR(0) but a smarter reduce strategy — restrict reductions using FOLLOW sets. See exactly where it helps, where it still fails, and why CLR is needed.
Consider the classic assignment grammar used by the Dragon Book to demonstrate SLR vs CLR:
id = id, *id = id, id = *id, etc.L = lvalue (left-hand side), R = rvalue (right-hand side).
After building the LR(0) DFA for this grammar, state I₂ contains items for both S → L•=R and R → L•. This creates an immediate conflict on the = token.
= to continue matching S → L = R. This is correct for an assignment statement.R → L on all terminals including =. But semantically, R → L shouldn't happen right before =!= in state I₂, we have both Shift and Reduce R→L — LR(0) cannot decide.
FOLLOW(A) = the set of terminals that can appear immediately after A in any valid sentential form.
SLR says: instead of reducing on ALL terminals, only reduce when the next token is in FOLLOW(A). Let's apply this to state I₂.
= ∈ FOLLOW(R), SLR says: reduce R → L on =!
=:= to continue matching.
=:
S → L = R)= ∈ FOLLOW(R) = {=, $})= in state I₂!
= because of the production S → L = R — after an R, we can see = in some context. But not this context! FOLLOW sets are global — they don't know we're specifically inside S → L•=R.
[R → L•, $] has lookahead {$} — NOT {=, $}. So reduce R→L only on $, and shift = without conflict. See CLR →
= because of S → L=R, even though that = appears before R, not after it in I₂'s context.
R → L• is as part of S → R, so $ is the only valid lookahead.
For our familiar S→CC grammar, let's compare what LR(0) vs SLR would do in a hypothetical conflict scenario. First, let's compute FOLLOW sets.
E → E+T | T and T → id. In LR(0), state with T → id• would reduce on ALL terminals including +. But if FOLLOW(T) = {+, $}, then SLR reduces only on + and $ — avoiding spurious reductions on tokens like * that would signal a conflict in more complex grammars.
The DFA for the S→L=R grammar has 10 states. State I₂ is the notorious conflict state.
Compared to LR(0), SLR restricts reduce entries to FOLLOW(A) only. The red cell shows the remaining conflict in I₂.
| State | ACTION | GOTO | |||||
|---|---|---|---|---|---|---|---|
| id | * | = | $ | S | L | R | |
id$
Let's parse the simplest valid string: id followed by end-of-input. This exercises the path S → R → L → id. We use the S→CC grammar (which IS SLR-parseable without conflict) for a clean demonstration.
ccdd$ with SLR: For the S→CC grammar, the SLR table is identical to the LR(0) table (FOLLOW(C) = all terminals). The power of SLR shines for grammars where restricting reduce lookaheads actually eliminates conflicts.
| Stack (states) | Remaining Input | Action | Notes |
|---|
| Aspect | LR(0) | SLR(1) |
|---|---|---|
| Reduce on | ALL terminals (no lookahead) | FOLLOW(A) only (1-token lookahead) |
| DFA states | Same as SLR | Same as LR(0) |
| Table size | Same as SLR | Same as LR(0) |
| Conflicts | More conflicts | Fewer conflicts (not zero) |
| Grammar class | LR(0) grammars (rare) | SLR(1) grammars (larger class) |
| Lookahead source | None | Global FOLLOW sets |
| Lookahead accuracy | N/A | Imprecise (global context) |
| Implementation | Simplest | Simple (just add FOLLOW check) |
| Handles S → L=R | ❌ Conflict | ❌ Still conflict (FOLLOW too broad) |