AI 可能出错，请核对原文 在独立页面打开
问文档
目录

递归下降与 LL 分析

11 分钟
本页目录

递归下降用函数之间的调用表达语法结构：表达式函数调用子表达式函数，语句函数调用表达式函数。LL 分析解释什么时候可以只看有限前瞻就选定产生式；Pratt 则把表达式运算符的决策组织为绑定强度。

手写递归下降不等于 LL(1)。实现也可以使用多 token 前瞻、回溯或语义判断；每增加一种机制，都要重新考虑复杂度、错误恢复和副作用。

从文法到函数

下面用 EBNF 的重复记号描述四则运算：

expr   = term, { ("+" | "-"), term } ;
term   = factor, { ("*" | "/"), factor } ;
factor = NUMBER | "(", expr, ")" ;

expr 先解析一个 term，再循环消费加减号及下一项；term 用同样方法处理乘除；factor 处理数字和括号。更强的优先级处在更深的调用层，所以 2 + 3 * 4 把乘法作为加法的右子树。

一个解析函数应约定它消费什么、在哪些 token 前停止、成功和失败分别返回什么。完整表达式入口还应检查 EOF，否则 1 2 可能被错误地当作已成功解析的 1。

左递归消除与左结合不是同一件事

朴素递归下降直接实现 E → E - T | T，会在消费输入前再次调用 E，造成无限递归。直接左递归可改为 E → T E'、E' → - T E' | ε。间接左递归要结合非终结符之间的依赖另行处理；某些扩展解析算法也能专门支持左递归。

改写后的右递归尾部不代表减法应右结合。构造 AST 时，用当前结果作为新节点的左孩子，依次折叠：读完 8 得到 Number，读完 - 3 得到 Sub(8,3)，再读 - 2 得到 Sub(Sub(8,3),2)。

同样三个操作数，结合方向决定 AST 减法左结合：(8 − 3) − 2 幂运算右结合：2 ^ (3 ^ 2) − − 2 8 3 ^ 2 ^ 3 2 文法改写保持可接受字符串时，仍需单独保证 AST 的结合性和求值语义。

FIRST、FOLLOW 与预测集合

FIRST(α) 是 α 能推导出的串的起始终结符集合；若 α 能推导空串，也包含 ε。FOLLOW(A) 是某个句型中能紧跟 A 的终结符集合；开始符号的 FOLLOW 包含输入终止标记 $。

计算 FIRST 时沿产生式从左向右传播，只有前一个符号可为空时才继续看下一个。对 A → α B β，把 FIRST(β) − {ε} 加入 FOLLOW(B)；若 β 可为空，再加入 FOLLOW(A)。循环文法要迭代到集合不再变化。

考虑简化文法：

E  → T E'
E' → + T E' | ε
T  → id
非终结符FIRSTFOLLOW
E{id}{$}
E'{+, ε}{$}
T{id}{+, $}

对产生式 A → α，预测集合为 FIRST(α) − {ε}；若 α 可为空，再并入 FOLLOW(A)。⁠同一非终结符的各候选预测集合两两不交，才能建立无冲突的 LL(1) 选择。 只检查 FIRST 之间不交会漏掉空产生式冲突。

示例中 E' 看到 + 选择继续，看到 $ 选择 ε，看到 id 应报错，不能无条件走 ε。预测表只是把这些决策表格化，递归下降则把它们写成函数分支。

空产生式为什么也会与普通候选争抢同一个 token

再看 S → A a、A → a | ε，小写 a 是终结符。A 的两个右侧 FIRST 分别是 {a} 和 {ε}，看起来不相交；但 FOLLOW(A) 含 a，因此空产生式的预测集合也是 {a}。解析器在 A 处看到 a 时，无法只凭这一个 token 判断该消费它，还是让它留给 S 末尾。

长度为 1 的输入 a 应选择 A→ε，长度为 2 的输入 aa 应选择 A→a。这个小文法并不歧义，只是不满足该文法的 LL(1) 预测条件；可以改写语言对应的文法，也可以使用更多前瞻。不能把预测表冲突直接等同于语言存在歧义。

def predict(first, nullable, follow):
    # first 已排除 ε；nullable 单独记录是否可为空。
    return set(first) | (set(follow) if nullable else set())


