跳到主要内容

第 11 章：解析与绑定（Resolving and Binding）

原文：Robert Nystrom, Crafting Interpreters, Chapter 11。原书以 CC BY-NC-SA 4.0 协议发布；本译文用于学习与研究。

名称是计算机科学中最困难的问题之一。

Phil Karlton

变量查找看起来简单：沿环境链向外搜索名称即可。但闭包与可变环境结合时会暴露微妙错误：语言规范要求按词法位置绑定名称，而简单运行时查找可能让函数意外看到后来声明的同名变量。本章增加一个独立的解析器（Resolver），在执行前做语义分析，静态确定每个局部变量引用要跨越多少层环境。

11.1 静态作用域（Static Scope）​

Lox 使用词法作用域，也称静态作用域：变量引用绑定到源代码中最内层、包含该引用的同名声明，而不是绑定到运行时最近创建的环境。更精确地说：一个变量使用绑定到包围该使用表达式的最内层作用域中、在程序文本里位于使用之前的同名声明。“使用”同时包括变量表达式与赋值；“之前”指文本顺序而非运行时先后。

这条规则解释了遮蔽，也避免 JavaScript var 的提升（hoisting）行为：Lox 中块内声明之后的同名变量不会反过来改变声明之前引用的绑定。

考虑：

var a = "global";
{
  fun showA() {
    print a;
  }

  showA();
  var a = "block";
  showA();
}

按静态作用域，两个 showA() 都应输出 global。函数定义处的块中，局部 a 尚未声明，因此函数中的 a 必须绑定到全局变量。若仅在运行时沿可变环境链查找，第二次调用可能找到后来添加到该块环境中的 a，错误输出 block。

原书期待的输出是：

global
global

原书插图：全局环境中定义的 a。

原书插图：链接到全局环境的块环境。

原书插图：showA() 函数体的环境链，a 解析到全局。

原书插图：块环境后来同时包含 a 与 showA。

原书插图：错误实现中 showA() 的 a 解析到块环境。

11.1.1 作用域与可变环境（Scopes and Mutable Environments）​

问题不在闭包本身，而在“一个可变 Map 既代表某段源代码作用域，又能在以后新增名称”。函数捕获的是环境对象引用；后续 var a 修改了同一对象，使过去定义的函数看见本不属于其声明位置的名称。一次变量引用在整个程序执行期间必须始终指向同一声明，而这种实现破坏了这个不变量。

一种解决办法是让环境持久化、不可变：每次声明变量都创建新环境，闭包保留旧版本。但这会为每个声明创建对象，且赋值与性能更复杂。另一种更直接的方案是在编译/解析期记录绑定关系，运行时按距离直接访问；本书选择后者。

11.1.2 持久环境（Persistent Environments）​

持久环境会让每次 var 声明生成一个新环境版本，而不是修改现有对象。这样在函数声明之前、之后的作用域拥有不同对象，闭包自然保留声明点可见的版本：

原书插图：变量声明前后分裂出的两个环境。

这种方案语义清晰，但持续分配与更新环境会增加解释器开销；Resolver 的距离表更贴合后续章节已经使用的可变环境模型。

11.2 语义分析（Semantic Analysis）​

扫描器做词法分析，解析器做语法分析，Resolver 做语义分析：程序的记号和语法树合法后，进一步检查名称与控制流是否合理。它不执行程序，也不做 Lox 的类型检查。编译器通常把这种遍历称为一个 pass；在这里，它把每处局部变量使用静态绑定到一个环境距离。

Resolver 维护一个作用域栈：每一层是名称到布尔状态的映射。false 表示变量已声明、尚未定义；true 表示已定义并可使用。遍历 AST 时：

  1. 进入块时压入新作用域。
  2. 遇到变量声明时先声明名称。
  3. 解析初始化器。
  4. 再将名称标记为已定义。
  5. 遇到变量使用时，从内向外查找并记录距离。
  6. 离开块时弹出作用域。

11.2.1 变量解析遍（A Variable Resolution Pass）​

例如变量引用位于三个环境嵌套层中，最近同名声明在外数第二层，Resolver 就记录距离 2。解释器执行时无需查字符串键或猜测范围，直接从当前环境向外跳两层。

在前述 showA() 示例的第一次调用中，a 的查找跨过函数体环境和块环境，最终抵达全局环境：

原书插图：第一次求值时，a 解析到全局环境。

若误用可变块环境，第二次查找会在第二层错误命中后来声明的块局部变量：

原书插图：错误实现中，a 解析到块环境。

这一信息存于解释器而非 AST。AST 表示纯语法，多个解释器或分析器可以复用；变量距离是某一解释策略的附加语义元数据。为此 Resolver 持有解释器引用，在发现局部声明时调用解释器的 resolve(expr, depth) 记录结果。

11.3 Resolver 类（A Resolver Class）​

