Skip to main content

第 5 章：表示代码（Representing Code）

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

对林中居民而言，几乎每种树都既有自己的声音，也有自己的形貌。

Thomas Hardy，《绿荫下》

扫描器把源文本转为一维记号序列；但程序结构是嵌套的。表达式 1 + 2 * 3 不应仅被看成线性序列，而要表示为以 + 为根、右侧 * 为子树的结构。本章定义描述这种结构的文法，构建抽象语法树（AST），并建立后续解析、解释和静态分析都会使用的访问方式。

这章还会经过形式文法、函数式与面向对象风格的差异、若干设计模式和元编程。作者担心它会变得过于枯燥，便不断塞入更多有趣主题，直到页面放不下为止。

原书插图：自底向上求值语法树。

对 1 + 2 * 3 - 4，后序遍历依次计算 2 * 3、+、-，最后得到答案。树不是唯一表示法，第 III 部分还会生成更接近机器、却不如树直观的字节码。

5.1 上下文无关文法（Context-Free Grammars）​

用自然语言解释程序结构很快会变得含糊，因此需要精确记法。上下文无关文法（context-free grammar，CFG）是一组规则，描述如何把符号组合成语言中的有效字符串。它由终结符（terminal）和非终结符（nonterminal）组成：终结符是不再展开的输入记号，非终结符是可继续按规则展开的命名结构。

词法文法的“字母表”是字符，字符串是词素或 token，由扫描器实现；语法文法的“字母表”则是 token，字符串是完整表达式，由解析器实现。正规语言不足以表达任意深度嵌套，所以需要位于 Chomsky 层级更高处的 CFG。

5.1.1 文法规则（Rules for Grammars）​

规则一般写成：

breakfast -> protein "with" breakfast "on the side"
          | bread

左侧是规则名，右侧是其可产生的形式；竖线 | 分隔替代项。breakfast 与 protein 是非终结符，"with"、"on the side" 和 bread 是终结符或更具体的选择。规则可以递归，因此能表示任意长的嵌套结构。

形式文法用有限规则描述通常无限的有效字符串集合。从规则正向展开得到的字符串称为推导（derivation），规则又称产生式（production）。CFG 的产生式有一个头部（规则名）和一个主体；头部限制为单一符号正是“上下文无关”的定义特征，更强的无约束文法允许头部也由符号序列组成。

原书插图：通过展开文法生成字符串。

文法并不规定程序做什么，只规定哪些记号序列在结构上有效。语义，例如加法是否只接收数字、变量指向什么值，留给后续阶段。

BNF 由 John Backus 等人为 ALGOL 58 普及；在此采用的变体以箭头连接规则名和主体，以分号结束，终结符写成引号字符串、非终结符写作小写单词。我们确实是在用一种元语法定义描述语法的语法，所谓“语言一直到底”。

5.1.2 增强记法（Enhancing Our Notation）​

为了少写一些重复内容，使用几项常见元记号：

记法含义
*前一项出现零次或多次
+前一项出现一次或多次
?前一项可选，出现零次或一次
()分组
``

例如：

crispiness -> "really" "really"? "crispy"

可匹配 really crispy 或 really really crispy。这些符号不是 Lox 源码的一部分，而是描述文法的语言。

5.1.3 Lox 表达式文法（A Grammar for Lox Expressions）​

先实现 Lox 的表达式子集，完整文法会随章节扩展。下面的 EBNF 描述了本阶段支持的表达式：

expression     -> literal
                | unary
                | binary
                | grouping ;

literal        -> NUMBER | STRING | "true" | "false" | "nil" ;
grouping       -> "(" expression ")" ;
unary          -> ( "!" | "-" ) expression ;
binary         -> expression operator expression ;
operator       -> "==" | "!=" | "<" | "<=" | ">" | ">="
                | "+"  | "-"  | "*" | "/" ;

