GATE 2024 CS2 Q.40: solution and answer

GATE 2024 · CS2Q.40 · 2 marks · MCQ

Consider the following context-free grammar where the start symbol is $S$ and the set of terminals is ${a, b, c, d}$ .

$S \to A a A b ∣ B b B a$
$A \to c S ∣ ε$
$B \to d S ∣ ε$

The following is a partially-filled LL(1) parsing table (rows S, A, B; columns a, b, c, d, $).

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.

GATE 2024 CS2 question 40: LL(1) parsing table with columns a, b, c, d, and rows S, A, B. — Figure from the GATE 2024 CS2 paper. It is part of the question.

(A)
(1) S -> AaAb (2) S -> BbBa (3) A -> epsilon (4) B -> epsilon
(B)
(1) S -> BbBa (2) S -> AaAb (3) A -> epsilon (4) B -> epsilon
(C)
(1) S -> AaAb (2) S -> BbBa (3) blank (4) blank
(D)
(1) S -> BbBa (2) S -> AaAb (3) blank (4) blank

Answer and solution

ANSWER

Option A: (1) $S \to A a A b$ , (2) $S \to B b B a$ , (3) $A \to ε$ , (4) $B \to ε$ .

Official answer: ASource: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

Rule for an LL(1) table: put $A \to α$ in column $t$ if $t \in FIRST (α)$ , or if $ε \in FIRST (α)$ and $t \in FOLLOW (A)$ .
$FIRST (A a A b)$ : $A$ can start with $c$ or vanish, so we get $c$ and then $a$ . Hence $FIRST (A a A b) = {c, a}$ .
$FIRST (B b B a)$ : $B$ can start with $d$ or vanish, so we get $d$ and then $b$ . Hence $FIRST (B b B a) = {d, b}$ .
Cell (1) is $[S, c]$ . Since $c \in FIRST (A a A b)$ , it holds $S \to A a A b$ . Cell (2) is $[S, d]$ . Since $d \in FIRST (B b B a)$ , it holds $S \to B b B a$ .
$FOLLOW (A)$ : in $S \to A a A b$ the first $A$ is followed by $a$ and the second $A$ by $b$ . So ${a, b} \subseteq FOLLOW (A)$ . ( $A$ occurs nowhere else on a right-hand side.)
Cell (3) is $[A, b]$ . Since $b \in FOLLOW (A)$ , we place $A \to ε$ there. Column $a$ already shows the same entry.
$FOLLOW (B)$ : in $S \to B b B a$ the first $B$ is followed by $b$ and the second $B$ by $a$ . So ${a, b} \subseteq FOLLOW (B)$ .
Cell (4) is $[B, a]$ . Since $a \in FOLLOW (B)$ , we place $B \to ε$ there. The given $[B, b]$ entry agrees.
So (1) $S \to A a A b$ , (2) $S \to B b B a$ , (3) $A \to ε$ , (4) $B \to ε$ , which is option A.

KEY IDEA

An LL(1) table entry for $A \to α$ goes under every terminal in $FIRST (α)$ , and, when $α$ can derive $ε$ , also under every terminal in $FOLLOW (A)$ . Here $FIRST (A a A b) = {c, a}$ , $FIRST (B b B a) = {d, b}$ and $FOLLOW (A) = FOLLOW (B) = {a, b}$ .

WATCH OUT FOR

Using only FIRST sets and leaving the $ε$ -entries blank (options C and D). The $ε$ -production must also be entered under every terminal of FOLLOW. Another slip is swapping the two $S$ productions, forgetting that a nullable leading symbol makes $c$ or $d$ select the production that begins with $A$ or $B$ respectively.

From the GATE 2024 CS2 paper. Every question of this paper · Download the full paper · All 13 Parsing questions, with notes

GATE 2024 CS2 Q.40: solution and answer

Answer and solution

More Parsing questions