GATE 2024 CS1 Q.38: solution and answer

GATE 2024 · CS1Q.38 · 2 marks · MCQ

Consider the following grammar $G$ , with $S$ as the start symbol. The grammar $G$ has three incomplete productions denoted by (1), (2), and (3).

S \to d a T ∣ \underline{(1)} T \to a S ∣ b T ∣ \underline{(2)} R \to \underline{(3)} ∣ ε

The set of terminals is ${a, b, c, d, f}$ . The FIRST and FOLLOW sets of the different non-terminals are as follows.

$FIRST (S) = {c, d, f}$ , $FIRST (T) = {a, b, ε}$ , $FIRST (R) = {c, ε}$

$FOLLOW (S) = FOLLOW (T)$ is the set of the three symbols $c$ , $f$ and the end marker $, and $FOLLOW (R) = {f}$ .

Which one of the following options CORRECTLY fills in the incomplete productions?

(A)
(1) $S \to R f$ , (2) $T \to ε$ , (3) $R \to c T R$
(B)
(1) $S \to f R$ , (2) $T \to ε$ , (3) $R \to c T R$
(C)
(1) $S \to f R$ , (2) $T \to c T$ , (3) $R \to c R$
(D)
(1) $S \to R f$ , (2) $T \to c T$ , (3) $R \to c R$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Option A: (1) $S \to R f$ , (2) $T \to ε$ , (3) $R \to c T R$ .

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

$FIRST (S) = {c, d, f}$ . The production $S \to d a T$ supplies only $d$ , so production (1) must supply both $c$ and $f$ .
$S \to f R$ has $FIRST = {f}$ , which misses $c$ . So options B and C are out.
$S \to R f$ : $R$ is nullable, so $FIRST (R f) = (FIRST (R) ∖ {ε}) \cup {f} = {c, f}$ . This works. It also puts $f$ in $FOLLOW (R)$ , as given.
$FIRST (T) = {a, b, ε}$ contains neither $c$ nor anything else that $T \to c T$ could add. $T \to c T$ would add $c$ to $FIRST (T)$ , and $ε$ would still have no source. Option D is out.
$T \to ε$ is the only choice that supplies the $ε$ in $FIRST (T)$ . Production (2) is $T \to ε$ .
Check (3) $R \to c T R$ . $FIRST (R) = {c, ε}$ is correct. For $FOLLOW (T)$ , take $FIRST (R) ∖ {ε} = {c}$ . Since $R$ is nullable, add $FOLLOW (R) = {f}$ . From $S \to d a T$ , $FOLLOW (T) \supseteq FOLLOW (S)$ , and $ is in $FOLLOW (S)$ because $S$ is the start symbol. From $T \to a S$ , $FOLLOW (S) \supseteq FOLLOW (T)$ . Together these give $FOLLOW (S) = FOLLOW (T) = {c, f}$ plus the end marker $, as stated. Also $FOLLOW (R)$ stays ${f}$ : $R \to c T R$ only adds $FOLLOW (R)$ to itself.
Answer: option A.

KEY IDEA

A production for a non-terminal must contribute exactly the missing terminals to its FIRST set, and a nullable non-terminal contributes its FOLLOW set to whatever precedes it. Use FIRST to pick (1) and (2), then verify (3) and the FOLLOW sets.

WATCH OUT FOR

Writing $S \to f R$ and forgetting that FIRST of a string starting with a nullable $R$ must include FIRST( $R$ ) minus $ε$ and so reaches past it. Also, adding $T \to c T$ without noticing it puts $c$ into FIRST( $T$ ), which the given set forbids.

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

GATE 2024 CS1 Q.38: solution and answer

Answer and solution

More Parsing questions