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,$ \mid$ 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 FIRST and FOLLOW sets for the non-terminals $A$ and $B$ are

(A)

$\text{FIRST}(A) = \{a, b, \varepsilon\} =\text{FIRST}(B)$ $\text{FOLLOW}(A) = \{a, b\}$ $\text{FOLLOW}(B) = \{a, b, \$ \} $

(B)

$\text{FIRST}(A) = \{a, b, \$ \} $ $\text{FIRST}(B) = \{a, b, \varepsilon\}$ $\text{FOLLOW}(A) = \{a, b\}$ $\text{FOLLOW}(B) = \{\$ \} $

(C)

$\text{FIRST}(A) = \{a, b, \varepsilon\} =\text{FIRST}(B)$ $\text{FOLLOW}(A) =\{a, b\}$ $\text{FOLLOW}(B) = \varnothing$

(D)

$\text{FIRST}(A) = \{a, b\} = \text{FIRST}(B)$ $\text{FOLLOW}(A) = \{a, b\}$ $\text{FOLLOW}(B) =\{a, b\}$