GATE 2026 CS2 Q.41: solution and answer

GATE 2026 · CS2Q.41 · 2 marks · MCQ

Consider the canonical $L R (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 A C B$
$A \to a A ∣ ϵ$
$C \to c C ∣ ϵ$
$B \to b B ∣ b$

Which one of the following options gives the number of shift-reduce conflicts that will occur in the $L R (0)$ ACTION table?

(A)
2
(B)
3
(C)
4
(D)
5

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The $L R (0)$ ACTION table has 5 shift-reduce conflicts, option (D).

Official answer: DSource: Official answer key, GATE 2026 CS2 (IIT Guwahati)

Augment the grammar with $S^{'} \to S$ . In an $L R (0)$ automaton a complete item $A \to α \cdot$ puts a reduce entry in every terminal column. A shift-reduce conflict therefore occurs in a state for each terminal $t$ that has an item $\cdot t$ in that state alongside a complete item.
$I_{0} = closure (S^{'} \to \cdot S) = {S^{'} \to \cdot S, S \to \cdot A C B, A \to \cdot a A, A \to \cdot}$ . The state shifts on $a$ and also reduces $A \to ε$ on $a$ . This is 1 conflict, on $a$ .
$goto (I_{0}, a) = I_{a} = {A \to a \cdot A, A \to \cdot a A, A \to \cdot}$ . It shifts on $a$ and reduces $A \to ε$ on $a$ . This is 1 conflict, on $a$ . Also $goto (I_{a}, a) = I_{a}$ , and $goto (I_{a}, A) = {A \to a A \cdot}$ , which has no shift item.
$goto (I_{0}, A) = I_{A} = {S \to A \cdot C B, C \to \cdot c C, C \to \cdot}$ . It shifts on $c$ and reduces $C \to ε$ on $c$ . This is 1 conflict, on $c$ .
$goto (I_{A}, C) = {S \to A C \cdot B, B \to \cdot b B, B \to \cdot b}$ . It has no complete item, so no conflict.
$goto (I_{A}, c) = I_{c} = {C \to c \cdot C, C \to \cdot c C, C \to \cdot}$ . It shifts on $c$ and reduces $C \to ε$ on $c$ . This is 1 conflict, on $c$ . Also $goto (I_{c}, c) = I_{c}$ , and $goto (I_{c}, C) = {C \to c C \cdot}$ , which has no shift item.
From ${S \to A C \cdot B, \dots}$ , $goto (\cdot, b) = I_{b} = {B \to b \cdot B, B \to b \cdot, B \to \cdot b B, B \to \cdot b}$ . It shifts on $b$ and reduces $B \to b$ on $b$ . This is 1 conflict, on $b$ . Also $goto (I_{b}, b) = I_{b}$ .
The remaining states are ${B \to b B \cdot}$ , ${S \to A C B \cdot}$ and ${S^{'} \to S \cdot}$ . Each has a complete item and no shift item, so none has a conflict.
Total: $1 + 1 + 1 + 1 + 1 = 5$ shift-reduce conflicts, which is option (D).

KEY IDEA

In $L R (0)$ , a complete item reduces on every terminal. So a state with a complete item and an item $\cdot t$ conflicts on $t$ . Here the $ε$ -productions $A \to ε$ and $C \to ε$ and the production $B \to b$ (beside $B \to b B$ ) each create such a state.

WATCH OUT FOR

Counting only states, or only the first state of each loop, and missing that the looping states $I_{a}$ and $I_{c}$ conflict again. Another slip is to count a state that has several reduce entries as one conflict per entry rather than one per terminal.

From the GATE 2026 CS2 paper. Every question of this paper · Download the full paper · All 13 Parsing questions, with notes

GATE 2026 CS2 Q.41: solution and answer

Answer and solution

More Parsing questions