Consider the following context-free grammar where the start symbol is $S$ and the set of terminals is $\{a,b,c,d\}$. $$\begin{aligned} S &\to AaAb \mid BbBa A &\to cS \mid \epsilon B &\to dS \mid \epsilon \end{aligned}$$ The following is a partially-filled LL(1) parsing table. 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.

To determine the entries in the LL(1) parsing table, we compute the $\text{FIRST}$ and $\text{FOLLOW}$ sets for each non-terminal.

### 1. First Sets

• $\text{FIRST}(A) = \{c, \epsilon\}$

• $\text{FIRST}(B) = \{d, \epsilon\}$

• For production $S \to AaAb$:

  $$\text{FIRST}(AaAb) = (\text{FIRST}(A) \setminus \{\epsilon\}) \cup \text{FIRST}(aAb) = \{c\} \cup \{a\} = \{a, c\}$$

  Therefore, $S \to AaAb$ is entered in $M[S, a]$ and $M[S, c]$.

  • Cell (1) is $M[S, c]$, so (1) = $S \to AaAb$.

• For production $S \to BbBa$:

  $$\text{FIRST}(BbBa) = (\text{FIRST}(B) \setminus \{\epsilon\}) \cup \text{FIRST}(bBa) = \{d\} \cup \{b\} = \{b, d\}$$

  Therefore, $S \to BbBa$ is entered in $M[S, b]$ and $M[S, d]$.

  • Cell (2) is $M[S, d]$, so (2) = $S \to BbBa$.

### 2. Follow Sets for $\epsilon$-productions

• For production $A \to \epsilon$, the entry is placed in $M[A, t]$ for every $t \in \text{FOLLOW}(A)$. From $S \to AaAb$, $A$ appears before $a$ and also before $b$. Thus, $\{a, b\} \subseteq \text{FOLLOW}(A)$. Therefore, $A \to \epsilon$ is placed in $M[A, a]$ and $M[A, b]$.

  • Cell (3) is $M[A, b]$, so (3) = $A \to \epsilon$.

• For production $B \to \epsilon$, the entry is placed in $M[B, t]$ for every $t \in \text{FOLLOW}(B)$. From $S \to BbBa$, $B$ appears before $b$ and also before $a$. Thus, $\{a, b\} \subseteq \text{FOLLOW}(B)$. Therefore, $B \to \epsilon$ is placed in $M[B, b]$ and $M[B, a]$.

  • Cell (4) is $M[B, a]$, so (4) = $B \to \epsilon$.

Thus, the correct combination is given by (A).