Compiler Design

CLR(1) & LALR Parsing / Solved Problem: LALR

Problem 1: LALR Table for S → bBb, B → ab | d

Construct the LALR(1) parsing table for the grammar:

S → bBb B → ab | d

State I0:

S' -> • S    , $
S  -> • b B b  , $

State I1:

S' -> S •    , $

State I2 (after shifting 'b'):

S -> b • B b  , $
B -> • a b    , b
B -> • d      , b

State I3 (after shifting B):

S -> b B • b  , $

State I4 (after shifting 'a'):

B -> a • b    , b

State I5 (Reduce B → d):

B -> d •      , b

State I6 (after shifting 'b' from state 3):

S -> b B b •  , $

State I7 (Reduce B → ab):

B -> a b •    , b

Since the LR(1) core item sets do not contain duplicate cores with different lookaheads, the resulting LALR table is identical to the SLR table with lookaheads properly restricted to FOLLOW(B) = { b } and FOLLOW(S) = { $ }.

Problem 2: Proof that Grammar is LR(1) but NOT LALR

Given Grammar:

S → A a | b A c | B c | b B a A → d B → d

Let us trace the LR(1) states involving the shift of d to show why CLR works but LALR fails due to lookahead collision:

1. CLR(1) Parsing States (Disjoint Lookaheads)

From the start state I0, shifting d takes us to state I_d:

I_d:
  A -> d • , a   (reduce A -> d only if next input is 'a')
  B -> d • , c   (reduce B -> d only if next input is 'c')

No conflict exists in CLR! If lookahead is 'a', reduce using rule 5. If lookahead is 'c', reduce using rule 6.

Similarly, from state I_b (after shifting b), shifting d takes us to state I_bd:

I_bd:
  A -> d • , c   (reduce A -> d only if next input is 'c')
  B -> d • , a   (reduce B -> d only if next input is 'a')

No conflict exists here either!

2. LALR(1) State Merging (Core Collision)

LALR merges states that have the exact same LR(0) cores. Notice that I_d and I_bd both have the core:

{ A -> d • , B -> d • }

LALR merges them into a single state I_merged and unions the lookahead sets:

I_merged:
  A -> d • , a/c  (reduce A -> d on 'a' or 'c')
  B -> d • , a/c  (reduce B -> d on 'a' or 'c')

Resulting Conflict:

In LALR, if the parser is in I_merged and the lookahead symbol is a, it cannot decide whether to reduce using A → d or B → d. The same occurs if the lookahead is c.

This introduces a REDUCE/REDUCE conflict. Thus, the grammar is LR(1) but NOT LALR(1).

Back to CLR(1) & LALR Parsing Advanced Parsing & Ambiguity