6.3 SLR, LALR, and LR(1)

“LR parser” names a family, not one table construction. The members share shift/reduce machinery but differ in how much lookahead context they preserve before allowing a completed item to reduce. More context accepts more grammars, but usually creates more states or more complex construction.

The table below gives the whole picture first:

Keep one through-line in mind: top to bottom, each member preserves finer context and accepts more grammars, paying with more states or more complex construction.

LR(0) and SLR: Global FOLLOW as a Filter

An LR(0) item A -> alpha . has no lookahead. It would reduce regardless of the next token, which causes many spurious conflicts. SLR(1) keeps LR(0) item sets but enters the reduction only for terminals in FOLLOW(A).

LR(0):  reduce A -> alpha on every terminal
SLR:    reduce A -> alpha only on FOLLOW(A)

SLR is inexpensive and useful for teaching, but FOLLOW is global. It cannot distinguish two contexts in which the same A is followed by different tokens. A grammar may be LR(1) yet fail SLR because FOLLOW(A) includes a token that is valid after A somewhere else, not in this automaton state.

Canonical LR(1): Local Lookahead in Each Item

An LR(1) item adds one terminal lookahead:

[A -> alpha . beta, a]

It means the parser is recognizing A -> alpha beta in a context where a may follow the completed A. During closure, an item [A -> alpha . B beta, a] adds [B -> . gamma, b] for every production B -> gamma and each b in FIRST(beta a). This is the precise local context SLR lacks.

When B -> gamma . is complete, reduce only on the item's own lookahead set. Canonical LR(1) recognizes the largest grammar class of the three, but its state graph may be large. Modern generator implementations often manage that cost well, yet table size and diagnostic clarity still matter.

LALR(1): Merge Compatible Cores Carefully

LALR(1) begins from canonical LR(1) states and merges states with the same LR(0) core, unioning their lookaheads. It usually has nearly as few states as SLR while accepting far more practical programming-language grammars. Classic Yacc-style tools popularized it for good reason.

The merge is not free. Two LR(1) contexts that were separately safe can acquire a reduce/reduce conflict after their lookaheads are unioned. Therefore a conflict report should say whether it exists in canonical LR(1) already or was introduced by LALR merging. The right solution may be a grammar change, a different generator algorithm such as IELR, or an intentional disambiguation rule.

Why Global FOLLOW Can Be Too Broad

Consider a nonterminal A used in two places: once before c, once before d. Globally, FOLLOW(A) = {c, d}. In one particular state the parser may know it is in the first context, where only c can follow. SLR still permits reduction on d because it uses the global set, possibly colliding with a needed shift. LR(1) writes the local fact directly into an item such as [A -> alpha ., c], so it reduces only on c in that state.

LALR makes a practical compromise. Imagine two canonical states have the same dotted productions but lookaheads {c} and {d}. Merging them produces one state with {c,d}. This is safe when the merged lookaheads never make competing completed items overlap; it is unsafe when they do. The merge operation is therefore a language-preserving compression only for compatible contexts, not a magic shortcut.

Choosing a Family

• Use SLR for small teaching grammars and as a quick diagnostic baseline.

• Use LALR when an ecosystem's generator and grammar conventions are built around it.

• Use canonical LR(1), IELR, or another stronger method when a real grammar has non-spurious LALR conflicts and table size remains acceptable.

• Do not infer parser power from table size alone; inspect the actual conflicting state and witness input.