GATE 2026 CS (CS2) – Question 41
Consider canonical $LR(0)$ parsing of the grammar below using terminals $\{a,b,c\}$ and non-terminals $\{A,B,C,S\}$, with $S$ as the start symbol.
$$S \to ACB$$
$$A \to aA \mid \epsilon$$
$$C \to cC \mid \epsilon$$
$$B \to bB \mid b$$
Which one of the following options gives the number of shift-reduce conflicts that will occur in the $LR(0)$ ACTION table?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (D) 5
Explanation
In the canonical $LR(0)$ collection, shift-reduce conflicts occur in states that contain both a completed or $\epsilon$-reduction item and a shift possibility. For this grammar, such conflicts arise in five states: the initial state for $A\to\epsilon$ versus shift on $a$, the corresponding state for $C\to\epsilon$ versus shift on $c$, the recursive $A$ state, the recursive $C$ state, and the state after recognizing $b$ where $B\to b\cdot$ conflicts with further shift on $b$. Therefore, the number of shift-reduce conflicts is 5, so option (D) is correct.