多数编译器教程止步于计算器——解析 1 + 2 * 3，求值，结束。这个系列的终点不同：从一个空目录开始，逐步构建一个能检查类型错误、生成本机可执行文件、报告源码位置并接入编辑器的编译器。

目标语言暂名 Sprout，扩展名 .spr，编译器命令暂定 sproutc。实现语言是 Rust，主后端是 LLVM。进阶部分还会接入 Cranelift 即时编译（Just-In-Time compilation, JIT）、WebAssembly 组件和 MLIR 张量编译。

这篇导读划定语言范围、列出编译架构、给出语义边界草案并确认先修条件。代码从第 01 篇开始；本篇没有可运行的编译器。

本篇目标

读完这篇，需要能回答一个问题：给定一段 Sprout 源码 fn main() -> i64 { return 42; }，区分源语言、实现语言、中间表示和机器码四个层次。

这个区分贯穿整个系列。源语言是读者设计的 Sprout，实现语言是 Rust，中间表示包括 AST、HIR、SSA 和 LLVM IR，机器码是目标架构的二进制指令。混淆任何两层都会在后续调试中制造困惑。

最终演示长什么样

完成系列时，同一份多文件 Sprout 程序能读取整数文本，解析为数组，排序并输出统计值。它调用用户定义函数，使用结构体（struct）、枚举（enum）与泛型容器（generic container）；输入错误时返回明确诊断信息。

编译器交付五组可观察能力：

  1. sproutc check 对类型错误和未定义名字给出文件名、源码范围和错误码；正常程序生成可执行文件。
  2. --emit 能导出词法单元（Token）、抽象语法树（Abstract Syntax Tree, AST）、带类型的高层中间表示（Typed HIR）、静态单赋值形式（Static Single Assignment, SSA）和 LLVM 中间表示（LLVM IR），追踪同一表达式的完整翻译过程。
  3. 无优化版本（O0）与优化版本在约定语义上行为一致；运行时错误保留可定位信息。
  4. 编辑器通过语言服务器协议（Language Server Protocol, LSP）显示诊断、悬停类型和跳转定义；修改依赖文件后结果正确刷新。
  5. 进阶实作展示 Cranelift JIT 调用、WebAssembly 组件接口和 MLIR 张量运算的逐层降低。

编译架构

一份 Sprout 源文件从文本变成可执行程序，经过以下阶段：

1
2
3
4
5
6
7
8
源文件 → Token → AST → 名称解析 / 类型检查 → Typed HIR
                                                ├→ 参考解释器
                                                ├→ CFG / SSA → 自制优化 → LLVM IR → 目标文件 → 链接
                                                │           ├→ Cranelift JIT（标量子集）
                                                │           └→ Wasm（标量子集）→ 组件封装
                                                └→ 张量扩展 HIR → MLIR → CPU

源码映射 + 语义查询 → CLI 诊断 / LSP

"从零"覆盖自制词法器（lexer）、解析器（parser）、名称解析（name resolution）、类型检查（type checking）、HIR、控制流图（Control Flow Graph, CFG）/SSA、若干优化 pass 和运行时接口。LLVM 负责指令选择（instruction selection）、寄存器分配（register allocation）和目标文件生成；系统链接器负责最终链接。附录会用有限指令子集实验一次寄存器分配，交代被复用的机制。

词法器把源文本拆成 Token 流，每个 Token 带有源码位置。解析器根据语法规则把 Token 流组装成 AST。名称解析为每个标识符找到定义，类型检查确认类型约束。到 Typed HIR 为止，程序的含义已经完全确定——参考解释器可以直接执行它。

从 Typed HIR 到 LLVM IR 是降低（lowering）过程。先构建控制流图，把嵌套的 if/while 拆成基本块（basic block）和跳转。再把每个变量转换成 SSA 形式：每个名字只被赋值一次，分支合流处插入 phi 节点。这样做是因为多数优化算法在 SSA 上更容易实现。最后把自制 SSA 翻译成 LLVM IR 文本，交给 LLVM 的优化管线和后端。

