GATE CS 2019 Q.53 (CS Q.43): Parsing and Syntax Analysis (LL and LR)

Consider the augmented grammar given below:

\begin{aligned} S' &\to S \\ S &\to \langle L \rangle \mid \text{id} \\ L &\to L, S \mid S \end{aligned}

Let $I_0 = \text{CLOSURE}(\{[S' \to \bullet S]\})$ . The number of items in the set $\text{GOTO}(I_0, \langle)$ is: ________.

Your answer

Official answer and solution

Solution

Compute the LR(0) kernel items and perform closure to find the number of items in GOTO(I0, '<').

The augmented grammar is:

S' \to S

S \to \langle L \rangle \mid \text{id}

L \to L, S \mid S

The initial state $I_0 = \text{CLOSURE}(\{[S' \to \bullet S]\})$ consists of:

To find $\text{GOTO}(I_0, \langle)$ , we take all items in $I_0$ where the dot precedes $\langle$ and advance the dot past $\langle$ :

\text{Kernel}(\text{GOTO}(I_0, \langle)) = \{[S \to \langle \bullet L \rangle]\}

Now compute $\text{CLOSURE}(\{[S \to \langle \bullet L \rangle]\})$ :

$[S \to \langle \bullet L \rangle]$ (initial kernel item)
Since the dot is before non-terminal $L$ $L$ , add all $L$ $L$ -productions with the dot at the start:
- $[L \to \bullet L, S]$
- $[L \to \bullet S]$
Since the dot in $[L \to \bullet S]$ $[L \to ∙ S]$ is before non-terminal $S$ $S$ , add all $S$ $S$ -productions with the dot at the start:
- $[S \to \bullet \langle L \rangle]$
- $[S \to \bullet \text{id}]$

Listing all distinct items in $\text{GOTO}(I_0, \langle)$ :

There are exactly $5$ items in the set.

Final answer

Common trap

Omitting the closure for S after expanding L -> .S.

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

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