第3章：AST设计——构建程序的骨架

在上一章中，我们通过词法分析器将源代码转换成了Token流。但Token序列只是平面的符号流，它还不"理解"程序的结构。比如，面对 1 + 2 * 3 这段代码，词法分析器只能看到 Number(1), Plus, Number(2), Star, Number(3) 这样一串Token，但它不知道哪些Token应该先组合，哪些是高优先级的操作。

这就是我们需要AST（抽象语法树）的原因——它赋予程序以结构，让代码的层次关系变得清晰可见。本章我们将深入探讨AST设计的核心思想：如何在类型系统中优雅地表达程序的语法结构。

3.1 问题引入：从平面到层次

为什么需要AST？

考虑一个简单的表达式：

if x > 0 then
    x + 1
else
    x - 1

词法分析后的Token流是：

If, Identifier("x"), Greater, Number(0), Then,
Identifier("x"), Plus, Number(1),
Else,
Identifier("x"), Minus, Number(1)

这个Token序列丢失了很多重要信息：

条件是什么？从哪里开始，到哪里结束？
then分支和else分支的边界在哪里？
整个if语句的范围是什么？

AST的目标就是重建这些层次关系，形成一棵树：

        IfStmt
       /      \
   condition   branches
      |        /    \
   BinaryExpr  then  else
   /   \      |      |
  x   >    BinaryExpr BinaryExpr
        |    /   \   /   \
       0    x   + x   -
                |   |   |
                1   1   1

有了这棵树，后续的类型检查、代码生成等阶段就可以直接操作树结构，而不需要重新解析Token。

设计目标

一个优秀的AST设计应该满足：

表达力强：能够精确表达语言的所有语法结构
类型安全：利用Rust的类型系统防止非法操作
易于遍历：方便后续的语法分析、类型检查、代码生成
可扩展性：添加新语法特性时不需要大规模重构
调试友好：携带足够的元数据（如位置信息）用于错误报告

接下来，我们通过一系列设计决策来实现这些目标。

3.2 设计思路一：分离Expression和Statement

核心问题

第一个要解决的设计问题是：是否需要区分Expression（表达式）和Statement（语句）？

在编程语言理论中：

表达式（Expression）：计算并返回值，如 1 + 2, func(), x * y
语句（Statement）：执行动作但不一定返回值，如 if, while, var x = 1

为什么分离？

方案A：统一使用Expr

enum Expr {
    If(IfExpr),           // if可以作为表达式
    While(WhileExpr),     // while也作为表达式
    // ...
}

方案B：分离Expr和Stmt（我们采用）

enum Expr { /* 表达式 */ }
enum Stmt { /* 语句 */ }

我们选择方案B，理由如下：

语义清晰：有些结构天生就是语句而非表达式
- while 循环执行副作用，不产生有意义的返回值
- var x = 1 是声明，不是计算

类型安全：防止在需要值的地方使用语句

// 如果只有Expr，这个代码类型上是合法的，但语义错误：
let x = Expr::While(while_loop);  // while不返回值！

// 分离后，编译器可以直接拒绝：
let x: Expr = /* ... */;
match x {
    Stmt::While(_) => compile_error!("while不是表达式"),
    // ...
}

符合Stone语言设计：Stone语言中if和while是语句，不是表达式
- 这与Rust不同（Rust中if是表达式）
- 需要准确反映目标语言的语义
优化机会：编译器可以对不返回值的语句进行优化
- 例如：语句末尾的表达式不需要保留结果

但边界在哪里？

有些语言的设计很有趣：

Rust：几乎所有东西都是表达式（包括if、match、block）
C/Java：严格区分表达式和语句
JavaScript：表达式可以是语句（表达式语句）

Stone的设计接近C/Java，所以我们选择分离。但在实现时，我们允许"表达式语句"的存在：

enum Stmt {
    Expr(Expr),  // 表达式语句：允许单独写一个表达式
    // ...
}

这样 x + 1; 这样的代码也是合法的（虽然效果通常是丢弃结果）。

3.3 设计思路二：AST节点的类型表示

核心问题

第二个关键问题是：如何用Rust的类型系统表达多样化的语法结构？

假设我们要表示这些表达式：

数字：42
标识符：x
二元运算：x + 1
函数调用：func(a, b)

