章节目录

AST 与 parser：拥有数量不定的字段子树

本节阅读量:

这一节把四种新语法变成明确的 AST：

1
2
3
4

(record expr ...)
(record? expr)
(size expr)
(get expr index)

AST 只描述源码结构。它不会分配运行时对象，也不会保存 tag、header 或字节偏移。

继续使用显式 kind

ExprKind 新增四类动作：

1
2
3
4
5
6
7

enum class ExprKind {
    // 前文种类省略
    record,
    record_predicate,
    record_size,
    field,
};

源码名称 get 对应 ExprKind::field：前者是语言语法，后者表示 AST 节点要执行字段读取。解释器和 IR lowerer 仍通过 switch (expr.kind) 分派，不把操作种类藏在 C++ 类型名里。

RecordExpr 使用 move-only vector

字段数量不定，AST 节点需要一个有序容器：

1
2
3
4
5
6

struct RecordExpr final : Expr {
    explicit RecordExpr(std::vector<std::unique_ptr<Expr>> fields);

    std::vector<std::unique_ptr<Expr>> fields;
    std::string dump() const override;
};

这里有两层所有权：

  • std::vector 保存数量不定且顺序确定的元素；
  • 每个 std::unique_ptr<Expr> 独占一棵字段表达式子树。

因此 (record) 对应空 vector，(record 10 20 30) 对应三个 AST 子树。源语言没有获得 vector；vector 只是 C++ AST 用来拥有若干子节点的容器。

构造器接管整个容器：

1
2

RecordExpr::RecordExpr(std::vector<std::unique_ptr<Expr>> fields)
    : Expr(ExprKind::record), fields(std::move(fields)) {}

unique_ptr 不可复制，所以 vector 也必须整体移动。根 AST 销毁时，vector 会逐个销毁 unique_ptr，所有字段子树随之释放。

AST 顺序就是源码顺序

例如：

1

(record (+ 20 20) (sub1 3) (record))

形成：

1
2
3
4
5
6
7
8

Record
├── fields[0]: Add
│   ├── Int(20)
│   └── Int(20)
├── fields[1]: Sub1
│   └── Int(3)
└── fields[2]: Record
    └── fields: empty

vector 的先后顺序保留了语言要求的左到右求值。解释器和 lowering 都应使用从 begin() 到 end() 的循环，不能先处理后面的字段。

predicate 与 size 各有一棵子树

record? 和 size 都是一元特殊形式，但它们的失败语义不同，因此使用不同 kind 与节点：

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

struct RecordPredicateExpr final : Expr {
    explicit RecordPredicateExpr(std::unique_ptr<Expr> expr);

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

struct RecordSizeExpr final : Expr {
    explicit RecordSizeExpr(std::unique_ptr<Expr> record);

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

record? 对任何 Value 都有结果，size 则要求求值结果确实是 record。AST 不执行这项检查，只把两种语言动作保留下来。

GetExpr 把 index 保存为元数据

get 的对象位置是任意表达式，index 则是 parser 已经验证过的非负字面量：

1
2
3
4
5
6
7

struct GetExpr final : Expr {
    GetExpr(std::unique_ptr<Expr> record, std::size_t index);