第 02 篇先打通最短路径：一个只接受常量返回的函数，生成 LLVM IR 文本，链接成本机程序。第 03–07 篇扩展前端，建立参考解释器（reference interpreter）固定语义。第 10–12 篇引入自制 CFG/SSA，替换早期的过渡表示。读者能及早运行程序，后续亲手完成 SSA 构造，而不是全部交给 LLVM 的现成 pass。

Sprout 语法一览

Sprout 采用显式函数签名（function signature）和局部类型推断（local type inference）。熟悉 C、Rust、Java 的读者可以直接理解语法。

以下是第 09 篇后的目标输入，预期输出 55：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fn sum_to(n: i64) -> i64 {
    let mut sum: i64 = 0;
    let mut i: i64 = 1;
    while i <= n {
        sum = sum + i;
        i = i + 1;
    }
    return sum;
}

fn main() -> i64 {
    print_i64(sum_to(10));
    return 0;
}

起步类型只有三种：i64（64 位有符号整数）、bool 和 unit（空类型）。变量声明即初始化，可变变量用 let mut 标记。函数参数和返回类型必须显式标注。控制流包括 if/while/显式 return。

后续章节逐步加入数组、UTF-8 字符串、值结构体、带标签枚举和显式类型参数的泛型。数组和堆字符串通过显式引用计数（reference counting）管理内存。主线不开放裸指针、闭包、用户定义析构、trait 系统、借用检查、宏、异常展开、协程和包仓库。

语义边界

编译器对源程序的每一种行为都需要明确规则。规则不明确的地方，优化可能改变程序行为，测试也无法判定正误。以下五类语义边界在主线中必须先确定：

语义类别 主线约定 必须覆盖的反例
数值规则 i64 加减乘与取负按二进制补码回绕（two’s complement wrapping）；除法向零截断 除零与 i64 最小值除以 -1 产生运行时错误；参考解释器不继承宿主语言的溢出行为
求值顺序 操作数与实参从左到右求值；&&/|| 短路求值（short-circuit evaluation） 未选择分支中的函数调用、输出和除零不发生
类型与初始化 函数参数与返回类型显式；变量声明即初始化；禁止 bool/i64 隐式转换 读取未定义名字、缺失返回值被拒绝
控制流 词法作用域（lexical scope）；局部可变变量；if/while/显式 return 同层重复声明报错；嵌套遮蔽（shadowing）按规范解析；终结指令后不追加普通指令
聚合与内存 数组和堆字符串使用显式引用计数（reference counting）；禁止递归堆类型 数组越界受检；字符串按字节长度计量；别名共享修改、提前返回、覆盖赋值都必须插入正确释放

每条规则在对应章节实现时，都有正例和反例。参考解释器和编译器对同一输入必须给出一致结果。

预期编译器行为

列几组输入，标明编译器应该接受还是拒绝。

接受：

1
fn main() -> i64 { return 0; }
1
fn main() -> i64 { return 1 + 2 * 3; }
1
2
fn add(a: i64, b: i64) -> i64 { return a + b; }
fn main() -> i64 { return add(1, 2); }

拒绝：

1
fn main() -> i64 { return true; }

原因：返回类型 i64 与 bool 值 true 不匹配。类型检查阶段报错。

1
fn main() -> i64 { return x; }

原因：名字 x 未定义。名称解析阶段报错。

1
fn main() -> i64 { let a: i64 = 1; let a: i64 = 2; return a; }

原因：同一作用域重复声明 a。名称解析阶段报错。

先修条件

默认读者掌握一种静态类型语言（C、Java、Rust、Go 均可），理解递归（recursion）、树（tree）、哈希表（hash table）、基本命令行操作和 Git。

Rust 的枚举与模式匹配（enum & pattern matching）、所有权（ownership）和错误处理（Result/? 运算符）在第 01 篇的预备部分补足。不需要先实现 Rust 借用检查器，也不需要先读完编译原理教材。

