Question

Consider the 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?

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

Hint:

Every place a nullable non-terminal (one with an epsilon rule) is expected in the item set produces a completed item sitting beside a shift item, which is exactly a shift-reduce conflict in an LR(0) table.

Answer 1

The Correct Option is D

Step 1: Understanding the Question.
We are given a grammar with two nullable non-terminals, \(A\) and \(C\) (both can derive \(\epsilon\)), and we need to build the canonical \(LR(0)\) item sets and count how many states have a shift-reduce conflict on some terminal symbol. A shift-reduce conflict happens when a state's item set has both a completed item (dot at the end, ready to reduce) and an item with the dot right before a terminal (ready to shift on that terminal), because in plain \(LR(0)\) a reduce action is placed in every column of that state's row, so it collides with any shift action already in that row.

Step 2: Build the augmented grammar and the initial state \(I_0\).
The augmented start production is \(S' \to S\).
\[ I_0 = \{\, S'\to .S,\; S\to .ACB,\; A\to .aA,\; A\to .\,\} \]
The item \(A \to .\) is already complete, since its right side is empty, so \(I_0\) has a reduce action by \(A \to \epsilon\) in every column. But \(I_0\) also has \(A\to.aA\), a shift on \(a\). So \(I_0\) gives a shift-reduce conflict on \(a\).

Step 3: Move on \(A\) from \(I_0\).
\[ I_2 = GOTO(I_0,A) = \{\, S\to A.CB,\; C\to .cC,\; C\to .\,\} \]
Again \(C\to.\) is a completed item (reduce by \(C\to\epsilon\)) sitting beside \(C\to.cC\), a shift on \(c\). So \(I_2\) gives a shift-reduce conflict on \(c\).

Step 4: Move on \(a\) from \(I_0\).
\[ I_3 = GOTO(I_0,a) = \{\, A\to a.A,\; A\to .aA,\; A\to .\,\} \]
Once more \(A\to.\) (reduce) sits with \(A\to.aA\) (shift on \(a\)). So \(I_3\) gives a shift-reduce conflict on \(a\). This state loops back to itself on further \(a\)'s, since it keeps regenerating the same closure.

Step 5: Move on \(c\) from \(I_2\).
\[ I_6 = GOTO(I_2,c) = \{\, C\to c.C,\; C\to .cC,\; C\to .\,\} \]
Same pattern: \(C\to.\) (reduce) with \(C\to.cC\) (shift on \(c\)). So \(I_6\) gives a shift-reduce conflict on \(c\).

Step 6: Move on \(C\) from \(I_2\), then on \(b\).
\[ I_5 = GOTO(I_2,C) = \{\, S\to AC.B,\; B\to .bB,\; B\to .b\,\} \]
This state has only shift items on \(b\), no completed item, so no conflict here. Moving further on \(b\) gives
\[ I_8 = GOTO(I_5,b) = \{\, B\to b.B,\; B\to b.,\; B\to .bB,\; B\to .b\,\} \]
Here \(B\to b.\) is a completed item (reduce by \(B\to b\)) sitting beside \(B\to.bB\) and \(B\to.b\), both shifts on \(b\). So \(I_8\) gives a shift-reduce conflict on \(b\).

Step 7: Count all the conflicting states.
The states with a genuine shift-reduce clash are \(I_0\) (on \(a\)), \(I_2\) (on \(c\)), \(I_3\) (on \(a\)), \(I_6\) (on \(c\)), and \(I_8\) (on \(b\)). The remaining states, such as \(GOTO(I_3,A)\), \(GOTO(I_6,C)\), \(GOTO(I_8,B)\), and \(GOTO(I_5,B)\), each hold only a single completed item with no competing shift, so they reduce cleanly with no conflict.

Step 8: Final Answer.
Counting the five conflicting states gives the total number of shift-reduce conflicts in the \(LR(0)\) ACTION table.
\[ \boxed{5} \]