GATE 2024 CS (CS2) – Question 65
Consider the augmented grammar parsed with an SLR parser, terminals $\{a,b,c,d,\#,@\}$: $S'\to S$; $S\to SS\mid Aa\mid bAc\mid Bc\mid bBa$; $A\to d\#$; $B\to @$. Let $I_0=CLOSURE(\{S'\to\bullet S\})$. The number of items in the set $GOTO(I_0,S)$ is ___________
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 9
Explanation
Augmented grammar: $S'\to S$; $S\to SS\mid Aa\mid bAc\mid Bc\mid bBa$; $A\to d\#$; $B\to @$.
$I_0$ contains $S'\to\bullet S$ and its closure. $GOTO(I_0,S)$ moves the dot over $S$ in every item of $I_0$ that has $\bullet S$:
- $S'\to S\bullet$
- $S\to S\bullet S$
Closure adds the items for the nonterminal $S$ now after the dot:
- $S\to\bullet SS$, $S\to\bullet Aa$, $S\to\bullet bAc$, $S\to\bullet Bc$, $S\to\bullet bBa$ (5 items)
- $A\to\bullet d\#$ and $B\to\bullet @$ (from $\bullet A$ and $\bullet B$)
Total $=2+5+2=\mathbf{9}$ items.