4.1 FIRST and FOLLOW Sets: Mathematical Formulations & Computation Algorithms

Back to DBMS Notes

📚Module 01FIRST and FOLLOW Sets: Formulations & Computation⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Forward Radar and The Trailing Shadow

Imagine standing at a train terminal deciding which track an incoming express train will arrive on:

1. $\text{FIRST}(\alpha)$ (The Forward Radar): You look down the track through a telescope. What color headlights could possibly appear first around the bend? If you see a green light, you know instantly it is the Northern Express. $\text{FIRST}(\alpha)$ is the set of all terminal characters that can appear as the very first symbol in any string derived from $\alpha$.
2. $\text{FOLLOW}(A)$ (The Trailing Shadow): Suppose a train car is completely transparent or empty ($\epsilon$). You look past it to see what car is coupled immediately behind it! $\text{FOLLOW}(A)$ is the set of all terminal symbols that can legally appear immediately to the right of non-terminal $A$ across all valid sentences in the language.

💻 Bridging to Computer Science: Predictive Lookahead Routing via FIRST and FOLLOW

In top-down predictive parsing, when the parser encounters a non-terminal $A$ on top of its stack and observes an incoming lookahead token $a$, it must choose which production rule to expand without backtracking:

• If $a \in \text{FIRST}(\alpha)$, the parser confidently expands $A \to \alpha$.
• If $\alpha$ can derive the empty string ($\epsilon \in \text{FIRST}(\alpha)$), the non-terminal $A$ effectively disappears! The parser then consults $\text{FOLLOW}(A)$: if $a \in \text{FOLLOW}(A)$, the parser applies the derivation $A \to \epsilon$.

📑Table of Contents

• 🏗️ Architectural Foundations & Lookahead Mechanics
  • ⚖️ FIRST vs FOLLOW: Conceptual Duals
• 📐 Formal Mathematical Definitions & Inductive Algorithms
  • 🔦 The FIRST Function
  • 👥 The FOLLOW Function
• 🏭 Real-World Production Context: How Industry Builds This
• 📐 Numerical Applications & Worked Examples
  • Example 1: The Canonical Arithmetic Expression Grammar
  • Example 2: Multi-Symbol Epsilon Cascades and Follow Propagation
• 🎯 Exam & Interview Pitfall Check

---

🏗️ Architectural Foundations & Lookahead Mechanics

Architecture Flow

The Predictive Lookahead Routing Pipeline

How top-down parsers use FIRST and FOLLOW sets to resolve deterministic production choices

📥Input

Lookahead Token (a)

Next unconsumed terminal symbol from the lexical token stream.

→

Queries

🔦Rule 1

FIRST(α) Inspection

If a ∈ FIRST(α), select production A → α deterministically.

→

Nullable?

👥Rule 2

FOLLOW(A) Fallback

If ε ∈ FIRST(α) and a ∈ FOLLOW(A), apply reduction A → ε.

→

Resolves

🎯Table

Deterministic Slot M[A, a]

Exact production rule populated in the LL(1) parsing table.

⚖️ FIRST vs FOLLOW: Conceptual Duals

FIRST vs FOLLOW: Conceptual Duals

Contrasting leading terminal sets against trailing context sets

Leading Symbols

FIRST(α)

🔦

Dominant Architecture / DomainDefined for Terminals, Non-Terminals, and Strings

• •The set of terminals that can begin strings derived from α.
• •Calculated for both terminals (T) and non-terminals (V).
• •Can contain the empty string symbol ε if α can derive ε.
• •Never contains the input end-marker `$` under normal circumstances.

"What terminal symbol does this grammatical construct start with?"

Trailing Symbols

FOLLOW(A)

👥

Dominant Architecture / DomainDefined ONLY for Non-Terminals (V)

• •The set of terminals that can appear immediately to the right of A.
• •Calculated STRICTLY for non-terminals (never for terminals).
• •CANNOT EVER contain ε under any circumstances.
• •Always contains the input end-marker `$` for the start symbol S.

"What terminal can legally follow this construct when it finishes or disappears?"

---

📐 Formal Mathematical Definitions & Inductive Algorithms

🔦 The FIRST Function

