第4章执行表达式（Evaluating Expressions: Tree-Walk Interpreter）

一、导读

有了抽象语法树之后，下一步就是执行它。本章介绍 Visitor 模式如何用于遍历 AST，以及如何通过环境（Environment）对象管理变量的绑定和查找，实现一个简单的树遍历解释器（Tree-Walk Interpreter）来执行 Lox 表达式。

学习目标：掌握 Visitor 设计模式的原理和应用，理解环境的数据结构设计和变量查找机制，学会实现表达式的递归求值，能够处理类型转换和运行时错误。

重要性：树遍历解释器是最直观的语言执行方式，它直接遍历 AST 并计算每个节点的值。这种实现方式虽然性能不是最优，但概念清晰，是理解语言执行机制的最佳起点。Visitor 模式的应用也为后续扩展语言特性提供了灵活的架构基础。

核心问题：如何遍历 AST 并计算每个节点的值？如何管理变量的定义、赋值和查找？如何处理不同类型的运算（如字符串拼接、数字比较）？如何报告运行时错误？

二、核心概念详解

2.1 Visitor 模式的应用

Visitor 模式将遍历逻辑与数据结构分离，为每种 AST 节点类型定义一个访问方法。在 Java 实现中，通过定义 Expr.Visitor<T> 接口，每种节点类型（如 Binary、Literal、Grouping、Unary、Variable）都需要实现对应的 visit 方法。解释器类实现该接口，在每个 visit 方法中编写对应节点的求值逻辑。这种设计使得添加新的操作（如类型检查、代码生成）变得容易，只需新增一个 Visitor 实现即可。

java

class Interpreter implements Expr.Visitor<Object> {
  @Override
  public Object visitBinaryExpr(Expr.Binary expr) {
    Object left = evaluate(expr.left);
    Object right = evaluate(expr.right);
    switch (expr.operator.type) {
      case PLUS:
        if (left instanceof Double && right instanceof Double) {
          return (double)left + (double)right;
        }
        if (left instanceof String && right instanceof String) {
          return (String)left + (String)right;
        }
        throw new RuntimeError(expr.operator, "Operands must be two numbers or two strings.");
      // ... 其他运算符
    }
  }
}

2.2 环境的变量管理机制

环境（Environment）是一个映射结构，存储变量名（字符串）到值（Object）的绑定关系。它支持三种基本操作：define(name, value) 定义新变量、get(name) 查找变量值、assign(name, value) 修改变量值。环境通过链式结构支持嵌套作用域，每个环境持有一个指向外层环境（enclosing environment）的引用。查找变量时，先在当前环境中查找，找不到则递归到外层环境中查找，直到找到或到达全局环境。

java

class Environment {
  private final Map<String, Object> values = new HashMap<>();
  private final Environment enclosing;

  Object get(String name) {
    if (values.containsKey(name)) {
      return values.get(name);
    }
    if (enclosing != null) {
      return enclosing.get(name);
    }
    throw new RuntimeError("Undefined variable '" + name + "'.");
  }

  void define(String name, Object value) {
    values.put(name, value);
  }
}

2.3 表达式的求值过程

不同类型的表达式有不同的求值规则。字面量表达式（Literal）直接返回其值；变量表达式（Variable）从环境中查找值；一元表达式（Unary）先求值操作数再执行运算（如取负、逻辑非）；二元表达式（Binary）先求值左右操作数再执行运算；分组表达式（Grouping）返回括号内表达式的值。这个过程递归地进行，从根节点开始，逐层向下求值，直到得到最终结果。

2.4 运行时错误处理

运行时错误（Runtime Error）是在程序执行过程中发生的错误，与编译时的语法错误不同。常见的运行时错误包括：除以零、类型不匹配（如对字符串取负）、未定义变量等。解释器需要在检测到运行时错误时抛出异常，携带错误信息和发生位置，以便向用户报告有意义的错误消息。在 Lox 的实现中，通过 RuntimeError 异常类来传递错误信息。

2.5 类型系统与隐式转换

Lox 是一门动态类型语言，类型检查在运行时进行。某些运算允许特定类型的组合，如 + 运算符既支持两个数字的加法，也支持两个字符串的拼接。解释器需要在执行运算前检查操作数的类型是否合法，不合法则报告运行时错误。这种运行时类型检查虽然灵活，但也意味着类型错误只有在代码实际执行时才会被发现。

三、深入分析

3.1 Visitor 模式 vs 模式匹配

Visitor 模式是面向对象语言中实现模式匹配的标准方式。在支持代数数据类型的语言（如 Haskell、OCaml、Rust）中，模式匹配更加简洁直观。Java 17 引入的 sealed classes 和 pattern matching 也在向这个方向发展。理解 Visitor 模式的本质——将数据与操作分离——有助于你在不同语言中选择最合适的实现方式。

