AST：从字符串到 C++ 可操作的结构

本节阅读量:

上一节说清楚了这套小语言的规则：

1
2


expr ::= integer
       | "(" "+" expr expr ")"

接下来要写 lexer 和 parser。动手之前，先看清楚我们想得到什么。

源码一开始只是文本：

1

(+ 40 2)

人能看出来它的意思：

1
2
3


这是加法。
左边是 40。
右边是 2。

但 C++ 程序不能只靠“看起来像”。我们要把这个结构存进对象里：

1
2
3


Add
  Int(40)
  Int(2)

这就是这里要用的 AST。

AST 是 abstract syntax tree 的缩写。第一次看到不用记英文，先把它理解成：

1

用 C++ 对象保存下来的表达式结构。

AST 解决什么问题

你可能会问：既然源码就是字符串，为什么不直接在字符串上算？

对最简单的 (+ 40 2)，硬写字符串处理也许能凑出来。比如找到 40 和 2，把它们相加。但字符串只是一排字符：

1

( + 4 0 2 )

程序真正的意思是结构：

1
2
3


这是一个加法。
左边是一个表达式。
右边是一个表达式。

字符顺序和程序结构不是一回事。

嵌套表达式会让这个问题更明显：

1

(+ (+ 1 2) (+ 3 4))

如果只看字符串，你要自己数括号，才能知道：

1
2


外层加法的左边是 (+ 1 2)
外层加法的右边是 (+ 3 4)

如果变成 AST，结构马上清楚：

1
2
3
4
5
6
7


Add
  Add
    Int(1)
    Int(2)
  Add
    Int(3)
    Int(4)

有了 AST，前后两段工作就分开了：

1
2


前面关心怎么读文本。
后面关心怎么处理结构。

这也是 AST 的价值：

1

把“文本问题”变成“结构问题”。

第一章的 AST 也很小，只有两种节点：

1
2


Int(value)
Add(lhs, rhs)

它们的规则是：

1
2


整数节点保存一个数。
加法节点保存两个子表达式。

例如 (+ 40 2) 对应：

1
2
3
4


Add(
  Int(40),
  Int(2)
)

AST 是模块之间的约定

从代码架构上看，AST 不只是 parser 的输出。它还是解释器和编译器共同使用的一份结构。

这几块核心代码的关系可以先这样看：

1
2
3
4
5
6
7
8


front/parser.cpp
  生成 AST

interp/interpreter.cpp
  读取 AST，直接算出整数

compile/ir.cpp
  读取 AST，生成 IR

这样分层有一个好处：parser 只管把源码读成结构，解释器和编译器只管消费这份结构。以后语言加新功能时，我们会先扩展 AST，再分别补解释器规则和编译器规则。

对应到 C++ 代码

代码在：

1
2


code/01_numbers/src/front/ast.h
code/01_numbers/src/front/ast.cpp

先看共同基类：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


enum class ExprKind {
    integer,
    add,
};

struct Expr {
    explicit Expr(ExprKind kind);
    virtual ~Expr() = default;

    ExprKind kind;
    virtual std::string dump() const = 0;
};

这里的意思是：

1
2
3


所有表达式都算 Expr。
每个表达式都带着自己的 kind。
每种表达式都要能 dump 出自己的结构。

enum class ExprKind 可以先理解成一张固定的分类表：

1
2


integer  整数表达式
add      加法表达式

我们不用字符串 "integer" 或 "add" 来猜节点类型，而是让 C++ 帮我们限制：ExprKind 只能取这些已经列出来的值。

kind 是给后面的 AST 消费者用的。解释器拿到一个 Expr 时，可以先看它是 integer 还是 add，再决定按哪条规则求值。

virtual std::string dump() const = 0 的意思可以先读成：

1
2


所有表达式都必须提供 dump。
但是 Int 怎么打印、Add 怎么打印，由具体节点自己决定。

这一节不用深入学完整的 C++ 多态规则。这里只要知道：parser 返回的是通用的 Expr，但真正的节点可能是 IntExpr，也可能是 AddExpr。

整数节点：

1
2
3
4
5
6


struct IntExpr final : Expr {
    explicit IntExpr(long value);

    long value;
    std::string dump() const override;
};

它只保存一个整数：

1
2


Int(42)
  value = 42

加法节点：

1
2
3
4
5
6
7


struct AddExpr final : Expr {
    AddExpr(std::unique_ptr<Expr> lhs, std::unique_ptr<Expr> rhs);

    std::unique_ptr<Expr> lhs;
    std::unique_ptr<Expr> rhs;
    std::string dump() const override;
};

它保存两个子表达式：

1
2


lhs 左边
rhs 右边

unique_ptr 和 std::move

为什么左右子表达式要用指针？因为 AddExpr 的左右两边都是“表达式”，而表达式的具体类型不固定。它可能是 IntExpr，也可能是另一个 AddExpr。

所以不能直接在 AddExpr 里写：

1
2


Expr lhs;
Expr rhs;

Expr 只是共同基类，而且有纯虚函数 dump()，不能被直接创建成普通对象。我们真正想保存的是：

1
2


左边指向哪个表达式节点。
右边指向哪个表达式节点。

这里用 std::unique_ptr<Expr>，是为了把 AST 的父子关系写进类型里：

1
2
3


AddExpr 拥有 lhs 和 rhs。
AddExpr 活着时，左右子节点也活着。
AddExpr 被销毁时，左右子节点也跟着释放。

构造函数里会看到 std::move：

1
2


AddExpr::AddExpr(std::unique_ptr<Expr> lhs, std::unique_ptr<Expr> rhs)
    : Expr(ExprKind::add), lhs(std::move(lhs)), rhs(std::move(rhs)) {}

这里的 lhs(std::move(lhs)) 可以读成：

1

把参数 lhs 拥有的节点，交给成员变量 lhs。

这里必须写 std::move，因为 unique_ptr 不能复制，只能移动。可以先这样记：

1
2


复制：变成两个拥有者，不允许。
移动：把所有权从一个地方交到另一个地方，允许。

parser 里创建加法节点时，也会看到同样的交接：

1
2
3


auto lhs = parse_expr();
auto rhs = parse_expr();
return std::make_unique<AddExpr>(std::move(lhs), std::move(rhs));

可以按顺序读成：

1
2
3


lhs 先拥有左子树。
rhs 先拥有右子树。
std::move(lhs) 和 std::move(rhs) 把两棵子树交给 AddExpr。

所以 (+ 40 2) 的 AST 所有权关系可以画成：

1
2
3
4


parse 返回的 unique_ptr
  -> AddExpr
       lhs unique_ptr -> IntExpr(40)
       rhs unique_ptr -> IntExpr(2)

这一章先记住三句话：

1
2
3


unique_ptr<Expr> 表示拥有一个表达式节点。
AST 用 unique_ptr 表示父节点拥有子节点。
std::move 用来把 unique_ptr 的所有权交给别人。

dump 是用来观察结构的

运行：

1
2
3


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

输出：

1

Add(Int(40), Int(2))

这个输出不是给最终用户看的，而是给学习和调试看的。它让你确认：

1
2


parser 真的读懂了源码。
AST 真的保存了程序结构。

如果运行嵌套加法：

1

./mini ast examples/nested_add.lang

会看到类似：

1

Add(Add(Int(1), Int(2)), Add(Int(3), Int(4)))

这说明 AST 的左右子表达式也可以继续是 Add。

下一节开始，我们再看源码文本怎样一步步变成 parser 能读的 token。

1.1 从两个表达式开始：整数和加法

1.3 Lexer：把源码切成 token

本节目录