这份文法有意不解决优先级和左递归问题，下一章的解析策略会把它改写为可直接解析的分层文法。此刻要关注的是每一种表达式对应的树节点形状：字面量存一个值；分组包住一个表达式；一元表达式有运算符和一个右子树；二元表达式有左右子树与运算符。

全大写的 NUMBER、STRING 表示文本可变的单个 token；引号内终结符则必须与该词素精确匹配。可以试着用文法生成表达式，并验证它不会产生 1 + / 3 一类无效序列；本阶段文法本身仍有歧义，下一章处理。

5.2 实现语法树（Implementing Syntax Trees）​

文法描述树的形状，代码需要把形状表示为对象。第一种直觉是为每类节点写一个类：

abstract class Expr {
  static class Binary extends Expr {
    final Expr left;
    final Token operator;
    final Expr right;

    Binary(Expr left, Token operator, Expr right) {
      this.left = left;
      this.operator = operator;
      this.right = right;
    }
  }
}

这种结构把所有表达式节点置于 Expr 的命名空间中，例如 new Expr.Binary(...)。各子类只包含描述语法所需的数据；它们是普通的、近乎不可变的数据对象。

这是一棵抽象语法树，而不是解析树：解析树会保留每个产生式，AST 会省去后续阶段无需关心的纯语法细节。与 token 不同，节点并不均质：一元表达式有一个操作数、二元表达式有两个、字面量没有。因此不采用统一的任意子节点列表，以便让 Java 在误取一元表达式“第二个操作数”时直接报编译错误。

5.2.1 迷失方向的对象（Disoriented Objects）​

这里有一个面向对象设计上的矛盾。表达式树中有若干类型（Binary、Grouping、Literal、Unary），而要在树上执行若干操作：打印、解释、解析、类型检查、优化、代码生成等。

若把每个操作作为方法放在节点类中，新增一种操作时必须修改每个类；但新增一种节点类型只需新增类。若把操作放在外部，新增节点类型时则需要修改每个操作。这个没有完美答案的取舍称为表达式问题（expression problem）。

将 interpret() 直接放进每个节点类是经典的 Interpreter pattern，但树同时服务解析、解释、名称解析、可能的类型检查等不同领域，把所有行为塞进节点会违反关注点分离。Scanner 这样拥有可变位置状态和清晰辅助方法的对象很适合 OOP；在阶段之间流动的 AST 数据则更像函数式风格中的纯数据。

本书选择让节点类只表示数据，把大多数操作放到外部。节点稳定而操作会不断增加，这样更适合解释器的演进；访问者模式会让外部操作仍保持类型安全。

5.2.2 用元编程生成树（Metaprogramming the Trees）​

AST 类单调、重复且容易写错。我们不必手写大量样板代码，可以写一个小 Java 脚本来生成它们。这个工具不属于解释器运行时，只在开发时运行一次：

package com.craftinginterpreters.tool;

import java.io.IOException;
import java.nio.charset.Charset;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Arrays;
import java.util.List;

public class GenerateAst {
  public static void main(String[] args) throws IOException {
    if (args.length != 1) {
      System.err.println("Usage: generate_ast <output directory>");
      System.exit(64);
    }

    String outputDir = args[0];
    defineAst(outputDir, "Expr", Arrays.asList(
        "Binary   : Expr left, Token operator, Expr right",
        "Grouping : Expr expression",
        "Literal  : Object value",
        "Unary    : Token operator, Expr right"
    ));
  }
}

defineAst() 创建 <outputDir>/Expr.java，写入包声明、抽象基类与各嵌套子类。它把每个描述字符串按冒号分为类名和字段列表，再产生构造器和 final 字段：

private static void defineAst(
    String outputDir, String baseName, List<String> types) throws IOException {
  String path = outputDir + "/" + baseName + ".java";
  StringBuilder builder = new StringBuilder();

  builder.append("package com.craftinginterpreters.lox;\n\n");
  builder.append("abstract class ").append(baseName).append(" {\n");

  for (String type : types) {
    String className = type.split(":")[0].trim();
    String fields = type.split(":")[1].trim();
    defineType(builder, baseName, className, fields);
  }

  builder.append("}\n");
  Files.write(Paths.get(path), builder.toString().getBytes(Charset.defaultCharset()));
}

