📘 FIRST and FOLLOW Sets (Compiler Construction)

in simple language with definitions, rules, examples, steps, and exam tips.

---

🧠 1. Introduction

In syntax analysis (LL(1) parsing), we need to decide which grammar rule to use.

👉 For that, we compute:

• FIRST set
• FOLLOW set

These help in building predictive parsing tables.

---

🔵 2. FIRST Set

✅ Definition

The FIRST set of a symbol is the set of all terminals that can appear as the first symbol in some string derived from it.

---

📌 Notation

FIRST(X)

---

🔧 Rules to Find FIRST Set

---

🔹 Rule 1: Terminal

If X is a terminal:

FIRST(X) = {X}

---

🔹 Rule 2: Non-terminal Production

If:

A → α

Then:

• Add FIRST(α) to FIRST(A)

---

🔹 Rule 3: If ε (epsilon) exists

If:

A → ε

Then:

ε ∈ FIRST(A)

---

🔹 Rule 4: Multiple Symbols

If:

A → X Y Z

Then:

• Add FIRST(X)
• If X → ε, then check Y, and so on

---

📌 Example

Grammar:

E → T E'
E' → + T E' | ε
T → id

---

🔵 FIRST Sets

FIRST(id) = {id}
FIRST(T) = {id}
FIRST(E') = {+, ε}
FIRST(E) = {id}

---

⭐ Key Points (Exam)

• FIRST = starting terminals
• Includes ε if empty string possible
• Used in predictive parsing

---

🟢 3. FOLLOW Set

✅ Definition

The FOLLOW set of a non-terminal is the set of terminals that can appear immediately after it in a derivation.

---

📌 Notation

FOLLOW(A)

---

🔧 Rules to Find FOLLOW Set

---

🔹 Rule 1: Start Symbol

For start symbol S:

$ ∈ FOLLOW(S)

($ = end of input marker)

---

🔹 Rule 2: If A → αBβ

Then:

FIRST(β) - ε ⊆ FOLLOW(B)

---

🔹 Rule 3: If A → αB

Then:

FOLLOW(A) ⊆ FOLLOW(B)

---

🔹 Rule 4: If β → ε

Then also:

FOLLOW(A) ⊆ FOLLOW(B)

---

📌 Example

Grammar:

E → T E'
E' → + T E' | ε
T → id

---

🔵 FOLLOW Sets

Step-by-step:

FOLLOW(E) = {$}
FOLLOW(E') = {$}
FOLLOW(T) = {+, $}

---

⭐ Key Points (Exam)

• FOLLOW = what comes after a variable
• Start symbol always has $
• Used in parsing table construction

---

🔄 4. Difference Between FIRST and FOLLOW

Feature	FIRST Set	FOLLOW Set
Meaning	First terminal in derivation	What follows a non-terminal
Applies to	Terminal & Non-terminal	Only Non-terminal
Includes ε	Yes	No
Used for	Starting rule selection	Parsing decision making
Input direction	Left side	Right side

---

🧪 5. Combined Example (Important Exam Type)

Grammar:

E → T E'
E' → + T E' | ε
T → id

---

🔵 FIRST

FIRST(E) = {id}
FIRST(E') = {+, ε}
FIRST(T) = {id}

---

🟢 FOLLOW

FOLLOW(E) = {$}
FOLLOW(E') = {$}
FOLLOW(T) = {+, $}

---

🧠 6. Why FIRST and FOLLOW are Important

They are used to build:

👉 LL(1) Parsing Table

• FIRST decides which rule to choose
• FOLLOW helps when ε appears

---

⚠️ 7. Common Exam Mistakes

• Forgetting $ in FOLLOW of start symbol
• Ignoring ε in FIRST
• Mixing FIRST and FOLLOW rules
• Not checking all productions

---

🎯 8. Important Exam Questions

👉 Frequently asked:

• Define FIRST set with example
• Define FOLLOW set with example
• Difference between FIRST and FOLLOW
• Compute FIRST and FOLLOW for given grammar
• Use FIRST and FOLLOW in LL(1) parsing
• Importance of ε in FIRST

---

📝 9. Short Notes (Quick Revision)

🔵 FIRST

• First terminal of derivation
• Includes ε if needed

🟢 FOLLOW

• Symbols that follow a non-terminal
• Start symbol has $

---

📊 10. Final Summary Table

Aspect	FIRST Set	FOLLOW Set
Definition	First terminal in derivation	Next possible terminals
Symbol Type	Terminal / Non-terminal	Non-terminal only
ε Handling	Included	Not included
Start Symbol	Not special	Contains $
Use	Parsing decisions	Parsing table creation
Importance	Very High	Very High

---

✅ Final Conclusion

• FIRST set tells what can appear at the beginning
• FOLLOW set tells what can appear after a symbol
• Both are fundamental for LL(1) parsing and compiler design

---