Question

Consider the canonical 𝐿𝑅(0) parsing of the grammar below using terminals
{𝑎, 𝑏, 𝑐} and non-terminals {𝐴, 𝐵, 𝐶, 𝑆} with 𝑆 as the start symbol.
𝑆→𝐴𝐶𝐵
𝐴→𝑎𝐴 | 𝜖
𝐶→𝑐𝐶 | 𝜖
𝐵→𝑏𝐵 | 𝑏
Which one of the following options gives the number of shift-reduce conflicts that
will occur in the 𝐿𝑅(0) ACTION table?

• A. 2
• B. 3
• C. 4
• D. 5

Hint:

Every place the LR(0) automaton must decide whether to reduce an empty production ($A \to \epsilon$ or $C \to \epsilon$) or shift the terminal that starts the alternative production is a shift-reduce conflict; also check the state reached after shifting one 'b' since $B \to b$ and $B \to bB$ overlap there. Count all such states.

Answer 1

The Correct Option is D

We must build the canonical LR(0) collection for the augmented grammar and count how many states contain both a shift item and a reduce item on the same terminal.

Step 1: Augmented grammar

\[S' \to S,\quad S \to ACB,\quad A \to aA \mid \epsilon,\quad C \to cC \mid \epsilon,\quad B \to bB \mid b\]

Step 2: Construct \(I_0 = closure(\{S' \to \cdot S\})\)

\[I_0 = \{\, S' \to \cdot S,\; S \to \cdot ACB,\; A \to \cdot aA,\; A \to \cdot \,\}\]

Since \(A \to \epsilon\) is a complete item (dot at end) sitting in the same state as the shift item \(A \to \cdot aA\) (which shifts on 'a'), \(I_0\) has a shift/reduce conflict on 'a'.

Step 3: GOTO(\(I_0\), A) = \(I_1\)

\[I_1 = \{\, S \to A \cdot CB,\; C \to \cdot cC,\; C \to \cdot \,\}\]

Again the reduce item \(C \to \cdot\) coexists with the shift item \(C \to \cdot cC\) (shift on 'c'). Conflict on 'c' in \(I_1\).

Step 4: GOTO(\(I_0\), a) = \(I_2\)

\[I_2 = \{\, A \to a \cdot A,\; A \to \cdot aA,\; A \to \cdot \,\}\]

Same pattern: shift on 'a' versus reduce \(A \to \cdot\). Conflict on 'a' in \(I_2\).

Step 5: GOTO(\(I_1\), c) = \(I_4\)

\[I_4 = \{\, C \to c \cdot C,\; C \to \cdot cC,\; C \to \cdot \,\}\]

Shift on 'c' versus reduce \(C \to \cdot\). Conflict on 'c' in \(I_4\).

Step 6: GOTO(\(I_1\), C) = \(I_3\) then GOTO(\(I_3\), b) = \(I_7\)

\[I_3 = \{\, S \to AC \cdot B,\; B \to \cdot bB,\; B \to \cdot b\,\}\]\[I_7 = \{\, B \to b \cdot B,\; B \to b \cdot,\; B \to \cdot bB,\; B \to \cdot b \,\}\]

Here \(B \to b \cdot\) is a completed reduce item while \(B \to b \cdot B\) (via \(B \to \cdot bB\)) requires a shift on 'b'. Conflict on 'b' in \(I_7\).

Step 7: Tally the conflicting states

The states carrying a genuine shift/reduce clash are \(I_0\) (on a), \(I_1\) (on c), \(I_2\) (on a), \(I_4\) (on c), and \(I_7\) (on b). Every other completed state (such as \(I_5: A \to aA \cdot\), \(I_6: S \to ACB \cdot\), \(I_8: C \to cC \cdot\), \(I_9: B \to bB \cdot\)) is a pure reduce state with no competing shift, so it adds no conflict.

Step 8: Count

Total shift-reduce conflicts \(= 5\).

Final Answer:

\[\boxed{5 \text{ (Option D)}}\]