系列参考两个外部资源的教学组织方式：Writing a C Compiler（Nora Sandler） 的功能递增结构与配套测试，以及 LLVM Kaleidoscope 教程 的后端接入方法。本系列的语言、语义和章节按 Sprout 重新设计。

31 篇怎样推进

主线 00–25 共 26 篇，进阶实作 26–30 共 5 篇。每篇从上一版的一个限制开始，增加一种可观察能力。

阶段 篇目 做到什么 阶段完成标志
第一份机器码 00–04 范围、工具链、最小编译器、词法、表达式解析 接受 return 42 生成可执行文件；拒绝非法输入
有类型的程序 05–09 名称解析、类型检查、参考解释器、函数、循环 sum_to(10) 输出 55；解释器与编译器结果一致
自制 SSA 与优化 10–14 基本块、CFG、SSA 构造、常量传播、LLVM 后端 O0 与 O2 输出一致；phi 节点正确处理循环和分支
数据与模块 15–19 数组、字符串、引用计数、结构体、泛型、多文件 多文件程序链接运行；引用计数无泄漏无双重释放
开发工具 20–25 源码映射、测试框架、增量分析、LSP、综合演示 编辑器实测诊断和跳转；干净构建可复现
进阶实作 26–30 Cranelift JIT、WebAssembly 组件、MLIR 张量 与 LLVM 主线结果对照

基础篇预计每篇阅读 40–60 分钟、实验 2–4 小时。SSA、运行时和 LSP 每篇实验 6–10 小时。按每周 2 篇估算，31 篇约需 16 周，另预留 2–4 周处理勘误和跨平台验证。该预算尚未经读者试读校准。

第 01 篇会先做什么

第 01 篇不急着写词法器。它先冻结工具链：Rust 版本、Cargo 配置、LLVM 工具（opt、llc、Clang）的精确版本号。手写一份最小的 LLVM IR 文本文件，包含一个返回 42 的函数，用 LLVM 工具链编译并链接成本机程序，检查退出码。

这一步看起来不像"写编译器"，但它决定后面每一篇的可复现性。没有固定的工具链版本和明确的目标架构，后面的错误会同时像 Rust 问题、LLVM 版本问题和链接问题，定位代价远大于一次前置验证。

先修自测

题目：给定以下 Sprout 源程序：

1
2
3
fn main() -> i64 {
    return 42;
}

回答四个问题：

  1. 这段文本属于什么语言？用什么语言实现它的编译器？
  2. 编译器会把它翻译成哪些中间表示？
  3. 最终可执行文件里，42 以什么形式存在？
  4. 如果把 42 改成 "hello"，编译器应该在哪个阶段报错？

答案：

  1. 源语言是 Sprout；实现语言是 Rust。两种语言各有自己的语法和类型系统，不能混淆。
  2. 编译器先生成 AST，经名称解析和类型检查后得到 Typed HIR，再降低（lower）到 CFG/SSA，最后输出 LLVM IR 文本。LLVM 把 IR 编译成目标文件，链接器生成可执行程序。
  3. 可执行文件里 42 是一条机器指令的立即数（immediate operand），具体编码取决于目标架构。在 x86-64 上，return 42 大致对应 mov eax, 42 加 ret。
  4. 类型检查阶段。main 声明返回 i64，"hello" 是字符串字面量，类型不匹配。编译器在生成代码之前就应该拒绝这段程序，给出包含文件名和源码位置的错误信息。

练习

  1. 画出表达式 1 + 2 * 3 的抽象语法树。根节点是什么运算？左子树和右子树分别包含什么？对比 (1 + 2) * 3 的树形结构。
  2. 查阅 LLVM Language Reference 中 add 和 ret 指令的语法。尝试手写一个返回 42 的 LLVM IR 函数（不需要编译通过，语法方向正确即可）。
  3. 安装 Rust 工具链，运行 rustc --version 和 cargo --version，记录版本号。第 01 篇会锁定具体版本要求。

参考资料

下一篇：01 - return 42：从源码到可执行文件。