GATE 2022 CS – Question 29
Consider the augmented grammar with $\{+, *, (, ), id\}$ as the set of terminals.
$S'\to S$
$S\to S+R\mid R$
$R\to R*P\mid P$
$P\to (S)\mid id$
If $I_0$ is the set of two $LR(0)$ items $\{[S'\to S.],[S\to S.+R]\}$, then $goto(closure(I_0),+)$ contains exactly __________ items.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 5
Explanation
$I_0$ here is the set $\{[S'\to S\cdot],\ [S\to S\cdot+R]\}$. $goto(I_0,+)$ moves the dot over `+` in every item that has `+` right after the dot. Only $[S\to S\cdot+R]$ qualifies, giving $[S\to S+\cdot R]$.
Now take the **closure**: the dot is before the non-terminal $R$, so add all $R$-productions with the dot at the start:
- $R\to\cdot R*P$
- $R\to\cdot P$
The second item has the dot before $P$, so add the $P$-productions:
- $P\to\cdot(S)$
- $P\to\cdot id$
Items: $[S\to S+\cdot R]$, $[R\to\cdot R*P]$, $[R\to\cdot P]$, $[P\to\cdot(S)]$, $[P\to\cdot id]$. That is **5** items.