---
title: Recursive Descent and LL Analysis
url: https://doc.liz6.com/en/compilers/02-syntax-analysis/01-recursive-descent-and-ll-analysis
locale: en
area: compilers
tags:
- compilers
- syntax-analysis
date: 2026-06-30
modified: 2026-07-16
description: '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.'
---

# 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*