Bottom-up parsing: GATE CS question with solution

Method. Build only the states that can conflict, then test with FOLLOW (SLR) and with LR(1) lookaheads (CLR/LALR).

Augment with $S^{\prime }\to S$. The LR(0) state $I_0$ contains $S\to \cdot Aa$, $S\to \cdot Bb$, $S\to \cdot cAb$, $A\to \cdot d$, $B\to \cdot d$. On $d$:

Two complete items in one state: a reduce-reduce conflict unless the lookaheads separate them.

SLR(1). $\text{FOLLOW}(A)=\{a,b\}$ (from $Aa$ and $cAb$), $\text{FOLLOW}(B)=\{b\}$. On $b$ the parser could reduce by either rule: conflict, so not SLR(1).

CLR(1). In the LR(1) start state the items are $[A\to \cdot d,a]$ and $[B\to \cdot d,b]$, so $I_d$ is $[A\to d\cdot ,a]$, $[B\to d\cdot ,b]$: no conflict. After $c$, the item is $[A\to \cdot d,b]$ and its $d$-successor is $\{[A\to d\cdot ,b]\}$, alone in its state. No other state has a conflict, so $G$ is CLR(1).

LALR(1). LALR merges states with the same LR(0) core. The core $\{A\to d\cdot ,B\to d\cdot \}$ and the core $\{A\to d\cdot \}$ are different, so nothing merges and the LALR table equals the CLR table: LALR(1).

The trap. SLR uses the whole FOLLOW set of a non-terminal, which mixes contexts: $b$ follows $A$ only after $c$, never in the state reached directly on $d$. Seeing "two states with $A\to d\cdot$" and concluding LALR will merge them is the opposite slip; merging needs identical item cores, not one shared item.

What was tested. Why LR(1) lookaheads are finer than FOLLOW sets, and exactly when LALR merging happens, applied to the containment SLR(1) $\subset$ LALR(1) $\subset$ CLR(1).