GATE CS 2019 Q43 — Parsing (LL, LR)

To find the number of items in the set $\text{GOTO}(I_0, \langle)$, we first construct the initial state $I_0$ and then compute the transition on the terminal symbol $\langle$.

Step 1: Compute the initial state $I_0$

The state $I_0$ is defined as $\text{CLOSURE}(\{[S’ \rightarrow \cdot S ]\})$.

Step 2: Compute $\text{GOTO}(I_0, \langle)$

The $\text{GOTO}$ operation is defined as the closure of the set of items obtained by shifting the dot past the symbol $\langle$ in $I_0$:

Now, we compute the closure of this kernel item:

1. Add the kernel item: $$S \rightarrow \langle \cdot L \rangle$$
2. Since the dot is before the non-terminal $L$, we add the productions of $L$ with the dot at the beginning: $$L \rightarrow \cdot L, S$$ $$L \rightarrow \cdot S$$
3. Since the dot is before the non-terminal $S$ in the item $L \rightarrow \cdot S$, we add the productions of $S$ with the dot at the beginning: $$S \rightarrow \cdot \langle L \rangle$$ $$S \rightarrow \cdot id$$

Combining all these, the set of items in $\text{GOTO}(I_0, \langle)$ is:

Thus, the total number of items in the set $\text{GOTO}(I_0, \langle)$ is 5.