生成器属于简单的元编程：程序生成程序。它没有让代码更少，只是将重复、机械、易出错的写入工作集中到一个可靠的地方。运行后得到的 Expr.java 如下。

生成器位于 .tool 而非 .lox 包，因为它不是解释器运行时的一部分，而是开发者生成 Expr.java 的工具。描述字符串的分割代码不追求健壮性，它只处理我们亲手提供的固定定义；全部节点完成后的生成结果见附录 II。这个主意来自 Jython、IronPython 的创造者 Jim Hugunin，实际脚本语言或许更适合该工具，但作者不想额外引入更多语言。

package com.craftinginterpreters.lox;

abstract class Expr {
  static class Binary extends Expr {
    Binary(Expr left, Token operator, Expr right) {
      this.left = left;
      this.operator = operator;
      this.right = right;
    }

    final Expr left;
    final Token operator;
    final Expr right;
  }

  static class Grouping extends Expr {
    Grouping(Expr expression) {
      this.expression = expression;
    }

    final Expr expression;
  }

  static class Literal extends Expr {
    Literal(Object value) {
      this.value = value;
    }

    final Object value;
  }

  static class Unary extends Expr {
    Unary(Token operator, Expr right) {
      this.operator = operator;
      this.right = right;
    }

    final Token operator;
    final Expr right;
  }
}

5.3 使用树（Working with Trees）​

有了树，真正的工作才开始。后续会以不同方式走访它：解析器构造树，解释器计算树，打印器显示树，解析器和静态分析器也会检查树。每个操作都要依据节点实际类型采取不同逻辑。

5.3.1 表达式问题（The Expression Problem）​

两种扩展维度彼此冲突：

原书插图：表达式类型和操作构成的二维表。

  • 新增一种表达式类型，例如调用、赋值或变量。
  • 新增一种对表达式的操作，例如解释、打印、解析或生成代码。

将操作置于每个类的方法中，有利于新增类型；将操作置于独立函数或对象中，有利于新增操作。本书预期 AST 类型集合相对稳定，而操作逐渐增多，因此选择外置操作，并使用访问者保留 Java 的静态类型检查。

ML 家族反过来按“列”组织：类型和函数分离，一个函数以模式匹配处理全部节点，因此新增操作很容易、增加节点却要修改所有匹配。ML（metalanguage）衍生出 SML、Caml、OCaml、Haskell、F#，Scala、Rust、Swift 也能看见其影响。Common Lisp CLOS、Dylan、Julia 等多方法语言可较容易同时扩展行列，通常代价是静态检查或分离编译能力。

原书插图：按类拆分后的行。

原书插图：按操作拆分后的列。

5.3.2 访问者模式（The Visitor Pattern）​

访问者（visitor）把“根据实际节点类型做什么”集中到一个接口。基类拥有一个抽象 accept()，每个子类调用访问者中恰好对应自己的方法：

原书插图：访问者将一个操作的所有单元聚合在同一类中。

abstract class Expr {
  interface Visitor<R> {
    R visitBinaryExpr(Binary expr);
    R visitGroupingExpr(Grouping expr);
    R visitLiteralExpr(Literal expr);
    R visitUnaryExpr(Unary expr);
  }

  abstract <R> R accept(Visitor<R> visitor);
}

R 是操作结果类型：解释器可返回 Object，打印器返回 String，不产生值的检查可用 Void。每个节点的 accept() 实现只有一行：

static class Binary extends Expr {
  // 字段与构造器省略。

  @Override
  <R> R accept(Visitor<R> visitor) {
    return visitor.visitBinaryExpr(this);
  }
}

这形成两次分派：先用 Java 的虚方法分派到具体节点 accept()，再显式调用与该类型匹配的 visit...()。访问者无需写 instanceof 链，也不会因漏处理一种节点而悄悄出错；接口变更会让编译器指出需要补齐的位置。

