GATE CSE 2024 | Set 2 | Question: 30

Question

Consider the following context-free grammar where the start symbol is $\text{S}$ and the set of terminals is $\{a, b, c, d\}$.
\[
\begin{array}{l}
S \rightarrow A a A b \mid B b B a \\
A \rightarrow c S \mid \epsilon \\
B \rightarrow d S \mid \epsilon
\end{array}
\]

The following is a partially-filled $\text{LL}(1)$ parsing table.

	$a$	$b$	$c$	$d$	$ $ $
$S$	$S \rightarrow A a A b$	$S \rightarrow B b B a$	$(1)$	$(2)$
$A$	$A \rightarrow \epsilon$	$(3)$	$A \rightarrow c S$
$B$	$(4)$	$B \rightarrow \epsilon$		$B \rightarrow d S$

Which one of the following options represents the CORRECT combination for the numbered cells in the parsing table?

Note: In the options, "blank" denotes that the corresponding cell is empty.

• A. $(1)$ $S \rightarrow A a A b$ $(2)$ $S \rightarrow B b B a$ $(3)$ $A \rightarrow \epsilon$ $(4)$ $B \rightarrow \epsilon$
• B. $(1)$ $S \rightarrow B b B a$ $(2)$ $S \rightarrow A a A b$ $(3)$ $A \rightarrow \epsilon$ $(4)$ $B \rightarrow \epsilon$
• C. $(1)$ $S \rightarrow A a A b$ $(2)$ $S \rightarrow B b B a$ $(3)$ blank $(4)$ blank
• D. $(1)$ $S \rightarrow B b B a$ $(2)$ $S \rightarrow A a A b$ $(3)$ blank $(4)$ blank

Answer 1

To complete the given LL(1) table first we have to find the FIRST and FOLLOW of the given grammar, that is:

$\begin{array}{|c|c|c|}\hline
&\textsf{FIRST}&\textsf{FOLLOW}\\\hline
S \rightarrow AaAb \mid BbBa & \left \{ a,b,c,d \right \} & \left \{ \$,a,b \right \} \\\hline
A \rightarrow cS  \mid \varepsilon & \left \{ c,\varepsilon \right \} & \left \{ a,b \right \} \\ \hline
B \rightarrow dS\mid  \varepsilon & \left \{ d,\varepsilon \right \} & \left \{ a,b \right \} \\\hline
\end{array}$

Now we can fill the entries in LL(1) table:

$\begin{array}{|c|c|c|c|c|c|c|}\hline
&a&b&c&d&\$ \\ \hline
S &S\rightarrow AaAb &S\rightarrow BbBa &\underset{\boxed{1}} {S \rightarrow AaAb}& \underset{\boxed{2}} {S \rightarrow BbBa}& \\ \hline
A & A \rightarrow \varepsilon &\underset{\boxed{3}}{A \rightarrow  \varepsilon} & A\rightarrow cS& &  \\ \hline
B &\underset{\boxed{4}}{B \rightarrow  \varepsilon} &{B \rightarrow  \varepsilon} & &B\rightarrow dS& \\ \hline
\end{array}$

The correct Option is (A).