FIRST and FOLLOW sets

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• When does a recursive-descent parser need to backtrack? from Lesson 2.3.1
• In E → E + T | T, T → T * F | F, which operator has higher precedence? from Lesson 2.1.2
• Write the regular definition of number for a lexer. from Lesson 1.2.1

1 · The Story

📖

Two lists per category

To stop Chetan’s rewinding, Kabir makes two lists for every category in the rulebook.

The starter list: which real words can begin a phrase of this category? A Subject can start with “the” or with a name like “Ramesh”. If one of the rules for a category can produce nothing at all, Kabir notes that too.

The follower list: which real words can come right after a phrase of this category in some proper sentence? After a Subject comes a Verb, so the starters of Verb are followers of Subject. And at the very end of a speech comes the end mark, written $.

Now when Chetan must choose a rule, he looks at the next word: if it is a starter of exactly one rule, take that rule. If a rule can produce nothing, take it when the next word is a follower of the category.

2 · Predict First

🤔

In S → A B C, A → a | ε, B → b | ε, C → c: which tokens can follow A? Write your guess down. The answer is in the vault.

3 · Core Concept

FIRST

For any string α of grammar symbols, FIRST(α) is the set of terminals that begin strings derived from α; if α ⇒* ε, then ε is also in FIRST(α).

Rules for FIRST(X) of one symbol:

• X a terminal: FIRST(X) = {X}.
• X → ε is a production: add ε.
• X → Y₁ Y₂ … Yₖ: add FIRST(Y₁) without ε; if Y₁ can derive ε, also add FIRST(Y₂) without ε; and so on. If all Y₁ … Yₖ can derive ε, add ε.

FIRST(Y₁ … Yₖ) of a string is computed the same way. A nonterminal that can derive ε is called nullable.

FOLLOW

For a nonterminal A, FOLLOW(A) is the set of terminals that can appear immediately to the right of A in some sentential form; $ (end of input) is in FOLLOW(A) if A can be the last symbol.

• Put $ in FOLLOW(S) for the start symbol S.
• For A → α B β: add FIRST(β) without ε to FOLLOW(B).
• For A → α B, or A → α B β with ε ∈ FIRST(β): add everything in FOLLOW(A) to FOLLOW(B).

Repeat until nothing changes. FOLLOW sets never contain ε.

Convention for $

Textbooks and GATE put the end marker $ in FOLLOW of the start symbol (rule 1), and it then spreads by rule 3. A few books write ⊣ or # for it. Questions always count $ as an element of FOLLOW when it is there.

How to compute by hand

• Mark nullable nonterminals first.
• FIRST: go through each production left to right, stopping at the first non-nullable symbol.
• FOLLOW: for every occurrence of each nonterminal B on a right side, look at what comes after it; if that can vanish (or nothing comes after), inherit FOLLOW of the left side.
• Iterate until stable.

Story → compiler term

4 · Visual

E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | id

S → A B C
A → a | ε
B → b | ε
C → c

5 · Worked Examples

Example 1 Easy

Compute FIRST and FOLLOW for E → T E′, E′ → + T E′ | ε, T → F T′, T′ → * F T′ | ε, F → ( E ) | id.

Solution

FIRST(F) = { (, id }. T → F T′ and E → T E′ give FIRST(T) = FIRST(E) = { (, id }. FIRST(E′) = { +, ε }, FIRST(T′) = { *, ε }.

FOLLOW(E) = { ), $ } ($ by rule 1, ) from F → ( E )). E′ is at the end of E’s productions: FOLLOW(E′) = FOLLOW(E). T is followed by E′, so FOLLOW(T) = FIRST(E′) − ε ∪ FOLLOW(E) = { +, ), $ }; FOLLOW(T′) = FOLLOW(T). F is followed by T′: FOLLOW(F) = { * } ∪ FOLLOW(T) = { +, *, ), $ }. See the first table.

Example 2 Medium