方案对比

方案1：单一枚举（Flat Enum）

#[derive(Debug, Clone)]
pub enum Expr {
    Number(i64),
    Identifier(String),
    Binary { op: BinaryOp, left: Box<Expr>, right: Box<Expr> },
    Call { callee: Box<Expr>, args: Vec<Expr> },
}

优点：

结构简单，易于理解
模式匹配直观

缺点：

每个variant的数据结构耦合在一起
添加字段需要修改枚举定义
难以共享通用逻辑

方案2：枚举+结构体（Enum + Structs）（我们采用）

pub enum Expr {
    NumberLiteral(NumberLiteral),
    Identifier(Identifier),
    BinaryExpr(BinaryExpr),
    Call(Call),
}

pub struct NumberLiteral {
    pub value: i64,
    pub location: Location,
}

pub struct BinaryExpr {
    pub left: Box<Expr>,
    pub op: BinaryOp,
    pub right: Box<Expr>,
    pub location: Location,
}

优点：

每个节点的数据结构独立定义，清晰明了
可以为每个节点实现trait（如Display、PartialEq）
便于序列化/反序列化
未来添加字段不影响其他节点

缺点：

需要定义更多类型
文件结构更复杂

我们选择方案2，因为它的可维护性和可扩展性更好。随着语言特性的增加，每个节点的元数据也会增多（如类型信息、作用域等），独立的结构体设计会让代码更清晰。

何时使用枚举，何时使用结构体？

使用枚举的场景：

表示"一个东西可能是多种类型之一"

pub enum Expr {
    NumberLiteral(NumberLiteral),
    StringLiteral(StringLiteral),
    // ...
}

变体之间是互斥的关系
需要在编译时穷尽所有可能（模式匹配）

使用结构体的场景：

表示"一个东西有多个属性"

pub struct BinaryExpr {
    pub left: Box<Expr>,
    pub op: BinaryOp,
    pub right: Box<Expr>,
}

属性之间是组合关系
需要为每个属性单独命名

在我们的AST设计中：

Expr 和 Stmt 是枚举（分发到具体类型）
NumberLiteral, BinaryExpr, IfStmt 等是结构体（包含具体数据）

这种"外层枚举，内层结构体"的模式是Rust中表示树状结构的经典方式，称为代数数据类型（ADT）。

3.4 核心实现：构建AST节点层次

实现Expr枚举

让我们看看实际的实现。首先是表达式的定义：

use stone_core::Location;

/// 表达式枚举：所有可能的表达式类型
#[derive(Debug, Clone, PartialEq)]
pub enum Expr {
    NumberLiteral(NumberLiteral),
    StringLiteral(StringLiteral),
    Identifier(Identifier),
    BinaryExpr(BinaryExpr),
    UnaryExpr(UnaryExpr),
    Call(Call),
    ArrayLiteral(ArrayLiteral),
    ArrayAccess(ArrayAccess),
}

/// 数字字面量
#[derive(Debug, Clone, PartialEq)]
pub struct NumberLiteral {
    pub value: i64,
    pub location: Location,
}

这里有几个设计要点：

Location的必要性
- 每个节点都携带位置信息
- 用于错误报告："在file.stone:10:5，类型错误"
- 调试时可以追踪到源代码位置
- 后续可以用于源码映射（source map）
为什么derive这些trait？
- Debug：调试打印AST结构
- Clone：AST转换时需要复制节点（如内联函数）
- PartialEq：测试时比较AST是否相等

BinaryOp的独立设计

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BinaryOp {
    Add, Sub, Mul, Div, Mod,
    Equal, Less, Greater,
    LessEqual, GreaterEqual,
    And, Or,
    Assign,
}

使用独立的枚举而非String，避免拼写错误
Copy trait使其可以廉价复制（运算符应该是Copy的）
后续可以为运算符添加元数据（如优先级、结合性）

实现Stmt枚举

语句的定义遵循同样的原则：

use stone_core::Location;
use super::Expr;

/// 语句枚举
#[derive(Debug, Clone, PartialEq)]
pub enum Stmt {
    Expr(Expr),
    Block(Block),
    If(IfStmt),
    While(WhileStmt),
    Def(DefStmt),
    Var(VarStmt),
}

