#compilers #语法分析
本页目录

递归下降与 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

相关页面

© 2026 liz's doc