6.2 FIRST, FOLLOW, and Error Recovery: Why Predictive Parsing Can Make Decisions

A predictive parser aims to choose a production from one lookahead token and continue reporting structural problems after an input error.

Recursive descent code may appear like hand-written branching, but behind each branch lies a checkable condition: given the current token, at most one production rule should be valid. FIRST and FOLLOW sets turn this intuition into a formal algorithm.

Learning Objectives

• Compute nullable, FIRST, and FOLLOW sets;
• Construct an LL(1) parsing table and identify conflicts;
• Distinguish between eliminating left recursion and factoring out left factors;
• Use panic mode, insertion, and error recovery nodes.

1. Nullable and FIRST

A nonterminal $A$ is nullable if it can derive the empty string $\epsilon$, i.e., if $A{\Rightarrow }^{\ast }\epsilon$. FIRST$(\alpha )$ contains each terminal $a$ for which $\alpha {\Rightarrow }^{\ast }a\beta$, where $\beta$ is a sequence of grammar symbols; if $\alpha$ is nullable, it also includes $\epsilon$.

Given the following grammar:

Stmt  → "return" ExprOpt ";"
ExprOpt → Expr | ε
Expr → IDENT | NUMBER

We have:

FIRST(Expr)    = { IDENT, NUMBER }
FIRST(ExprOpt) = { IDENT, NUMBER, ε }
FIRST(Stmt)    = { "return" }

Computing FIRST requires fixed-point iteration: repeatedly propagate information from productions until the sets no longer change. For recursive grammars, a single top-down pass is insufficient.

2. FOLLOW Processing Optional Branches

FOLLOW$(A)$ contains the terminals that may immediately follow $A$ in a sentential form derived from the start symbol. It also includes EOF if $A$ can occur at the end. EOF marks the input boundary rather than an ordinary grammar terminal. Here, Stmt is the start symbol.

Key rules:

• If $X\to \alpha A\beta$, add FIRST$(\beta )\setminus \{\epsilon \}$ to FOLLOW$(A)$;
• If $\beta$ is nullable or the production ends with $A$, add FOLLOW$(X)$ to FOLLOW$(A)$.

In this grammar, ExprOpt is followed directly by ;, so:

FOLLOW(ExprOpt) = { ";" }

When encountering return ;, the current token ; is not in FIRST$(Expr)$ but is in FOLLOW$(ExprOpt)$, and the parser selects the $\epsilon$ branch accordingly.

3. LL(1) Parsing Table Filling Rules

For a production rule $A\to \alpha$:

1. For each symbol $a\in FIRST(\alpha )\setminus \{\epsilon \}$, add the production to table entry $M[A,a]$;
2. If $\epsilon \in FIRST(\alpha )$, then for each symbol $b\in FOLLOW(A)$, add the production to $M[A,b]$.

If a table cell contains two distinct productions, an LL(1) conflict exists. Possible causes include:

• The FIRST sets of two alternatives overlap;
• One alternative is nullable and another alternative’s FIRST set intersects the nonterminal’s FOLLOW set;
• The grammar is ambiguous;
• The grammar is unambiguous but not LL(1).

The presence of a conflict does not imply that the language cannot be parsed with recursive descent. Conflicts can be resolved by rewriting the grammar, introducing lookahead symbols, using semantic predicates, or switching to a different parsing algorithm.

4. Left Recursion and Common Prefixes Are Different Problems

Direct left recursion:

Expr → Expr "+" Term | Term

causes a direct recursive descent parser to call itself before consuming a token. Expressions are typically rewritten as:

Expr → Term ("+" Term)*

Common prefix:

Stmt → IDENT "=" Expr | IDENT "(" Args ")"

A lookahead only sees IDENT and cannot determine which alternative to choose. This can be resolved by factoring out the common prefix:

Stmt → IDENT StmtTail
StmtTail → "=" Expr | "(" Args ")"

Eliminating left recursion prevents recursion without input progress. Left factoring delays the choice until after the shared prefix. These transformations do not automatically resolve grammatical ambiguity or design conflicts in the language.

5. Good Diagnostics Require an Expected Set

