skip to content

Why does a recursive-descent parser need FOLLOW sets, and not just FIRST sets, when a grammar rule can derive the empty string?

level: middleimportance: should knowfreq 50%

answer

  1. an alternative that spells out nothing
  2. no starting token to branch on
  3. look past the rule, not into it
  4. the delimiter that closes the enclosing block
  5. two sets feed one prediction

basics

~20 s

An alternative that derives nothing begins with no token, so FIRST cannot describe it. The parser takes that empty branch when the next token is one that may legally appear immediately after the rule — that set is FOLLOW.

solid answer

~50 s

FIRST of an alternative is the set of tokens some string derived from it can begin with. For an alternative that derives the empty string there is no such token, so FIRST says nothing useful and the parser needs another signal. That signal is FOLLOW of the nonterminal: the tokens that can appear immediately after it anywhere in a derivation from the start rule. The prediction set for an alternative is therefore FIRST of that alternative, minus the empty marker, plus FOLLOW of the nonterminal when the alternative can vanish. In a job language with `block -> '{' directives '}'` and `directives -> directive directives | (nothing)`, FIRST of the non-empty alternative is `{'every','retry','run'}` and FOLLOW of `directives` is `{'}'}` — so a closing brace, and only a closing brace, tells the loop to stop.

go deeper

for a junior

Recall that some rules can match nothing at all, and that such a rule has no starting token to look for. Knowing that a parser must then look at what comes next is the right level of detail here.

for a middle

Define both sets precisely and combine them: prediction set equals FIRST of the alternative, without the empty marker, plus FOLLOW of the nonterminal when the alternative can vanish. Work a small list rule through it out loud.

for a senior

Show that the sets are a whole-grammar fixed point and that reusing one list rule in a second enclosing context grows FOLLOW and can break a branch that was previously correct. Tie the sets to the parser's error message.

for a principal

Weigh whether a language's rule set stays inside the one-token discipline as it evolves. Decide whether to keep the grammar checkable by a tool or accept that its prediction sets will only ever be verified by tests.

## Two sets, two different questions A predictive parser has one question to answer at every choice point: *given this one unconsumed token, which alternative do I take?* Two sets computed from the grammar answer it. - **FIRST(alpha)** is the set of terminals that can begin some string derived from the symbol sequence `alpha`. It also records a marker for the empty string when `alpha` can derive nothing at all — that marker is not a token and never appears in the input. - **FOLLOW(A)**, defined for a nonterminal `A` only, is the set of terminals that can appear immediately to the right of `A` in some sequence derivable from the start rule. It includes the end-of-input marker when `A` can end a whole valid input. FIRST answers *what can this alternative start with*. FOLLOW answers *what can legally come next once this rule is finished*. Only the second question has an answer when the alternative produces nothing. ## The prediction set Combining them gives the set a function actually branches on. For each alternative `A -> alpha`: 1. Start with FIRST(alpha), with the empty marker removed. 2. If `alpha` can derive the empty string, add all of FOLLOW(A). 3. The result is the **prediction set** — the tokens on which this alternative is taken. The grammar is **LL(1)** exactly when, for every nonterminal, the prediction sets of its alternatives are pairwise disjoint. That is the condition under which the mechanical branch-on-one-token design is even possible, and at most one alternative of a nonterminal may be empty-deriving, since two would have identical prediction sets. ## Worked on a job-scheduling rule set ```pseudocode job -> 'job' NAME block block -> '{' directives '}' directives -> directive directives | (nothing) directive -> 'every' DURATION | 'retry' NUMBER | 'run' STRING ``` | set | value | why | |---|---|---| | FIRST(directive) | `{'every','retry','run'}` | the three alternatives' leading keywords | | FIRST(directives) | `{'every','retry','run'}` plus the empty marker | it may be a directive list or nothing | | FOLLOW(directives) | `{'}'}` | the only place it occurs is before the closing brace of `block` | | predict(directives -> directive directives) | `{'every','retry','run'}` | FIRST, with the empty marker dropped | | predict(directives -> nothing) | `{'}'}` | FOLLOW, because the alternative vanishes | The two prediction sets are disjoint, so `parse_directives` is a loop: while the next token is one of the three keywords, parse another directive; on a closing brace, return; on anything else, report an error naming those four tokens. The error message writes itself out of the prediction sets, which is one practical payoff of computing them. ## Computing the sets is a fixed point Neither set can be read off a rule in isolation, because both are defined in terms of each other across the whole grammar. Both are computed by iterating to a fixed point: 1. Initialise every set to empty. 2. Sweep all rules, adding whatever each rule forces: a terminal at the front of an alternative joins that nonterminal's FIRST; whatever can follow a nonterminal in some right-hand side joins its FOLLOW; and when the symbols after an occurrence can all vanish, the enclosing nonterminal's FOLLOW flows into it too. 3. Repeat the sweep until nothing changes. The iteration always terminates because the sets only grow and the alphabet is finite. Two directions are easy to get backwards and worth stating explicitly: the empty marker lives in FIRST and never in FOLLOW, and FOLLOW is defined for nonterminals, never for terminals. ## Why hand-written parsers still care A hand-written parser contains no table, so it is tempting to skip this analysis and write the branches by intuition. The analysis is what tells you the intuition is sound. Two failures show up in production parsers written without it: - **A loop that never stops or stops too early**, because the author guessed the exit condition for an empty-deriving list instead of deriving it from FOLLOW. - **A silent overlap**, where a token belongs to two prediction sets and the alternative written first quietly wins — an input the grammar says is legal is then rejected, or parsed as the wrong construct. One caution about FOLLOW: it is a whole-grammar property, not a local one. If the same list nonterminal is reused in a second context — say a directive list that can also close with an `end` keyword — FOLLOW grows, and a branch that was correct becomes wrong everywhere. Reusing one list rule in two enclosing contexts is exactly how that surprise arrives.

  • Can two alternatives of the same nonterminal both derive the empty string?
    Not in a grammar a one-token parser can handle. Both would have the same prediction set — FOLLOW of that nonterminal — so no lookahead could ever separate them, and the choice would be arbitrary. In practice two empty alternatives also mean the rule set is redundant, since one of them contributes nothing the other does not.
  • What happens to the prediction sets if the same list rule is reused inside a second construct?
    FOLLOW of that nonterminal grows to include whatever can come after it in the new context, so its empty alternative is now predicted on more tokens. If any of those tokens already belongs to another alternative's prediction set, a grammar that was LL(1) stops being so, and the breakage appears in the original context too, not only the new one.
  • Does the end-of-input marker belong in these sets?
    It belongs in FOLLOW, for every nonterminal that can end a complete input — beginning with the start rule. Without it, a parser cannot tell that a top-level empty-deriving rule should stop at the end of the file, and it will demand a token that never arrives.

saying these in an interview costs you the question

  • Says FIRST sets alone decide every branch, including the empty one
  • Puts the empty-string marker into a prediction set as a token
  • Computes FOLLOW for terminals instead of for nonterminals
  • Claims a rule deriving nothing always makes a grammar unusable
  • Treats FOLLOW as local to one rule rather than whole-grammar