Yasir Explains/Compiler Design/Syntax Analysis/FIRST and FOLLOW Sets
Syntax Analysis

FIRST and FOLLOW Sets

On this page

Why Do We Need FIRST and FOLLOW?FIRST Set — Definition and RulesFOLLOW Set — Definition and RulesFIRST Set — Advanced Examples (All Cases)FOLLOW Set — Advanced Examples (All Cases)Summary and Common Mistakes
Syntax Analysis

FIRST and FOLLOW Sets

Master the two most important sets in LL parsing — FIRST tells you what a grammar symbol can start with, and FOLLOW tells you what can come after it. Together they build the LL(1) parsing table.

Why Do We Need FIRST and FOLLOW?

A predictive parser needs to decide, given a non-terminal A and the current input token a, which production rule to use. This decision is encoded in a parsing table.

To build the parsing table, we need to answer two questions:

  1. "What can A generate first?" — If A → α and α can start with a, then when we see a we should try this production. This is the FIRST set.

  2. "What can come after A?" — If A → ε (A can disappear), we need to know what comes after A in the input to decide if we should use A → ε. This is the FOLLOW set.

Quick Preview

Example
Grammar:
E → T E'
E' → + T E' | ε
T → id
FIRST(E) = { id } → E always starts with id
FIRST(E') = { +, ε } → E' can start with + or disappear (ε)
FIRST(T) = { id } → T always starts with id
FOLLOW(E) = { $, ) } → E can be followed by $ (end) or )
FOLLOW(E') = { $, ) } → same as FOLLOW(E), since E' can vanish at the end of E
FOLLOW(T) = { +, $, ) } → T can be followed by +, $, or )

These sets tell the parser exactly which production to pick at each step.

FIRST Set — Definition and Rules

FIRST(α) is the set of terminals that can appear as the first symbol of any string derived from α.

If α can derive the empty string (ε), then ε is also in FIRST(α).

Rules for Computing FIRST

Rule 1 — Terminal:

Example
FIRST(a) = { a } for any terminal a
FIRST(ε) = { ε }

Rule 2 — Non-terminal A with production A → X₁ X₂ … Xₙ:

Example
Add FIRST(X₁) − {ε} to FIRST(A)
If ε ∈ FIRST(X₁):
Add FIRST(X₂) − {ε} to FIRST(A)
If ε ∈ FIRST(X₁) and ε ∈ FIRST(X₂):
Add FIRST(X₃) − {ε} to FIRST(A)
...
If ε ∈ FIRST(Xᵢ) for ALL i = 1 to n:
Add ε to FIRST(A)

In other words: keep looking right until you find a symbol that cannot disappear.

Example — Computing FIRST

Grammar:

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

Step 1 — FIRST of terminals:

Example
FIRST(+) = {+}, FIRST(*) = {*}, FIRST(() = {(}, FIRST()) = {)}
FIRST(id) = {id}

Step 2 — FIRST(F):

