LALR Parse Tables

LALR(1) stands for Look-Ahead LR with 1 token of lookahead. It is the engineering compromise between SLR(1) and CLR(1) — and is the parser-construction technique used by virtually every production parser generator: yacc, bison, GNU Bison, Java CUP, Menhir.

For a typical real-world grammar, LALR's parse table can be 5–10× smaller than CLR's, while still handling almost every grammar CLR handles. That's why bison's default is LALR and not CLR.

The Key Insight

Look back at the CLR(1) construction. Several states had identical LR(0) cores — the same items, ignoring lookaheads — and differed only in their lookahead sets.

These pairs were split apart by CLR purely to keep their lookaheads separate. LALR merges them back together, uniting their lookahead sets:

The result has the same number of states as LR(0)/SLR, but each reduce item carries its own lookahead — almost the same precision as CLR.

The simplest way to build an LALR(1) table is in two steps: build CLR(1) first, then merge.

Step-by-Step

Why the LR(0) Core Matters

If two CLR(1) states have the same LR(0) core, they react to inputs in exactly the same way:

Both transitions go to states with the same core — merging the targets is consistent with merging the sources. The LR(0) DFA structure is preserved.

What Merging Costs

Most of the time: nothing. The merged lookahead set is just the union, and reductions fire correctly.

But occasionally, merging creates a problem:

That is a reduce/reduce conflict introduced by the merge. The grammar is CLR(1) but not LALR(1). These cases are rare — yacc and bison print them as errors when they occur.

What Merging Does NOT Cause

Merging never introduces shift/reduce conflicts. A shift/reduce conflict requires a terminal transition out of the state on the same symbol that triggers the reduction — and the LR(0) transitions are identical between the merged states, so a shift/reduce conflict in the merged state must have existed in every original state too. If CLR was conflict-free, LALR cannot break that by merging.

We continue with the same grammar so the three constructions can be compared.

From the CLR topic, the full LR(1) DFA had 10 states:

We will now collapse it to 7 states — the same count as SLR.

Strip each state's lookaheads and look at its LR(0) core. Group states whose cores are identical.

Three pairs merge, four states stay as they are. The LALR(1) DFA will have 7 states.

Naming the Merged States

A common naming convention is to combine the original numbers:

We'll use these names throughout.

For each group, the merged state's items are the LR(0) core items, with lookaheads taken as the union of the corresponding lookaheads in the originals.

Merging I₃ and I₆ → I₃₆

Merging I₄ and I₇ → I₄₇

Merging I₈ and I₉ → I₈₉

Result — All 7 LALR(1) States

When we merge states, the GOTO transitions targeting the original states must be redirected to the merged ones.

Updated Transition Table

Both I₂ — c → ? and I₃ — c → ? now point to the same merged state I₃₆. Same for the other merged pairs.

Visual Diagram of the Merged DFA

The merged LALR(1) DFA has 7 states — the SLR count — but each item keeps a unioned lookahead set. Compare this with the 10-state CLR diagram: the three split pairs have collapsed into I₃₆, I₄₇, and I₈₉.

How to read it:

• Blue — the start state (I₀).
• Cyan — the accept state (I₁, on lookahead $).
• Amber — reduce states (I₄₇, I₅, I₈₉), each now reducing on its merged lookahead set.
• Arrow labels — the grammar symbol that triggers the transition.

Both I₀ and I₂ now transition to the single merged state I₃₆ on c (and to I₄₇ on d) — the merge preserved the LR(0) transition structure exactly, so the diagram has the same shape as the SLR DFA, just with richer lookaheads inside each node.

With the merged DFA in hand, the LALR(1) table is built using the same rule as CLR(1) — each item's lookahead set drives the reduce entries.

Reduce Entries

Accept Entry

Shift and GOTO Entries

Straight from the redirected transitions.

The Complete LALR(1) Parse Table

Every cell has at most one entry — the grammar is LALR(1).

Compare Side by Side

For this particular grammar, the LALR(1) and SLR(1) tables happen to coincide — both grammars accept on the same lookaheads. The difference shows up on harder grammars (like the L = R example) where SLR fails and LALR succeeds.

Almost every grammar that is CLR(1) is also LALR(1) — but almost is not "always." When merging combines states whose distinct lookaheads happen to clash, a new reduce/reduce conflict can appear.

A Minimal Example

After processing a c we are in a state containing [A → c · , d] and [B → c · , e] — no conflict, two different lookaheads.

After processing b c we are in a (different) state containing [B → c · , d] and [A → c · , e] — also no conflict.

But both states share the same LR(0) core {A → c ·, B → c ·}, so LALR merges them:

The grammar is CLR(1) (no conflict in 10 separate states), but not LALR(1) (conflicts after merging).

How Bison Handles It

When bison detects this pattern it reports:

The default resolution is to prefer the production listed first in the grammar file. The fix is usually to rewrite the grammar so the two non-terminals are merged or distinguished earlier:

Frequency

In practice, LALR-only conflicts are rare. The grammars of C, Java, Pascal, SQL, JavaScript, PHP, Ruby, and Python are all expressible in LALR(1) (sometimes with a small number of bison %prec directives to nudge the resolver). The LALR(1) sweet spot is no accident — it covers nearly everything you would want to parse.

LALR(1) wins by dominating the trade-off space.

The Three-Way Comparison

• SLR(1) → small but not powerful enough for many real grammars.
• CLR(1) → maximum power but tables grow huge.
• LALR(1) → nearly the power of CLR with the size of SLR.

Real Tools That Use LALR(1)

This is not a coincidence — the LALR(1) algorithm was designed in 1969 by Frank DeRemer explicitly to make LR parsing practical on the memory-limited machines of that era. The trade-off held up so well that fifty years later, it is still the default.

Practical Workflow

The whole point of LALR(1) is that you almost never have to think about it. The tool handles construction, conflict reporting, and table generation — you focus on grammar design and semantic actions.

Summary

If you ever build a programming language with bison or a similar tool, you are using LALR(1). The next topic — Shift-Reduce Parsing — shows the runtime engine that interprets these tables.