For any grammar symbol $X \in (V \cup \Sigma)$ or string of symbols $\alpha \in (V \cup \Sigma)^*$:

📖Formal Definition: The FIRST Functiondefinition

$$\text{FIRST}(\alpha) = \{ a \in \Sigma \mid \alpha \Rightarrow^* a \beta \text{ for some string } \beta \} \cup \{ \epsilon \mid \alpha \Rightarrow^* \epsilon \}$$

Inductive Rules to Compute FIRST:

1. If $X$ is a Terminal: $\text{FIRST}(X) = \{ X \}$
2. If $X \to \epsilon$ is a Production: $\epsilon \in \text{FIRST}(X)$
3. If $X \to Y_1 Y_2 \dots Y_k$ is a Production:
   • Add $\text{FIRST}(Y_1) \setminus \{\epsilon\}$ to $\text{FIRST}(X)$.
   • If $\epsilon \in \text{FIRST}(Y_1)$, also add $\text{FIRST}(Y_2) \setminus \{\epsilon\}$ to $\text{FIRST}(X)$.
   • Continue in order: for any $i \le k$, if $\epsilon \in \text{FIRST}(Y_j)$ for all $1 \le j < i$, add $\text{FIRST}(Y_i) \setminus \{\epsilon\}$ to $\text{FIRST}(X)$.
   • If $\epsilon \in \text{FIRST}(Y_j)$ for all $1 \le j \le k$, then add $\epsilon$ to $\text{FIRST}(X)$ (meaning $X$ is completely nullable).

---

👥 The FOLLOW Function

For any non-terminal $A \in V$:

📖Formal Definition: The FOLLOW Functiondefinition

$$\text{FOLLOW}(A) = \{ a \in \Sigma \mid S \Rightarrow^* \alpha A a \beta \text{ for some } \alpha, \beta \in (V \cup \Sigma)^* \} \cup \{ \$ \mid S \Rightarrow^* \alpha A \}$$

Inductive Rules to Compute FOLLOW:

1. Start Symbol Rule: $\$ \in \text{FOLLOW}(S) \quad \text{where } S \text{ is the start symbol of the grammar.}$
2. Direct Successor Rule: If there is a production of the form $B \to \alpha A \beta$: $\big( \text{FIRST}(\beta) \setminus \{\epsilon\} \big) \subseteq \text{FOLLOW}(A)$ (Whatever begins $\beta$ immediately follows $A$).
3. Transmission / Nullable Suffix Rule: If there is a production of the form:
   • $B \to \alpha A$, OR
   • $B \to \alpha A \beta$ where $\epsilon \in \text{FIRST}(\beta)$ (i.e. $\beta \Rightarrow^* \epsilon$): $\text{FOLLOW}(B) \subseteq \text{FOLLOW}(A)$ (Since $\beta$ disappears or $A$ is the final symbol of the rule, whatever can trail $B$ also legally trails $A$).

Cardinal Rule: $\epsilon$ is NEVER an element of any $\text{FOLLOW}$ set! $\text{FOLLOW}$ sets consist strictly of input terminals and $ (the input end-marker).

---

🏭 Real-World Production Context: How Industry Builds This

In industrial compiler engines (such as recursive-descent parsers in GCC, Clang, and Roslyn):

When a recursive-descent parser encounters a syntax error while executing the parsing function for non-terminal $A$, it initiates Panic-Mode Error Recovery:

• The parser does not crash. Instead, it enters a token-skipping loop until it encounters a token in $\text{FOLLOW}(A)$.
• It then cleanly returns from function parse_A(), popping $A$ from the virtual call stack and allowing the parent grammar rule to resume parsing the remainder of the file.

Automated parser tools compute $\text{FIRST}$ and $\text{FOLLOW}$ sets across the entire grammar during compilation:

• If $\text{FIRST}(\alpha) \cap \text{FIRST}(\beta) \neq \emptyset$, the generator immediately flags a First/First Conflict.
• If $\epsilon \in \text{FIRST}(\alpha)$ and $\text{FIRST}(\alpha) \cap \text{FOLLOW}(A) \neq \emptyset$, the generator flags a First/Follow Conflict.

---

📐 Numerical Applications & Worked Examples

Example 1: The Canonical Arithmetic Expression Grammar

