Question 29

Given $I_0 = \{[S' \to S\cdot], [S \to S\cdot + R]\}$.

To compute $\text{goto}(\text{closure}(I_0), +)$:

1. Since the dot is followed by end-of-string in $[S' \to S\cdot]$ and by the terminal '+' in $[S \to S\cdot + R]$, no non-terminals follow the dot. Thus $\text{closure}(I_0) = I_0$.
2. On symbol '+', we shift the dot over '+' in the item $[S \to S\cdot + R]$ to obtain the kernel of the new state:

3. Now compute $\text{closure}(J)$:
   • The dot is immediately before non-terminal $R$. We add all productions for $R$ with the dot at the beginning:
     $$[R \to \cdot R * P], \quad [R \to \cdot P]$$
   • In $[R \to \cdot P]$, the dot is before non-terminal $P$. We add all productions for $P$ with the dot at the beginning:
     $$[P \to \cdot ( S )], \quad [P \to \cdot \text{id}]$$
   • In $[R \to \cdot R * P]$, the dot is before $R$, which is already added.
   • In $[P \to \cdot ( S )]$ and $[P \to \cdot \text{id}]$, the dots are before terminals '(' and 'id', so no further items are added.

Collecting all items in the state:

1. $[S \to S + \cdot R]$
2. $[R \to \cdot R * P]$
3. $[R \to \cdot P]$
4. $[P \to \cdot ( S )]$
5. $[P \to \cdot \text{id}]$

There are exactly 5 items.