Official PYQ · 2021Set 2 · Q51Parsing (LL, LR)NAT2 marks

GATE CS 2021 Set 2 Q51 — Parsing (LL, LR)

Consider the following augmented grammar with

\{ \#, @, <, >, a, b, c \}

as the set of terminals.

\begin{array}{l} S’ \rightarrow S \\ S \rightarrow S \# cS \\ S \rightarrow SS \\ S \rightarrow S @ \\ S \rightarrow < S > \\ S \rightarrow a \\ S \rightarrow b \\ S \rightarrow c \end{array}

Let

I_0 = \text{CLOSURE}(\{S’ \rightarrow \bullet S\})

. The number of items in the set

\text{GOTO(GOTO}(I_0<), <)

is ___________

View worked solution

Answer: 8 : 8

To find the number of items in the set $\text{GOTO}(\text{GOTO}(I_0, <), <)$ , we compute the sets step-by-step.

Step 1: Find $I_0 = \text{CLOSURE}(\{S’ \rightarrow \bullet S\})$

Expanding the closure of the start item, we get:

\begin{aligned}I_0 = \{ & S’ \rightarrow \bullet S, \\ & S \rightarrow \bullet S \# cS, \\ & S \rightarrow \bullet SS, \\ & S \rightarrow \bullet S @, \\ & S \rightarrow \bullet < S >, \\ & S \rightarrow \bullet a, \\ & S \rightarrow \bullet b, \\ & S \rightarrow \bullet c \}\end{aligned}

Step 2: Find $I_1 = \text{GOTO}(I_0, <)$

The only item in $I_0$ with the dot before the terminal $<$ is $S \rightarrow \bullet < S >$ . Moving the dot over $<$ gives the kernel of $I_1$ :

\text{Kernel}(I_1) = \{ S \rightarrow < \bullet S > \}

Taking the closure of this kernel (since the dot is before the non-terminal $S$ ):

\begin{aligned}I_1 = \{ & S \rightarrow < \bullet S >, \\ & S \rightarrow \bullet S \# cS, \\ & S \rightarrow \bullet SS, \\ & S \rightarrow \bullet S @, \\ & S \rightarrow \bullet < S >, \\ & S \rightarrow \bullet a, \\ & S \rightarrow \bullet b, \\ & S \rightarrow \bullet c \}\end{aligned}

Step 3: Find $I_2 = \text{GOTO}(I_1, <)$

In $I_1$ , the only item with the dot before $<$ is $S \rightarrow \bullet < S >$ . Moving the dot over $<$ gives the kernel of $I_2$ :

\text{Kernel}(I_2) = \{ S \rightarrow < \bullet S > \}

Since the kernel of $I_2$ is identical to the kernel of $I_1$ , their closures are identical, meaning $I_2 = I_1$ .

Counting the items in $I_2$ , we have exactly 8 items.

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Related questions