/// if语句
#[derive(Debug, Clone, PartialEq)]
pub struct IfStmt {
    pub condition: Box<Expr>,        // 条件是表达式
    pub then_branch: Box<Stmt>,       // 分支是语句
    pub else_branch: Option<Box<Stmt>>, // else分支可选
    pub location: Location,
}

设计要点：

递归结构使用Box
```
pub struct BinaryExpr {
    pub left: Box<Expr>,   // 为什么是Box？
    pub right: Box<Expr>,
}
```
- Rust需要在编译时知道类型的大小
- Expr是枚举，大小取决于最大的variant
- 如果直接用Expr，会导致递归类型大小无穷大
- Box<Expr>是指针，大小固定（8字节）
Option的使用
- else_branch是可选的：Option<Box<Stmt>>
- Rust的Option是空指针优化的，不占用额外空间
- 类型系统强制处理None的情况，防止空指针错误

Vec的使用

pub struct Block {
    pub stmts: Vec<Stmt>,  // 语句序列
    pub location: Location,
}

Vec是动态增长的数组
适合表示"零个或多个"的集合
后续可以轻松迭代、索引

3.5 深入理解：与Java版本的对比

如果你看过《Programming Language Pragmatics》中的Stone语言Java实现，你会发现两种语言的设计哲学差异：

Java版本的设计

// 抽象基类
abstract class ASTree {
    abstract Object eval(Environment env);
}

// 具体类
class NumberLiteral extends ASTree {
    private int value;
    @Override
    public Object eval(Environment env) {
        return value;
    }
}

class BinaryExpr extends ASTree {
    private ASTree left;
    private ASTree right;
    // ...
}

Rust版本的设计

// 枚举分发
pub enum Expr {
    NumberLiteral(NumberLiteral),
    BinaryExpr(BinaryExpr),
}

// 独立结构体
pub struct NumberLiteral {
    pub value: i64,
    pub location: Location,
}

// 评估逻辑通过模式匹配
impl Expr {
    pub fn eval(&self, env: &Environment) -> Value {
        match self {
            Expr::NumberLiteral(n) => Value::Int(n.value),
            Expr::BinaryExpr(b) => b.eval(env),
            // ...
        }
    }
}

对比分析

维度	Java方式	Rust方式
类型系统	继承层次（子类型多态）	代数数据类型（ADT）
分发机制	虚函数表（动态分发）	模式匹配（静态分发）
扩展性	添加新节点类容易，添加新操作难	添加新操作容易，添加新节点需要修改match
性能	虚函数调用开销	零成本抽象，内联优化
类型安全	运行时类型检查（可能ClassCastException）	编译时检查，无运行时类型错误
内存布局	对象 + 虚表指针	栈上分配，无额外开销

为什么选择ADT？

模式匹配的威力

match expr {
    Expr::BinaryExpr(BinaryExpr { op: BinaryOp::Add, left, right }) => {
        // 可以在匹配时解构，代码更清晰
    }
    // 编译器会检查是否遗漏了某个variant
}

内存效率
- enum的内存大小 = 最大variant的大小 + discriminant
- 相比Java的引用，减少了堆分配
编译器优化
- Rust可以内联整个match表达式
- 消除了虚函数调用的开销
null安全
- Option强制处理None的情况
- 不需要像Java那样到处检查null

3.6 深入理解：Location的设计哲学

为什么每个节点都需要Location？

初学者可能会疑惑：为什么简单的数字字面量也需要存储位置信息？

pub struct NumberLiteral {
    pub value: i64,
    pub location: Location,  // 有必要吗？
}

Location的三大用途

1. 错误报告

当类型检查器发现错误时，需要精确指出问题所在：

// 类型错误示例
let x: String = 42;  // 错误：不能将i64赋值给String

没有Location：

error: type mismatch
  --> src/main.rs:10:5

有Location：

error: type mismatch
  --> src/main.stone:10:15
   |
10 | let x: String = 42;
   |               ^^ expected String, found i64

2. 调试信息

运行时错误需要堆栈跟踪：

panic: division by zero
  --> src/main.stone:15:10
   |
15 | let x = a / b;
   |          ^^^^^ attempted to divide by zero
  --> called from function 'calculate' at line 8

3. 源码映射

在编译器或IDE中，Hover某个变量时显示其定义位置：

