LR(0) Parsing and Canonical Item Sets
LR parsers read input left-to-right and build a rightmost derivation in reverse — a bottom-up parsing strategy used by many real compiler-generator tools (like yacc/bison), in contrast to the top-down approach LL parsers use. Building an LR(0) parser starts with augmenting the grammar with a new start symbol, then computing the canonical collection of item sets: each item set tracks which productions could be "in progress" at a given parsing state, marked with a dot showing how far into the production the parser has read.
The closure operation expands an item set by adding new items whenever the dot sits before a non-terminal — since that non-terminal's own productions could now also be starting. GOTO transitions connect item sets together based on which symbol is consumed, forming the parsing automaton's state graph, which ultimately becomes the parsing table an actual parser implementation would use to decide shift/reduce actions.
This is genuinely intricate to trace by hand for anything beyond a toy grammar, which is exactly why automating the construction — closure, GOTO, and the resulting state table — matters for verifying compiler-construction coursework.
LR(0) vs SLR(1)
Both tables are built from the same canonical collection of LR(0) item sets; they differ only in where reduce actions go. LR(0) puts a reduce in every column of a state that holds a completed item, while SLR(1) only puts the reduce for A → α under the terminals in FOLLOW(A). That one change resolves many conflicts.
Worked example
The expression grammar E → E + T | T, T → T * F | F, F → ( E ) | id has 12 LR(0) states. As an LR(0) table it has two shift/reduce conflicts on *, in the states holding E → T • and E → E + T •, which also hold T → T • * F. SLR(1) resolves both because * is not in FOLLOW(E) = { +, ), $ }, so the grammar is SLR(1) and id * id + id parses successfully.
The grammar S → L = R | R, L → * R | id, R → L is the textbook case that is not SLR(1): "=" is in FOLLOW(R), so one state gets a shift/reduce conflict on "=". It needs LALR(1) or canonical LR(1) lookaheads.
Reading a conflict
Every conflict lists the items behind it. On that grammar the tool shows state 2 on "=": a shift because of S → L • = R, and a reduce by R → L because R → L • is complete and = ∈ FOLLOW(R). In LR(0) mode it also says when SLR(1) would resolve the conflict, which is the usual exam question: "is this grammar LR(0)? Is it SLR(1)?"
LALR(1) and canonical LR(1)
Canonical LR(1) (CLR) items carry a lookahead: [A → α • β, a] means "after recognising α β, reduce only if the next token is a". The closure of [A → α • B β, a] adds [B → • γ, b] for every b in FIRST(β a), so each item knows exactly which tokens may follow it, rather than the whole FOLLOW set SLR(1) uses. That is why S → L = R | R is LR(1): the item R → L • only has "=" as a lookahead where an "=" can really follow.
The price is size. LALR(1) keeps LR(1) lookaheads but merges states with the same core (the same items ignoring lookaheads), so it always has as many states as LR(0). It is what yacc and bison build. The textbook grammar S → C C, C → c C | d shows the difference: 10 canonical LR(1) states, merged into 7 LALR(1) states, both conflict-free.
Merging can occasionally create a reduce/reduce conflict that canonical LR(1) does not have. Load the example "LR(1) but not LALR(1)" (S → a A d | b B d | a B e | b A e, A → c, B → c): LR(1) parses it, LALR(1) gets a reduce/reduce conflict between A → c and B → c, and the tool says the merge caused it. The four table types form a ladder, each accepting more grammars: LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1).
Where this fits
SLR(1) relies on the FOLLOW sets from the FIRST and FOLLOW calculator; LALR(1) and CLR(1) compute their own lookaheads. For the top-down alternative, and to see why left recursion breaks it, compare with the LL(1) parser. Once a parser accepts the input, the next compiler phase turns it into intermediate code: see the three-address code generator.