GATE CS 2022 Q19 — Parsing (LL, LR)

To find the number of items in $\text{goto}(\text{closure}(I_0), +)$, we proceed step-by-step:

Step 1: Compute $\text{closure}(I_0)$

Given $I_0 = \{ [S’ \rightarrow S.], [S \rightarrow S. + R] \}$.

In both items, the dot is not placed before any non-terminal (it is at the end in the first item, and before the terminal $+$ in the second). Therefore, no expansion is needed:

Step 2: Compute $\text{goto}(\text{closure}(I_0), +)$

The $\text{goto}$ function on terminal $+$ shifts the dot over $+$ in any item where the dot is immediately before $+$. The only such item in $\text{closure}(I_0)$ is $[S \rightarrow S. + R]$.

Shifting the dot gives the kernel item:

Step 3: Compute the closure of the kernel item

We apply the closure rules to the kernel set:

1. Start with the kernel item: $$[S \rightarrow S + . R]$$
2. Since the dot is before the non-terminal $R$, we add all $R$-productions with the dot at the beginning: $$[R \rightarrow . R * P]$$ $$[R \rightarrow . P]$$
3. In $[R \rightarrow . P]$, the dot is before the non-terminal $P$, so we add all $P$-productions with the dot at the beginning: $$[P \rightarrow . (S)]$$ $$[P \rightarrow . \text{id}]$$

Combining all these, the final set of items in $\text{goto}(\text{closure}(I_0), +)$ is:

Counting the items, we find there are exactly 5 items in the set.