AST：保存变量和绑定结构

本节阅读量:

上一节说清楚了第二章的规则：

1
2
3
4


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

第一章已经有两个 AST 节点：

1
2


Int(value)
Add(lhs, rhs)

第二章增加两个节点：

1
2


Var(name)
Let(name, value, body)

AST 的作用仍然没变：

1

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

ExprKind 增加两类

代码在：

1
2


code/02_let/src/front/ast.h
code/02_let/src/front/ast.cpp

先看表达式分类：

1
2
3
4
5
6


enum class ExprKind {
    integer,
    add,
    variable,
    let,
};

解释器和编译器拿到一个通用的 Expr 时，会先看 kind，再用 switch 选择处理规则。

这和第一章一样，只是分类表变长了：

1
2
3
4


integer   整数
add       加法
variable 变量引用
let       局部绑定

VarExpr 只保存名字

变量引用的节点很小：

1
2
3
4
5
6


struct VarExpr final : Expr {
    explicit VarExpr(std::string name);

    std::string name;
    std::string dump() const override;
};

例如源码：

1

x

对应 AST：

1

Var(x)

注意，VarExpr 里没有保存 x 的值。AST 只是结构，不是求值结果。

x 到底是多少，要等后面处理：

1
2


解释器：查 environment
编译器：查 x 对应的 IR 内部名字

LetExpr 保存名字、value 和 body

let 节点保存三件事：

1
2
3
4
5
6
7
8


struct LetExpr final : Expr {
    LetExpr(std::string name, std::unique_ptr<Expr> value, std::unique_ptr<Expr> body);

    std::string name;
    std::unique_ptr<Expr> value;
    std::unique_ptr<Expr> body;
    std::string dump() const override;
};

例如：

1

(let x 40 (+ x 2))

对应：

1

Let(x, Int(40), Add(Var(x), Int(2)))

里面三部分是：

1
2
3


name  = x
value = Int(40)
body  = Add(Var(x), Int(2))

这个结构还保留了作用域边界：name 建立的新绑定只对 body 子树生效，不对 value 子树生效。AST 本身暂时不会把 Var(x) 直接连到某个 Let，但解释器和 lowerer 可以沿着这棵树，在进入 body 时扩展各自的环境。

value 和 body 都是 unique_ptr<Expr>，因为它们可以是任意表达式：

1

(let x (+ 20 20) (+ x 2))

这里的 value 是一个加法表达式：

1

Add(Int(20), Int(20))

为什么不直接替换字符串

看到：

1

(let x 40 (+ x 2))

你可能会想：parser 能不能直接把 body 里的 x 替换成 40？

不要这样做。parser 不知道求值规则，也不应该修改含义。

shadowing 会让字符串替换马上出错：

1

(let x 10 (+ (let x 32 x) x))

这段程序里有两个 x 绑定：

1
2


外层 x -> 10
内层 x -> 32

内层 body 里的 x 应该指向 32，最后那个 x 应该指向 10。

所以 AST 只保留结构：

1
2
3
4
5
6
7
8


Let(
  x,
  Int(10),
  Add(
    Let(x, Int(32), Var(x)),
    Var(x)
  )
)

哪个 Var(x) 对应哪个绑定，留给解释器和 lowerer 通过各自的环境判断。parser 只负责保留名字和嵌套结构，不负责解析名字最终指向哪里。

观察 AST

运行：

1
2
3


cd code/02_let
make
./mini ast examples/let.lang

输出：

1

Let(x, Int(40), Add(Var(x), Int(2)))

再运行：

1

./mini ast examples/shadow.lang

输出：

1

Let(x, Int(10), Add(Let(x, Int(32), Var(x)), Var(x)))

这说明 parser 已经保留了两个同名绑定的结构。下一节看 parser 怎样读出这些节点。

2.1 从名字开始：变量和 `let`

2.3 Parser：读出 identifier 和 let

本节目录