def table(candidates):
    cells = {}
    for rule, lookaheads in candidates:
        for token in lookaheads:
            if token in cells:
                raise ValueError(f"conflict on {token}: {cells[token]} / {rule}")
            cells[token] = rule
    return cells


assert table([
    ("E' -> + T E'", predict({"+"}, False, {"$"})),
    ("E' -> empty", predict(set(), True, {"$"})),
]) == {"+": "E' -> + T E'", "$": "E' -> empty"}
try:
    table([
        ("A -> a", predict({"a"}, False, {"a"})),
        ("A -> empty", predict(set(), True, {"a"})),
    ])
except ValueError as error:
    assert "conflict on a" in str(error)
else:
    raise AssertionError("FIRST/FOLLOW conflict missed")

代码只构造一个非终结符的预测表，不负责计算完整文法的 FIRST/FOLLOW。它保留冲突的两个产生式来源，避免后插入候选悄悄覆盖已有项；真正的分析器生成器还应指出产生空串和 FOLLOW 传播的相关路径，帮助定位文法问题。

看到 a 时，两条产生式都声称自己可被选择 当前位置：展开 A 输入前瞻：a A → a FIRST 提供预测 token a A → ε FOLLOW(A) 提供预测 token a 文法 S → A a，A → a | ε：FIRST 不冲突，预测集合仍可能冲突。

ε 不消费字符，为什么仍会争抢前瞻？

先看候选 a 需要消费什么，再看空候选需要把什么留给外层。S→Aa 时，两种候选都可能面对前瞻 a：短串 a 需要留给外层，长串 aa 需要先消费一个。把 S 末尾改成 b 后，两套预测集合分开。这里改变的是文法的预测条件，不是给 ε 指令偷偷增加一个消费字符的动作。

正在呈现知识画面
ε 不消费字符，为什么仍会争抢前瞻？

空候选的预测集合来自 FOLLOW(A)。当 S 末尾也是 a，两条候选都响应 a；文法不满足 LL(1)，但这不证明语言有歧义。

公共前缀、歧义与回溯

左因子提取把 A → αβ | αγ 改成 A → αA'、A' → β | γ，使选择推迟到公共前缀之后。但它不保证任意文法因此变成 LL(1)，也不会自动消除歧义。

悬空 else 涉及它应该绑定哪层 if。语言可以规定匹配最近未匹配的 if，要求显式结束符，或用文法区分已匹配与未匹配语句。需要说明具体规则，不能只把它称为“前瞻不够”。

试探解析若回退，应同时恢复游标、暂存诊断及其他可变状态。频繁重试可能重复解析同一前缀；记忆化又会增加内存，并要求结果依赖被正确纳入缓存键。

Pratt：左右绑定强度控制树形

下面是可直接运行的 Python 教学实现。输入是已分词的 token 列表；数字是非负十进制整数，一元负号单独解析。此处 ^ 被这门示例语言定义为幂运算，与 Python 的 ^ 含义无关。

class Parser:
    # (左绑定强度, 右侧递归门槛)
    INFIX = {"+": (10, 11), "-": (10, 11),
             "*": (20, 21), "/": (20, 21), "^": (30, 30)}

    def __init__(self, tokens):
        self.tokens = list(tokens) + [None]
        self.pos = 0

    def peek(self):
        return self.tokens[self.pos]

    def take(self):
        token = self.peek()
        if token is None:
            raise SyntaxError("expected expression before EOF")
        self.pos += 1
        return token

    def expr(self, minimum=0):
        token = self.take()
        if token.isascii() and token.isdecimal():
            left = ("number", int(token))
        elif token == "-":
            left = ("negate", self.expr(30))
        elif token == "(":
            left = self.expr()
            if self.peek() != ")":
                raise SyntaxError("expected closing parenthesis")
            self.take()
        else:
            raise SyntaxError(f"expected expression, got {token!r}")

        while self.peek() in self.INFIX:
            op = self.peek()
            lbp, rbp = self.INFIX[op]
            if lbp < minimum:
                break
            self.take()
            left = (op, left, self.expr(rbp))
        return left

    def parse(self):
        result = self.expr()
        if self.peek() is not None:
            raise SyntaxError(f"unexpected trailing token {self.peek()!r}")
        return result