Nonempty entries in the current prediction-table row identify lookaheads that select a production for that nonterminal. An empty entry for the actual token means no production can be selected there. Expected-token reporting must also account for the current call or stack context, including nullable exits. Error messages should include:

actual token + expected token set + source span + relevant context

For example:

line 8:14: Encountered `}` in parameter list; expected an expression or `)`

Internal non-terminal names should not be exposed to users, such as "expected ExprTailPrime". The diagnostic layer should map these to language-level concepts and control the size of the expected set.

6. Panic Mode Synchronization

After encountering an error, skip tokens until reaching a boundary defined in the synchronization set:

Statement synchronization: ; } EOF
Declaration synchronization: class fn let EOF
Parameter synchronization: , ) EOF

The synchronization set is often derived from the FOLLOW set, but should be manually adjusted based on the language's structural constraints. Skipping too few tokens can lead to cascading errors, while skipping too many may inadvertently consume valid subsequent code that should be parsed.

static void synchronize_statement(Parser *p, size_t failed_start) {
    assert(failed_start <= p->current);
    while (peek(p)->kind != TOK_EOF) {
        if (p->current > failed_start
                && p->tokens[p->current - 1].kind == TOK_SEMICOLON) return;
        if (peek(p)->kind == TOK_RIGHT_BRACE) return;
        if (p->current > failed_start && starts_statement(peek(p)->kind)) return;
        p->current++;
    }
}

This recovery fragment uses the previous lesson’s Parser; the language defines starts_statement. The caller saves failed_start = p->current before attempting a statement and maintains 0 <= failed_start <= current < count. It may return at a new statement start only after that attempt has advanced; the same guard makes access to the previous token safe.

A closing brace is left for the enclosing block to consume. At top level, an unmatched } must be diagnosed and consumed, or parsing must stop. Returning from a helper is not enough: the whole calling loop must make progress.

7. Inserting, Deleting, and Error Nodes

If the parser encounters:

print(value

and the file ends there, it can generate a zero-length ) token, report a missing token, and continue building the call node. For extraneous commas, the parser may remove the current token and retry.

Recovery operations come with costs and constraints:

• Prefer minimal, local insertions or deletions;
• Avoid re-reporting the same location;
• Limit the total number of diagnostics;
• Retain missing or error nodes in the AST;
• Allow subsequent semantic analysis to detect error nodes, preventing the generation of meaningless cascading diagnostics.

8. LL(k) and Hand-Crafted Parsing

LL(1) uses a single lookahead token. LL(k) extends this by using a fixed number $k$ of lookahead tokens, with grammar classes becoming more powerful as $k$ increases, though the parsing tables may grow significantly in size. Hand-written parsers often examine two or more tokens locally, or employ Pratt parsers to handle expressions.

This does not preclude using FIRST/FOLLOW sets to analyze most grammars. What truly matters is clearly documenting exception branches, lookahead counts, and backtracking behavior, not treating hand-written parsing as something that bypasses formal analysis.

Common Misconceptions

• FIRST only looks at the first symbol of a production: If the prefix can be empty, continue through the following symbols.
• FOLLOW is the next token at runtime: It is the set of all possible tokens that can follow a given non-terminal across all possible derivations.
• LL conflicts imply grammatical ambiguity: An unambiguous grammar may still not be LL(1).
• Aggressive error recovery is better: Excessive error correction can produce incorrect ASTs and misleading diagnostics.

Exercise

1. Compute the FIRST and FOLLOW sets for a grammar that accepts comma-separated, optional-empty lists of parameters.
2. Identify one FIRST/FIRST conflict and one FIRST/FOLLOW conflict.
3. Design synchronization sets for blocks, statements, and parameter lists.
4. Represent a missing semicolon with a zero-length synthetic token and prevent duplicate diagnostics.

Summary

FIRST tells the parser how it might begin parsing, and FOLLOW provides a basis for exit when encountering nullable branches; together, they determine whether an LL(1) parser can make a unique choice based on a single token. Error recovery elevates a "parsing failure" into a bounded diagnosis with a fallback to continue processing.

The next lesson takes a different approach: it first consumes input fragments, then reduces to nonterminals when a handle is detected.