In Ambiguity, Left Recursion & Left Factoring we prepared grammars for top-down parsing. Now imagine a parser that is about to expand a non-terminal A, has several productions for A to choose from, and can see only the next input token. How does it choose?
It needs two pieces of information about the grammar, both computed in advance:
FIRST: which tokens can a production's right side begin with? If the next token is
(and only one production can start with(, choose that one.FOLLOW: if A can vanish (derive ε), which tokens can come right after A? If the next token is one of those, choosing an ε-production is reasonable.
These two sets are the backbone of LL(1) parsing and also of SLR parsing, and computing them is one of the most frequently asked GATE topics in compiler design. In this chapter we define them precisely, give the algorithms, and work through several grammars step by step. Every set in this chapter was computed by a program and checked against the hand computation.
FIRST Sets
For any string of grammar symbols α, FIRST(α) is the set of terminals that begin the strings derived from α. If α ⇒* ε, then ε is also in FIRST(α).
In symbols: FIRST(α) = { a ∈ T | α ⇒* aβ for some β } ∪ { ε if α ⇒* ε }.
A non-terminal is called nullable if it can derive ε. Nullable symbols are the only reason FIRST computations are ever tricky: if X is nullable, then whatever comes after X can also appear at the start.
Rules for Computing FIRST(X) for a Single Symbol
If X is a terminal, FIRST(X) = { X }.
If X → ε is a production, add ε to FIRST(X).
If X → Y1Y2...Yk is a production:
Add everything in FIRST(Y1) except ε.
If Y1 is nullable, also add FIRST(Y2) except ε; if Y1 and Y2 are both nullable, also add FIRST(Y3) except ε; and so on.
If all of Y1, ..., Yk are nullable, add ε.
Repeat until no FIRST set changes. (Repetition is needed because a FIRST set used in rule 3 may still be growing.)
FIRST of a String
The same idea works for any string α = X1X2...Xn: take FIRST(X1) without ε; if X1 is nullable add FIRST(X2) without ε; and so on; add ε only if every Xi is nullable. FIRST of a production's right side is what an LL(1) parser actually uses to pick a production.
FIRST(X1 X2 ... Xn):
result = {}
for i = 1 to n:
result = result ∪ (FIRST(Xi) − {ε})
if ε ∉ FIRST(Xi): return result ← stop at the first non-nullable symbol
return result ∪ {ε} ← every symbol was nullableFOLLOW Sets
For a non-terminal A, FOLLOW(A) is the set of terminals a that can appear immediately to the right of A in some sentential form, that is, S ⇒* αAaβ for some α and β. If A can be the rightmost symbol in some sentential form, the end marker $ is also in FOLLOW(A).
Two things to notice straight away:
FOLLOW is defined only for non-terminals.
FOLLOW sets never contain ε. They can contain $, which stands for "end of input". FIRST sets are the opposite: they may contain ε and never contain $.
Rules for Computing FOLLOW
Put $ in FOLLOW(S), where S is the start symbol. (The whole program is followed by end of input.)
For every production A → αBβ: everything in FIRST(β) except ε goes into FOLLOW(B). (Whatever β begins with can come right after B.)
For every production A → αB, or A → αBβ where β is nullable (ε ∈ FIRST(β)): everything in FOLLOW(A) goes into FOLLOW(B). (If nothing of A is left after B, then whatever follows A also follows B.)
Repeat until no FOLLOW set changes.
A practical way to apply these rules by hand: go through every production, find every non-terminal on its right side, and look at what stands to its right. Write down what you learn as "FOLLOW(B) ⊇ ..." facts. Then solve the facts. This is how all the examples below are done.
Rule 3 points from FOLLOW(A) into FOLLOW(B), and not the other way. Mixing up this direction is the single most common error in exams.
Worked Example 1: The Expression Grammar
This is the left-recursion-free expression grammar from the previous chapter:
E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | idStep 1: Nullable Symbols
E' and T' have ε-productions, so they are nullable. E, T and F are not: every production of F starts with a terminal, so T → F T' and E → T E' always produce at least one token.
Step 2: FIRST Sets (Bottom-Up)
FIRST(F): F → ( E ) gives
(; F → id givesid. So { (, id }.FIRST(T'): T' → * F T' gives
*; T' → ε gives ε. So { *, ε }.FIRST(T): T → F T'. F is not nullable, so FIRST(T) = FIRST(F) = { (, id }.
FIRST(E'): { +, ε }.
FIRST(E): E → T E'. T is not nullable, so FIRST(E) = FIRST(T) = { (, id }.
Step 3: FOLLOW Facts from Each Production
Production | Non-terminal on the right | What follows it | Fact |
|---|---|---|---|
(start symbol) | E | end of input | FOLLOW(E) ∋ $ |
E → T E' | T | E', which is nullable | FOLLOW(T) ⊇ { + } and FOLLOW(T) ⊇ FOLLOW(E) |
E → T E' | E' | nothing | FOLLOW(E') ⊇ FOLLOW(E) |
E' → + T E' | T | E', nullable | FOLLOW(T) ⊇ { + } and FOLLOW(T) ⊇ FOLLOW(E') |
E' → + T E' | E' | nothing | FOLLOW(E') ⊇ FOLLOW(E') (nothing new) |
T → F T' | F | T', nullable | FOLLOW(F) ⊇ { * } and FOLLOW(F) ⊇ FOLLOW(T) |
T → F T' | T' | nothing | FOLLOW(T') ⊇ FOLLOW(T) |
T' → * F T' | F, T' | same as above | FOLLOW(F) ⊇ { * } ∪ FOLLOW(T'); nothing new for T' |
F → ( E ) | E |
| FOLLOW(E) ⊇ { ) } |
Step 4: Solve the Facts
FOLLOW(E) = { $, ) } (only direct facts)
FOLLOW(E') = FOLLOW(E) = { ), $ }
FOLLOW(T) = { + } ∪ FOLLOW(E) ∪ FOLLOW(E') = { +, ), $ }
FOLLOW(T') = FOLLOW(T) = { +, ), $ }
FOLLOW(F) = { * } ∪ FOLLOW(T) ∪ FOLLOW(T') = { *, +, ), $ }Final Answer
Non-terminal | Nullable? | FIRST | FOLLOW |
|---|---|---|---|
E | No | { (, id } | { ), $ } |
E' | Yes | { +, ε } | { ), $ } |
T | No | { (, id } | { +, ), $ } |
T' | Yes | { *, ε } | { +, ), $ } |
F | No | { (, id } | { *, +, ), $ } |
The pattern makes sense: an F can be followed by anything that can follow a term or a factor, a T by anything that follows an expression or a +, and an E only by ) or the end.
Some FIRST sets of strings that a parser for this grammar uses: FIRST(+ T E') = { + }, FIRST(T E') = { (, id }, and FIRST(E' T') = { +, *, ε } (both symbols are nullable, so ε is included).
Worked Example 2: A Chain of Nullable Symbols
S → A B C | C d
A → a A | ε
B → b | ε
C → c | εFIRST
FIRST(A) = { a, ε }, FIRST(B) = { b, ε }, FIRST(C) = { c, ε }.
FIRST(A B C): take FIRST(A) − ε = { a }; A is nullable, so add FIRST(B) − ε = { b }; B is nullable, so add FIRST(C) − ε = { c }; C is nullable too, so all three are nullable and we add ε. Result: { a, b, c, ε }.
FIRST(C d): { c } from C; C is nullable, so add FIRST(d) = { d }; d is a terminal, stop. Result: { c, d } (no ε, because d can never vanish).
FIRST(S) = FIRST(A B C) ∪ FIRST(C d) = { a, b, c, d, ε }.
FOLLOW
Production | Facts |
|---|---|
start | FOLLOW(S) ∋ $ |
S → A B C | For A: FIRST(B C) = { b, c, ε }, so FOLLOW(A) ⊇ { b, c } and, since B C is nullable, FOLLOW(A) ⊇ FOLLOW(S). |
S → C d | FOLLOW(C) ⊇ { d } |
A → a A | FOLLOW(A) ⊇ FOLLOW(A): nothing new |
Non-terminal | FIRST | FOLLOW |
|---|---|---|
S | { a, b, c, d, ε } | { $ } |
A | { a, ε } | { b, c, $ } |
B | { b, ε } | { c, $ } |
C | { c, ε } | { d, $ } |
Notice that $ reaches FOLLOW(A) only because everything after A in S → A B C can vanish. That is the step students most often miss.
Worked Example 3: Sets That Depend on Each Other
This GATE-style grammar has FOLLOW sets that feed into each other in a cycle:
S → a A b B | b A a B | ε
A → S
B → SFIRST
FIRST(S) = { a, b, ε }. Since A → S and B → S, FIRST(A) = FIRST(B) = { a, b, ε }.
FOLLOW
Start: FOLLOW(S) ∋ $.
S → a A b B: A is followed by b, so FOLLOW(A) ⊇ { b }. B is at the end, so FOLLOW(B) ⊇ FOLLOW(S).
S → b A a B: FOLLOW(A) ⊇ { a }, and again FOLLOW(B) ⊇ FOLLOW(S).
A → S: S is at the end, so FOLLOW(S) ⊇ FOLLOW(A).
B → S: FOLLOW(S) ⊇ FOLLOW(B).
Now solve. FOLLOW(A) = { a, b } (it only gets direct facts). FOLLOW(S) gets $ and everything in FOLLOW(A), so { a, b, $ }. FOLLOW(B) ⊇ FOLLOW(S) = { a, b, $ }, and FOLLOW(S) ⊇ FOLLOW(B) adds nothing new. Stable.
Non-terminal | FIRST | FOLLOW |
|---|---|---|
S | { a, b, ε } | { a, b, $ } |
A | { a, b, ε } | { a, b } |
B | { a, b, ε } | { a, b, $ } |
Notice that FOLLOW(A) does not contain $: in every production, A is followed by a terminal. When sets depend on each other in a cycle like S and B here, they end up equal; the "repeat until nothing changes" rule takes care of that automatically.
Here FIRST(S) − ε and FOLLOW(S) overlap (both contain a and b). As the LL(1) Parsing chapter explains, that overlap means a predictive parser cannot decide between S → a A b B and S → ε on input a, so this grammar is not LL(1).
Worked Example 4: The Dangling Else After Left Factoring
S → i E t S S' | a
S' → e S | ε
E → bFIRST(S) = { i, a }, FIRST(S') = { e, ε }, FIRST(E) = { b }.
FOLLOW facts: FOLLOW(S) ∋ $. In S → i E t S S', E is followed by t, so FOLLOW(E) = { t }; the inner S is followed by S' (nullable), so FOLLOW(S) ⊇ { e } ∪ FOLLOW(S); S' is at the end, so FOLLOW(S') ⊇ FOLLOW(S). In S' → e S, FOLLOW(S) ⊇ FOLLOW(S').
Non-terminal | FIRST | FOLLOW |
|---|---|---|
S | { i, a } | { e, $ } |
S' | { e, ε } | { e, $ } |
E | { b } | { t } |
The symbol e is in both FIRST(S') and FOLLOW(S'). When the parser is expanding S' and sees e, it could use S' → e S (attach the else here) or S' → ε (leave the else for an outer if). This is the dangling-else ambiguity showing up in the FIRST/FOLLOW sets.
Worked Example 5: FIRST and FOLLOW Work Even with Left Recursion
FIRST and FOLLOW are properties of the grammar, not of a particular parser, so they can be computed for any CFG, including left-recursive ones (SLR parsing needs exactly this):
P → D S
D → D d ; | ε
S → S s ; | s ;Think of D as a list of declarations d ; and S as a non-empty list of statements s ;.
FIRST(D): D → D d ; starts with D; since D is nullable we look past it and find
d; D → ε adds ε. So { d, ε }.FIRST(S): S → S s ; adds nothing new (S is not nullable), S → s ; gives { s }.
FIRST(P): FIRST(D) − ε = { d }, and D is nullable so add FIRST(S) = { s }. So { d, s }.
FOLLOW(D): in P → D S, D is followed by S, giving { s }; in D → D d ;, D is followed by d, giving { d }. So { d, s }.
FOLLOW(S): S is at the end of P → D S, so FOLLOW(S) ⊇ FOLLOW(P) = { $ }; in S → S s ;, S is followed by s. So { s, $ }.
The left recursion caused no difficulty. (Only the parsing step would: a top-down parser could not use this grammar.)
Why FIRST and FOLLOW Matter
Used in | How |
|---|---|
LL(1) parsing table | For A → α, put the production in row A under each terminal in FIRST(α); if α is nullable, also under each symbol of FOLLOW(A), including $ when it is there |
LL(1) test | A grammar is LL(1) if no table cell gets two productions, which can be checked directly with FIRST and FOLLOW |
SLR parsing | Reduce by A → α only when the next token is in FOLLOW(A) |
Error recovery | FOLLOW(A) is a natural set of synchronizing tokens for panic mode while parsing A |
The details are in LL(1) Parsing and SLR Parsing; this chapter gives you the sets they rely on.
Common Mistakes
Putting ε in a FOLLOW set or $ in a FIRST set. Never.
Reversing rule 3. For A → αB, FOLLOW(A) is added to FOLLOW(B), not the other way round.
Stopping at the first symbol when computing FIRST(Y1Y2...). If Y1 is nullable you must look at Y2, and so on.
Adding ε to FIRST(X Y) just because X is nullable. ε belongs only if every symbol is nullable.
Forgetting $ in FOLLOW of the start symbol, and forgetting to pass it on to symbols at the right end of productions.
Looking only at productions of A when computing FOLLOW(A). FOLLOW(A) comes from the productions where A appears on the right side.
Stopping after one pass. When sets depend on each other, keep going until nothing changes.
GATE and Interview Questions
Can FOLLOW(A) contain ε? Can FIRST(A) contain $?
No to both. FIRST may contain ε (if A is nullable) but never $. FOLLOW may contain $ but never ε.
For S → A a | b, A → c | ε, what are FIRST(S) and FOLLOW(A)?
FIRST(S) = { c, a, b }: from A a we get c, and since A is nullable also a; from b we get b. ε is not in FIRST(S) because a cannot vanish. FOLLOW(A) = { a }.
For S → A B, A → a | ε, B → b | ε, what is FOLLOW(A)?
FIRST(B) − ε = { b }, and since B is nullable, FOLLOW(S) = { $ } is added too: FOLLOW(A) = { b, $ }.
In the grammar E → T E', E' → + T E' | ε, T → F T', T' → * F T' | ε, F → ( E ) | id, what is FOLLOW(F)?
{ *, +, ), $ }. The * comes from FIRST(T'), and because T' is nullable, FOLLOW(T) = { +, ), $ } is added.
If A → αB is a production, which is true: FOLLOW(A) ⊆ FOLLOW(B) or FOLLOW(B) ⊆ FOLLOW(A)?
FOLLOW(A) ⊆ FOLLOW(B). Whatever follows A follows the B at the end of A. The reverse need not hold, because B may appear elsewhere with other followers.
Why do we need repeated passes to compute FIRST and FOLLOW?
Because the sets depend on each other (possibly cyclically, as in A → S, S → ... A ...). A set computed early may later grow, so we repeat until a pass adds nothing; this always terminates because the sets can only grow and the number of terminals is finite.
How does a nullable non-terminal affect the FIRST of a production?
If the right side is Y1Y2...Yk and Y1 is nullable, then the production can also start with whatever Y2 starts with, and so on down the line. If all of them are nullable, the production can derive ε.
Summary
FIRST(α): terminals that can begin a string derived from α, plus ε if α ⇒* ε.
FOLLOW(A): terminals that can appear immediately after A in some sentential form, plus $ if A can be at the right end.
FIRST of a sequence: keep adding FIRST(Yi) − ε while the symbols so far are nullable; add ε only if all are nullable.
FOLLOW rules: $ ∈ FOLLOW(S); A → αBβ puts FIRST(β) − ε into FOLLOW(B); if β is empty or nullable, FOLLOW(A) goes into FOLLOW(B).
Both are computed by repeating the rules until nothing changes, and work for any CFG, left-recursive or not.
They drive LL(1) table construction, the LL(1) test, SLR reductions and panic-mode recovery.
FIRST answers "how can this begin?" and FOLLOW answers "what can come after this when it disappears?". Together they let a parser make the right choice by looking at a single token.