11 树遍历：让树自己跑起来

eval：对着节点类型分个类

求值器的核心，是一个叫 eval 的函数。你给它一个语法树节点，它还你这个节点算出来的值。它做的事，就是看这个节点是什么类型，然后对症下药：

function eval(node) {
  switch (node.k) {
    case "lit":                       // 字面量：值就是它自己
      return node.value;

    case "group":                     // 括号：里面是什么就是什么
      return eval(node.expr);

    case "unary": {                   // 一元：先算孩子，再作用
      const right = eval(node.right);
      if (node.op.type === "MINUS") return -right;
      if (node.op.type === "BANG")  return !truthy(right);
    }

    case "binary": {                  // 二元：先算左右孩子，再合并
      const a = eval(node.left);
      const b = eval(node.right);
      switch (node.op.type) {
        case "PLUS":  return a + b;
        case "MINUS": return a - b;
        case "STAR":  return a * b;
        case "SLASH": return a / b;
        case "GT":    return a > b;
        case "LT":    return a < b;
        // ……
      }
    }
  }
}

盯着 binary 那一支看。要算 a + b，它先 eval(左孩子)、再 eval(右孩子)，最后把两个结果加起来。而左孩子、右孩子可能又是复杂的子树 —— 没关系，eval 调用自己去把它们各自算成一个值。递归在这里的作用，就是「不管孩子多复杂，我先把它塌成一个值，再来处理我自己」。

◆ 后序遍历：先孩子，后自己

这个「先算孩子、再合并」的顺序，有个正式名字叫后序遍历（post-order）。它是求值唯一说得通的顺序 —— 你没算出 2 * 3 是 6，就没法算 1 + (2 * 3)。值从叶子往根「冒泡」上来：叶子先各自变成值，然后一层层向上合并，最后在根节点汇成整个表达式的结果。

还记得第 8 章解析器建树也是「叶子先建」吗？求值又是「叶子先算」。建树和求值，是同一棵树上两趟方向一致的递归 —— 一趟把结构搭起来，一趟把结构兑现成值。

两个必须做的判断

动态类型语言把类型检查推迟到了运行时，所以 eval 里得亲自处理一些「这俩东西能不能这么算」的问题。

其一，什么算「真」。if 和 ! 需要判断一个值是真是假。Lox 的规则很简单：只有 false 和 nil 是假，其余一切都是真（包括 0 和空字符串 —— 这是 Lox 的选择，不同语言各有各的规矩）：

function truthy(v) {
  return !(v === null || v === false);   // 只有 nil 和 false 为假
}

其二，+ 的两副面孔。它既能加数字，又能拼字符串。所以要看两边的类型：

case "PLUS":
  if (typeof a === "number" && typeof b === "number") return a + b;   // 数字相加
  if (typeof a === "string" && typeof b === "string") return a + b;   // 字符串拼接
  throw runtimeError("+ 两边要么都是数字，要么都是字符串");           // 否则，运行时错误

这里冒出了第三类错误 —— 运行时错误（还记得第 3 章那张表吗）。1 + "a" 在语法上完全合法，扫描和解析都顺利通过，只有真的求值到这一步，才发现类型对不上。这正是动态类型的代价：一些本可以更早发现的错，被拖到了运行时才爆。

看子树一个个塌成值

下面这台真求值器，把这个「后序、逐步归约」的过程摊开给你看。选一个表达式，按「算一步」，每一步它挑出最左最深、孩子都已是值的那棵子树（琥珀色），把它算成一个值：

试试 1 + 2 * 3：你会看到它先把 (2 * 3) 塌成 6，再算 (1 + 6) 得 7 —— 不是因为谁教了它「先乘后加」，而是因为上一卷解析器已经把乘法括进了更内层，更内层的子树，自然更先满足「孩子都是值」的条件，也就更先被算。优先级在这里再一次显形：它早就物理地长在树的形状里了，求值器只是老实地后序走一遍。

回流

⟲ 回流 · 「递归遍历一棵树」是你的高频动作

eval 用的这个「switch 节点类型 + 递归处理孩子」的套路，有个设计模式的名字叫访问者模式（Visitor） —— 但它的本质你早就会：只要数据是一棵树，处理它就是这个形状。

React 渲染：协调器（reconciler）就是在递归遍历你的组件树，每个节点算出它该渲染成什么 —— 和 eval 逐节点求值同构。DOM 操作、文件系统遍历、JSON 深拷贝、AST 转换（Babel plugin、ESLint 规则、KSP） —— 全是「递归下降到一棵树上，对每种节点做点事」。

你写 Babel plugin / ESLint 规则时的那个 visitor 对象，就是一个 eval 的近亲：它也是「遇到 BinaryExpression 节点就做 X，遇到 Identifier 节点就做 Y」。区别只在于：eval 遍历树是为了算出值，而 codemod 遍历树是为了改写树。同一个骨架，不同的目的。学会了 eval，你再看那些「在 AST 上爬」的工具，会觉得亲切得多。

这一章的一句话

eval 平平无奇：后序递归遍历语法树，叶子返回自己的值，内部节点先算孩子、再合并 —— 值从叶子往根冒泡上来。

现在我们只能算表达式。下一章加上语句、变量和环境，让程序能记住东西 —— 从此它不只是个大计算器了。