Visitor 并不天生与树遍历有关，它也可用于单个对象；名称与 accept() 容易误导。其本质是在 OOP 中近似函数式的“按列”组织方式，通过一层间接，用节点的多态 accept() 选择 Visitor 的正确方法。书中将 visitBeignet()、visitCruller() 取不同名字，而非靠重载同名 visit()，使运行时分派路径更清楚。

5.3.3 为表达式生成访问者（Visitors for Expressions）​

既然 AST 由生成器产生，访问者接口和每个 accept() 也应由生成器产生。defineAst() 先调用 defineVisitor()：

private static void defineVisitor(
    StringBuilder builder, String baseName, List<String> types) {
  builder.append("  interface Visitor<R> {\n");

  for (String type : types) {
    String typeName = type.split(":")[0].trim();
    builder.append("    R visit").append(typeName)
        .append(baseName).append("(").append(typeName)
        .append(" ").append(baseName.toLowerCase()).append(");\n");
  }

  builder.append("  }\n\n");
}

再在每个子类中生成：

builder.append("    @Override\n");
builder.append("    <R> R accept(Visitor<R> visitor) {\n");
builder.append("      return visitor.visit").append(className)
    .append(baseName).append("(this);\n");
builder.append("    }\n\n");

最后在基类中生成抽象 accept()。AST 的定义列表由此成为单一事实来源；新增节点时，生成器会同步更新全部必要的机械代码。

5.4 一个不太漂亮的打印器（A (Not Very) Pretty Printer）​

为了验证树结构，先写一个将树打印为 Lisp 风格前缀表示法的小工具。它不是最终用户界面，只是方便观察：

原书插图：一个示例语法树。

package com.craftinginterpreters.lox;

class AstPrinter implements Expr.Visitor<String> {
  String print(Expr expr) {
    return expr.accept(this);
  }

  @Override
  public String visitBinaryExpr(Expr.Binary expr) {
    return parenthesize(expr.operator.lexeme, expr.left, expr.right);
  }

  @Override
  public String visitGroupingExpr(Expr.Grouping expr) {
    return parenthesize("group", expr.expression);
  }

  @Override
  public String visitLiteralExpr(Expr.Literal expr) {
    if (expr.value == null) return "nil";
    return expr.value.toString();
  }

  @Override
  public String visitUnaryExpr(Expr.Unary expr) {
    return parenthesize(expr.operator.lexeme, expr.right);
  }

  private String parenthesize(String name, Expr... exprs) {
    StringBuilder builder = new StringBuilder();
    builder.append("(").append(name);
    for (Expr expr : exprs) {
      builder.append(" ");
      builder.append(expr.accept(this));
    }
    builder.append(")");
    return builder.toString();
  }
}

将 -123 * (45.67) 手工构造成树：

Expr expression = new Expr.Binary(
    new Expr.Unary(
        new Token(TokenType.MINUS, "-", null, 1),
        new Expr.Literal(123)),
    new Token(TokenType.STAR, "*", null, 1),
    new Expr.Grouping(
        new Expr.Literal(45.67)));

System.out.println(new AstPrinter().print(expression));

输出为：

(* (- 123) (group 45.67))

这证明访问者能正确穿行树；下一章解析器将自动构造同样的树，而不是手写它。

挑战（Challenges）​

  1. 给 AST 打印器添加新的方法，输出合法 Lox 语法而不是前缀表示法。何处需要括号以避免改变表达式含义？
  2. 为 AST 打印器添加“RPN”输出，即逆波兰表达式。1 + 2 * 3 应输出什么？
  3. 修改生成器，使其为 Stmt 也生成一套树；后续章节会需要它。思考表达式与语句共享哪些生成逻辑，哪些不同。
  4. 访问者模式让新增操作方便、增加节点麻烦。尝试另一种设计，例如把操作作为节点方法或使用模式匹配，比较新增节点和新增操作的成本。