GATE CS 2021 Set 2 Q.61 (CS Q.51): Parsing and Syntax Analysis (LL and LR)

Consider the following augmented grammar with $\{\#, @, <, >, a, b, c\}$ as the set of terminals.

\begin{aligned} S' &\to S \\ S &\to S \# c S \\ S &\to S S \\ S &\to S @ \\ S &\to {<} S {>} \\ S &\to a \\ S &\to b \\ S &\to c \end{aligned}

Let $I_0 = \text{CLOSURE}(\{S' \to \cdot S\})$ . The number of items in the set $\text{GOTO}(\text{GOTO}(I_0, <), <)$ is ______.

Your answer

Official answer and solution

Official answer: 8
From: Official GATE 2021 answer key

Solution

Trace the LR(0) item set closures and GOTO transitions starting from state $I_0$ .

The augmented grammar has start symbol $S'$ and non-terminal $S$ with productions:

$S' \to S$
$S \to S \# c S$
$S \to S S$
$S \to S @$
$S \to {<} S {>}$
$S \to a$
$S \to b$
$S \to c$

State $I_0 = \text{CLOSURE}(\{S' \to \cdot S\})$ .
Taking the transition on terminal '<':

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

Among the items in $I_0$ , only $S \to \cdot {<} S {>}$ has the dot immediately before '<'. Moving the dot gives the kernel item:

\text{Kernel}(I_1) = \{S \to {<} \cdot S {>}\}

Since the dot is before non-terminal $S$ , the closure adds all productions of $S$ with the dot at the beginning:

$S \to \cdot S \# c S$
$S \to \cdot S S$
$S \to \cdot S @$
$S \to \cdot {<} S {>}$
$S \to \cdot a$
$S \to \cdot b$
$S \to \cdot c$

Next, compute $I_2 = \text{GOTO}(I_1, <)$ :
Among all items in $I_1$ , the only item with the dot before '<' is again $S \to \cdot {<} S {>}$ .
Moving the dot past '<' gives the kernel item:

\text{Kernel}(I_2) = \{S \to {<} \cdot S {>}\}

Taking the closure of $I_2$ adds the same 7 initial items for $S$ with the dot at the front:

$S \to {<} \cdot S {>}$ (kernel item)
$S \to \cdot S \# c S$
$S \to \cdot S S$
$S \to \cdot S @$
$S \to \cdot {<} S {>}$
$S \to \cdot a$
$S \to \cdot b$
$S \to \cdot c$

Counting all distinct items in $I_2$ , we have $1 + 7 = 8$ items.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology - Session 2 (CS2)
Question: 61 of 65, printed as CS Q.51
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source