// 用户鼠标悬停在 'x' 上
// IDE显示：x defined at src/main.stone:5:10

Location的实现

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Location {
    pub file: &'static str,  // 文件名
    pub line: usize,         // 行号（从1开始）
    pub column: usize,       // 列号（从1开始）
}

设计考量：

Copy trait：Location应该可以廉价复制
&'static str：文件名在编译期已知，避免String开销
从1开始计数：符合人类习惯（编辑器显示也从1开始）

何时可以省略Location？

对于一些辅助性的、不直接对应源代码的节点，可以省略Location：

// 不好的设计：优化后的中间节点也带Location
pub struct OptimizedExpr {
    pub node: Expr,
    pub location: Location,  // 没有意义：这个节点不在源码中
}

// 好的设计：分清源码节点和中间表示
pub enum IRNode {
    Expr(Expr),              // 源码节点，有Location
    Temporary(TempVar),      // 临时变量，无Location
}

3.7 实践：构建stone-ast crate

创建crate结构

stone-lang-rs/
├── stone-ast/
│   ├── Cargo.toml
│   └── src/
│       ├── lib.rs
│       ├── expr.rs
│       └── stmt.rs

Cargo.toml

[package]
name = "stone-ast"
version = "0.1.0"
edition = "2021"

[dependencies]
stone-core = { path = "../stone-core" }

expr.rs

use stone_core::Location;

#[derive(Debug, Clone, PartialEq)]
pub enum Expr {
    NumberLiteral(NumberLiteral),
    Identifier(Identifier),
    BinaryExpr(BinaryExpr),
    // ...
}

