08 递归下降：把文法翻译成函数

解析器：又是 peek 和 advance

好消息：解析器的底层操作，和扫描器一模一样。扫描器拿一个指针在字符流上爬，解析器拿一个指针在记号流上爬。同样的 peek（看当前记号）、advance（吃掉并返回）、match（如果是某类型就吃掉）：

let current = 0;                          // 当前看到第几个记号
function peek()  { return tokens[current]; }
function advance() { return tokens[current++]; }
function check(type) { return peek().type === type; }
function match(...types) {                 // 命中任意一种就吃掉、返回真
  for (const t of types) if (check(t)) { advance(); return true; }
  return false;
}

如果你上一卷把扫描器看懂了，这套东西你已经会了。解析器不是一个新物种，是同一个「指针 + peek/advance」套路，换了个层次运行 —— 它啃的是记号，不是字符。

核心手法：一条规则，一个函数

现在见证「抄」的过程。文法里这一条：

term → factor ( ( "-" | "+" ) factor )*

直译成人话是：「一个 term，是一个 factor，后面跟着零个或多个『加减号 + 又一个 factor』」。把这句话逐字翻译成代码：

function term() {
  let expr = factor();                    // 先解析一个 factor

  while (match("MINUS", "PLUS")) {         // ( ... )* 那个「零个或多个」= while
    const op = previous();                 // 刚吃掉的 + 或 -
    const right = factor();                // 右边又一个 factor
    expr = { k: "binary", op, left: expr, right };   // 搭一个二元节点
  }
  return expr;
}

一一对上号：文法里的 factor → 调用 factor() 函数；文法里的 ( … )*「重复」→ 代码里的 while 循环；文法里的 "-" | "+" → match("MINUS", "PLUS")。文法怎么写，函数就怎么长。这就是递归下降 —— 「下降」是因为一个规则调用比它更底层的规则，「递归」是因为最终会（经由 primary 里的括号）绕回来调用自己。

其余几条规则，同样照抄。factor（管乘除）长得和 term 一个样，只是换了运算符、换了它调用的下一层：

function factor() {
  let expr = unary();
  while (match("SLASH", "STAR")) {
    const op = previous();
    expr = { k: "binary", op, left: expr, right: unary() };
  }
  return expr;
}
function unary() {                         // 一元：!x  -x
  if (match("BANG", "MINUS")) {
    return { k: "unary", op: previous(), right: unary() };  // 递归：--x 也行
  }
  return primary();
}
function primary() {                       // 叶子：字面量、变量、括号
  if (match("NUM", "STR")) return { k: "lit", value: previous().literal };
  if (match("TRUE"))  return { k: "lit", value: true };
  if (match("IDENT")) return { k: "var", name: previous() };
  if (match("LPAREN")) {
    const expr = expression();             // 括号里又是一整个表达式 —— 递归回到顶层
    consume("RPAREN", "括号没有收口：缺一个 )");
    return { k: "group", expr };
  }
  throw error("这里需要一个表达式");
}

看 primary 里的括号分支 —— 它调用了 expression()，也就是文法最顶层的规则。这就是那根递归的线闭合的地方：一路下降到最底层的括号，又能跳回最顶层重新来一轮。有限的几个函数，靠这个回环，解析出无限深的嵌套。

◆ 语法树节点：就是普通对象

别被「抽象语法树（AST）」这个高大上的名字唬住。一个 AST 节点，就是一个记着「我是什么、我的孩子是谁」的普通对象：

{ k: "binary", op: +, left: {…}, right: {…} } —— 一个加法节点，带左右两个孩子；{ k: "lit", value: 3 } —— 一个字面量叶子。就这么朴素。整棵语法树，不过是这些小对象互相嵌套成的一坨。解析器干的全部事情，就是把扁平的记号，组装成这坨嵌套对象。

亲眼看树长出来

说了这么多不如看。下面这台是真的递归下降解析器。选一个表达式，然后按「建一个节点」一步步走 —— 注意节点冒出来的顺序：

叶子先建，父节点后建。这不是巧合，正是这组函数返回的顺序：term() 得先让 factor() 返回一个结果，才能拿这个结果去搭二元节点；而 factor() 又得先等 unary()、primary() 返回…… 一路递归到最深的字面量，建好叶子往回返的路上，才把运算符节点一层层搭上去。你看到的建树顺序，就是递归触底反弹的顺序。

一个必须处理的细节：consume

注意 primary 里那个 consume("RPAREN", …)。它和 match 的区别是：match 是「有就吃、没有就算了」，consume 是「必须有，没有就报错」。

function consume(type, message) {
  if (check(type)) return advance();
  throw error(message);    // 该有的记号没出现 —— 语法错误
}

左括号后面必须有配对的右括号，这是文法的硬要求。consume 就是把「文法要求这里非有某个记号不可」这件事，落实成一句「否则报错」。这是解析器抛出语法错误的主要出口 —— 下一章我们专门讲，当 consume 失败时，怎么优雅地收场而不是整个崩掉。

回流

⟲ 回流 · 手写递归下降，是主流，不是玩具

你可能以为「手写解析器」是教学用的简化版，真实编译器都用某种自动生成工具。恰恰相反。

业界最顶级的编译器，几乎全是手写递归下降：GCC、Clang（C/C++）、V8（JavaScript）、Roslyn（C#）、Go 的官方编译器、Kotlin 编译器 —— 它们的解析器都是人手一条规则一条规则写出来的，不是 yacc/bison 这类工具生成的。为什么？因为手写的能给出好得多的错误信息、更容易做错误恢复、性能也可控。你刚学的这个方法，就是工业界的主力方法，不是简化版。

你写过的「解析器」也是它。手搓一个 Markdown 转换、解析一个自定义查询语法、处理一段嵌套的配置 —— 只要数据是嵌套的，你多半不自觉地写出了递归下降的雏形：一个处理外层的函数，遇到嵌套就递归调用自己。现在你知道这个套路有名字、有理论、有一整套配套技术了。

这一章的一句话

递归下降就是把文法逐条翻译成互相调用的函数 —— 一条规则一个函数，重复用 while，嵌套用递归；叶子先建、父节点后建，一棵语法树就这么长出来。

但我们还没解释那个魔法：这叠函数凭什么让 1 + 2 * 3 只搭出唯一正确的一棵树？下一章揭穿它 —— 答案藏在函数的调用层次里。