解释器：沿着 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


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

可以读成：

1
2
3
4


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

这里也一样，先通过 kind 确认它是加法，再把通用的 Expr 当成具体的 AddExpr 来用。

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


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);
        return eval(*add_expr.lhs) + eval(*add_expr.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.4 Parser：把 token 组成 AST

1.6 IR：编译器的草稿步骤

本节目录