Recursive Descent and LL Analysis

The most widely used parser writing method: hand-written recursive descent, intuitive, controllable, and good error messages—underpinned by LL(1) FIRST/FOLLOW theory and Pratt parser priority-driven logic, a combination that covers most practical grammars.

Overview

Parsing is the second stage of compilation: transforming the sequence of tokens produced by lexical analysis into an Abstract Syntax Tree (AST). There are two main approaches: LL (top-down, deriving input from the grammar) and LR (bottom-up, reducing input to the grammar). This article focuses on the LL approach—recursive descent and its underlying theory (LL(1), FIRST/FOLLOW, left-recursion elimination). Hand-written recursive descent parsers remain the industry mainstream (Clang, Rust, and Go compilers all use hand-written recursive descent) because they are intuitive, readable, and allow for better control over error messages—features that parser generators still struggle to match.

Recursive Descent: One Function Per Grammar Rule

The core idea is extremely simple: write a function for each non-terminal (the left-hand side symbol of a grammar rule, such as expression or statement). The function body attempts to match the right-hand side of that rule. Consider a simple arithmetic grammar:

expr    → term (('+' | '-') term)*
term    → factor (('*' | '/') factor)*
factor  → NUMBER | '(' expr ')'

Translated into recursive descent:

def expr():
    left = term()
    while peek() in ('+', '-'):    ← Repeatedly attempt, not recursion
        op = consume()
        right = term()
        left = BinOp(op, left, right)
    return left

def term():
    left = factor()
    while peek() in ('*', '/'):
        op = consume()
        right = factor()
        left = BinOp(op, left, right)
    return left

def factor():
    if peek() == '(':
        consume('(')
        node = expr()              ← Recursion back to expr here
        consume(')')
        return node
    else:
        return Number(consume(NUMBER))

Key mechanisms:

• Each function starts from the current token, consumes exactly the number of tokens it can handle, and returns an AST subtree.
• peek() looks at the current token without consuming it; consume() consumes it and advances.
• Left recursion (expr → expr + term) leads directly to infinite recursion—expr() calls expr() in its first line. Left recursion must be eliminated: rewrite A → Aα | β as A → β A', A' → α A' | ε. This elimination targets direct left recursion; indirect left recursion (A → B → A) must first be eliminated via substitution.

Eliminating Left Recursion: Algorithms and Costs

Immediate left recursion (where the first symbol on the right-hand side of a rule is the non-terminal itself) can be mechanically eliminated:

Original Grammar:  expr → expr + term | term
                   term → term * factor | factor

After Elimination: expr  → term expr'
                   expr' → + term expr' | ε
                   term  → factor term'
                   term' → * factor term' | ε

The cost is that the AST structure changes—the original grammar's expr + term directly corresponds to a left-associative subtree, whereas after elimination, expr' accumulates right-associatively. You must manually enforce left-associativity when constructing the AST to preserve operation order. The Pratt parser avoids explicit left-recursion elimination by using a different approach (descending layer by layer based on precedence).

FIRST and FOLLOW: The Theoretical Foundation of LL

The essence of recursive descent is deciding which branch to take based on the current token. The theoretical basis for this decision is the FIRST and FOLLOW sets:

• FIRST(X): The set of the first tokens of all strings that can be derived from X. If X can derive ε (empty), then ε is also in FIRST(X).
• FOLLOW(X): The set of tokens that can immediately follow X in any derivation.

For Grammar:  E → T E'
              E'→ + T E' | ε
              T → id

FIRST(T) = {id}
FIRST(E')= {+, ε}
FIRST(E) = FIRST(T) = {id}
FOLLOW(E')= FOLLOW(E) = {$}   ← $ is the end-of-input marker

The engineering implication for LL(1): For a rule A → α | β, FIRST(α) and FIRST(β) must not intersect—otherwise, you cannot decide which path to take when seeing the current token. The 1 in LL(1) refers to "looking at 1 token to make a decision."

Therefore, when a hand-written recursive descent parser cannot make an LL(1) decision, it may:

• For operators: Use Pratt/precedence climbing (relying on a precedence table, requiring no left-recursion elimination) to handle expressions. This is flatter than the traditional expr→term→factor hierarchy; adding an operator only requires modifying one table. Of course, writing recursive descent as expr → term expr' / expr' → + term expr' | ε after eliminating left recursion is also fully feasible and is the standard textbook approach.
• For keywords: if / while / return are naturally mutually exclusive in FIRST sets, allowing direct routing based on the current token.

Pratt Parser: Replacing Grammar Hierarchy with a Precedence Table

For expressions (arithmetic, comparison, logical), the hierarchy of recursive descent (expr→term→factor) results in deep call stacks for operator nesting, and adding an operator requires restructuring the grammar hierarchy. The Pratt parser replaces this with a precedence table:

precedence = {
    '+': 10, '-': 10,
    '*': 20, '/': 20,
    '(': 0,                 ← Lowest precedence, handled only in prefix
}

def expr(min_prec=0):
    left = prefix(peek())   ← Prefix operator (e.g., -x)
    while prec(peek()) >= min_prec:    ← Core: compare precedence
        op = consume()
        right = expr(prec(op) + (1 if left_associative else 0))
        left = BinOp(op, left, right)
    return left

Core rule: If the current operator's precedence ≥ minimum precedence, continue combining to the right (forming a larger expression); otherwise, return. +1 handles left-associativity (increasing min_prec so that operators of the same precedence are consumed first); right-associativity (e.g., =) does not add 1.

This is flatter than the "expr/term/factor" hierarchy; adding a new operator only requires adding a line to the precedence table, without changing the grammar or the call stack.

Problems with LL and Solutions

• Left Recursion: Elimination changes the AST structure → Pratt bypasses this (for expressions), or you manually reverse associativity when constructing the AST.
• Common Prefixes: LL(1) conflict in if (cond) { ... } if (cond) { ... } else { ... }—after seeing if, you cannot decide whether to choose if or if-else → Solution: The dangling else is always matched with the nearest if (in recursive descent, parse_if greedily consumes else once seen).
• Error Recovery: The biggest advantage of recursive descent—each function can decide on the fly to "skip extra tokens to a sync marker" (e.g., jump to ; or }), producing error messages far superior to those of LR parsers.

Table-Driven LL: When Recursive Descent Is Not Enough

In some scenarios (e.g., user-provided grammars, or grammars too large for hand-writing), table-driven LL is used. Calculate FIRST/FOLLOW from the grammar and build a predictive parsing table:

For rule A → α:
  For each token t in FIRST(α):
    table[A][t] = α
  If ε ∈ FIRST(α):
    For each token t in FOLLOW(A):
      table[A][t] = α

At runtime, select the rule based on table[current non-terminal][current token]—equivalent to recursive descent, but the branches are not hardcoded in the code but stored in a table. However, error messages are hard to handle well in table-driven approaches (lacking the semantic context present in hand-written functions).

References

• Dragon Book: Chapter 4, Syntax Analysis — Complete derivation of LL(1), FIRST/FOLLOW
• Pratt (1973): "Top Down Operator Precedence" — The original paper on the Pratt parser
• Nystrom: "Crafting Interpreters", Chapter 6 (Excellent explanation of Pratt parser implementation)

Keywords: recursive descent, LL(1), FIRST, FOLLOW, predictive parsing, left recursion, left recursion elimination, Pratt parser, precedence climbing, top-down operator precedence, table-driven LL, dangling else, synchronizing token, error recovery