Algorithm to Compute FIRST and FOLLOW Sets for a Given Grammar

Verified Sources

Nov 4, 2026

Computing FIRST and FOLLOW is a foundational step for constructing LL(1) parsing tables. The core idea is to apply grammar production rules that propagate terminals through nullable derivations until the sets reach a fixed point (no more changes). This section provides clear algorithm rules and then presents a complete algorithmic procedure (with pseudocode) for computing FIRST and FOLLOW for an arbitrary context-free grammar, including grammars with $\varepsilon$ (epsilon) productions.

We will rely on the standard fixed-point rules for:

Nullable (whether $X \Rightarrow^* \varepsilon$ ),
FIRST propagation,
FOLLOW propagation.

A typical workflow is:

compute FIRST (and nullability) for all symbols,
compute FOLLOW by scanning productions and propagating lookahead using FIRST of suffixes and FOLLOW of left-hand sides when the suffix is nullable.

Mermaid overview of dependency flow:

Key terminals/nonterminals notions:

$\varepsilon$ is a special “empty string” token (not a terminal).
Let $S$ be the start symbol. The end-marker $[\$ ]{def="Input end marker used for FOLLOW(start) initialization"} is placed in FOLLOW( $S$ ).

Important: The algorithms below are “worklist/fixed-point” algorithms: they repeatedly apply inference rules until no set changes.

FIRST and FOLLOW Sets (LL(1) Parsing) - Algorithm Overview

Step 1 — Define notation and inference rules

1
Step 1
Let grammar productions be $A \to \alpha$ where $A$ is a nonterminal and $\alpha$ is a string of terminals/nonterminals (possibly empty). Define FIRST for symbols (terminals/nonterminals) and FOLLOW for nonterminals.
2
Step 2
For any terminal $a$ , define FIRST( $a$ ) = { $a$ }. For epsilon, FIRST( $\varepsilon$ ) = { $\varepsilon$ }.
3
Step 3
A nonterminal $A$ is nullable if $A \Rightarrow^* \varepsilon$ . We will compute this implicitly via FIRST containing $\varepsilon$ .
4
Step 4
If $A \to X_1 X_2 \cdots X_k$ , then FIRST( $A$ ) includes FIRST( $X_1$ ){{ $\varepsilon$ }}. If $X_1$ is nullable, then also include FIRST( $X_2$ ){{ $\varepsilon$ }}, and so on. If all $X_i$ are nullable, include $\varepsilon$ in FIRST( $A$ ).
5
Step 5
Put $[\$ ] $into FOLLOW(start symbol$ S $). For other nonterminals, initialize FOLLOW($ A$) = empty set.
6
Step 6
For any production $B \to \alpha A \beta$ (where $A$ is a nonterminal occurrence in the RHS and $\alpha,\beta$ are strings): add FIRST( $\beta$ ){{ $\varepsilon$ }} to FOLLOW( $A$ ). If $\beta$ can derive $\varepsilon$ (i.e., $\beta$ is nullable), then add FOLLOW( $B$ ) to FOLLOW( $A$ ).

keyword FIRST/FOLLOW are computed by fixed-point iteration.

A Fixed-point approach guarantees termination because each set only grows (monotonic). Each update adds terminals (or $\\varepsilon$ for FIRST) and never removes elements; since there are finitely many grammar symbols/terminals, convergence occurs.

We can implement “apply inference rules” using:

either repeated full passes over productions (“while changed”),
or a worklist keyed by which FIRST/FOLLOW sets changed.

Below, we present a clear version using repeated passes, which is easiest to understand and still efficient for typical course-scale grammars.

Step 2 — Compute FIRST sets (with epsilon)

1
Step 1
For each nonterminal $A$ : set FIRST( $A$ ) = empty. For each terminal $a$ : FIRST( $a$ ) = { $a$ }. Set FIRST( $\varepsilon$ ) = { $\varepsilon$ }.
2
Step 2
Repeat until no changes: for every production $A \to X_1 X_2 \cdots X_k$ do:

For $i=1$ .. $k$ : add FIRST( $X_i$ ){{ $\varepsilon$ }} into FIRST( $A$ ).

Stop early once you reach a non-nullable $X_i$ .

If every $X_i$ is nullable, add $\varepsilon$ to FIRST( $A$ ).
3
Step 3
To support FOLLOW later, define a helper FIRSTstring( $\beta$ ): compute FIRST of a sequence $\beta=X_1...X_k$ using the same logic (propagate terminals while nullable continues; include $\varepsilon$ only if all are nullable).
4
Step 4
Stop when a complete pass over all productions makes no FIRST additions.

Step 3 — Compute FOLLOW sets (using FIRST of suffixes)

1
Step 1
For the start symbol $S$ , set FOLLOW( $S$ ) = { $[\$ ] $}. For every other nonterminal$ A $, FOLLOW($ A$) = empty.
2
Step 2
Repeat until no changes: for each production $B \to \alpha A \beta$ (scan each RHS occurrence of a nonterminal $A$ ):

