Motivation
A context-free grammar describes how strings can be built, but a parser must decide which production to use while it reads an input. A predictive parser makes that choice with one symbol of lookahead. It does not guess and then rewind. The central difficulty is an empty production: if a nonterminal can disappear, the next symbol might come from what follows it rather than from the nonterminal itself.
The FIRST and FOLLOW sets separate those two sources of lookahead. We will construct an LL(1) table, prove what successful parsing means, and see why a conflict is a warning about a particular grammar rather than a proof that its language is impossible to parse another way.
Definitions
Let be a finite context-free grammar. Assume and are disjoint, , and is a fresh end marker outside the grammar alphabet. Assume every nonterminal is reachable from and derives at least one terminal word; this reduced-grammar hypothesis makes the semantic sets below agree with the standard local fixed-point rules. A grammar whose language is empty does not meet this hypothesis because its start symbol is not productive; this chapter does not claim the fixed-point statements for that case. Usual useful-symbol preprocessing can remove nonproductive and unreachable symbols when a productive start remains, but we work with the resulting hypothesis explicitly.
Definition 3.2.1
(Nullable strings and FIRST)
A string of grammar symbols is nullable if . Define to contain each terminal that can begin a terminal word derived from , and also if is nullable.
Definition 3.2.2
(FOLLOW sets and the end marker)
For a nonterminal , contains a terminal if for grammar-symbol strings . It contains if and is nullable. Equivalently, in a sentential form where an occurrence of can be followed by a terminal continuation beginning with , that is in FOLLOW; the end marker records an occurrence that can be the last source of input.
Definition 3.2.3
(Predictive parsing table and conflicts)
A table has one row per nonterminal and one column for each terminal and . For every production , put that production in for each terminal . If , also put it in for each . A cell may remain empty. A conflict is a cell containing two distinct productions; inserting the same production twice does not create a conflict.
Concept lensStructural
Conflict-freeness as two disjointness tests
For a reduced grammar, the table has no conflict exactly when, for each with productions , two conditions hold. First, for , counting as a member. Second, if is nullable, then for every . These are the FIRST/FIRST and FIRST/FOLLOW tests, and each failure names the pair of productions that collide.
Theorem 3.2.4
(FOLLOW propagation)
For every production , every terminal in is in . If is nullable, every member of is also in . The end marker is in .
Proof
(Extending a derivation of the outer symbol)
Because is reachable, for some strings , and with the production this gives . If is a terminal, then for some string , so and .
Now let be nullable. If , say , then , because disappears; so . If instead , with and nullable, then is nullable and , so . Finally with empty and , which puts in .
The rule handles occurrences separately: a nonterminal can have several different contexts, and its FOLLOW set is the union of the sets they give.
Computing the sets
Nullable nonterminals are obtained by a least fixed point. Initially none is marked. Repeatedly mark if a production has every already marked nullable; the empty right-hand side qualifies immediately. A right-hand side containing a terminal cannot be nullable. Because there are finitely many nonterminals, this process stops.
To compute FIRST, add a terminal to when it can begin the right-hand side of a production for . Scan the right-hand side left to right: add the nonempty FIRST terminals of each symbol, and continue past that symbol only when it is nullable. Add when every symbol is nullable. Repeating until no set grows gives the least fixed point. For a terminal , ; the FIRST set of the empty string is .
For FOLLOW, start with and repeatedly apply the propagation theorem to every nonterminal occurrence in every right-hand side. Never insert into a FOLLOW set. Each set is a subset of the finite set , so the fixed point terminates. The least fixed points contain exactly the symbols justified by finite derivations: each insertion has a derivation witness, and induction on a finite derivation shows that every required symbol is eventually inserted.
Reading a fixed-point calculation
It helps to separate the rounds from the final answer. Consider , , and . The first nullable round marks and because each has an empty production; the next round can mark . FIRST of then contains both and , because may disappear, and contains because both components may disappear. If is the start symbol, its FOLLOW contains the end marker. The rule for the occurrence of adds and the end marker to FOLLOW; the occurrence of gets the end marker.
One should continue until no change is possible rather than stop after a fixed number of passes. A chain of productions can have many nonterminals, and the information at one end may take several rounds to reach the other. Termination follows from finite sets that only grow, not from a prescribed number such as two. Conversely, adding a terminal merely because it appears somewhere later in a production can overestimate FIRST when an earlier nonnullable symbol blocks it. Both the direction and the condition on nullable prefixes matter.
The predictive parser
Initialize a stack with above and an input consisting of the word followed by . Repeatedly inspect the top stack symbol and current input symbol. If they are matching terminals, remove both and advance the input. If the top is a nonterminal , consult for the current input symbol . If it contains a production , remove and push the right-hand side in reverse order, leaving on top. For an empty right-hand side, push nothing. An empty table cell or mismatched terminal reports failure. Accept when stack and input both show .
The stack is written with its top on the left in our traces. For example, replacing top by changes a stack into . Only the leftmost outstanding nonterminal is expanded after all preceding terminals have been matched. Consequently, the parser's production choices describe a leftmost derivation.
Proof: soundness and completeness
Theorem 3.2.5
(Predictive table correctness)
If the table has no conflicts, the stack parser described above accepts exactly the terminal words generated by . For every generated word it reaches acceptance in finitely many steps. On inputs outside the language, acceptance never occurs; termination on every such input is not asserted here.
Proof
(A stack invariant and a leftmost derivation)
For soundness, maintain an invariant: the consumed input followed by the grammar-symbol portion of the stack is a sentential form derived from . A production step applies the indicated grammar rule to the leftmost outstanding nonterminal; a matching step transfers the first stack terminal into the consumed prefix without changing their concatenation. When both markers are reached, the stack has no grammar symbols left. The consumed input is therefore a terminal word derived from .
For completeness, fix a generated word and a finite leftmost derivation of it. Suppose the parser has followed that derivation so far. If the next stack symbol is a terminal, it equals the next input terminal. If it is a nonterminal expanded by in the chosen derivation, either the remaining input begins with a terminal generated by , or derives and the lookahead comes from the continuation after that occurrence of (possibly ). In the first case the production was inserted using FIRST; in the second it was inserted using FOLLOW. The table has no conflict, so the parser selects that same production. Induction follows the finite derivation through to acceptance.
This argument does not require a claim that arbitrary table-driven computations terminate on every rejected input. It proves that a member has a finite successful computation and, because the table is deterministic, the parser follows it. Under the stated assumptions, any reported failure is therefore a correct rejection. Proving a separate worst-case running time or termination guarantee for all nonmembers requires additional analysis of the grammar and implementation.
Proof X-ray
Where does the lookahead come from?
The completeness argument is a case split on the stack top. A terminal on top needs no table: the derivation fixes it and the input agrees. A nonterminal expanded by splits again according to the current lookahead . If begins a word derived from , then and the FIRST rule filled the cell . If in the chosen derivation, then comes from what follows this occurrence of , so and the FOLLOW rule filled the cell; here may be . The two cases are exhaustive, and this is why both sets are needed.
Hypotheses enter at three points. The reduced-grammar assumption makes the semantic FOLLOW used here agree with the set computed by the fixed point. Absence of conflicts is used once, at the end: it turns "the right production is in the cell" into "the right production is the only one in the cell". Without it the table may still contain every correct choice, but the parser cannot know which to take. For and on input , the cell holds both productions, and a parser that picks fails at although is generated. Finally, the induction follows one fixed finite derivation, so the successful run is finite automatically.
Worked examples
Worked example 3.2.6
(An optional a before b)
Let and . Then is nullable, , and . The table has , , and . No cell conflicts. The language is .
On input , the stack/input pairs begin , then , then . Matching and reaches . On input , the entry chooses the empty production and permits the same final match.
Worked example 3.2.7
(A FIRST/FIRST conflict)
For , both right-hand sides have FIRST set , so contains two productions. The table cannot choose between them using only the current lookahead. Factoring to and gives a conflict-free table for the same language. Thus the original table conflict concerns the given grammar, not the regular language itself.
Worked example 3.2.8
(A FIRST/FOLLOW conflict)
Let and . Because , the table cell receives both from FIRST and from FOLLOW. On seeing the first , one symbol of lookahead does not distinguish whether it belongs to or to the following terminal. The language is , again showing that a grammar conflict need not make the language intrinsically difficult.
Worked example 3.2.9
(A nullable suffix propagates FOLLOW)
For , , , , both and are nullable. Hence FIRST of contains . The FOLLOW rule puts and in FOLLOW; because the entire suffix is nullable, it also puts there. Looking only at the immediately adjacent nonterminal would miss the terminal and the end marker.
Counterexample mode
A table conflict is not a language impossibility proof
Claim: if the table of a grammar has a conflict, the language cannot be parsed deterministically with one symbol of lookahead. For the cell holds both productions, so the table conflicts. Yet the language is finite, and the factored grammar , has , , , with no cell holding two productions. A conflict shows that this grammar and this one-symbol table construction cannot make the required deterministic choice; it does not show that every grammar for the language conflicts.
Common mistakes
Common mistake
(FIRST of a sequence is not a union)
FIRST of a sequence is not simply the union of FIRST sets of every symbol in that sequence. A later symbol can begin the derived word only if all earlier symbols disappear. In with nullable and FIRST, FIRST; the empty word is not in that set because the terminal remains.
Common mistake
(FOLLOW is not FIRST, and # is not the empty word)
FOLLOW describes possible symbols after an occurrence, not symbols generated by the nonterminal itself. Put a nullable production into FOLLOW columns, but do not add as a table column. The end marker is different from the empty word: it is a bookkeeping symbol indicating that no input remains.
Common mistake
(Empty cells are not defects)
A conflict-free table may have empty cells. They are useful: if the parser reaches an empty cell, that lookahead cannot begin a successful continuation under the correctness theorem. Filling an empty cell with an arbitrary rule could create an incorrect parser.
Summary
Nullable information controls how far FIRST scans through a right-hand side. FOLLOW supplies the lookahead after a nullable expansion. A conflict-free table selects productions deterministically; a stack invariant proves soundness, and a finite leftmost derivation proves completeness for every member. Table conflicts belong to the chosen grammar and lookahead construction, so equivalent grammar transformations can remove some conflicts.
Exercises
Quick check
(For , compute and and give the two nonempty table cells.)
Remember that for the start symbol.
Solution · Answer
and . Cell contains and contains .
Quick check
(For , , , compute and .)
Decide first which of and are nullable.
Solution · Answer
Both and are nullable, so . The suffix after is , whose nonempty FIRST contains and which is nullable; therefore .
Quick check
(Explain the conflict in and give an equivalent conflict-free grammar.)
Compare the FIRST sets of the two right-hand sides.
Solution · Answer
Both alternatives begin with , so contains both productions. The grammar , generates the same language and has disjoint table choices: on and on .
Quick check
(Trace the parser for the grammar on input , listing the production choices and the final marker condition.)
Use the table cells from the first question.
Solution · Answer
On the first and second , the parser chooses and matches that terminal. At end of input it chooses , leaving on the stack and input. It accepts. The derivation is .