GATEverse — GATE CSE previous year questions

For the grammar below, a partial $LL(1)$ parsing table is also presented along with the grammar. Entries that need to be filled are indicated as $E1, E2,$ and $E3$ . $\varepsilon$ is the empty string, $ indicates end of input, and, | separates alternate right hand sides of productions. $S \rightarrow a A b B \mid b A a B \mid \varepsilon$ $A \rightarrow S$ $B \rightarrow S$

\begin{array}{|l|l|l|l|}\hline \text{} & \textbf{a} & \textbf{b} & \textbf{\$} \\\hline \text{$S$} & \text{E1} & \text{E2} & \text{$S\rightarrow \varepsilon $} \\\hline \text{$A$} & \text{$A\rightarrow S$} & \text{$A\rightarrow S$} & \text{error} \\\hline \text{$B$} & \text{$B\rightarrow S$} & \text{$B\rightarrow S$} & \text{$E3$} \\\hline \end{array}

The appropriate entries for $E1, E2,$ and $E3$ are

(A)

$E1 : S \rightarrow aAbB, A\rightarrow S$ $E2 : S \rightarrow bAaB, B\rightarrow S$ $E3 : B \rightarrow S$

(B)

$E1 : S \rightarrow aAbB, S \rightarrow \varepsilon$ $E2 : S \rightarrow bAaB, S \rightarrow \varepsilon$ $E3 : S \rightarrow \varepsilon$

(C)

$E1 : S \rightarrow aAbB, S \rightarrow \varepsilon$ $E2 : S \rightarrow bAaB, S \rightarrow \varepsilon$ $E3 : B \rightarrow S$

(D)

$E1 : A \rightarrow S, S \rightarrow \varepsilon$ $E2 : B \rightarrow S, S \rightarrow \varepsilon$ $E3 : B \rightarrow S$