assert Parser(["8", "-", "3", "-", "2"]).parse() == (
    "-", ("-", ("number", 8), ("number", 3)), ("number", 2))

本实现允许 lbp >= minimum 的运算符进入当前调用。左结合减法让右侧使用 11，因此右侧不会吃掉 lbp 为 10 的下一个减号，后者留给外层循环。右结合幂的左右门槛同为 30，使右侧能继续吸收下一次幂。

一元负号让其操作数从 30 开始，因而这里 - 2 ^ 2 解析为 -(2^2)。这是明确选定的语言规则；修改门槛可以定义别的规则。括号和 EOF 不在中缀表中，自然终止循环，不应给它们虚构一个最低中缀优先级。

完整 Pratt 实现还可为 token 配置前缀、后缀和中缀处理器，加入函数调用、成员访问或三元表达式。本例专注绑定方向，没有加入源码位置、资源上限和错误恢复；深度嵌套在实际实现中还需避免耗尽调用栈。作者教程展示了这种按 token 组织表达式编译的方式。Crafting Interpreters 第 17 章

追踪门槛，观察 token 究竟被哪层调用消费

对 8 - 3 - 2，外层看到第一个减号后以门槛 11 递归解析右侧。右侧读到 3，随后看到第二个减号的左绑定强度为 10，小于 11，于是返回而不消费减号。外层先构成 8−3，再继续消费第二个减号，最终得到 (8−3)−2。

表达式片段当前门槛下一个运算符强度决策
第一个减号右侧的 311- 为 10留给外层，形成左结合
第一个幂号右侧的 330^ 为 30当前层继续，形成右结合
前缀负号右侧的 230^ 为 30先把幂纳入负号操作数
括号内表达式结束任意) 不是中缀返回，由括号处理器消费

将以下断言接在 Parser 定义之后，直接检查 AST，而不借助求值结果掩盖树形差异：

N = lambda x: ("number", x)
assert Parser(["2", "+", "3", "*", "4"]).parse() == ("+", N(2), ("*", N(3), N(4)))
assert Parser(["2", "^", "3", "^", "2"]).parse() == ("^", N(2), ("^", N(3), N(2)))
assert Parser(["-", "2", "^", "2"]).parse() == ("negate", ("^", N(2), N(2)))
assert Parser(["(", "-", "2", ")", "^", "2"]).parse() == ("^", ("negate", N(2)), N(2))
for tokens in ([], ["1", "2"], ["1", "+"], ["(", "1"], ["1", ")"], ["*", "2"]):
    try:
        Parser(tokens).parse()
    except SyntaxError:
        pass
    else:
        raise AssertionError(f"invalid input accepted: {tokens}")

空输入、尾部 token、缺右操作数、缺右括号和非法前缀分别来自不同失败位置。检查这些入口与出口条件，比只观察一个算式是否得到正确数字更能揭示解析器是否完整消费输入。

改一个绑定门槛，树为什么就变了？

绑定强度不是求值顺序的动画速度，而是当前递归调用是否继续消费运算符的门槛。下面真正运行一个受限 Pratt 解析器，再从得到的树生成括号形式和结果。修改减法的右门槛会改变结合方向；把乘法强度降到加法以下，会改变哪一棵子树先组成。门槛记录可以解释结果为什么变，而不只显示两个不同答案。

正在呈现知识画面
改一个绑定门槛，树为什么就变了？

右侧门槛高于相同运算符的左绑定强度时，右侧返回，把下一个运算符留给外层。门槛相等则可吸收它，形成右结合。

选型与后续

分层递归下降适合直接对应语言规则；Pratt 适合集中管理表达式运算符。生成器也可以提供良好的诊断，手写也可能恢复不佳，质量取决于实现投入。需要更一般的确定性文法处理时，可接着看 LR 分析；产出怎样的树见 AST 设计与错误恢复。

Keywords: recursive descent, LL(1), FIRST, FOLLOW, prediction set, left recursion, left factoring, Pratt parser, binding power, associativity

链接预览

新窗口打开