# Bottom-up parsing: GATE CS question with solution

From the GATE Daily set of 27 October 2026, question 7 of 10 (https://gatedaily.in/q/2026-10-27-lalr-but-not-slr-reduce-reduce/). Difficulty: standard.

### Q.7 · Compiler Design · Bottom-up parsing · MCQ, 2 marks (choose one option)

Consider the context-free grammar $G$ with start symbol $S$, non-terminals $\{S, A, B\}$ and terminals $\{a, b, c, d\}$:

$$S \to A\,a \mid B\,b \mid c\,A\,b$$
$$A \to d$$
$$B \to d$$

Which ONE of the following statements is TRUE?

(A) G is SLR(1), and hence also LALR(1)
(B) G is LALR(1) but not SLR(1)
(C) G is CLR(1) but not LALR(1)
(D) G is not CLR(1)

**Answer:** (B) G is LALR(1) but not SLR(1)

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

Augment with $S' \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$:

$$I_d = \{\,A \to d\cdot,\;\; B \to d\cdot\,\}$$

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).

**Remember:** SLR decides reductions with FOLLOW sets, which pool every context; LR(1) lookaheads keep contexts apart. LALR merges only states with identical LR(0) cores, so if no two LR(1) states share a core, LALR(1) equals CLR(1).

**Why each option:**
- (A) Misses the SLR conflict: the state reached on d holds A -> d. and B -> d., and b is in both FOLLOW(A) and FOLLOW(B).
- (B) The d-state has lookahead a for A and b for B in LR(1), and no other state shares its core, so LALR keeps the split that SLR loses.
- (C) Assumes the two states containing A -> d. get merged; they have different cores ({A -> d., B -> d.} vs {A -> d.}), so LALR merges nothing here.
- (D) Takes the SLR reduce-reduce conflict as fundamental; with LR(1) lookaheads A -> d. reduces only on a and B -> d. only on b.