Compute the complete $\text{FIRST}$ and $\text{FOLLOW}$ sets for the unambiguous arithmetic expression grammar:

$$\begin{aligned} E &\to T E' \\ E' &\to + T E' \mid \epsilon \\ T &\to F T' \\ T' &\to * F T' \mid \epsilon \\ F &\to ( E ) \mid \text{id} \end{aligned}$$

Step-by-Step Analytical Solution:

Step 1: Compute FIRST Sets (Bottom-Up Evaluation)

• For $F \to ( E ) \mid \text{id}$:
  • Leading terminals are '(' and 'id'.
  • $\text{FIRST}(F) = \{ (, \text{id} \}$
• For $T' \to * F T' \mid \epsilon$:
  • Leading terminal is '*', plus $\epsilon$.
  • $\text{FIRST}(T') = \{ *, \epsilon \}$
• For $T \to F T'$:
  • Begins with $F$. Since $\epsilon \notin \text{FIRST}(F)$, $\text{FIRST}(T) = \text{FIRST}(F) = \{ (, \text{id} \}$.
• For $E' \to + T E' \mid \epsilon$:
  • Leading terminal is '+', plus $\epsilon$.
  • $\text{FIRST}(E') = \{ +, \epsilon \}$
• For $E \to T E'$:
  • Begins with $T$. Since $\epsilon \notin \text{FIRST}(T)$, $\text{FIRST}(E) = \text{FIRST}(T) = \{ (, \text{id} \}$.

Step 2: Compute FOLLOW Sets

• Start Symbol: Add $ to $\text{FOLLOW}(E)$:

$$\text{FOLLOW}(E) = \{ \$ \}$$

• Inspect occurrences of $E$:
  • In $F \to ( E )$: Followed by ')'. Add ')' to $\text{FOLLOW}(E)$:

$$\text{FOLLOW}(E) = \{ ), \$ \}$$

• Inspect occurrences of $E'$:
  • In $E \to T E'$: $E'$ is at the end:

$$\text{FOLLOW}(E') = \text{FOLLOW}(E) = \{ ), \$ \}$$

• In $E' \to + T E'$: Adds $\text{FOLLOW}(E')$ to itself (no new tokens):

$$\text{FOLLOW}(E') = \{ ), \$ \}$$

• Inspect occurrences of $T$:
  • In $E \to T E'$: Followed by $E'$. Add $\text{FIRST}(E') \setminus \{\epsilon\} = \{ + \}$.
  • Since $\epsilon \in \text{FIRST}(E')$, also add $\text{FOLLOW}(E)$:

$$\text{FOLLOW}(T) = \{ +, ), \$ \}$$

• Inspect occurrences of $T'$:
  • In $T \to F T'$: $T'$ is at the end:

$$\text{FOLLOW}(T') = \text{FOLLOW}(T) = \{ +, ), \$ \}$$

• Inspect occurrences of $F$:
  • In $T \to F T'$: Followed by $T'$. Add $\text{FIRST}(T') \setminus \{\epsilon\} = \{ * \}$.
  • Since $\epsilon \in \text{FIRST}(T')$, also add $\text{FOLLOW}(T)$:

$$\text{FOLLOW}(F) = \{ *, +, ), \$ \}$$

Consolidated Sets:

Non-Terminal	FIRST Set	FOLLOW Set
E	(, id	), $
E'	+, ε	), $
T	(, id	+, ), $
T'	*, ε	+, ), $
F	(, id	*, +, ), $

---

Example 2: Multi-Symbol Epsilon Cascades and Follow Propagation

Compute the $\text{FIRST}$ and $\text{FOLLOW}$ sets for the following grammar featuring multi-symbol epsilon cascades:

$$\begin{aligned} S &\to a B D h \\ B &\to c C \\ C &\to b \mid \epsilon \\ D &\to E F \\ E &\to g \mid \epsilon \\ F &\to f \mid \epsilon \end{aligned}$$

Step-by-Step Analytical Solution:

Step 1: Compute FIRST Sets

• $\text{FIRST}(C) = \{ b, \epsilon \}$
• $\text{FIRST}(B) = \{ c \}$ (begins with terminal $c$)
• $\text{FIRST}(E) = \{ g, \epsilon \}$
• $\text{FIRST}(F) = \{ f, \epsilon \}$
• For $D \to E F$:
  • Add $\text{FIRST}(E) \setminus \{\epsilon\} = \{ g \}$.
  • Since $\epsilon \in \text{FIRST}(E)$, add $\text{FIRST}(F) \setminus \{\epsilon\} = \{ f \}$.
  • Since both $E$ and $F$ derive $\epsilon$, add $\epsilon$.
  • $\text{FIRST}(D) = \{ g, f, \epsilon \}$.
• For $S \to a B D h$:
  • Begins with terminal $a \implies \text{FIRST}(S) = \{ a \}$.

Step 2: Compute FOLLOW Sets

• Start Symbol: Add $ to $\text{FOLLOW}(S)$:

$$\text{FOLLOW}(S) = \{ \$ \}$$

• For non-terminal $B$ in $S \to a B D h$:
  • Followed by $D h$.
  • $\text{FIRST}(D h) \setminus \{\epsilon\} = (\text{FIRST}(D) \setminus \{\epsilon\}) \cup \text{FIRST}(h) = \{ g, f, h \}$.
  • $\text{FOLLOW}(B) = \{ g, f, h \}$.
• For non-terminal $C$ in $B \to c C$:
  • $C$ is at the very end of $B \to c C$.
  • $\text{FOLLOW}(C) = \text{FOLLOW}(B) = \{ g, f, h \}$.
• For non-terminal $D$ in $S \to a B D h$:
  • Followed by terminal $h \implies \text{FOLLOW}(D) = \{ h \}$.
• For non-terminal $E$ in $D \to E F$:
  • Followed by $F$. Add $\text{FIRST}(F) \setminus \{\epsilon\} = \{ f \}$.
  • Since $\epsilon \in \text{FIRST}(F)$, add $\text{FOLLOW}(D) = \{ h \}$.
  • $\text{FOLLOW}(E) = \{ f, h \}$.
• For non-terminal $F$ in $D \to E F$:
  • $F$ is at the end of $D \to E F$.
  • $\text{FOLLOW}(F) = \text{FOLLOW}(D) = \{ h \}$.

Final Table of Sets:

Non-Terminal	FIRST Set	FOLLOW Set
S	a	$
B	c	g, f, h
C	b, ε	g, f, h
D	g, f, ε	h
E	g, ε	f, h
F	f, ε	h

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: "Can the empty string symbol ε ever be a member of a FOLLOW set?"
Key Focus Points:

• Strict Rule: $\epsilon$ can NEVER belong to any $\text{FOLLOW}$ set under any circumstances.
• Physical Meaning: $\text{FOLLOW}(A)$ represents the set of concrete terminal tokens that can physically appear after $A$ on the input tape. The empty string is an absence of characters, not a physical character on the input stream.

Question 2: "Can FIRST be computed for terminal symbols? Can FOLLOW be computed for terminal symbols?"
Key Focus Points:

• FIRST: Defined for both terminals and non-terminals: for any terminal $a$, $\text{FIRST}(a) = \{ a \}$.
• FOLLOW: Defined strictly for non-terminals ($V$). The mathematical concept of $\text{FOLLOW}(a)$ for a terminal $a$ is undefined in compiler syntax theory.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Forgetting to add $ to FOLLOW of the start symbol.
Answer: Fatal calculation bug. The input stream always ends with the end-marker $. The start symbol $S$ derives the entire sentence; therefore, $ is universally in $\text{FOLLOW}(S)$. Forgetting $ corrupts all dependent FOLLOW sets.

Trap 2: Propagating ε into FOLLOW when applying Rule 2.
Answer: Follow sets never receive ε. When computing $\text{FOLLOW}(A)$ from $B \to \alpha A \beta$, we take $\text{FIRST}(\beta) \setminus \{\epsilon\}$. If $\beta$ is nullable, we invoke Rule 3 and add $\text{FOLLOW}(B)$, but $\epsilon$ itself is stripped.

---

🗺️View Complete Compiler Design Roadmap & Syllabus

← Previous Topic3.2 Grammar Ambiguity, Left Recursion & Left FactoringNext Topic →4.2 LL(1) Predictive Parsing & Conflict Analysis