For S → A B C, A → a | ε, B → b | ε, C → c, compute FIRST(S), FOLLOW(A), FOLLOW(B).

Solution

A and B are nullable, C is not. FIRST(S) = { a } ∪ { b } ∪ { c } = { a, b, c } (ε is not in it, because C cannot vanish).

FOLLOW(A) = FIRST(B C) − ε = { b, c }. FOLLOW(B) = FIRST(C) = { c }. FOLLOW(C) = FOLLOW(S) = { $ }. These are Kabir’s follower lists: after an A may come a b, or a c if B is empty.

Example 3 GATE

For S → a A B | b A, A → c A | ε, B → d | ε: find FOLLOW(A) and FOLLOW(B).

Solution

From S → a A B: FIRST(B) − ε = { d } ⊆ FOLLOW(A), and since B is nullable, FOLLOW(S) = { $ } ⊆ FOLLOW(A). From S → b A: FOLLOW(S) ⊆ FOLLOW(A). From A → c A: FOLLOW(A) ⊆ FOLLOW(A) (nothing new).

FOLLOW(A) = { d, $ }, FOLLOW(B) = { $ }.

6 · Shortcuts

⚡

FOLLOW checklist: (1) $ for the start symbol; (2) what stands right after B in every production; (3) if that can vanish or B is last, add FOLLOW of the left side. Valid when: every FOLLOW computation; iterate until no set grows.

⚡

Nullable first: a nonterminal is nullable if some production has a right side made only of nullable symbols (or ε). Valid when: grammars with ε-productions, where most mistakes happen.

7 · GATE Traps

⚠️

• FOLLOW never contains ε. FIRST may.
• FIRST of a production right side stops at the first non-nullable symbol.
• $ belongs to FOLLOW(start symbol) and spreads only through rule 3.
• A nonterminal appearing several times on right sides contributes several times to FOLLOW.
• FIRST(S) for S → A B C excludes ε if C is not nullable, even if A and B are.

8 · Memory Hook

🧠

FIRST = who can open the door; FOLLOW = who can walk in right after. ε may open (FIRST), but never walks in (FOLLOW).

9 · Connect the Dots

With FIRST and FOLLOW you can fill a table: for each nonterminal and each next token, which production to use. The next lesson builds that table, tests whether it has clashes, and runs the parser with a stack.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markFOLLOW

Which can never be an element of a FOLLOW set?

• (A) $
• (B) ε
• (C) a terminal
• (D) )

Q2MSQ1 markFIRST

For S → X Y z, X → x X | ε, Y → y Y | ε, which are in FIRST(S)?

• (A) x
• (B) y
• (C) z
• (D) ε

Q3NAT1 markFOLLOW

For S → X Y z, X → x X | ε, Y → y Y | ε, how many elements are in FOLLOW(X)?

Numerical answer: ________

Q4MCQ2 marksFOLLOW

For S → A B, A → a A | ε, B → b B | c, FOLLOW(A) is:

• (A) { b, c }
• (B) { a, b, c }
• (C) { $ }
• (D) { b, c, $ }

Q5MCQ1 markFIRST

For P → Q R, Q → q Q | ε, R → r | ε, FIRST(P) is:

• (A) { q, r, ε }
• (B) { q, r }
• (C) { q }
• (D) { q, ε }

11 · Rule Card

• FIRST(a) = {a}; X → ε adds ε; X → Y₁…Yₖ: add FIRST(Yᵢ)−ε while Y₁…Yᵢ₋₁ are nullable; all nullable ⇒ add ε.
• FOLLOW: $ ∈ FOLLOW(S); A → αBβ: FIRST(β)−ε ⊆ FOLLOW(B); β nullable or absent: FOLLOW(A) ⊆ FOLLOW(B).
• FOLLOW never contains ε; FIRST may.
• Compute nullable first; iterate to a stable result.

12 · Concept Ledger

FIRST(α)FOLLOW(A)nullableend marker $

13 · Answer Vault