GATE CS 2006 Q7 — Parsing (LL, LR)

To determine which items appear in the same canonical set of LR(0) items, let us construct the relevant states of the LR(0) parser starting from the augmented grammar:

$S' \rightarrow S$
$S \rightarrow S * E \mid E$
$E \rightarrow F + E \mid F$
$F \rightarrow id$

Let $I_0$ be the initial state containing the item $S' \rightarrow .S$. Let us trace the transitions:

1. State $I_3 = \text{GOTO}(I_0, F)$: $$\begin{aligned} E &\rightarrow F. + E \quad \text{(Item ii)}\\ E &\rightarrow F. \end{aligned}$$
2. State $I_1 = \text{GOTO}(I_0, S)$ contains $S \rightarrow S. * E$. Transitioning on $*$ gives State $I_5 = \text{GOTO}(I_1, *)$: $$\begin{aligned} S &\rightarrow S * . E \quad \text{(Item i)}\\ E &\rightarrow .F + E\\ E &\rightarrow .F\\ F &\rightarrow .id \end{aligned}$$
3. From State $I_3$, transitioning on $+$ gives State $I_6 = \text{GOTO}(I_3, +)$: $$\begin{aligned} E &\rightarrow F + . E \quad \text{(Item iii)}\\ E &\rightarrow .F + E\\ E &\rightarrow .F\\ F &\rightarrow .id \end{aligned}$$

As we can see, Item (i) is in state $I_5$, Item (ii) is in state $I_3$, and Item (iii) is in state $I_6$. No two of these items appear together in any single set of the canonical collection. Therefore, the correct option is D.