1 Definition
FOLLOW set is a standard notion in context-free grammar analysis. For a given nonterminal, it describes which terminal symbols may appear immediately after that symbol in some valid derivation. The idea is central to top-down parsing because it helps a parser decide when a production can be reduced, expanded, or considered complete.
1.1 Context in formal grammar
In formal language theory, grammars generate strings by repeatedly replacing nonterminal symbols with the right-hand sides of productions. FOLLOW sets summarize the local surroundings of nonterminals inside these generated strings. They are defined with respect to a particular grammar, so the result depends on the production rules in use.
1.2 Nonterminal symbols
A nonterminal is a grammar symbol that can be expanded using one or more productions. FOLLOW sets are usually computed for each nonterminal separately. They answer the question of what may legally come after that symbol in some derivation from the start symbol.
1.3 Terminal symbols
Terminal symbols are the atomic symbols that appear in the final strings of the language. In a FOLLOW set, the relevant members are terminals that can occur directly to the right of a nonterminal. In addition, many definitions include a special end-of-input marker for the start symbol.
2 Mathematical formulation
FOLLOW sets can be described precisely using sentential forms and the notion of immediate right context. The definition is usually framed in terms of all strings derivable from the grammar, not just one production.
2.1 Sentential forms
A sentential form is any intermediate string of terminals and nonterminals produced during a derivation from the start symbol. FOLLOW sets examine all sentential forms that can arise in this way. If a nonterminal appears in such a form, the symbols that can follow it are candidates for its FOLLOW set.
2.2 Immediate right context
The immediate right context of a nonterminal consists of the symbols that appear directly after it in a sentential form. FOLLOW captures the possible terminals in that position across all derivations. If nothing follows the nonterminal, special handling is needed.
2.3 End-of-input marker
The start symbol is typically assigned an end-of-input marker, often written as $ or another distinguished symbol. This indicates that the parser expects the input to finish after a complete derivation from the start symbol. It is included in the FOLLOW set of the start symbol by convention.
3 Computation of FOLLOW sets
FOLLOW sets are usually computed by repeatedly applying grammar-based rules until no set changes. This process is practical because the sets are finite and can be updated monotonically.
3.1 Initialization rules
The FOLLOW set of the start symbol is initialized to include the end-of-input marker. All other FOLLOW sets typically begin empty. From there, information is added using the grammar’s productions.
3.2 Propagation rules
Rules for propagation inspect each production and determine what may follow each nonterminal occurrence. Information may come from the symbols to the right of the nonterminal or, if needed, from the FOLLOW set of the production’s left-hand side.
3.2.1 Terminals following a nonterminal
If a nonterminal is followed by a terminal in a production, that terminal is placed in the nonterminal’s FOLLOW set. This is the simplest case and often provides immediate information. For example, in a rule such as A → X a, the terminal a belongs to FOLLOW(X).
3.2.2 Nullable symbols and epsilon productions
If the symbols to the right of a nonterminal can derive the empty string, then the nonterminal may also be followed by whatever can follow the left-hand side. This is where epsilon productions matter. Nullable symbols therefore cause FOLLOW information to propagate further through the grammar.
3.3 Iterative fixed-point algorithm
Because one update can create new opportunities for later updates, FOLLOW computation is typically iterative. The algorithm repeatedly scans all productions and adds terminals until no set grows further. At that point, a fixed point has been reached and the FOLLOW sets are complete.
4 Relationship with FIRST sets
FOLLOW sets are closely linked to FIRST sets, and the two are often computed together. FIRST describes what can begin a derivation, while FOLLOW describes what can come after a symbol.
4.1 Complementary roles
FIRST and FOLLOW serve complementary parsing tasks. FIRST helps identify which production may match the beginning of a string, while FOLLOW helps determine what symbols are legally expected after a nonterminal. Together they provide a compact summary of grammar behavior.
4.2 Use in parsing rules
In predictive parsing, the parser uses FIRST sets to choose among alternatives. When a production can derive the empty string, FOLLOW sets help decide whether that production is appropriate in the current context. This makes the two sets jointly essential for LL parsing.
4.3 Handling epsilon in FIRST sets
If a symbol sequence has epsilon in its FIRST set, then the symbols following that sequence become relevant. In such cases, FOLLOW information often supplies the terminals needed to complete the parsing decision. This interaction is one of the main reasons epsilon requires special treatment.
5 FOLLOW set construction rules
FOLLOW sets are built by applying a small number of recurring grammar rules. These rules are mechanical, making them well suited to algorithmic implementation.
5.1 Rule for symbols followed by terminals
When a nonterminal is immediately followed by a terminal, that terminal is added directly to the nonterminal’s FOLLOW set. This rule reflects the simplest notion of immediate adjacency in a production. It is local and does not require further inference.
5.2 Rule for symbols followed by nonterminals
When a nonterminal is followed by another nonterminal, the first symbol receives the terminals in the second symbol’s FIRST set, excluding epsilon. If the second nonterminal can derive epsilon, additional symbols may also be inherited from the surrounding context. This rule links FOLLOW computation to FIRST computation.
5.3 Rule for symbols at the end of productions
If a nonterminal appears at the end of a production, then its FOLLOW set includes everything in the FOLLOW set of the production’s left-hand side. This rule allows context to flow backward through the grammar. It is particularly important in chains of nullable symbols.
6 Applications in parsing
FOLLOW sets are widely used in parser construction and grammar analysis. They are especially important in top-down methods, where the parser must decide which rule to apply without backtracking.
6.1 LL(1) parsing
In LL(1) parsing, a single lookahead symbol is used to choose the correct production. FOLLOW sets help determine whether an empty production should be selected when the next input symbol does not match any non-empty alternative. This makes them a key ingredient in deterministic predictive parsing.
6.2 Predictive parsing tables
Predictive parsing tables map nonterminals and lookahead terminals to productions. FIRST sets populate many entries, while FOLLOW sets fill entries associated with nullable productions. A grammar suitable for LL(1) parsing typically yields a table with no conflicts.
6.3 Grammar checking and error recovery
FOLLOW sets also support grammar analysis beyond routine parsing. They can help identify conflicts, such as multiple productions competing for the same table entry. In error recovery, they provide plausible synchronization points, allowing a parser to resume after skipping malformed input.
7 Examples
Examples make FOLLOW sets easier to understand because the abstract rules become concrete. Even small grammars can illustrate how terminals flow through productions.
7.1 Simple grammar examples
| Consider a grammar with a start symbol S and productions such as S → A b and A → a | ε. Since A is followed by b in one production, b belongs to FOLLOW(A). Because S is the start symbol, the end-of-input marker belongs to FOLLOW(S). |
|---|
7.2 Step-by-step computation
First, place the end marker in FOLLOW(S). Next, inspect each production and add terminals that follow nonterminals. Then propagate information through nullable symbols and productions where a symbol appears at the end. Repeating these steps yields stable sets after no new symbols can be added.
7.3 Parse table illustration
In a predictive parse table, a nullable production for A is entered under terminals in FOLLOW(A) when epsilon is part of FIRST of the production. For instance, if A → ε and FOLLOW(A) contains b, then the table entry for A under b may point to that production. This illustrates how FOLLOW sets guide parser choices when no input symbol is consumed.
8 Properties and limitations
FOLLOW sets are useful but depend strongly on the grammar being analyzed. They describe parsing context, not the language in an absolute sense.
8.1 Dependence on grammar form
Two grammars can generate the same language while producing very different FOLLOW sets. The sets reflect the organization of productions, nullable symbols, and recursion patterns. As a result, grammar transformation can change FOLLOW behavior substantially.
8.2 Non-uniqueness across different grammars
Because FOLLOW sets are grammar-specific, there is no single FOLLOW set for a language independent of its presentation. A left-recursive grammar, a factored grammar, and a simplified grammar may assign different contexts to the same conceptual construct. This is why parsing theory often studies grammar form as carefully as language content.
8.3 Practical considerations in compiler implementation
In compiler construction, FOLLOW sets are usually computed as part of a larger grammar-analysis pass. Efficient implementations store sets in bit vectors or similar structures to support fast union operations. The resulting information is then reused in table construction, diagnostics, and parser generation.