GATE CS 2026 Set 2 Q31 — Parsing (LL, LR)

To find the number of shift-reduce (S-R) conflicts in the $LR(0)$ parsing table, we construct the canonical collection of $LR(0)$ items for the augmented grammar:

1. $S' \rightarrow S$
2. $S \rightarrow A C B$
3. $A \rightarrow a A \mid \epsilon$
4. $C \rightarrow c C \mid \epsilon$
5. $B \rightarrow b B \mid b$

An $LR(0)$ state has a shift-reduce conflict if it contains at least one shift item (e.g., $X \rightarrow \alpha \cdot a \beta$) and at least one reduce item (e.g., $Y \rightarrow \gamma \cdot$). Let's trace the states containing such conflicts:

• State $I_0$:
  $S' \rightarrow \cdot S$
  $S \rightarrow \cdot A C B$
  $A \rightarrow \cdot a A$   (shift on $a$)
  $A \rightarrow \cdot$   (reduce $A \rightarrow \epsilon$)
  Conflict 1


• State $I_2 = \text{goto}(I_0, A)$:
  $S \rightarrow A \cdot C B$
  $C \rightarrow \cdot c C$   (shift on $c$)
  $C \rightarrow \cdot$   (reduce $C \rightarrow \epsilon$)
  Conflict 2


• State $I_3 = \text{goto}(I_0, a)$:
  $A \rightarrow a \cdot A$
  $A \rightarrow \cdot a A$   (shift on $a$)
  $A \rightarrow \cdot$   (reduce $A \rightarrow \epsilon$)
  Conflict 3


• State $I_5 = \text{goto}(I_2, c)$:
  $C \rightarrow c \cdot C$
  $C \rightarrow \cdot c C$   (shift on $c$)
  $C \rightarrow \cdot$   (reduce $C \rightarrow \epsilon$)
  Conflict 4


• State $I_8 = \text{goto}(I_4, b)$ where $I_4 = \text{goto}(I_2, C)$:
  $B \rightarrow b \cdot B$
  $B \rightarrow b \cdot$   (reduce $B \rightarrow b$)
  $B \rightarrow \cdot b B$   (shift on $b$)
  $B \rightarrow \cdot b$   (shift on $b$)
  Conflict 5

No other states contain both a shift and a reduce item. Thus, there are exactly $5$ shift-reduce conflicts in the $LR(0)$ parsing table.