3.2 环境的性能优化

简单的 HashMap 实现在变量数量较少时性能良好，但在作用域嵌套较深或变量较多时，链式查找的效率会降低。实际的语言实现中，环境通常通过以下方式优化：将变量名解析为固定偏移量（在编译期完成），运行时通过数组索引访问；使用局部变量表代替 HashMap；对全局变量使用专门的快速查找结构。这些优化在第二部分字节码虚拟机中会详细讨论。

3.3 求值顺序与副作用

表达式的求值顺序在某些情况下会影响程序行为，特别是当表达式包含副作用（如函数调用、赋值）时。大多数语言规定二元表达式的左操作数先于右操作数求值。Lox 也遵循这一约定。理解求值顺序对于正确实现语言特性和避免微妙的 bug 至关重要。

四、实践案例

4.1 案例一：求值混合类型表达式

考虑表达式 "Hello" + " " + "World"，求值过程如下：

解析为 Binary(Binary("Hello", +, " "), +, "World")

求值外层 Binary：先求值左操作数

求值内层 Binary："Hello" + " " -> 两个字符串，执行拼接 -> "Hello "

回到外层："Hello " + "World" -> 两个字符串，执行拼接 -> "Hello World"

最终结果："Hello World"

如果改为 "Hello" + 42，解释器检测到操作数类型不匹配（一个字符串一个数字），抛出运行时错误。

4.2 案例二：变量定义与查找

考虑以下代码的执行过程：

lox

var a = 10;
var b = a + 5;
var c = b * 2;

执行 var a = 10：求值右侧 10 得到 10.0，在环境中定义 a -> 10.0

执行 var b = a + 5：查找 a 得到 10.0，计算 10.0 + 5.0 = 15.0，定义 b -> 15.0

执行 var c = b * 2：查找 b 得到 15.0，计算 15.0 * 2.0 = 30.0，定义 c -> 30.0

环境在整个过程中维护了变量的状态，使得后续语句可以引用前面定义的变量。

五、常见误区

5.1 误区一：Visitor 模式只适用于解释器

Visitor 模式在编译器中有广泛的应用，包括类型检查、常量折叠、代码优化、代码生成等多个阶段。每个阶段都可以实现为一个独立的 Visitor，遍历同一棵 AST 执行不同的操作。这种设计极大地提高了代码的可维护性和可扩展性。

5.2 误区二：环境应该用单一的全局 Map

使用单一全局 Map 无法正确处理作用域规则。当内层作用域定义了与外层同名的变量时（变量遮蔽，Shadowing），内层变量应该遮蔽外层变量。链式环境结构天然支持这种遮蔽行为：查找时先找到最近的绑定就返回，不会继续向外层查找。

5.3 误区三：动态类型语言不需要类型检查

动态类型语言只是将类型检查推迟到运行时，而不是完全不做类型检查。在解释器中执行运算时，必须检查操作数的类型是否合法。缺少运行时类型检查会导致不可预测的行为，如将字符串当作数字进行算术运算。

5.4 误区四：变量查找应该从全局环境开始

变量查找应该从当前（最内层）环境开始，逐层向外查找。这种"由内向外"的查找顺序实现了词法作用域（Lexical Scoping）规则，即变量的可见性由其定义位置的文本结构决定。从全局开始查找会破坏作用域的封装性。

5.5 误区五：求值顺序不重要

在存在副作用的语言中，求值顺序直接影响程序行为。例如 f() + g() 中，如果 f() 和 g() 都修改了同一个全局变量，那么先执行哪个函数会影响最终结果。语言规范必须明确定义求值顺序，解释器必须严格遵守。

六、本章小结

本章讲解了如何实现树遍历解释器。通过 Visitor 模式遍历 AST，结合环境对象管理变量，解释器能够递归地求值各种表达式。字面量直接返回值，变量从环境中查找，一元和二元表达式递归求值操作数后执行运算。运行时类型检查确保了运算的合法性，环境链式结构支持了嵌套作用域。这种实现方式简单直观，是理解语言执行机制的良好起点。

七、思考题

请实现一个类型检查 Visitor，在求值之前遍历 AST 检查所有表达式的类型是否合法，并报告类型错误。

如果将环境的链式结构改为扁平结构（所有变量存在同一个 Map 中，通过作用域编号区分），变量遮蔽和查找会如何变化？有什么优缺点？

请设计并实现 Lox 的 += 复合赋值运算符，说明需要修改哪些组件（扫描器、解析器、解释器）。

在 Lox 中，nil 参与算术运算应该产生什么结果？请设计并实现 nil 的运算规则。

比较树遍历解释器和直接编译为机器码的执行方式，分析它们在性能、实现复杂度和可移植性方面的差异。

第4章 执行表达式（Evaluating Expressions: Tree-Walk Interpreter）