GATE CS 2024 Set 2 Q55 — Parsing (LL, LR)

To find the number of items in the set $\operatorname{GOTO}(I_0, S)$, we first determine the items in $I_0$ that have the dot immediately preceding the non-terminal $S$.

The initial state $I_0 = \operatorname{CLOSURE}(\{S' \rightarrow \bullet S\})$ contains the following items with $\bullet S$:

• $S' \rightarrow \bullet S$
• $S \rightarrow \bullet S S$

The kernel of $\operatorname{GOTO}(I_0, S)$ is obtained by shifting the dot over $S$ in these items:

To find the complete set $\operatorname{GOTO}(I_0, S)$, we compute the closure of this kernel. Since the item $S \rightarrow S \bullet S$ has the dot before $S$, we must add all productions of $S$ with the dot at the beginning:

• $S \rightarrow \bullet S S$
• $S \rightarrow \bullet A a$
• $S \rightarrow \bullet b A c$
• $S \rightarrow \bullet B c$
• $S \rightarrow \bullet b B a$

Since we added items with $\bullet A$ and $\bullet B$, we must also include the productions of $A$ and $B$ with the dot at the beginning:

• $A \rightarrow \bullet d \#$
• $B \rightarrow \bullet @$

Combining the kernel and closure items, the complete set $\operatorname{GOTO}(I_0, S)$ consists of the following $9$ items:

1. $S' \rightarrow S \bullet$
2. $S \rightarrow S \bullet S$
3. $S \rightarrow \bullet S S$
4. $S \rightarrow \bullet A a$
5. $S \rightarrow \bullet b A c$
6. $S \rightarrow \bullet B c$
7. $S \rightarrow \bullet b B a$
8. $A \rightarrow \bullet d \#$
9. $B \rightarrow \bullet @$

Thus, the number of items in $\operatorname{GOTO}(I_0, S)$ is 9.