FIRST and FOLLOW Sets
A predictive parser stands at a nonterminal A, peeks at the next input token,
and must decide — without backtracking — which production for A to use. To make
that decision mechanically it needs two pieces of look-ahead information about every symbol in the
grammar: which terminals can begin the strings a symbol derives, and which terminals can
follow it. These are the FIRST and FOLLOW sets, and they are
the raw material from which every
LL(1) parse table
is built. They also drive SLR bottom-up parsing, so the effort pays twice.
Both are computed by the same idea: start empty, apply a handful of rules, and repeat until nothing
changes — a fixed-point iteration. The subtlety, and every bug, lives in one place: how
the empty string \varepsilon propagates.
FIRST: what can begin a string
- \mathrm{FIRST}(\alpha) is the set of terminals that begin some
string derivable from \alpha; if
\alpha \Rightarrow^{*} \varepsilon then
\varepsilon \in \mathrm{FIRST}(\alpha) as well.
- For a terminal a: \mathrm{FIRST}(a) = \{a\}.
- For a nonterminal, union the FIRST of each production body, threading through
\varepsilon.
The rule for a sequence \alpha = Y_1 Y_2 \dots Y_k is the one to internalise —
it is where \varepsilon bites:
\mathrm{FIRST}(Y_1 Y_2 \dots Y_k) = \mathrm{FIRST}(Y_1)\setminus\{\varepsilon\}
\;\cup\; \big(\text{if } \varepsilon \in \mathrm{FIRST}(Y_1)\big)\, \mathrm{FIRST}(Y_2 \dots Y_k),
\text{and } \varepsilon \in \mathrm{FIRST}(\alpha) \text{ only if } \varepsilon \in \mathrm{FIRST}(Y_i)\ \text{for every } i.
In words: always add \mathrm{FIRST}(Y_1) (minus
\varepsilon). Only if Y_1 can vanish do you also
look at Y_2; continue while each symbol is nullable. Add
\varepsilon to the whole sequence only if every symbol is nullable.
FOLLOW: what can come next
- \mathrm{FOLLOW}(A) is the set of terminals that can appear
immediately to the right of A in some sentential form derivable
from the start symbol. FOLLOW is defined for nonterminals only and never contains
\varepsilon.
- Rule 1. Put the end-marker \$ in
\mathrm{FOLLOW}(S) for the start symbol S.
- Rule 2. For a production A \to \alpha B \beta, add
\mathrm{FIRST}(\beta)\setminus\{\varepsilon\} to
\mathrm{FOLLOW}(B).
- Rule 3. For A \to \alpha B, or
A \to \alpha B \beta with
\varepsilon \in \mathrm{FIRST}(\beta), add all of
\mathrm{FOLLOW}(A) to \mathrm{FOLLOW}(B).
Rule 3 is the tricky one and the source of most mistakes: when B sits at the
end of a body (or everything after it can vanish), whatever can follow the parent
A can also follow B. That "inherit the parent's
FOLLOW" step chains, so FOLLOW too must be iterated to a fixed point.
Worked computation on the expression grammar
Take the left-recursion-eliminated grammar, ready for LL(1):
\begin{aligned}
E &\to T\,E' & E' &\to +\,T\,E' \mid \varepsilon \\
T &\to F\,T' & T' &\to *\,F\,T' \mid \varepsilon \\
F &\to (\,E\,) \mid \mathbf{id}
\end{aligned}
FIRST, bottom-up. F starts with
( or \mathbf{id}. Since
T \to F T' and F is not nullable,
\mathrm{FIRST}(T) = \mathrm{FIRST}(F), and likewise
\mathrm{FIRST}(E) = \mathrm{FIRST}(T). The primed helpers each begin with their
operator or vanish. FOLLOW: seed \mathrm{FOLLOW}(E) = \{\$\},
then propagate through F \to (E) (adds )) and the
end-of-body Rule 3.
| Nonterminal X | \mathrm{FIRST}(X) | \mathrm{FOLLOW}(X) |
|---|
| E | \{\,(,\ \mathbf{id}\,\} | \{\,),\ \$\,\} |
| E' | \{\,+,\ \varepsilon\,\} | \{\,),\ \$\,\} |
| T | \{\,(,\ \mathbf{id}\,\} | \{\,+,\ ),\ \$\,\} |
| T' | \{\,*,\ \varepsilon\,\} | \{\,+,\ ),\ \$\,\} |
| F | \{\,(,\ \mathbf{id}\,\} | \{\,+,\ *,\ ),\ \$\,\} |
Trace one tricky entry. Why is + \in \mathrm{FOLLOW}(T)? Because
E \to T E' puts \mathrm{FIRST}(E') = \{+, \varepsilon\}
after T (Rule 2 contributes +), and because
\varepsilon \in \mathrm{FIRST}(E'), Rule 3 also drags
\mathrm{FOLLOW}(E) = \{), \$\} into
\mathrm{FOLLOW}(T) — giving \{+, ), \$\}.
Computing both by fixed-point iteration
The definitions are circular (FOLLOW of a child depends on FOLLOW of its parent, which may depend
back…), so we do not solve them algebraically — we iterate. Initialise every set empty, sweep
all productions applying the rules, and repeat the whole sweep until a full pass adds nothing. Because
sets only grow and are bounded by the finite alphabet, this must terminate.
type Rules = Record<string, string[][]>; // nonterminal -> alternatives; "eps" = ε
const G: Rules = {
E: [["T", "E'"]],
"E'": [["+", "T", "E'"], ["eps"]],
T: [["F", "T'"]],
"T'": [["*", "F", "T'"], ["eps"]],
F: [["(", "E", ")"], ["id"]],
};
const START = "E";
const isNT = (s: string) => s in G;
// FIRST of a *sequence*, using the current FIRST table. May include "eps".
function firstOfSeq(seq: string[], FIRST: Record<string, Set<string>>): Set<string> {
const out = new Set<string>();
let allNullable = true;
for (const X of seq) {
if (X === "eps") { out.add("eps"); break; }
const fx = isNT(X) ? FIRST[X] : new Set([X]);
for (const t of fx) if (t !== "eps") out.add(t);
if (!fx.has("eps")) { allNullable = false; break; }
}
if (allNullable) out.add("eps");
return out;
}
// ---- FIRST, to a fixed point ----
const FIRST: Record<string, Set<string>> = {};
for (const A of Object.keys(G)) FIRST[A] = new Set();
let changed = true;
while (changed) {
changed = false;
for (const [A, alts] of Object.entries(G)) {
for (const alt of alts) {
for (const t of firstOfSeq(alt, FIRST)) {
if (!FIRST[A].has(t)) { FIRST[A].add(t); changed = true; }
}
}
}
}
// ---- FOLLOW, to a fixed point ----
const FOLLOW: Record<string, Set<string>> = {};
for (const A of Object.keys(G)) FOLLOW[A] = new Set();
FOLLOW[START].add("$");
changed = true;
while (changed) {
changed = false;
for (const [A, alts] of Object.entries(G)) {
for (const alt of alts) {
for (let i = 0; i < alt.length; i++) {
const B = alt[i];
if (!isNT(B)) continue;
const beta = alt.slice(i + 1);
const fb = firstOfSeq(beta.length ? beta : ["eps"], FIRST);
for (const t of fb) if (t !== "eps" && !FOLLOW[B].has(t)) { FOLLOW[B].add(t); changed = true; }
if (fb.has("eps")) {
for (const t of FOLLOW[A]) if (!FOLLOW[B].has(t)) { FOLLOW[B].add(t); changed = true; }
}
}
}
}
}
const fmt = (s: Set<string>) => "{ " + [...s].join(", ") + " }";
for (const A of Object.keys(G)) {
console.log(`${A}: FIRST ${fmt(FIRST[A])} FOLLOW ${fmt(FOLLOW[A])}`);
}
The output reproduces the table exactly — including the delicate
\mathrm{FOLLOW}(F) = \{+, *, ), \$\}, which only comes out right if Rule 3's
"inherit the parent's FOLLOW when the tail is nullable" is handled. That if (fb.has("eps"))
branch is the whole ball game.
FIRST asks a question inside a string — "what terminal can start what this symbol derives?" —
and every answer is an ordinary terminal already in the grammar (or \varepsilon,
meaning "derives nothing"). FOLLOW asks a question at the edges — "what can sit to the right of
this nonterminal?" — and a nonterminal can legitimately sit at the very end of the whole input, with
nothing after it. We need a symbol to name that "nothing", so we imagine the input is bracketed
as S\$ with a synthetic end-marker \$. Then "at the
end of input" becomes "followed by \$", a perfectly ordinary FOLLOW entry. The
parser later treats \$ as the token that means "no more input", and a
production is chosen on \$ exactly when the parser is allowed to finish.
Two classic errors, both about \varepsilon. First, in FIRST of a
sequence: you only advance from Y_1 to Y_2
if \varepsilon \in \mathrm{FIRST}(Y_1). A frequent bug is to blindly
union \mathrm{FIRST}(Y_2) in even when Y_1 is not
nullable — that wrongly floods the set. And \varepsilon joins the whole
sequence's FIRST only when all of Y_1 \dots Y_k are nullable.
Second, in FOLLOW: for A \to \alpha B \beta you add
\mathrm{FIRST}(\beta)\setminus\{\varepsilon\}, and then, if
\beta can derive \varepsilon (or
\beta is empty), you must also add
\mathrm{FOLLOW}(A) to \mathrm{FOLLOW}(B). Forgetting
that second addition is the number-one reason a hand-computed FOLLOW comes out too small — and a too-small
FOLLOW builds a parse table with missing entries. Never put \varepsilon itself
into any FOLLOW set.