GATE 2025 CS1 Q.46: solution and answer

GATE 2025 · CS1Q.46 · 2 marks · MSQ

Which of the following statement(s) is/are TRUE while computing First and Follow during top down parsing by a compiler?

(A)
For a production $A \to ϵ$ , $ϵ$ will be added to $First (A)$ .
(B)
If there is any input right end marker, it will be added to $First (S)$ , where $S$ is the start symbol.
(C)
For a production $A \to ϵ$ , $ϵ$ will be added to $Follow (A)$ .
(D)
If there is any input right end marker, it will be added to $Follow (S)$ , where $S$ is the start symbol.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Options A and D are true.

Official answer: A, DSource: Official answer key, GATE 2025 CS1 (IIT Roorkee)

$FIRST (A)$ holds the terminals that can begin a string derived from $A$ , plus $ε$ if $A \Rightarrow^{*} ε$ .
(A) With the production $A \to ε$ , $A$ derives the empty string, so $ε \in FIRST (A)$ . TRUE.
(B) The end marker $ is not a grammar symbol, so it is never the first symbol of a string derived from $S$ and never enters any FIRST set. FALSE.
(C) $FOLLOW (A)$ holds the terminals that can come right after $A$ , plus the end marker. $ε$ is not a terminal and never appears in a FOLLOW set. FALSE.
(D) The first rule for FOLLOW is: put $ in $FOLLOW (S)$ for the start symbol $S$ , because the input ends right after the whole string derived from $S$ . TRUE.
Correct options: A and D.

KEY IDEA

$ε$ belongs only in FIRST sets (when a symbol can derive the empty string); the end marker $ belongs only in FOLLOW sets, starting with $FOLLOW (S)$ for the start symbol.

WATCH OUT FOR

Mixing up the two sets: adding $ε$ to a FOLLOW set because of $A \to ε$ , or adding the end marker $ to $FIRST (S)$ .

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

GATE 2025 CS1 Q.46: solution and answer

Answer and solution

More Parsing questions