GATE2025_CS1_Q46

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

Note: This is a Multiple Select Question (MSQ). One or more options may be correct.

✅ Final Answer:

The correct options are (A) and (D).

🔹 Short Answer:

Statement (A) is true because if a non-terminal A can derive epsilon (ε), then ε must be in First(A). Statement (D) is true by the definition of Follow sets; the input right end marker ($) is always in the Follow set of the start symbol S. Statements (B) and (C) are false as they incorrectly mix the concepts of First and Follow sets; $ is not part of First sets, and ε is not part of Follow sets.

🔸 Long Answer:

This question tests the fundamental rules for computing First and Follow sets, which are essential for constructing predictive (top-down) parsers like LL(1).

Definitions

• First(A): The set of terminals that can be the first symbol in a string derived from a non-terminal A. If A can derive the empty string ε, then ε is also in First(A).
• Follow(A): The set of terminals that can appear immediately to the right of the non-terminal A in some sentential form. It also includes the special end-of-input marker $ if A can appear at the end of a sentence.

Let's analyze each statement based on these definitions.

Analysis of Options:

• (A) For a production A → ε, ε will be added to First(A).
  This is TRUE. This is one of the core rules for computing First sets. If a non-terminal can directly produce the empty string, then ε is by definition in its First set.
• (B) If there is any input right end marker, it will be added to First(S), where S is the start symbol.
  This is FALSE. The input right end marker ($) is a concept related to what can follow a non-terminal, not what can start a derivation from it. The First set contains terminals from the grammar's alphabet and potentially ε, but never $.
• (C) For a production A → ε, ε will be added to Follow(A).
  This is FALSE. The Follow set, by definition, never contains ε. It only contains terminals and the $ marker. The production A → ε is used to compute the Follow sets of *other* non-terminals. For example, in a production B → C A D, if First(D) contains ε, then everything in Follow(B) is added to Follow(A). The production itself doesn't add ε 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.
  This is TRUE. This is the first rule in computing Follow sets. We always place the end marker $ into Follow(S) to signify that the input string can validly end after the grammar has been fully parsed starting from S.

Summary of Rules:

Rule	Correct Application
Production A → ε	Add ε to First(A). (Statement A is TRUE)
Start Symbol S	Add $ to Follow(S). (Statement D is TRUE)

Bibliography:
- Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2007). Compilers: Principles, Techniques, and Tools (2nd ed.). Pearson/Addison Wesley. (Chapter 4: Syntax Analysis).

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.