---
title: 递归下降与 LL 分析
url: https://doc.liz6.com/compilers/02-syntax-analysis/01-recursive-descent-and-ll-analysis
locale: zh
area: compilers
tags:
- compilers
- 语法分析
date: 2026-06-30
modified: 2026-06-30
description: 最广泛使用的 parser 编写方式:手写递归下降,直观、可控、错误信息好——背后是 LL(1) 的 FIRST/FOLLOW 理论和 Pratt parser 的优先级驱动,一套组合拳覆盖了大多数实用文法。
---

# 递归下降与 LL 分析

> 最广泛使用的 parser 编写方式:手写递归下降,直观、可控、错误信息好——背后是 LL(1) 的 FIRST/FOLLOW 理论和 Pratt parser 的优先级驱动,一套组合拳覆盖了大多数实用文法。

## 概述

语法分析(parsing)是编译的第二道工序:把词法分析产出的 token 序列变成**抽象语法树(AST)**。主要有两条路线:**LL**(自顶向下,从文法出发推导输入)和 **LR**(自底向上,从输入归约到文法)。这篇讲 LL 路线——递归下降(recursive descent)及其背后的理论(LL(1)、FIRST/FOLLOW、左递归消除)。手写的递归下降 parser 仍然是业界主流(Clang、Rust、Go 的编译器都是手写递归下降),原因是**直观、可读、错误信息好控制**——这些是 parser generator 至今难做好的。

## 递归下降:一个函数对应一条语法规则

核心思想极其朴素:每条非终结符(文法的左侧符号,如 `expression`、`statement`)写成一个函数,函数体中按该规则的右侧**试探**。看一个简单算术文法:

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

翻译成递归下降:

```
def expr():
    left = term()
    while peek() in ('+', '-'):    ← 反复试探,不是递归
        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()              ← 这里递归回到了 expr
        consume(')')
        return node
    else:
        return Number(consume(NUMBER))
```

关键机制:
- **每个函数从当前 token 开始**,消费恰好它能处理的 token 数量,返回 AST 子树。
- **peek() 看当前 token,不消费;consume() 消费并前进**。
- 左递归(`expr → expr + term`)会直接导致无限递归——`expr()` 第一行又调 `expr()`。**必须消除左递归**:把 `A → Aα | β` 重写成 `A → β A'`, `A' → α A' | ε`。这段消除针对**直接左递归**；间接左递归(`A → B → A`)需要先通过代入消除。

## 消除左递归:算法与代价

立即左递归(规则右侧第一个符号就是自己)可以机械消除:

```
原文法:  expr → expr + term | term
        term → term * factor | factor

消除后: expr  → term expr'
        expr' → + term expr' | ε
        term  → factor term'
        term' → * factor term' | ε
```

代价是 AST 结构变了——原文法的 `expr + term` 直接对应一个左结合子树,消除后 `expr'` 累积右结合——需要在构造 AST 时手动左结合化(保持运算顺序)。Pratt parser 用另一种方式(按优先级逐层下沉)避免了显式的左递归消除。

## FIRST 与 FOLLOW:LL 的理论基座

递归下降的本质是**看当前 token 决定走哪条分支**。这个决策的理论依据是 FIRST 和 FOLLOW 集:

- **FIRST(X)**:从 X 能推导出的所有串的**第一个 token 的集合**。如果 X 可推导出 ε(空),ε 也在 FIRST(X) 里。
- **FOLLOW(X)**:在所有推导中,紧跟在 X 之后的 token 的集合。

```
对文法:  E → T E'
        E'→ + T E' | ε
        T → id

FIRST(T) = {id}
FIRST(E')= {+, ε}
FIRST(E) = FIRST(T) = {id}
FOLLOW(E')= FOLLOW(E) = {$}   ← $ 是输入结束符
```

LL(1) 的工程含义:对于规则 `A → α | β`,**FIRST(α) 和 FIRST(β) 不能有交集**——否则看到当前 token 没法选。`LL(1)` 的 `1` 指"看 1 个 token 做决定"。

所以手写递归下降 parser 在无法 LL(1) 决策时会:
- **对运算**:可以用 Pratt/precedence climbing(靠优先级表,无需消除左递归)来处理表达式——这比传统的 `expr→term→factor` 层次更扁平,加运算符只需改一张表。当然，消除左递归后写成 `expr → term expr'` / `expr' → + term expr' | ε` 的递归下降也完全可行，是教科书的标准写法。
- **对关键词**:`if` / `while` / `return` 天然 FIRST 互斥,直接按当前 token 路由。

## Pratt parser:用优先级表替代文法层次

对于表达式(算术、比较、逻辑),递归下降的层次(`expr→term→factor`)会把运算符的嵌套写成很深的调用栈,且增加运算符时要重构文法层次。Pratt parser 用一张优先级表替代:

```
precedence = {
    '+': 10, '-': 10,
    '*': 20, '/': 20,
    '(': 0,                 ← 最低优先级,只在 prefix 处理
}

def expr(min_prec=0):
    left = prefix(peek())   ← 前缀算子(如 -x)
    while prec(peek()) >= min_prec:    ← 核心:比较优先级
        op = consume()
        right = expr(prec(op) + (1 if left_associative else 0))
        left = BinOp(op, left, right)
    return left
```

核心规则:**当前运算符的优先级 ≥ 最小优先级时,继续向右结合**(形成更大的表达式);否则返回。`+1` 处理左结合(左结合时提高 `min_prec`,使同优先级 op 先被消费);右结合(如 `=`)不加 1。

这比"expr/term/factor"的层次更扁平,加新运算符只需要在优先级表加一行,不改文法、不改调用栈。

## LL 的问题与应对

- **左递归**:消除后 AST 结构变化 → Pratt 绕过(表达式),或手动在构造 AST 时反转结合性。
- **公共前缀**:`if (cond) { ... } if (cond) { ... } else { ... }` 的 LL(1) 冲突——看到 `if` 后没法决定选 `if` 还是 `if-else` → 解决:dangling else 总是匹配最近的 `if`(在递归下降里,`parse_if` 中一旦看到 `else` 就贪心吃掉)。
- **错误恢复**:递归下降的最大优势——每个函数里可以即场决定"跳过多余 token 到同步标记"(如跳到 `;` 或 `}`),产出比 LR parser 好得多的错误信息。

## 表驱动 LL:当递归下降不够时

有些场景(如文法由用户提供、或文法规很大不适合手写)用表驱动 LL。从文法计算 FIRST/FOLLOW,构建预测分析表:

```
对规则 A → α:
  对 FIRST(α) 里的每个 token t:
    table[A][t] = α
  如果 ε ∈ FIRST(α):
    对 FOLLOW(A) 里的每个 token t:
      table[A][t] = α
```

运行时根据 `table[当前非终结符][当前 token]` 选规则——和递归下降等效,只是分支不写死在代码里而存在表里。但表驱动的错误信息很难做好(没有手写函数里的语义上下文)。

## 参考

- **Dragon Book**: Chapter 4, Syntax Analysis — LL(1), FIRST/FOLLOW 的完整推导
- **Pratt (1973)**: "Top Down Operator Precedence" — Pratt parser 的原始论文
- **Nystrom**: "Crafting Interpreters", Chapter 6 (Pratt parser 的极佳实现讲解)

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