AST、parser 与自由变量：写入目标也是一次变量使用

本节阅读量:

语言规则已经确定，前端要把两个新形式准确保存在 AST 中。begin 有两个表达式子树；set! 则有一个特殊之处：它的目标是名字，不是任意表达式。

这个差异会一路影响 parser 和自由变量分析。

ExprKind 明确增加两个分支

第八章继续使用显式 kind + switch 处理 AST 变体。枚举中的相关部分是：

1
2
3
4
5
6
7
8
9


enum class ExprKind {
    // ...
    let,
    letrec,
    set,
    begin,
    equal,
    // ...
};

新增节点定义为：

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


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

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

struct BeginExpr final : Expr {
    BeginExpr(std::unique_ptr<Expr> first,
              std::unique_ptr<Expr> second);

    std::unique_ptr<Expr> first;
    std::unique_ptr<Expr> second;
    std::string dump() const override;
};

SetExpr::name 是一个字符串，而不是 std::unique_ptr<Expr>。这直接表达了本章语法边界：写入目标只能是 identifier。

右侧 value 仍是完整表达式，因此下面是合法的：

1

(set! x (+ x 1))

而下面不是：

1

(set! (get box 0) 42)

若以后真的加入 record 字段更新，应新增语义清楚的节点，而不是让 SetExpr 暗中承担两种不同操作。

查看真实 AST

构建后运行：

1
2


cd code/08_state
./mini ast examples/set.lang

输出：

1

Let(x, Int(1), Begin(Set(x, Int(41)), Add(Var(x), Int(1))))

从外向内看：

1
2
3
4


Let
└─ body: Begin
   ├─ first: Set(x, 41)
   └─ second: Add(Var(x), 1)

AST 只记录源码结构。x 最终对应哪个 location、写入发生在 Store 还是堆 cell，都是后续阶段的职责。

嵌套 begin 也只是重复使用同一个二元节点：

1

./mini ast examples/begin_order.lang

输出：

1

Let(x, Int(0), Begin(Set(x, Int(40)), Begin(Set(x, Add(Var(x), Int(2))), Var(x))))

不需要为三个表达式再增加一种 AST 形状。

parser 在列表头部识别固定特殊形式

set! 含有感叹号，但普通 identifier 的规则仍是 letter+。parser 只在列表头部看到完整拼写 set! 时进入专用分支：

1
2
3
4
5
6
7
8


if (head == "set!") {
    advance();
    std::string name =
        expect_identifier("expected variable name after 'set!'");
    auto value = parse_expr();
    expect(")", "expected ')' after set! value");
    return std::make_unique<SetExpr>(name, std::move(value));
}

这里依次消费：

1

set! -> identifier -> expr -> )

expect_identifier 保证目标不是数字、列表或带任意特殊字符的用户名字。expect(")", ...) 又保证本章 set! 只有一个右侧表达式。

parser 不负责检查名字是否已经绑定。例如 (set! missing 42) 可以形成 AST，随后由解释器查找 location，或由 lowering 解析编译环境时报告未定义名字。这保持了阶段边界：

1
2


parser     判断形状是不是 set! identifier expr
语义阶段   判断 identifier 在当前位置指向哪个绑定

begin 的 parser 分支保持源码顺序

对应代码是：

1
2
3
4
5
6
7
8


if (head == "begin") {
    advance();
    auto first = parse_expr();
    auto second = parse_expr();
    expect(")", "expected ')' after begin expressions");
    return std::make_unique<BeginExpr>(
        std::move(first), std::move(second));
}

先调用一次 parse_expr() 得到 first，再调用一次得到 second。parser 本身不会执行它们，但 AST 中的字段顺序保存了语言规定的求值顺序。

多写或少写子表达式都会在 parser 阶段失败：

1
2


(begin 1)
(begin 1 2 3)

更长序列应显式嵌套二元 begin。

两条新语法规则

把新增部分写成文法是：

1
2
3


expr ::= ...
       | "(" "set!" identifier expr ")"
       | "(" "begin" expr expr ")"

set! 和 begin 必须在通用函数调用分支之前判断。否则 parser 会尝试把它们当作普通 callee，既无法接受 !，也会丢失特殊的求值和写入语义。

自由变量分析不能只递归 AST 子指针