Resolver 既访问表达式也访问语句：

package com.craftinginterpreters.lox;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

class Resolver implements Expr.Visitor<Void>, Stmt.Visitor<Void> {
  private final Interpreter interpreter;
  private final Stack<Map<String, Boolean>> scopes = new Stack<>();

  Resolver(Interpreter interpreter) {
    this.interpreter = interpreter;
  }

  void resolve(List<Stmt> statements) {
    for (Stmt statement : statements) resolve(statement);
  }

  private void resolve(Stmt stmt) {
    stmt.accept(this);
  }

  private void resolve(Expr expr) {
    expr.accept(this);
  }
}

使用 Void 表示访问没有计算值，只产生解析元数据或报告错误。Stack<Map<String, Boolean>> 按从外至内的顺序保存词法作用域；全局作用域特意不入栈，因为原生函数和 REPL 的全局绑定不完全遵守本地声明规则，找不到局部距离的名称留给全局环境在运行时查找。

11.3.1 解析块（Resolving Blocks）​

块创建词法作用域：

@Override
public Void visitBlockStmt(Stmt.Block stmt) {
  beginScope();
  resolve(stmt.statements);
  endScope();
  return null;
}

private void beginScope() {
  scopes.push(new HashMap<String, Boolean>());
}

private void endScope() {
  scopes.pop();
}

全局作用域没有放进 scopes 栈，因为原生函数和宿主提供的全局名称可能不完全遵守 Lox 本地声明规则；未解析到距离的名称会由解释器在全局环境查找。

11.3.2 解析变量声明（Resolving Variable Declarations）​

变量必须在初始化器前声明、在初始化器后定义：

@Override
public Void visitVarStmt(Stmt.Var stmt) {
  declare(stmt.name);
  if (stmt.initializer != null) {
    resolve(stmt.initializer);
  }
  define(stmt.name);
  return null;
}

private void declare(Token name) {
  if (scopes.isEmpty()) return;

  Map<String, Boolean> scope = scopes.peek();
  if (scope.containsKey(name.lexeme)) {
    Lox.error(name, "Already a variable with this name in this scope.");
  }
  scope.put(name.lexeme, false);
}

private void define(Token name) {
  if (scopes.isEmpty()) return;
  scopes.peek().put(name.lexeme, true);
}

这能发现同一局部作用域中的重复声明，也为“读取自身初始化器”提供状态信息。

例如下面的同一函数局部作用域中，第二个 a 是静态错误：

fun bad() {
  var a = "first";
  var a = "second";
}

11.3.3 解析变量表达式（Resolving Variable Expressions）​

读取一个仍处于 false 状态的局部变量意味着：

{
  var a = a;
}

应在静态阶段报错：

@Override
public Void visitVariableExpr(Expr.Variable expr) {
  if (!scopes.isEmpty() &&
      scopes.peek().get(expr.name.lexeme) == Boolean.FALSE) {
    Lox.error(expr.name,
        "Can't read local variable in its own initializer.");
  }

  resolveLocal(expr, expr.name);
  return null;
}

private void resolveLocal(Expr expr, Token name) {
  for (int i = scopes.size() - 1; i >= 0; i--) {
    if (scopes.get(i).containsKey(name.lexeme)) {
      interpreter.resolve(expr, scopes.size() - 1 - i);
      return;
    }
  }
}

若找不到本地声明，引用视为全局，由运行时全局环境负责。这个策略支持前置定义的原生函数，也让全局变量在后续章节保持灵活。

11.3.4 解析赋值表达式（Resolving Assignment Expressions）​

赋值首先解析右值，再按变量名解析左值：

@Override
public Void visitAssignExpr(Expr.Assign expr) {
  resolve(expr.value);
  resolveLocal(expr, expr.name);
  return null;
}

右值先解析符合执行顺序，也避免将未完成的赋值状态带入右侧表达式。

11.3.5 解析函数声明（Resolving Function Declarations）​

函数名要先声明再定义，允许递归；随后在新作用域中把参数声明并定义：

private enum FunctionType {
  NONE,
  FUNCTION
}

private FunctionType currentFunction = FunctionType.NONE;

@Override
public Void visitFunctionStmt(Stmt.Function stmt) {
  declare(stmt.name);
  define(stmt.name);
  resolveFunction(stmt, FunctionType.FUNCTION);
  return null;
}

private void resolveFunction(Stmt.Function function, FunctionType type) {
  FunctionType enclosingFunction = currentFunction;
  currentFunction = type;
  beginScope();
  for (Token param : function.params) {
    declare(param);
    define(param);
  }
  resolve(function.body);
  endScope();
  currentFunction = enclosingFunction;
}

解析函数体前保存、之后恢复 currentFunction，使嵌套函数工作正确。形参在函数调用环境中与局部变量处于同一作用域；函数体解析完成后再恢复外围函数类型。

