Question

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 \epsilon \), \( \epsilon \) 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 \epsilon \), \( \epsilon \) 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.

Hint:

In top-down parsing, \( \epsilon \) is added to \( {First}(A) \) if a production \( A \to \epsilon \) exists. Additionally, the end-of-input marker is always added to \( {Follow}(S) \), where \( S \) is the start symbol.

Answer 1

The Correct Option is A, D

Step 1: Understand the First and Follow Sets
The First set of a non-terminal \( A \) contains the set of terminal symbols that can begin the strings derived from \( A \). If \( A \to \epsilon \), then \( \epsilon \) is added to \( \text{First}(A) \), since \( A \) can derive the empty string.

The Follow set of a non-terminal \( A \) contains the set of terminal symbols that can appear immediately to the right of \( A \) in any derivation. If \( A \) is the start symbol \( S \), then the end-of-input marker (denoted as \( \$ \)) is added to \( \text{Follow}(S) \).

Step 2: Analyzing Each Option
(A) For a production \( A \to \epsilon \), \( \epsilon \) will be added to \( \text{First}(A) \).
This is correct because if a non-terminal \( A \) can derive the empty string, then \( \epsilon \) is included in \( \text{First}(A) \).

(B) If there is any input right end marker, it will be added to \( \text{First}(S) \), where \( S \) is the start symbol.
This is incorrect because the end-of-input marker is part of the Follow set of the start symbol \( S \), not the First set.

(C) For a production \( A \to \epsilon \), \( \epsilon \) will be added to \( \text{Follow}(A) \).
This is incorrect because \( \epsilon \) is only added to \( \text{First}(A) \), not \( \text{Follow}(A) \).

(D) If there is any input right end marker, it will be added to \( \text{Follow}(S) \), where \( S \) is the start symbol.
This is correct because the end-of-input marker is added to the Follow set of the start symbol \( S \), as it denotes the end of the input string.

Thus, the correct answers are (A) and (D).