FIRST and FOLLOW Sets: Building the LL(1) Predictive Parse Table

The problem: which production do I expand?

A top-down parser builds a parse tree from the root down, expanding nonterminals into productions. The core difficulty: when the parser has nonterminal A on top of its stack and several productions A -> alpha_1 | alpha_2 | ..., which one does it choose? A naive parser tries one, and on failure backtracks and tries another — potentially exponential work.

A predictive parser eliminates backtracking by looking at the next input token (one token of lookahead) and consulting a table that says exactly which production to use. FIRST and FOLLOW are the sets that make that table well-defined:

• FIRST(alpha) = the terminals that can begin any string derived from alpha. If the next token is in FIRST(alpha_i), pick production A -> alpha_i.
• FOLLOW(A) = terminals that can legally appear right after A. It resolves the case where alpha_i can derive the empty string epsilon — then A is chosen when the lookahead could follow A.

A grammar is LL(1) exactly when these choices are always unambiguous.

How the sets are computed (the fixpoint algorithm)

Both sets are computed by iterating to a fixpoint: repeatedly apply the rules until no set changes. FIRST rules:

• If X is a terminal, FIRST(X) = { X }.
• If X -> epsilon is a production, add epsilon to FIRST(X).
• For X -> Y_1 Y_2 ... Y_k: add FIRST(Y_1) minus {epsilon}. If epsilon is in FIRST(Y_1), also add FIRST(Y_2), and so on; if every Y_i can derive epsilon, add epsilon to FIRST(X).

FOLLOW rules (start symbol S seeded with the end-marker $):

• Place $ in FOLLOW(S).
• For A -> alpha B beta: add FIRST(beta) minus {epsilon} to FOLLOW(B).
• For A -> alpha B, or A -> alpha B beta where epsilon is in FIRST(beta): add FOLLOW(A) to FOLLOW(B).

Then build the table: for each A -> alpha, for each terminal a in FIRST(alpha), set M[A,a] = A -> alpha. If epsilon is in FIRST(alpha), for each b in FOLLOW(A) set M[A,b] = A -> alpha. Note FOLLOW never contains epsilon.

Complexity and a worked step trace

The fixpoint iteration touches every production a bounded number of times; each pass is linear in grammar size, and the number of passes is bounded by the number of symbols, giving O(n^2) to O(n^3) in grammar size n depending on representation (set-union work dominates). The parse table is O(|N| x |T|) space (nonterminals x terminals). Once built, parsing runs in O(length of input) time — each token drives at most a constant amount of stack work per grammar symbol produced.

Classic expression grammar (already left-recursion-eliminated):

E  -> T E'
E' -> + T E' | epsilon
T  -> F T'
T' -> * F T' | epsilon
F  -> ( E ) | id

FIRST(F)=FIRST(T)=FIRST(E) = { (, id }
FIRST(E') = { +, epsilon }   FIRST(T') = { *, epsilon }
FOLLOW(E)=FOLLOW(E') = { ), $ }
FOLLOW(T)=FOLLOW(T') = { +, ), $ }
FOLLOW(F)          = { +, *, ), $ }

Parsing id + id $: stack starts E $. Lookahead id is in FIRST(E), so expand E->T E'; then T->F T'; F->id matches; T' sees + in FOLLOW so takes epsilon; E'->+ T E' consumes the plus, and so on to acceptance — no backtracking.

Where it is used in real systems

FIRST/FOLLOW computation lives inside essentially every LL toolchain:

• Parser generators: JavaCC, Coco/R, and classic LL(1) generators build the predictive table directly from these sets. ANTLR uses their generalization (LL(*)/ALL(*)) and reports conflicts in FIRST/FOLLOW terms.
• Hand-written recursive-descent parsers: many production compilers and interpreters (early C compilers, GCC's and Clang's hand-written parsers, many language front ends, JSON/config parsers) are recursive descent. Engineers reason about FIRST sets to decide which branch to take and FOLLOW sets to know when to stop a repetition.
• Error recovery: FOLLOW sets drive panic-mode recovery — on a syntax error, skip input tokens until one in FOLLOW(A) appears, then pop A and resynchronize.
• Teaching and grammar debugging: they are the standard diagnostic for whether a grammar is LL(1) at all.

They also appear in syntax-directed IDE tooling, linters, and DSL engines where predictable, linear-time parsing with good error messages matters more than raw grammar power.

Comparison with the alternatives

The main rival family is bottom-up LR parsing (LR(1), LALR(1), used by yacc/Bison). LR strictly subsumes LL(1): every LL(1) grammar is LR(1), but not vice versa — LR can handle left recursion and many grammars that FIRST/FOLLOW analysis rejects. The tradeoff: LR builds a larger automaton, is harder to write by hand, and typically produces worse error messages, whereas LL(1) predictive parsing is transparent, gives excellent errors, and maps cleanly onto readable recursive-descent code.

• vs. plain recursive descent: same top-down idea, but the table makes production selection explicit and provably conflict-free; hand-written descent trades that rigor for flexibility and easy semantic actions.
• vs. LL(*)/ANTLR: adaptive lookahead resolves many FIRST/FOLLOW conflicts LL(1) cannot, at runtime prediction cost.
• vs. Earley/GLR: handle any (even ambiguous) CFG in up to O(n^3), but lose the linear-time, single-table simplicity.

Choose LL(1) when your language fits and you value clarity and diagnostics.

Pitfalls, failure modes, and significance

The defining failure mode is a parse-table conflict: a cell M[A,a] gets two productions. This signals the grammar is not LL(1). Two common causes and their fixes:

• Left recursion (A -> A alpha): FIRST(A) is defined in terms of itself and the parser would loop forever. Fix by left-recursion elimination before computing the sets.
• Common prefixes (A -> a B | a C): both alternatives share FIRST tokens. Fix by left factoring into A -> a A'.
• FIRST/FOLLOW overlap: when alpha is nullable and FIRST(other alternative) intersects FOLLOW(A), the choice is ambiguous.

Other pitfalls: forgetting to seed FOLLOW(S) with $, mishandling nullable (epsilon-deriving) chains, and confusing FIRST(epsilon) membership with FOLLOW. Significance: FIRST and FOLLOW are the precise mathematical criterion for when one-token top-down parsing is possible. Formalized in Aho and Ullman's parsing theory and canonized by the Dragon Book, they remain the first algorithm every compiler student implements and the mental model working engineers use to reason about any recursive-descent front end.

LL(1) predictive parsing versus related parsing techniques

Technique	Direction / lookahead	Grammar power	Cost & tradeoff
LL(1) + FIRST/FOLLOW	Top-down, 1 token	LL(1) grammars only (no left recursion)	Table build O(n^2)-O(n^3); parse O(input); simple, great errors
Recursive descent (hand-written)	Top-down, 1+ tokens	LL(k), often ad hoc	No table; more code; easy to add semantic hooks
LR(1) / LALR(1)	Bottom-up, 1 token	Strictly larger (all LL(1) plus more)	Bigger automaton; yacc/Bison; harder error messages
LL(*) / ANTLR	Top-down, adaptive	More than LL(1) via extra lookahead	Runtime prediction cost; resolves many LL(1) conflicts
Earley / GLR	Any CFG	All context-free grammars	O(n^3) worst case parse time; used for ambiguous grammars