11.3.6 其他 AST 节点​

大多数节点只递归解析子节点：

@Override
public Void visitBinaryExpr(Expr.Binary expr) {
  resolve(expr.left);
  resolve(expr.right);
  return null;
}

@Override
public Void visitCallExpr(Expr.Call expr) {
  resolve(expr.callee);
  for (Expr argument : expr.arguments) resolve(argument);
  return null;
}

@Override
public Void visitIfStmt(Stmt.If stmt) {
  resolve(stmt.condition);
  resolve(stmt.thenBranch);
  if (stmt.elseBranch != null) resolve(stmt.elseBranch);
  return null;
}

@Override
public Void visitWhileStmt(Stmt.While stmt) {
  resolve(stmt.condition);
  resolve(stmt.body);
  return null;
}

字面量没有子节点；逻辑、一元、分组、打印、表达式语句都遵循同一原则。visitReturnStmt() 仅解析可选返回值；visitFunctionStmt() 已在前述专门处理。每种 AST 节点都要让 Resolver 的遍历结构与解释器实际创建环境的结构严格对应。

11.4 执行已解析的变量（Interpreting Resolved Variables）​

环境增加按距离访问的操作：

Environment ancestor(int distance) {
  Environment environment = this;
  for (int i = 0; i < distance; i++) {
    environment = environment.enclosing;
  }
  return environment;
}

Object getAt(int distance, String name) {
  return ancestor(distance).values.get(name);
}

void assignAt(int distance, Token name, Object value) {
  ancestor(distance).values.put(name.lexeme, value);
}

解释器用 Map<Expr, Integer> 保存 Resolver 的结果：

private final Map<Expr, Integer> locals = new HashMap<>();

void resolve(Expr expr, int depth) {
  locals.put(expr, depth);
}

读取变量：

11.4.1 访问已解析变量（Accessing Resolved Variables）​

private Object lookUpVariable(Token name, Expr expr) {
  Integer distance = locals.get(expr);
  if (distance != null) {
    return environment.getAt(distance, name.lexeme);
  } else {
    return globals.get(name);
  }
}

@Override
public Object visitVariableExpr(Expr.Variable expr) {
  return lookUpVariable(expr.name, expr);
}

赋值同理：已解析局部变量按距离写入，未记录者写入全局：

11.4.2 赋值已解析变量（Assigning to Resolved Variables）​

@Override
public Object visitAssignExpr(Expr.Assign expr) {
  Object value = evaluate(expr.value);
  Integer distance = locals.get(expr);
  if (distance != null) {
    environment.assignAt(distance, expr.name, value);
  } else {
    globals.assign(expr.name, value);
  }
  return value;
}

这样 showA() 无论何时被调用，都会按照函数定义点确定的距离读取全局 a，而不是受后续局部声明影响。Resolver 与 Interpreter 在环境结构上存在有意的紧耦合：前者保证目标环境和名称存在，后者才可放心绕过逐层查找。实际工程中可用断言验证这项契约。

11.4.3 运行 Resolver​

解释前插入解析遍：

Parser parser = new Parser(tokens);
List<Stmt> statements = parser.parse();

if (hadError) return;

Resolver resolver = new Resolver(interpreter);
resolver.resolve(statements);

if (hadError) return;

interpreter.interpret(statements);

顺序很重要：只有语法树有效后才解析；只有解析无错误后才执行。解析错误与 Resolver 错误都共享 hadError，因此第二次检查必须位于 resolver.resolve(statements) 之后。

11.5 解析错误（Resolution Errors）​

Resolver 还能报告一些无法由纯语法或运行时环境更好表达的问题。局部作用域中的重复声明会在 declare() 看到已有名称时报告；全局重复声明仍被允许，方便 REPL。

11.5.1 非法 return 错误（Invalid Return Errors）​

另一个典型问题是函数外的 return：

return "at top level";
@Override
public Void visitReturnStmt(Stmt.Return stmt) {
  if (currentFunction == FunctionType.NONE) {
    Lox.error(stmt.keyword, "Can't return from top-level code.");
  }

  if (stmt.value != null) resolve(stmt.value);
  return null;
}

若不检查，Return 异常会逃出函数调用边界，成为 Java 层面的内部故障。静态诊断把问题清楚地归还给 Lox 程序员。

挑战（Challenges）​

  1. 为什么函数名可在函数体解析前急切定义，而普通变量必须等初始化完成才可使用？
  2. 其他语言如何处理初始化器引用同名局部变量的代码：var a = "outer"; { var a = a; }？它们对全局变量是否不同？评价这些选择。
  3. 扩展 Resolver：局部变量从未被使用时报告错误。
  4. 将局部变量从按名称的 Map 改为按索引的数组。Resolver 为每个声明分配作用域内唯一索引，并让解释器按“环境距离 + 索引”快速访问。