第七章的 closure 只捕获自由变量。第八章把捕获内容从 Value 改成 location，但“哪些源码名字需要捕获”仍由同一个 front/free_vars.cpp 回答。

普通变量使用会形成 VarExpr，分析器自然能遇到：

1

(lambda ignored x)

可是写入目标保存在 SetExpr::name 字符串中：

1

(lambda value (set! x value))

这个函数没有 VarExpr(x)。如果分析器只递归 set.value，它会遗漏 x，closure 也就找不到应当修改的外层 location。

set 分支先处理目标，再分析右侧

真实实现是：

1
2
3
4
5
6
7
8


case ExprKind::set: {
    const auto& set = static_cast<const SetExpr&>(expr);
    if (!contains(bound, set.name)) {
        add_unique(result, set.name);
    }
    collect(*set.value, bound, result);
    return;
}

规则可以分成两步：

若目标名字不在当前 bound 中，把它作为自由变量使用加入结果；
再递归分析右侧表达式。

例如：

1

(lambda ignored (set! x y))

在 x、y 都来自外层时，稳定顺序是：

1

[x, y]

不是只包含右侧的 [y]，也不是按字母排序后的结果。目标先出现于源码操作的语义位置，因此先进入捕获列表。

如果目标是函数参数：

1

(lambda x (set! x 42))

x 已在 bound 中，不需要捕获。调用时新建的参数 location 会提供写入目标。

用只写示例验证捕获没有遗漏

运行：

1

./mini ir examples/write_only_capture.lang

开头会看到：

1
2


x0.cell = cell 0
f.0 = closure lambda0 [x0.cell]

函数体只通过 set! 使用 x，closure 仍然捕获 x0.cell。函数自己的 IR 中则出现：

1

store x1.cell t.0

这正是 SetExpr::name 被自由变量分析识别出来的结果。

begin 按执行顺序分析两棵子树

begin 的分支很直接：

1
2
3
4
5
6


case ExprKind::begin: {
    const auto& begin = static_cast<const BeginExpr&>(expr);
    collect(*begin.first, bound, result);
    collect(*begin.second, bound, result);
    return;
}

这既保持首次出现顺序，也不会让 first 中的普通使用或写入目标漏掉。begin 本身不建立新绑定，所以分析两个子树时使用同一份 bound。

letrec 的 self 仍然不是自由变量

相对于 letrec 的函数体，函数名和参数名都已经绑定：

1
2
3
4
5
6


std::vector<std::string> free_vars(const LetRecExpr& letrec) {
    std::vector<std::string> bound{letrec.name, letrec.param};
    std::vector<std::string> result;
    collect(*letrec.function_body, bound, result);
    return result;
}

即使函数体读取或修改 self 名字，它在源语言作用域上也不是自由变量。

但第八章实现仍需让递归 closure 访问 self location。解释器和 lowering 会在普通自由变量结果之外，显式把预先分配的 self location 放到 closure 环境的第一项。要区分两句话：

1
2


self 不是源码自由变量
self location 是可变递归实现需要的隐藏捕获

把 self 混进通用 free_vars 结果，会破坏词法分析的定义；完全不保存 self location，又无法让 set! 修改递归绑定。

原有节点必须继续完整遍历

加入两个枚举值以后，collect 的 switch 仍要覆盖全部 AST：

let、letrec 和 lambda 正确维护绑定边界；
call 先分析 callee，再分析 argument；
record 从左到右分析所有字段；
record?、size 和 get 分析各自的表达式子树；
if 按 condition、then、else 顺序遍历；
set 与 begin 使用本节新增规则。

不要因为本章重点是状态，就把第六章的可变长度 record 或第七章的嵌套 closure 从分析器中删掉。每个语言特性都必须在后续快照继续成立。

本节的检查点

完成前端后，可以确认：

./mini ast examples/set.lang 中出现 Set 和 Begin；
set! 目标只能是普通 identifier；
二元 begin 恰好保存两个子表达式；
只写外层变量的 closure 仍捕获对应 cell；
set! 的目标和右侧按稳定顺序进入自由变量列表；
letrec 的 self 不属于普通自由变量，却由后续阶段显式保存 self location；
record、closure 等已有 AST 节点没有从 switch 中回退。

8.1 语言：修改绑定，但不改变词法作用域

8.3 解释器：Environment 找位置，Store 保存值

本节目录