GATE CS 2025 Set 1 | Question 46

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

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

Answer

(A), (D)

(A) True: $\epsilon \in First(A)$ whenever $A$ can derive the empty string, and $A \to \epsilon$ does so directly.
(B) False: $First$ sets contain the terminals (and possibly $\epsilon$) that can begin a string derived from a symbol; the end marker $\$$ never goes into a $First$ set.
(C) False: $Follow(A)$ contains the terminals (and $\$$) that can appear just after $A$ in a sentential form; $\epsilon$ is never added to a $Follow$ set.
(D) True: the first rule for $Follow$ sets puts the right end marker $\$$ into $Follow(S)$, because the input ends right after a string derived from $S$.

Answer: A, D