GATE CS 2024 Set 2 — Question 65

NAT+2 / -0HardLR(0) & SLR(1)Syntax AnalysisCompiler Design

Compiler Design → Syntax Analysis → LR(0) & SLR(1)

Last updated 20 August 2026

Question

Consider the following augmented grammar, which is to be parsed with a SLR parser. The set of terminals is

\{a, b, c, d, \#, @\}

S' \rightarrow S

S \rightarrow SS \mid Aa \mid bAc \mid Bc \mid bBa

A \rightarrow d\#

B \rightarrow @

Let

I_0 = CLOSURE(\{S' \rightarrow \bullet S\})

. The number of items in the set

GOTO(I_0, S)

is ___________

9 to 9

To find the number of items in

GOTO(I_0, S)

, we first determine the set

I_0

and then compute the

GOTO

transition for the symbol

S

1.Compute $I_0 = CLOSURE(\{S' \rightarrow \bullet S\})$ :

Start with the initial item: $S' \rightarrow \bullet S$ .
Since the dot is before $S$ , add all productions of $S$ with the dot at the beginning:
$S \rightarrow \bullet SS$
$S \rightarrow \bullet Aa$
$S \rightarrow \bullet bAc$
$S \rightarrow \bullet Bc$
$S \rightarrow \bullet bBa$
Now, check for non-terminals after the dot in the newly added items:
In $S \rightarrow \bullet Aa$ , the dot is before $A$ . Add $A$ productions: $A \rightarrow \bullet d\#$ .
In $S \rightarrow \bullet Bc$ , the dot is before $B$ . Add $B$ productions: $B \rightarrow \bullet @$ .
Thus, $I_0 = \{S' \rightarrow \bullet S, S \rightarrow \bullet SS, S \rightarrow \bullet Aa, S \rightarrow \bullet bAc, S \rightarrow \bullet Bc, S \rightarrow \bullet bBa, A \rightarrow \bullet d\#, B \rightarrow \bullet @\}$ .

2. Compute $GOTO(I_0, S)$ :

$GOTO(I_0, S) = CLOSURE(\{A \rightarrow \alpha S \bullet \beta \mid A \rightarrow \alpha \bullet S \beta \in I_0\})$ .
The items in $I_0$ with $S$ immediately after the dot are $S' \rightarrow \bullet S$ and $S \rightarrow \bullet SS$ .
Moving the dot over $S$ gives the kernel of the new state: $\{S' \rightarrow S \bullet, S \rightarrow S \bullet S\}$ .
Now, compute the closure of this kernel:
$S' \rightarrow S \bullet$ is already complete.
For $S \rightarrow S \bullet S$ , the dot is before $S$ , so we add all $S$ productions with the dot at the beginning:
$S \rightarrow \bullet SS$
$S \rightarrow \bullet Aa$
$S \rightarrow \bullet bAc$
$S \rightarrow \bullet Bc$
$S \rightarrow \bullet bBa$
In $S \rightarrow \bullet Aa$ , the dot is before $A$ , so add $A \rightarrow \bullet d\#$ .
In $S \rightarrow \bullet Bc$ , the dot is before $B$ , so add $B \rightarrow \bullet @$ .

3. Count the items in $GOTO(I_0, S)$ :
The complete set of items is:
1.

S' \rightarrow S \bullet

S \rightarrow S \bullet S

S \rightarrow \bullet SS

S \rightarrow \bullet Aa

S \rightarrow \bullet bAc

S \rightarrow \bullet Bc

S \rightarrow \bullet bBa

A \rightarrow \bullet d\#

B \rightarrow \bullet @

There are 9 items in total.