Example
F → ( E ) : first symbol is '(' (terminal) → add '(' to FIRST(F)
F → id : first symbol is 'id' (terminal) → add 'id' to FIRST(F)
FIRST(F) = { (, id }

Step 3 — FIRST(T'):

Example
T' → * F T' : first symbol is '*' → add '*' to FIRST(T')
T' → ε : add ε to FIRST(T')
FIRST(T') = { *, ε }

Step 4 — FIRST(T):

Example
T → F T' : FIRST(F) = { (, id } (no ε in FIRST(F)) → add { (, id } to FIRST(T)
→ F cannot be empty, so we stop here.
FIRST(T) = { (, id }

Step 5 — FIRST(E'):

Example
E' → + T E' : first symbol is '+' → add '+' to FIRST(E')
E' → ε : add ε to FIRST(E')
FIRST(E') = { +, ε }

Step 6 — FIRST(E):

Example
E → T E' : FIRST(T) = { (, id } (no ε) → add { (, id } to FIRST(E)
FIRST(E) = { (, id }

Final FIRST sets:

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

FOLLOW Set — Definition and Rules

FOLLOW(A) is the set of terminals that can appear immediately after A in some sentential form.

FOLLOW is only defined for non-terminals. It is never defined for ε.

Rules for Computing FOLLOW

Rule 1 — Start symbol:

Example
Add $ (end-of-input marker) to FOLLOW(S)

Rule 2 — For each production B → α A β:

Example
Add FIRST(β) − {ε} to FOLLOW(A)
If ε ∈ FIRST(β) (or β = ε):
Add FOLLOW(B) to FOLLOW(A)
(because if β disappears, whatever follows B also follows A)

Example — Computing FOLLOW (same grammar)

Grammar:

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

FIRST sets (already computed):

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

Step 1 — FOLLOW(E):

Example
E is the start symbol → add $ to FOLLOW(E)
From production F → ( E ) :
β = ')' → add FIRST(')') = { ) } to FOLLOW(E)
FOLLOW(E) = { $, ) }

Step 2 — FOLLOW(E'):

Example
From E → T E' : E' is at the end of the production
β = ε → add FOLLOW(E) = { $, ) } to FOLLOW(E')
From E' → + T E' : E' is again at the end
β = ε → add FOLLOW(E') to FOLLOW(E') (already included)
FOLLOW(E') = { $, ) }

Step 3 — FOLLOW(T):

Example
From E → T E' : β = E', FIRST(E') = { +, ε }
Add FIRST(E') − {ε} = { + } to FOLLOW(T)
Since ε ∈ FIRST(E'), also add FOLLOW(E) = { $, ) } to FOLLOW(T)
From E' → + T E' : β = E', same analysis
Add { + } to FOLLOW(T) (already there)
Add FOLLOW(E') = { $, ) } to FOLLOW(T) (already there)
FOLLOW(T) = { +, $, ) }

Step 4 — FOLLOW(T'):

Example
From T → F T' : T' is at the end
Add FOLLOW(T) = { +, $, ) } to FOLLOW(T')
From T' → * F T' : T' is at the end again
Add FOLLOW(T') to FOLLOW(T') (already included)
FOLLOW(T') = { +, $, ) }

Step 5 — FOLLOW(F):

Example
From T → F T' : β = T', FIRST(T') = { *, ε }
Add FIRST(T') − {ε} = { * } to FOLLOW(F)
Since ε ∈ FIRST(T'), add FOLLOW(T) = { +, $, ) } to FOLLOW(F)
From T' → * F T' : β = T', same analysis
Add { * } to FOLLOW(F) (already there)
Add FOLLOW(T') = { +, $, ) } to FOLLOW(F) (already there)
FOLLOW(F) = { *, +, $, ) }

Final FOLLOW sets:

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

FIRST Set — Advanced Examples (All Cases)

The examples below cover every edge case you will encounter when computing FIRST sets.

Example 2 — All Symbols Nullable (ε Reaches the LHS)

Grammar:

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

Step 1 — FIRST of A, B, C:

Example
A → a and A → ε ⟹ FIRST(A) = { a, ε }
B → b and B → ε ⟹ FIRST(B) = { b, ε }
C → c and C → ε ⟹ FIRST(C) = { c, ε }

Step 2 — FIRST(S) for S → A B C:

Example
Add FIRST(A) − {ε} = { a } ← A can start with 'a'
ε ∈ FIRST(A) → look right:
Add FIRST(B) − {ε} = { b } ← A vanished; B can start with 'b'
ε ∈ FIRST(B) → look right:
Add FIRST(C) − {ε} = { c } ← A,B vanished; C can start with 'c'
ε ∈ FIRST(C) → all three symbols can vanish:
Add ε ← entire string can derive the empty string
FIRST(S) = { a, b, c, ε }

Key rule: ε propagates all the way to FIRST(S) only when every symbol in the production can independently derive ε. If any single symbol cannot vanish, the chain stops there.

Example 3 — Recursive Productions

Grammar:

Example
S → a S b | A B
A → c A d | ε
B → e | ε

Step 1 — FIRST(A) and FIRST(B):

Example
A → c A d : leftmost symbol is terminal 'c' → add 'c'
A → ε : add ε
FIRST(A) = { c, ε }
B → e : add 'e'
B → ε : add ε
FIRST(B) = { e, ε }

Step 2 — FIRST(S):

Example
Production S → a S b:
Leftmost symbol is terminal 'a' → add 'a'
'a' cannot derive ε → stop
Production S → A B:
Add FIRST(A) − {ε} = { c }
ε ∈ FIRST(A) → look right at B:
Add FIRST(B) − {ε} = { e }
ε ∈ FIRST(B) → all symbols in "A B" can vanish → add ε
FIRST(S) = { a, c, e, ε }

Note on recursion: In A → c A d, the recursive A is buried inside the production — it does not affect FIRST(A). FIRST only looks at the leftmost symbol of each production. For A → c A d, that is the terminal 'c'. The inner recursive A is never reached during the FIRST computation.

Example 4 — Multiple Alternatives, One Non-terminal Never Nullable

Grammar:

Example
S → A B | c
A → a A | ε
B → b B | d

Step 1:

Example
FIRST(A) = { a, ε } (A → a A contributes 'a'; A → ε contributes ε)
FIRST(B) = { b, d } (neither alternative of B can produce ε — no B → ε rule exists)

Step 2 — FIRST(S):

Example
Production S → A B:
Add FIRST(A) − {ε} = { a }
ε ∈ FIRST(A) → look right at B:
Add FIRST(B) − {ε} = { b, d }
ε ∉ FIRST(B) → B cannot vanish → STOP (ε is NOT added to FIRST(S))
Production S → c:
Add { c }
FIRST(S) = { a, b, c, d }

Key contrast with Example 2: B is not nullable, so the chain stops at B. ε does NOT reach FIRST(S) even though A can vanish.

Example 5 — Indirect Nullable via Another Non-terminal

Grammar:

Example
S → X Y
X → A B
A → p | ε
B → q | ε
Y → r

Step 1 — bottom up:

Example
FIRST(A) = { p, ε }
FIRST(B) = { q, ε }
FIRST(Y) = { r }
FIRST(X) via X → A B:
Add FIRST(A) − {ε} = { p }
ε ∈ FIRST(A) → look right:
Add FIRST(B) − {ε} = { q }
ε ∈ FIRST(B) → both A and B can vanish → add ε
FIRST(X) = { p, q, ε }

Step 2 — FIRST(S) via S → X Y:

Example
Add FIRST(X) − {ε} = { p, q }
ε ∈ FIRST(X) → look right at Y:
Add FIRST(Y) − {ε} = { r }
ε ∉ FIRST(Y) → stop (r is always present)
FIRST(S) = { p, q, r }

Takeaway: The ε-chain propagates even when the nullable group is itself wrapped inside another non-terminal (X). Always reduce to base cases first, then combine.

FIRST Edge Cases — Quick Reference

Example
Case What happens
────────────────────────────────────────────────────────────────────────────
X is a terminal 'a' FIRST(X) = { a }
X → ε FIRST(X) = { ε }
X → A B, A is not nullable FIRST(X) ⊇ FIRST(A); chain stops at A
X → A B, A is nullable, B is not FIRST(X) ⊇ FIRST(A) ∪ FIRST(B); no ε
X → A B C, all nullable FIRST(X) ⊇ FIRST(A)∪FIRST(B)∪FIRST(C)∪{ε}
X → a Y (leftmost is terminal 'a') Add 'a'; the recursive Y is irrelevant
X → Y | Z (two alternatives) FIRST(X) = FIRST(Y) ∪ FIRST(Z)
X → A, A is non-terminal FIRST(X) = FIRST(A) (inherit directly)

FOLLOW Set — Advanced Examples (All Cases)

The examples below cover every edge case you will encounter when computing FOLLOW sets.

Example 2 — Same Non-terminal Appearing Twice in One Production

Grammar:

Example
S → A a A b
A → c | ε

FIRST sets:

Example
FIRST(A) = { c, ε }
FIRST(S) via S → A a A b:
FIRST(A) − {ε} = { c }; ε ∈ FIRST(A) → look right at terminal 'a': add { a }
'a' cannot derive ε → stop
FIRST(S) = { a, c }

FOLLOW(S) = { $ }

FOLLOW(A): A appears at two positions in the same production — analyse each separately.

Example
Production: S → A a A b
↑ ↑
pos 1 pos 2
Position 1 — first A, what follows it = "a A b":
'a' is terminal → add { a }
'a' cannot derive ε → stop
Position 2 — second A, what follows it = "b":
'b' is terminal → add { b }
'b' cannot derive ε → stop
FOLLOW(A) = { a, b }

Common trap: A can produce ε, so you might think FOLLOW(S) = { $ } should be in FOLLOW(A). It is not. Whether A can produce ε is irrelevant to what tokens can follow A in a sentential form — what matters is the concrete context around each occurrence.

Example 3 — FOLLOW Propagating Through a Nullable Chain

Grammar:

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

FIRST sets (computed earlier):

Example
FIRST(A) = { a, ε } FIRST(B) = { b, ε } FIRST(C) = { c, ε }

FOLLOW(S) = { $ }

FOLLOW(C): C is at the right end of S → A B C

Example
β = ε → add FOLLOW(S) = { $ }
FOLLOW(C) = { $ }

FOLLOW(B): B is followed by C in S → A B C

Example
FIRST(C) − {ε} = { c } → add { c }
ε ∈ FIRST(C) → C can vanish → add FOLLOW(S) = { $ }
FOLLOW(B) = { c, $ }

FOLLOW(A): A is followed by "B C" in S → A B C

Example
FIRST(B) − {ε} = { b } → add { b }
ε ∈ FIRST(B) → B can vanish, look further right at C:
FIRST(C) − {ε} = { c } → add { c }
ε ∈ FIRST(C) → C can also vanish → end of production → add FOLLOW(S) = { $ }
FOLLOW(A) = { b, c, $ }

Final FOLLOW sets:

Example
FOLLOW(S) = { $ }
FOLLOW(C) = { $ }
FOLLOW(B) = { c, $ }
FOLLOW(A) = { b, c, $ }

Pattern: FOLLOW "flows leftward" through nullable symbols. A's FOLLOW includes everything that B and C could start with, plus S's own FOLLOW (because B and C can both disappear, exposing S's surrounding context to A).

Example 4 — Non-terminal Appearing in Multiple Different Productions

Grammar:

Example
S → A B
B → A c | d
A → a | ε

FIRST sets:

Example
FIRST(A) = { a, ε }
FIRST(B):
B → A c : FIRST(A) − {ε} = { a }; ε ∈ FIRST(A) → add FIRST(c) = { c }
B → d : add { d }
FIRST(B) = { a, c, d } ← B is not nullable (no B → ε)
FIRST(S) via S → A B:
FIRST(A) − {ε} = { a }; ε ∈ FIRST(A) → add FIRST(B) − {ε} = { a, c, d }
FIRST(S) = { a, c, d }

FOLLOW(S) = { $ }

FOLLOW(B): From S → A B, B is at the end

Example
β = ε → add FOLLOW(S) = { $ }
FOLLOW(B) = { $ }

FOLLOW(A): A appears in three places across two different productions — scan all of them.

Example
Occurrence 1 — S → A B, what follows first A = B:
FIRST(B) − {ε} = { a, c, d } → add { a, c, d }
ε ∉ FIRST(B) → stop
Occurrence 2 — B → A c, what follows A = c:
FIRST(c) = { c } → add { c } (already in FOLLOW(A))
'c' cannot derive ε → stop
Occurrence 3 — A → a A, A is at the right end, β = ε:
→ add FOLLOW(A) to FOLLOW(A) (self-reference — no new information)
FOLLOW(A) = { a, c, d }

Key rule: FOLLOW is the union over every occurrence of A anywhere in the grammar — across every production, every alternative.

Example 5 — ε in FIRST Triggers Two Different Paths in FOLLOW

Grammar:

Example
S → A B C $
A → p | ε
B → q A r | ε
C → s

($ is end-of-input, treated as a terminal here for clarity)

FIRST sets:

Example
FIRST(A) = { p, ε }
FIRST(B):
B → q A r : first is 'q' → add { q }; 'q' ≠ ε → stop
B → ε : add ε
FIRST(B) = { q, ε }
FIRST(C) = { s }

FOLLOW(S) = { $ }

FOLLOW(C): C followed by $ (terminal) in S → A B C $

Example
Add { $ }
FOLLOW(C) = { $ }

FOLLOW(B): B followed by "C $" in S → A B C $

Example
FIRST(C) − {ε} = { s } → add { s }
ε ∉ FIRST(C) → stop
FOLLOW(B) = { s }

FOLLOW(A): A appears in two places:

Example
Occurrence 1 — S → A B C $, what follows first A = "B C $":
FIRST(B) − {ε} = { q } → add { q }
ε ∈ FIRST(B) → B can vanish, look right at C:
FIRST(C) − {ε} = { s } → add { s }
ε ∉ FIRST(C) → stop
Occurrence 2 — B → q A r, what follows A = "r":
'r' is terminal → add { r }
'r' cannot derive ε → stop
FOLLOW(A) = { q, r, s }

Observation: { $ } is NOT in FOLLOW(A) even though FOLLOW(S) = { $ } and A is the first symbol of S. The terminal C always consumes 's' before end-of-input is reached after A.

FOLLOW Edge Cases — Quick Reference

Example
Case What to add to FOLLOW(A)
──────────────────────────────────────────────────────────────────────────────
A is the start symbol Always add $
... A b ... (terminal b immediately after) Add { b }
... A B ... (B not nullable) Add FIRST(B) − {ε}
... A B ... (B nullable) Add FIRST(B) − {ε} AND FOLLOW(LHS)
A at end of production X → ... A Add FOLLOW(X)
A appears twice in X → α A β A γ Analyse each occurrence independently; union results
A appears in multiple productions Union all occurrences from every production
ε ∉ FOLLOW(A) ever ε is a FIRST concept ("can vanish"); FOLLOW only tracks real input tokens

Summary and Common Mistakes

Quick Reference

SetDefined ForContainsKey Rule
FIRST(α)Any string αTerminals that α can start with; also ε if α ⟹* εLook at the leftmost symbol, continue right if it can be ε
FOLLOW(A)Non-terminals onlyTerminals that can appear right after A; also $Look at the right context of A in every production

Common Mistakes

Mistake 1 — Adding ε to FOLLOW:

FOLLOW sets never contain ε. The ε in FIRST means "this can disappear." FOLLOW tracks what comes after in the actual input, not what the non-terminal produces.

Example
Wrong: FOLLOW(E') = { $, ), ε }
Right: FOLLOW(E') = { $, ) }

Mistake 2 — Forgetting to propagate FOLLOW through ε-productions:

If A → α B and B can derive ε, then FOLLOW(A) must be added to FOLLOW(B).

Mistake 3 — Not adding $ to FOLLOW(S):

The start symbol S is always followed by end-of-input ($). Always add $ to FOLLOW(S) first.

Full Summary Table (Arithmetic Example)

Example
Non-terminal FIRST FOLLOW
──────────────────────────────────────────
E { (, id } { $, ) }
E' { +, ε } { $, ) }
T { (, id } { +, $, ) }
T' { *, ε } { +, $, ) }
F { (, id } { *, +, $, ) }