    std::unique_ptr<Expr> record;
    std::size_t index;
    std::string dump() const override;
};

这里没有第二棵 index 子树。std::size_t 表达“数组位置不会为负”；实际是否小于 record 长度，要等求值时才能知道。

例如：

1

(get values 20)

在语法上完全合法，会形成：

1
2
3

Get
├── record: Var(values)
└── index: 20

若 values 只有三个字段，运行时才报告越界。

dump 保持结构可见

RecordExpr::dump() 用循环输出所有字段：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

std::string RecordExpr::dump() const {
    std::string result = "Record(";
    for (std::size_t i = 0; i < fields.size(); ++i) {
        if (i != 0) {
            result += ", ";
        }
        result += fields[i]->dump();
    }
    return result + ")";
}

于是：

1
2
3
4
5

(record)              -> Record()
(record 40 2)         -> Record(Int(40), Int(2))
(record? 42)          -> RecordPredicate(Int(42))
(size (record))       -> RecordSize(Record())
(get (record 40 2) 1) -> Get(Record(Int(40), Int(2)), 1)

可以用现有示例核对：

1

./mini ast examples/record_get.lang

parser 先识别固定特殊形式

和 let、if、lambda 一样，四个新 head 必须在普通函数调用兜底之前识别：

1
2
3
4

(record ...)  -> RecordExpr
(record? ...) -> RecordPredicateExpr
(size ...)    -> RecordSizeExpr
(get ...)     -> GetExpr

record? 中的问号不是普通 identifier 规则的一部分。它只作为固定特殊拼写由 parser 的 head 分支识别；用户变量名仍保持 letter+。

解析零个或多个字段

遇到 record 后，parser 一直读取表达式，直到看见与当前列表配对的 )：

1
2
3
4
5
6
7
8
9

if (head == "record") {
    advance();
    std::vector<std::unique_ptr<Expr>> fields;
    while (peek() != ")") {
        fields.push_back(parse_expr());
    }
    advance();
    return std::make_unique<RecordExpr>(std::move(fields));
}

这个循环自然覆盖所有 arity：

1
2
3

(record)            循环零次
(record 1)          循环一次
(record 1 2 3)      循环三次

每次 push_back 都发生在上一个 parse_expr() 返回之后，AST 字段顺序与源码顺序一致。

注意右括号在这里由 advance() 消费。parser 创建的是 AST 节点；真正的 record 只有解释器执行或编译后程序运行时才会分配。

解析 record? 与 size

两种一元形式都递归解析恰好一个表达式，再立即要求右括号：

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

if (head == "record?") {
    advance();
    auto expr = parse_expr();
    expect(")", "expected ')' after record? expression");
    return std::make_unique<RecordPredicateExpr>(std::move(expr));
}

if (head == "size") {
    advance();
    auto record = parse_expr();
    expect(")", "expected ')' after size expression");
    return std::make_unique<RecordSizeExpr>(std::move(record));
}

因此 (record? x y) 和 (size) 都会在 parser 阶段失败；parser 检查的是 arity，不检查 x 是否为 record。

index 必须是 digit-only token

解析 get 时，第一项调用 parse_expr()，第二项直接读取一个 token并交给 parse_field_index：

1
2
3
4
5
6
7

if (head == "get") {
    advance();
    auto record = parse_expr();
    std::size_t index = parse_field_index(advance());
    expect(")", "expected ')' after get expression");
    return std::make_unique<GetExpr>(std::move(record), index);
}

辅助函数要求 token 中每个字符都是十进制数字，再转为 std::size_t。因此：

源码 parser 结果
(get r 0) index 0
(get r 2) index 2
(get r 01) index 1
(get r -1) 拒绝：不是非负字面量
(get r i) 拒绝：不是整数字面量
(get r (+ 1 1)) 拒绝：index 不是单个 token

parser 不知道 r 最终有多长，因此接受 2，但不能在这里判断越界。

语法检查与动态检查的边界

下面三段程序都能形成 AST：

1
2
3

(size 42)
(get 42 0)
(get (record 10) 3)

parser 只确认每种形式的形状正确。运行时才分别发现：

  • size 收到的不是 record；
  • get 收到的不是 record；
  • get 的 index 超过实际字段数。

让 parser 只承担结构检查，才能保持解释器和编译器共享同一 AST，并在各自执行路线中实现相同的动态语义。

前端检查点

完成这一节后，应能确认：

  • RecordExpr 用 vector 拥有零个或多个 unique_ptr 子树；
  • record?、size、get 有各自显式 kind；
  • GetExpr::index 是 std::size_t，不是 Expr；
  • (record) 合法且 dump 为 Record()；
  • (record 1 2 3) 保留三个字段，而不是 arity 错误；
  • index 只接受非负整数字面量；
  • 普通 identifier 规则没有因 record? 而扩大。

下一节让解释器消费这些节点。它会用 C++ vector 保存求值后的字段，同时处理对象身份、类型检查和实际边界。

6.2 值表示：一个机器字怎样引用不同的堆对象

上一节

6.4 解释器：用共享对象保存一组 Value

下一节
本节目录