#[derive(Debug, Clone, PartialEq)]
pub struct NumberLiteral {
    pub value: i64,
    pub location: Location,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BinaryOp {
    Add, Sub, Mul, Div,
}

#[derive(Debug, Clone, PartialEq)]
pub struct BinaryExpr {
    pub left: Box<Expr>,
    pub op: BinaryOp,
    pub right: Box<Expr>,
    pub location: Location,
}

// ... 其他节点定义

stmt.rs

use stone_core::Location;
use super::Expr;

#[derive(Debug, Clone, PartialEq)]
pub enum Stmt {
    Expr(Expr),
    Block(Block),
    If(IfStmt),
    // ...
}

#[derive(Debug, Clone, PartialEq)]
pub struct Block {
    pub stmts: Vec<Stmt>,
    pub location: Location,
}

#[derive(Debug, Clone, PartialEq)]
pub struct IfStmt {
    pub condition: Box<Expr>,
    pub then_branch: Box<Stmt>,
    pub else_branch: Option<Box<Stmt>>,
    pub location: Location,
}

// ... 其他语句定义

lib.rs

mod expr;
mod stmt;

pub use expr::*;
pub use stmt::*;

编译验证

cd stone-lang-rs
cargo build -p stone-ast

如果编译成功，恭喜！你已经完成了AST节点的定义。

3.8 设计反思：可以改进的地方

当前的AST设计虽然可用，但还有一些改进空间：

问题1：缺少通用trait

目前没有统一的AST trait，难以编写通用算法：

// 当前：需要为Expr和Stmt分别实现
impl Expr {
    pub fn location(&self) -> Location {
        match self {
            Expr::NumberLiteral(n) => n.location,
            Expr::BinaryExpr(b) => b.location,
            // ...
        }
    }
}

// 改进：定义trait
pub trait ASTNode {
    fn location(&self) -> Location;
    fn children(&self) -> Vec<&dyn ASTNode>;
}

impl ASTNode for Expr {
    fn location(&self) -> Location {
        match self {
            Expr::NumberLiteral(n) => n.location,
            // ...
        }
    }
}

问题2：缺少类型信息

当前AST只保存语法结构，没有类型信息：

// 当前：只有语法
pub struct BinaryExpr {
    pub left: Box<Expr>,
    pub op: BinaryOp,
    pub right: Box<Expr>,
}

// 改进：添加类型字段（用于类型检查后）
pub struct BinaryExpr {
    pub left: Box<Expr>,
    pub op: BinaryOp,
    pub right: Box<Expr>,
    pub type_: Type,  // 表达式的类型
}

问题3：缺少所有权信息

后续实现垃圾回收或借用检查时需要所有权信息：

pub struct Identifier {
    pub name: String,
    pub is_mutable: bool,     // 是否可变
    pub is_owned: bool,       // 是否拥有所有权
    pub location: Location,
}

这些问题我们会在后续章节逐步解决，构建一个更完善的AST体系。

3.9 练习

基础练习

手动构建AST
- 写一个函数，手动构建表达式 (1 + 2) * 3 的AST
- 打印这个AST，观察其结构
添加新的运算符
- 为BinaryOp添加指数运算符 Pow
- 修改相关代码，确保编译通过
Location测试
- 创建几个AST节点，设置不同的Location
- 实现一个函数，格式化打印Location（如 "file.stone:10:5"）

进阶练习

实现AST遍历器

pub trait Visitor {
    fn visit_expr(&mut self, expr: &Expr);
    fn visit_stmt(&mut self, stmt: &Stmt);
}

// 实现一个打印AST的Visitor
struct ASTPrinter {
    indent: usize,
}

impl Visitor for ASTPrinter {
    // ...
}

实现AST变换

// 将所有二元表达式展开为三元表达式（a+b -> a+0+b）
pub fn canonicalize(expr: Expr) -> Expr {
    match expr {
        Expr::BinaryExpr(b) => /* ... */
        _ => expr,
    }
}

对比分析
- 阅读《Programming Language Pragmatics》中Stone语言的Java实现
- 对比Java的类层次和Rust的ADT，写出你的分析
- 考虑：如果要添加一个新的表达式类型（如Lambda表达式），两种方案各需要修改多少代码？

挑战练习

设计TypedAST
- 定义一个带类型信息的AST
- 实现从AST到TypedAST的转换（类型检查）
- 考虑类型信息应该如何存储？（泛型？enum？trait对象？）
实现AST序列化
- 使用serde为所有AST节点添加Serialize/Deserialize
- 实现将AST保存为JSON，再从JSON恢复
- 这对于编译器缓存、增量编译很有用
性能优化
- 当前AST使用Box和Vec，可能存在性能问题
- 考虑使用Arena分配器（如bumpalo）减少内存碎片
- 对比优化前后的性能差异

3.10 小结

本章我们深入探讨了AST设计的核心思想：

设计原则：

分离关注点：Expr和Stmt分离，语义更清晰
类型安全：利用Rust类型系统防止错误
可扩展性：枚举+结构体的组合易于扩展
元数据丰富：Location等信息支持错误报告

技术要点：

使用枚举表示"或"关系（Expr可能是A或B）
使用结构体表示"与"关系（BinaryExpr有left和right）
使用Box解决递归类型大小问题
使用Option表达可选性
使用Vec表示集合

下一步：

AST定义完成后，我们需要实现语法分析器，将Token流转换为AST。在第4章中，我们将：

学习解析组合子（Parser Combinator）的概念
使用nom库实现递归下降解析器
处理运算符优先级和结合性
构建完整的语法分析流程

AST是编译器的基础，理解其设计思想对于构建编译器至关重要。一个好的AST设计能让后续的代码更简洁、更安全、更高效。继续加油！

FilesExpand file tree

chapter-3.md

Latest commit

History

chapter-3.md

File metadata and controls

第3章：AST设计——构建程序的骨架

3.1 问题引入：从平面到层次

为什么需要AST？

设计目标

3.2 设计思路一：分离Expression和Statement

核心问题

为什么分离？

但边界在哪里？

3.3 设计思路二：AST节点的类型表示

核心问题

方案对比

何时使用枚举，何时使用结构体？

3.4 核心实现：构建AST节点层次

实现Expr枚举

实现Stmt枚举

3.5 深入理解：与Java版本的对比

Java版本的设计

Rust版本的设计

对比分析

为什么选择ADT？

3.6 深入理解：Location的设计哲学

为什么每个节点都需要Location？

Location的三大用途

Location的实现

何时可以省略Location？

3.7 实践：构建stone-ast crate

创建crate结构

Cargo.toml

expr.rs

stmt.rs

lib.rs

编译验证

3.8 设计反思：可以改进的地方

问题1：缺少通用trait

问题2：缺少类型信息

问题3：缺少所有权信息

3.9 练习

基础练习

进阶练习

挑战练习

3.10 小结