Add FIRSTstring( $\beta$ ){{ $\varepsilon$ }} to FOLLOW( $A$ ).

If $\beta$ is nullable (i.e., FIRSTstring( $\beta$ ) contains $\varepsilon$ ), then add FOLLOW( $B$ ) to FOLLOW( $A$ ).
3
Step 3
Stop when a complete pass produces no FOLLOW additions.

Complete pseudocode (end-to-end)

Helper functions

FIRSTset: FIRST for symbols/nonterminals.
Nullable: nullable if FIRST contains epsilon.
FIRSTstring: FIRST of $X_1...X_k$ .

1INPUT:
2  Grammar G = (V, T, P, S)
3  Productions P: each is A -> α
4
5OUTPUT:
6  FIRST(X) for all symbols X (terminals, nonterminals, ε)
7  FOLLOW(A) for all nonterminals A
8
9ALGORITHM:
10
111) Initialize FIRST
12  For each terminal a in T:
13    FIRST(a) = {a}
14  FIRST(ε) = {ε}
15  For each nonterminal A in V:
16    FIRST(A) = ∅
17
182) Compute FIRST (fixed point)
19  repeat
20    changed = false
21    for each production A -> X1 X2 ... Xk in P:
22      // compute FIRST contribution of the RHS sequence
23      add_epsilon = true
24      for i in 1..k:
25        beforeSize = |FIRST(A)|
26        FIRST(A) = FIRST(A) ∪ (FIRST(Xi) \ {ε})
27        if |FIRST(A)| > beforeSize: changed = true
28
29        if ε not in FIRST(Xi):
30          add_epsilon = false
31          break
32
33      if add_epsilon:
34        beforeSize = |FIRST(A)|
35        FIRST(A) = FIRST(A) ∪ {ε}
36        if |FIRST(A)| > beforeSize: changed = true
37  until not changed
38
393) Helper: FIRSTstring(β)
40  function FIRSTstring(β = Y1...Ym):
41    result = ∅
42    for j in 1..m:
43      result = result ∪ (FIRST(Yj) \ {ε})
44      if ε not in FIRST(Yj): return result
45    // if all nullable:
46    return result ∪ {ε}
47
484) Initialize FOLLOW
49  For each nonterminal A in V:
50    FOLLOW(A) = ∅
51  FOLLOW(S) = FOLLOW(S) ∪ {$}
52
535) Compute FOLLOW (fixed point)
54  repeat
55    changed = false
56    for each production B -> α in P:
57      Let α positions be α1 α2 ... αn (each αi is terminal or nonterminal)
58      for each index i such that αi is a nonterminal A:
59        β = α(i+1) ... αn   // suffix after A
60        firstBeta = FIRSTstring(β)
61
62        beforeSize = |FOLLOW(A)|
63        FOLLOW(A) = FOLLOW(A) ∪ (firstBeta \ {ε})
64        if |FOLLOW(A)| > beforeSize: changed = true
65
66        if ε in firstBeta:
67          beforeSize = |FOLLOW(A)|
68          FOLLOW(A) = FOLLOW(A) ∪ FOLLOW(B)
69          if |FOLLOW(A)| > beforeSize: changed = true
70  until not changed
71
72return FIRST, FOLLOW

Where each rule “feeds” FIRST vs FOLLOW

Conceptual mapping of inference sources.

Common edge cases and correctness notes

Pro Tip

Implement FIRSTstring(β) as a function that scans the sequence left-to-right and stops at the first non-nullable symbol; this matches the definition and keeps FOLLOW propagation correct.

Pitfall: confusing ε with the empty string in FOLLOW

In FOLLOW, you should add FIRST(β){ε} to FOLLOW(A), not ε itself. ε is a marker for 'nullable derivation' and only determines whether to add FOLLOW(B).

Roadmap: FIRST/FOLLOW to LL(1) parsing table

Compute FIRST sets

Step A

Use production-based propagation; include ε when all RHS symbols are nullable."

Compute FOLLOW sets

Step B

Initialize FOLLOW(start) with $; propagate via FIRST of suffixes and LHS FOLLOW when suffix nullable."

Build LL(1) table

Step C

For each production A->α: use FIRST(α) to fill entries; if α⇒*ε use FOLLOW(A)."

Parse test strings

Step D

Predictive parsing with 1-token lookahead; ensure no table conflicts for LL(1)."

Knowledge Check

Question 1 of 4

Q1Single choice

In the algorithm for FOLLOW sets, what do you add to FOLLOW(A) from a production B -> α A β?

Add FIRST(β) \ {ε}; if β is nullable, also add FOLLOW(B)

Add FOLLOW(B) always, regardless of whether β is nullable

Add FIRST(A) to FOLLOW(B)

Add ε itself to FOLLOW(A)

Explore Related Topics

LL(1) Parsing: Working Mechanism and Parsing Table Construction for a Given Grammar

FIRST, FOLLOW, and LL(1) Parsing Table for the Given Expression Grammar

FIRST and FOLLOW Sets for a Given CFG

Browse all research articles