GATE CS 2024 Set 2 — Question 40

MCQ+2 / -0.67MediumLL(1) ParsingSyntax AnalysisCompiler Design

Compiler Design → Syntax Analysis → LL(1) Parsing

Last updated 20 August 2026

Question

Consider the following context-free grammar where the start symbol is

S

and the set of terminals is

\{a,b,c,d\}

S \rightarrow AaAb \mid BbBa

A \rightarrow cS \mid \epsilon

B \rightarrow dS \mid \epsilon

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.

(1)

S \rightarrow AaAb

(2)

S \rightarrow BbBa

(3)

A \rightarrow \epsilon

(4)

B \rightarrow \epsilon

(1)

S \rightarrow BbBa

(2)

S \rightarrow AaAb

(3)

A \rightarrow \epsilon

(4)

B \rightarrow \epsilon

(1)

S \rightarrow AaAb

(2)

S \rightarrow BbBa

(3) blank (4) blank

(1)

S \rightarrow BbBa

(2)

S \rightarrow AaAb

(3) blank (4) blank

(A) (1) S arrow AaAb (2) S arrow BbBa (3) A arrow ε (4) B arrow ε

To determine the entries in the LL(1) parsing table, we first compute the First and Follow sets for the non-terminals.

1. Compute First Sets:

$First(A) = \{c, \epsilon\}$ (from $A \rightarrow cS \mid \epsilon$ )
$First(B) = \{d, \epsilon\}$ (from $B \rightarrow dS \mid \epsilon$ )
$First(S)$ :
For $S \rightarrow AaAb$ : $First(AaAb) = (First(A) \setminus \{\epsilon\}) \cup First(aAb) = \{c\} \cup \{a\} = \{a, c\}$ .
For $S \rightarrow BbBa$ : $First(BbBa) = (First(B) \setminus \{\epsilon\}) \cup First(bBa) = \{d\} \cup \{b\} = \{b, d\}$ .
Thus, $First(S) = \{a, b, c, d\}$ .

2. Compute Follow Sets:

3. Fill the Parsing Table Cells:

Cell (1) for $(S, c)$ : Since $c \in First(AaAb)$ , the entry is $S \rightarrow AaAb$ .
Cell (2) for $(S, d)$ : Since $d \in First(BbBa)$ , the entry is $S \rightarrow BbBa$ .
Cell (3) for $(A, b)$ : Since $b \in Follow(A)$ and $A \rightarrow \epsilon$ is a production, the entry is $A \rightarrow \epsilon$ .
Cell (4) for $(B, a)$ : Since $a \in Follow(B)$ and $B \rightarrow \epsilon$ is a production, the entry is $B \rightarrow \epsilon$ .

Matching these results with the options:
(1)

S \rightarrow AaAb

(2)

S \rightarrow BbBa

(3)

A \rightarrow \epsilon

(4)

B \rightarrow \epsilon

This corresponds to Option (A).