解释器：沿着 AST 直接算结果

本节阅读量:

解释器做的事很直接：

1
2


拿到 AST。
顺着 AST 把结果算出来。

它不会生成汇编，也不会生成别的文件。

例如：

1

(+ 40 2)

解释器最后直接得到：

1

42

先用人脑算一次

看这个表达式：

1

(+ (+ 1 2) 3)

我们手算时会这样想：

1
2
3


先算左边 (+ 1 2)，得到 3。
右边是 3。
最后 3 + 3，得到 6。

换成更机械的步骤：

1
2
3
4
5


eval((+ (+ 1 2) 3))
= eval((+ 1 2)) + eval(3)
= (eval(1) + eval(2)) + 3
= (1 + 2) + 3
= 6

这就是解释器的核心。

先处理两种表达式

第一章的语言还很小，解释器先学会处理两种表达式。

这里写下的不是“某个实现碰巧这样算”，而是第一节语言规则对应的求值语义：所有合法实现都应该让整数得到自身，让加法得到两个子表达式结果之和。

整数表达式：

1

整数的值就是它自己。

比如：

1

eval(Int(42)) = 42

加法表达式：

1

加法的值 = 左边的值 + 右边的值。

比如：

1

eval(Add(Int(40), Int(2))) = 40 + 2 = 42

如果左右两边本身还是加法，就继续用同样的规则。

这就是递归：解决一个大表达式时，先解决它的子表达式。

对应到 C++ 代码

代码在 code/01_numbers/src/interp/interpreter.cpp。

AST 节点有一个 kind 字段：

1
2


ExprKind::integer
ExprKind::add

解释器先看 kind，再用 switch 选择求值规则。

这里的顺序很重要：

1
2


先看 kind，确认它是哪一种表达式。
确认以后，再按那一种表达式的结构去读取字段。

先看整数：

1
2
3
4


case ExprKind::integer: {
    const auto& int_expr = static_cast<const IntExpr&>(expr);
    return int_expr.value;
}

可以读成：

1
2


如果当前表达式的 kind 是 integer，
就返回里面保存的 value。

expr 的类型是通用的 Expr&。确认 kind 是 integer 之后，这一行：

1

const auto& int_expr = static_cast<const IntExpr&>(expr);

可以先理解成：

1
2


现在我已经知道它是 IntExpr，
所以把它当成 IntExpr 来读 value。

再看加法：

1
2
3
4
5
6


case ExprKind::add: {
    const auto& add_expr = static_cast<const AddExpr&>(expr);
    long lhs = eval(*add_expr.lhs);
    long rhs = eval(*add_expr.rhs);
    return lhs + rhs;
}

可以读成：

1
2
3
4


如果当前表达式的 kind 是 add，
先递归求左边，
再递归求右边，
最后把两个结果相加。

这里也一样，先通过 kind 确认它是加法，再把通用的 Expr 当成具体的 AddExpr 来用。AST 的构造函数始终让 kind 和实际节点类型保持一致，解释器依赖的就是这条约定。

add_expr.lhs 和 add_expr.rhs 是 unique_ptr<Expr>，也就是“拥有子表达式的指针”。前面的 * 表示取出它指向的那个表达式节点：

1
2


add_expr.lhs   左子表达式的指针
*add_expr.lhs  左子表达式本身

把两次递归调用分别写成语句，也明确规定了从左到右的求值顺序。第一章的加法还没有副作用，交换顺序不会改变数值；后面加入可变状态以后，这个顺序会成为语言语义的一部分。

所以：

1

eval(*add_expr.lhs)

就是“递归求左子表达式的值”。

完整函数：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


long eval(const Expr& expr) {
    switch (expr.kind) {
    case ExprKind::integer: {
        const auto& int_expr = static_cast<const IntExpr&>(expr);
        return int_expr.value;
    }
    case ExprKind::add: {
        const auto& add_expr = static_cast<const AddExpr&>(expr);
        long lhs = eval(*add_expr.lhs);
        long rhs = eval(*add_expr.rhs);
        return lhs + rhs;
    }
    }

    throw std::runtime_error("unknown expression kind");
}

switch 在这里的作用是判断：

1

这个 Expr 应该按哪一种规则求值？

第一章只有两种可能：

1
2


ExprKind::integer
ExprKind::add

后面章节会加更多节点。

跑一下解释器

运行：

1
2
3


cd code/01_numbers
make
./mini run examples/add.lang

输出：

1

42

再运行：

1

./mini run examples/nested_add.lang

输出：

1

10

解释器在整条路径里的位置

现在，前半条路径已经走通：

1

源代码 -> token -> AST -> eval -> 整数结果

解释器在 eval 返回时已经完成工作，它不会保存一份以后再执行的计划。编译器走的是另一条路：先把 AST 变成计算步骤，再把这些步骤写成汇编。下一节就从这份中间计算计划开始。

1.4 Parser：把 token 组成 AST

1.6 IR：编译器的草稿步骤

本节目录