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

The parser room wants to choose a production rule based solely on the next token lookahead, and still be able to report structural errors after input mistakes.

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 $\varepsilon$, i.e., if $A \Rightarrow^* \varepsilon$. The FIRST$(\alpha)$ set contains all terminal symbols that can appear at the beginning of a string derived from the symbol sequence $\alpha$; if $\alpha$ is nullable, it also includes $\varepsilon$.

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) is the set of terminal symbols that may immediately follow A in a sentence. The FOLLOW set of the start symbol includes EOF.

Key rules:

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

In the grammar above, something after ExprOpt is always followed 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 $\varepsilon$ 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 {\varepsilon}$, add the production to table entry $M[A, a]$;
2. If $\varepsilon \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;
• A nullable alternative's FIRST and FOLLOW sets conflict;
• 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 infinite recursion by delaying the choice until after parsing the shared prefix. These transformations do not automatically resolve grammatical ambiguity or design conflicts in the language.

5. Good Diagnostics Require an Expected Set

When a prediction table has empty entries, it directly indicates which tokens are allowed at the current position. 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) {
    while (peek(p)->kind != TOK_EOF) {
        if (previous(p)->kind == TOK_SEMICOLON) return;
        if (peek(p)->kind == TOK_RIGHT_BRACE) return;
        if (starts_statement(peek(p)->kind)) return;
        p->current++;
    }
}

Loops must ensure either consumption or return. Recovery functions also need access to a safe previous to prevent underflow at the start of the input.

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, propagation must continue backward.
• 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. Introduce a synthetic token for zero-length parameter lists (missing semicolons), and ensure no duplicate error messages are generated.

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.