LALR(1) Parser Merging Explained: LR(1) States, Tables and Conflicts

The usual LALR(1) mistake begins with the merge rule. LALR(1) does not merge states because their full LR(1) item sets match. It merges canonical LR(1) states whose LR(0) cores match, then unions the lookaheads of corresponding items. For S -> C C and C -> c C | d, the canonical collection has 10 states, merging produces 7, and c d d $ reaches accept without a conflict.

Related reading: LALR parser MCQs and canonical LR items.

What an LALR(1) parser keeps from canonical LR(1)

An LR(1) item has the form [A -> alpha . beta, a]. The production and dot position form its LR(0) item, while a is the one-symbol lookahead. CLOSURE adds items for a non-terminal after the dot and propagates the correct lookaheads. GOTO(I, X) moves the dot across grammar symbol X, then closes the resulting item set.

The construction is compact: build the canonical LR(1) collection, group states with identical LR(0) cores, union corresponding lookahead sets, and retain the induced transitions. LALR(1) therefore preserves item-specific LR(1) lookaheads. It does not replace them with global FOLLOW sets as SLR does.

The exact LALR(1) merge rule

If core(Ip) = core(Iq), replace the pair by M = Ip union Iq. For every shared core item A -> alpha . beta, calculate:

LA_M(A -> alpha . beta) = LA_Ip(A -> alpha . beta)
                         union LA_Iq(A -> alpha . beta)

States with even one different production or dot position must remain separate. Two invariants help you check a legal merge. First, identical-core states have compatible outgoing transitions on grammar symbols. Second, a completed item reduces only on its own merged lookaheads. Since a union can add reductions to new ACTION cells, inspect conflicts after unioning, not before.

Core test: Same kernel size is not enough. The same production names are not enough. You need the same complete LR(0) core, including every dot position.

Worked example: all 10 canonical LR(1) states

The augmented grammar is:

(0) S' -> S
(1) S  -> C C
(2) C  -> c C
(3) C  -> d

The terminals are {c, d, $}, and FIRST(C) = {c, d}. In I0, closure gives the first C in S -> . C C the lookaheads FIRST(C$) = {c, d}. In I2, the dot is before the second C, so that C receives only {$}. The First and Follow in Compiler Design: Solved Examples guide develops this lookahead calculation from the basics.

Items that differ only in lookahead are grouped in braces:

I0: S' -> . S, {$}
    S  -> . C C, {$}
    C  -> . c C, {c,d}
    C  -> . d,   {c,d}

I1: S' -> S ., {$}

I2: S  -> C . C, {$}
    C  -> . c C, {$}
    C  -> . d,   {$}

I3: C  -> c . C, {c,d}
    C  -> . c C, {c,d}
    C  -> . d,   {c,d}

I4: C  -> d ., {c,d}

I5: S  -> C C ., {$}

I6: C  -> c . C, {$}
    C  -> . c C, {$}
    C  -> . d,   {$}

I7: C  -> d ., {$}

I8: C  -> c C ., {c,d}

I9: C  -> c C ., {$}

Now move each possible dot. From I0, symbols S, C, c, and d produce I1, I2, I3, and I4. From I2, symbols C, c, and d produce I5, I6, and I7. State I3 goes on c to itself, on d to I4, and on C to I8. State I6 similarly goes on c to itself, on d to I7, and on C to I9.

Merge the identical-core states into seven states

Erase the lookaheads and compare cores item by item. Exactly three pairs match: I3 with I6, I4 with I7, and I8 with I9. In each pair, corresponding lookaheads union to {c,d,$}. States I0, I1, I2, and I5 are unique, so the count falls from 10 to 7.

Renumber the result as M0=I0, M1=I1, M2=I2, M3=I3+I6, M4=I4+I7, M5=I5, and M6=I8+I9. The merged transitions are:

• M0: S->M1, C->M2, c->M3, d->M4

• M2: C->M5, c->M3, d->M4

• M3: C->M6, c->M3, d->M4

Build the LALR(1) table and parse c d d $

Let r1 mean S -> C C, r2 mean C -> c C, and r3 mean C -> d. Shifts come from terminal transitions, reductions come from completed items on their lookaheads, and the completed augmented item gives acc.

The parse for c d d $ is:

1. Start at 0. Shift c with s3: 0 c 3.

2. Shift the first d with s4: 0 c 3 d 4.

3. On lookahead d, reduce by r3: C -> d. Pop d 4, then GOTO(3,C)=6: 0 c 3 C 6.

4. Reduce by r2: C -> c C. Pop c 3 C 6, then GOTO(0,C)=2: 0 C 2.

5. Shift the second d with s4: 0 C 2 d 4.

6. On $, reduce by r3. After GOTO(2,C)=5: 0 C 2 C 5.

7. Reduce by r1: S -> C C. After GOTO(0,S)=1: 0 S 1.

8. State 1 accepts on $.

An LR/LALR parse yields a rightmost derivation in reverse. Here, reading the reductions r3, r2, r3, r1 backward gives the recall form r1, r3, r2, r3 and the rightmost derivation S => C C => C d => c C d => c d d.

When merging creates a reduce-reduce conflict

Consider S'->S, S->aAd | bAe | aBe | bBd, A->c, and B->c. The canonical state reached after a c contains [A->c., d] and [B->c., e]. The state reached after b c contains [A->c., e] and [B->c., d].

Both states have the core {A->c., B->c.}. Merging produces [A->c., {d,e}] and [B->c., {d,e}]. On both d and e, the table now has two possible reductions. The grammar is therefore CLR(1) but not LALR(1).

There is a useful trap here. Merging identical-core canonical states can create a new reduce-reduce conflict, but it cannot create a new shift-reduce conflict. If their shared core shifts terminal x, that shift item already occurs in each state. A reduction on x in either original state would already have conflicted with it.

How exams test LALR(1) merging

Questions usually ask you to identify equal cores, count states after merging, union one lookahead set, fill an ACTION cell, detect a reduce-reduce conflict, or classify a grammar as CLR(1) but not LALR(1). For this grammar, the check answers are (I3,I6), (I4,I7), (I8,I9), 7 merged states, no conflict, and ACTION[M4,$]=r3.

A 30-second routine is enough: erase lookaheads, partition states by exact cores, restore and union lookaheads item by item, then inspect completed items terminal by terminal. Never merge two states merely because they share one item. The SLR, CLR and LALR Parsers for GATE: States & Conflicts comparison is the better reference for the parser-power hierarchy; for LALR construction questions, rebuild the core partitions and merged ACTION cells on a fresh grammar.

Short version and the next study step

Remember the ladder:

1. Canonical LR(1) items carry lookaheads.

2. Equal LR(0) cores are merge candidates.

3. Corresponding lookaheads are unioned.

4. The merged ACTION table decides whether the grammar stays conflict-free.

The compact recall hook is 10 canonical states -> 7 LALR states -> c d d $ accepted. For a complete core-subject sequence, use Zero to Hero, Complete CS Course. If you are organising the wider exam journey, GATE Guidance by Sanchit Sir provides that structure. You can browse adjacent subject explanations in the CS Fundamentals for Exams & Placements category.