5.1 FIRST and FOLLOW Sets

Top-down parsing is a commitment problem. At a nonterminal with several productions, a predictive parser must choose a production before it has parsed the rest of the construct. FIRST and FOLLOW sets turn that choice into finite, inspectable lookahead information. They are not implementation trivia: they are the proof obligations behind an LL(1) parser and the raw material for useful recovery later in this chapter.

For the running grammar, token names are terminals and epsilon denotes the empty sequence:

Program  -> StmtList EOF
StmtList -> Stmt StmtList | epsilon
Stmt     -> let IDENT = Expr ; | print Expr ;
Expr     -> Term ExprTail
ExprTail -> + Term ExprTail | epsilon
Term     -> NUMBER | IDENT | ( Expr )

The grammar has already been left-factored and stripped of left recursion where needed. That work was not cosmetic. FIRST and FOLLOW reveal whether this rewritten grammar can actually be driven by one token of lookahead.

FIRST: What Can Begin Here?

For a grammar symbol or sequence alpha, FIRST(alpha) contains the terminal tokens that may appear first in some string derived from alpha. The set can also contain epsilon when alpha can derive the empty string.

The base rules are deliberately small:

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

• FIRST(epsilon) = { epsilon }.

• For a nonterminal A, union the FIRST sets of every right-hand side of A.

The important case is a sequence. For X1 X2 ... Xn, begin with FIRST(X1) without epsilon. If X1 is nullable, continue into X2; if both are nullable, continue again. Include epsilon only when every symbol in the sequence is nullable.

For example:

FIRST(Term)     = { NUMBER, IDENT, ( }
FIRST(ExprTail) = { +, epsilon }
FIRST(Expr)     = { NUMBER, IDENT, ( }
FIRST(Stmt)     = { let, print }
FIRST(StmtList) = { let, print, epsilon }

Notice the difference between FIRST(StmtList) and FIRST(Stmt StmtList). The first contains epsilon because the list may end. The second does not, because Stmt itself is not nullable. A single incorrect epsilon can put an incorrect production into a parse table, so do not treat nullable as a vague notion of “optional.” It is a formal property of a particular symbol sequence.

FOLLOW: What May Appear Immediately After?

FOLLOW(A) answers a different question: which terminals may occur immediately to the right of a completed A in some sentential form from the start symbol? A nonterminal never appears in a final token stream, so FOLLOW is always a set of terminals. The end-of-input marker EOF belongs in FOLLOW(Program) because a complete program must be followed by the end of the stream.

There are three propagation rules. Reapply them until no set changes.

1. Put EOF in FOLLOW(Start).

2. For every production A -> alpha B beta, add FIRST(beta) - { epsilon } to FOLLOW(B).

3. In the same production, if beta can derive epsilon (including when beta is empty), add FOLLOW(A) to FOLLOW(B).

Consider Expr -> Term ExprTail. FIRST(ExprTail) - { epsilon } contributes + to FOLLOW(Term). Because ExprTail is nullable, anything that follows Expr also follows Term. This is the propagation people most often miss: a nullable suffix lets the enclosing context flow backward to the earlier symbol.

For the running grammar, a fixed point includes:

FOLLOW(Program)  = { EOF }
FOLLOW(StmtList) = { EOF }
FOLLOW(Stmt)     = { let, print, EOF }
FOLLOW(Expr)     = { ;, ) }
FOLLOW(ExprTail) = { ;, ) }
FOLLOW(Term)     = { +, ;, ) }

FOLLOW(Stmt) contains let and print because another statement may immediately begin after a complete statement. This is a grammar-level fact, not a request for a separator token. Whether the language should require newlines or semicolons is encoded elsewhere in the grammar.

Compute to a Fixed Point, Then Validate the Intuition

Mutually recursive grammars make a one-pass calculation unreliable. A robust implementation initializes every set to empty, inserts the obvious base facts, then repeatedly scans productions until an iteration adds nothing. Sets only grow, and there are finitely many terminals, so the process terminates.

repeat
  changed = false
  for each production A -> alpha:
    changed |= addFirstFacts(A, alpha)
until not changed

repeat
  changed = false
  for each production A -> alpha B beta:
    changed |= add(FOLLOW(B), FIRST(beta) - { epsilon })
    if epsilon in FIRST(beta):
      changed |= add(FOLLOW(B), FOLLOW(A))
until not changed

In production code, firstOfSequence deserves its own tested helper. It is used in both FIRST calculation and parse-table construction. A good trace records why a token entered a set, for example ) entered FOLLOW(Expr) from Factor -> ( Expr ). That provenance turns a mysterious table conflict into a debuggable grammar fact.

Sanity-check results against the language, but do not replace the algorithm with intuition. FOLLOW(Expr) should contain ) in a language with parenthesized expressions; it should not contain NUMBER, because two primaries cannot normally touch without an operator. If a surprising token appears, find the exact production and nullable suffix that justified it.

Compute a Sequence From Left to Right

For A -> B C D, FIRST of the right side starts with FIRST(B) without epsilon. Inspect C only when B is nullable, and inspect D only when both B and C are nullable. This stopping rule is the usual source of bad parse tables. FOLLOW moves in the opposite direction: C contributes FIRST(C) to FOLLOW(B), and FOLLOW(A) reaches B only when C can disappear.

Record why each token entered a set, for example “) entered FOLLOW(Expr) from Factor -> ( Expr ).” That provenance turns a later conflict into an explainable grammar fact.