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

A quicker way to see this without redrawing every item set is to notice the grammar's structure directly: every nonterminal that has an \(\epsilon\)-production sits inside a state that also offers a shift on the very terminal that begins its non-empty alternative.

Reasoning from nullable nonterminals

\(A \to aA \mid \epsilon\) is nullable, and wherever the parser is 'expecting' an \(A\) (right after seeing nothing, or right after shifting an 'a'), the item set simultaneously contains \(A \to \cdot\) (reduce by the empty rule) and \(A \to \cdot aA\) (shift on 'a'). Since \(A\) is expected in two distinct contexts in this grammar -- at the very start (inside \(I_0\), since \(S \to \cdot ACB\)) and after consuming one 'a' (inside \(I_2\), since \(A \to a \cdot A\)) -- each of those two states produces one shift/reduce clash on 'a'.

Similarly \(C \to cC \mid \epsilon\) is nullable. The parser expects a \(C\) right after reducing \(A\) (state \(I_1\), from \(S \to A \cdot CB\)) and again after consuming one 'c' (state \(I_4\), from \(C \to c \cdot C\)). Each of those two states gives one shift/reduce clash on 'c'.

Finally \(B \to bB \mid b\) is not nullable, but it is still ambiguous about when to stop reading b's: after shifting one 'b' the parser cannot tell whether that b was the last symbol of \(B \to b\) (reduce) or the first symbol of \(B \to bB\) (shift another b). That single state contributes one shift/reduce clash on 'b'.

Adding the contributions

Nullable \(A\) contexts: 2 conflicts (at start, and after one 'a').
Nullable \(C\) contexts: 2 conflicts (after \(A\) is reduced, and after one 'c').
Ambiguous tail of \(B\): 1 conflict (after one 'b').

\(2 + 2 + 1 = 5\) shift-reduce conflicts in total, matching option D.

Answer: 5