Chapter 09 of 33

FIRST & FOLLOW Sets

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

  1. If X is a terminal, FIRST(X) = { X }.

  2. If X → ε is a production, add ε to FIRST(X).

  3. 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 ε.

  4. 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 nullable

FOLLOW 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

  1. Put $ in FOLLOW(S), where S is the start symbol. (The whole program is followed by end of input.)

  2. For every production A → αBβ: everything in FIRST(β) except ε goes into FOLLOW(B). (Whatever β begins with can come right after B.)

  3. 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.)

  4. 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 ) | id

Step 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 gives id. 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).
For B: FIRST(C) = { c, ε }, so FOLLOW(B) ⊇ { c } ∪ FOLLOW(S).
For C: at the end, so FOLLOW(C) ⊇ 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 → S

FIRST

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  → b

FIRST(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.