Question:hard
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?
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?
\[ 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?
Show 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.
Updated On: Jul 22, 2026
- 2
- 3
- 4
- 5
Show Solution
The Correct Option is D
Solution and Explanation
Step 1: Spot why conflicts can happen at all.
A shift-reduce clash in $LR(0)$ needs one item with the dot at the very end (a reduce, since $LR(0)$ ignores lookahead and reduces in every column) and another item in the same state with the dot just before a terminal (a shift on that terminal). The two nullable rules $A\to aA\mid\epsilon$ and $C\to cC\mid\epsilon$ are exactly the source of trouble, because the moment $A$ or $C$ is expected, the item $A\to.$ or $C\to.$ appears in the closure right next to the shift item on $a$ or $c$.
Step 2: Track every place $A$ is expected.
$A$ is expected at the very start, right after $S\to.ACB$ closes in, giving the state $\{S\to.ACB, A\to.aA, A\to.\}$, one clash on $a$. It is also expected again inside its own recursive rule, after shifting an $a$: $\{A\to a.A, A\to.aA, A\to.\}$, a second clash on $a$. So the $A$ side contributes $2$ conflicting states.
Step 3: Track every place $C$ is expected.
By the same logic, once $A$ is reduced away, $C$ is expected: $\{S\to A.CB, C\to.cC, C\to.\}$, a clash on $c$. Then after shifting a $c$, $C$ is expected again: $\{C\to c.C, C\to.cC, C\to.\}$, a second clash on $c$. So the $C$ side also contributes $2$ conflicting states.
Step 4: Check $B$ separately.
$B\to bB\mid b$ has no empty alternative, so on its own it would not create a clash, since a state built only from $B\to.bB$ and $B\to.b$ has two shift items and no reduce item. But once one $b$ is consumed, we land in $\{B\to b.B, B\to b., B\to.bB, B\to.b\}$: now $B\to b.$ is a completed item sitting with the shift items on $b$. That is one more clash, on $b$, coming from the ambiguity between stopping at a single $b$ and continuing into $bB$.
Step 5: Add them up.
$2$ conflicts from $A$'s nullable rule, $2$ from $C$'s nullable rule, and $1$ from $B$'s two alternatives overlapping after one $b$, gives
\[ 2+2+1=5 \]
\[ \boxed{5} \]
A shift-reduce clash in $LR(0)$ needs one item with the dot at the very end (a reduce, since $LR(0)$ ignores lookahead and reduces in every column) and another item in the same state with the dot just before a terminal (a shift on that terminal). The two nullable rules $A\to aA\mid\epsilon$ and $C\to cC\mid\epsilon$ are exactly the source of trouble, because the moment $A$ or $C$ is expected, the item $A\to.$ or $C\to.$ appears in the closure right next to the shift item on $a$ or $c$.
Step 2: Track every place $A$ is expected.
$A$ is expected at the very start, right after $S\to.ACB$ closes in, giving the state $\{S\to.ACB, A\to.aA, A\to.\}$, one clash on $a$. It is also expected again inside its own recursive rule, after shifting an $a$: $\{A\to a.A, A\to.aA, A\to.\}$, a second clash on $a$. So the $A$ side contributes $2$ conflicting states.
Step 3: Track every place $C$ is expected.
By the same logic, once $A$ is reduced away, $C$ is expected: $\{S\to A.CB, C\to.cC, C\to.\}$, a clash on $c$. Then after shifting a $c$, $C$ is expected again: $\{C\to c.C, C\to.cC, C\to.\}$, a second clash on $c$. So the $C$ side also contributes $2$ conflicting states.
Step 4: Check $B$ separately.
$B\to bB\mid b$ has no empty alternative, so on its own it would not create a clash, since a state built only from $B\to.bB$ and $B\to.b$ has two shift items and no reduce item. But once one $b$ is consumed, we land in $\{B\to b.B, B\to b., B\to.bB, B\to.b\}$: now $B\to b.$ is a completed item sitting with the shift items on $b$. That is one more clash, on $b$, coming from the ambiguity between stopping at a single $b$ and continuing into $bB$.
Step 5: Add them up.
$2$ conflicts from $A$'s nullable rule, $2$ from $C$'s nullable rule, and $1$ from $B$'s two alternatives overlapping after one $b$, gives
\[ 2+2+1=5 \]
\[ \boxed{5} \]
Was this answer helpful?
0
Questions Asked in GATE CS exam
A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the block’s anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of \(b\) blocks needs \(\lceil \log_2 b \rceil\) block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.
- GATE CS - 2023
- Database Management Systems