从零编写现代编译器 01 - return 42：从源码到可执行文件

一个只返回 42 的函数，从源码文本变成本机可执行文件，中间到底经历了什么？这篇把整条路走一遍：手动分词、构造语法树、生成 LLVM IR、编译成目标文件、链接为二进制、运行并检查退出码。走完这条最短路径之后，后续每篇只需往流水线里加东西。

最小的程序

Sprout 语言的第一个合法程序只有一行有效逻辑：

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

fn 声明函数，main 是入口，-> i64 标注返回类型为 64 位有符号整数，函数体只做一件事——返回整数字面量 42。这个程序没有变量、没有条件、没有循环，但它足以驱动编译器的每一个阶段。

编译器要做的事情可以用一条流水线概括：

源码 → 词法分析 → 语法分析 → 代码生成 → LLVM 工具链 → 可执行文件

下面逐段走完这条线。

源码到 Token：词法分析

词法分析器（lexer）的工作是把字符流切成有意义的最小单元——Token。对上面那段源码，手动分词的结果是：

FN              -- 关键字 fn
IDENT("main")   -- 标识符
LPAREN          -- (
RPAREN          -- )
ARROW           -- ->
IDENT("i64")    -- 标识符（类型名，词法阶段视为普通标识符）
LBRACE          -- {
RETURN          -- 关键字 return
INT(42)         -- 整数字面量
SEMI            -- ;
RBRACE          -- }

11 个 Token，每个要么是关键字，要么是标点，要么是带值的字面量或标识符。空白和换行被消耗掉，不出现在 Token 列表里。

分词的规则很简单：维护一个指向当前字符的索引，从头扫到尾。看到字母开头的连续字母数字序列，查关键字表——命中就是关键字 Token（fn、return），否则是 IDENT。i64 在词法阶段视为普通标识符，由后续的类型解析阶段识别。看到数字开头的连续数字序列，解析成 INT。看到 - 后紧跟 >，合并成 ARROW——这是唯一一个需要向前看一个字符的情况。单个标点字符各自对应一种 Token：( 是 LPAREN，) 是 RPAREN，{ 是 LBRACE，} 是 RBRACE，; 是 SEMI。遇到空白、制表符、换行，跳过并继续。遇到不认识的字符，报错。

这一步没有歧义，不需要回溯，时间复杂度是源码长度的线性函数。词法分析器的输出是一个 Vec<Token>，后续阶段不再接触原始字符串。Token 列表是语法分析器的唯一输入，两个阶段之间通过这个明确的数据结构解耦。

Token 到 AST：语法分析

语法分析器（parser）读入 Token 序列，按文法规则组织成树形结构——抽象语法树（Abstract Syntax Tree, AST）。对这个程序，AST 长这样：

Program
└── Function
    ├── name: "main"
    ├── params: []
    ├── return_type: I64
    └── body: Block
        └── ReturnStmt
            └── expr: IntLiteral(42)

顶层是 Program，包含一个 Function 节点。函数节点记录名字、参数列表（空）、返回类型和函数体。函数体是一个 Block，里面只有一条 ReturnStmt，返回表达式是整数字面量 42。

对于当前只接受"一个函数、一条 return 语句、一个整数"的极简文法，解析器的逻辑可以硬编码：依次期望 FN，期望 IDENT（取出函数名），期望 LPAREN 和 RPAREN（空参数列表），期望 ARROW 和 IDENT("i64")（返回类型），期望 LBRACE（函数体开始），期望 RETURN 和 INT（取出返回值），期望 SEMI，期望 RBRACE（函数体结束）。任何位置遇到不符合预期的 Token 都直接报错退出。

这不是真正的递归下降——更像是一份检查清单——但它能正确处理当前唯一合法的输入形式。AST 的关键作用是把线性的 Token 序列转化成带层次关系的树结构：程序包含函数，函数包含语句，语句包含表达式。这个层次关系决定了代码生成器的遍历方式。后续加入算术表达式和多条语句后，解析器会扩展成真正的递归下降解析器，并引入 Pratt 算法处理运算符优先级。

AST 到 LLVM IR：代码生成

代码生成器（codegen）遍历 AST，输出 LLVM 文本格式的中间表示（IR）。对这棵树，输出是：

define i64 @main() {
    ret i64 42
}

三行，逐个拆解：

• define i64 @main() —— 定义一个返回 i64 的函数，名字是 main，无参数。define 是 LLVM 关键字，@ 前缀表示全局符号。
• ret i64 42 —— 返回指令，类型 i64，值 42。这是 LLVM IR 的终结指令，执行到这里函数就结束了。
• 花括号界定函数体。

LLVM IR 是一种强类型的、SSA（Static Single Assignment）形式的中间语言。每条指令的操作数都带类型标注，每个值只被赋值一次。现在只有一条 ret，SSA 的约束自动满足。等后续引入变量和分支，SSA 的构造就需要专门处理了。

代码生成器的实现同样极简：遍历 AST，遇到 Function 节点就输出 define 头部，遇到 ReturnStmt 就输出 ret，遇到 IntLiteral 就输出对应数值。输出目标是一个 .ll 文本文件。

把上面的 IR 保存为 hello.ll，接下来交给 LLVM 的命令行工具。

LLVM IR 到目标文件

llc -filetype=obj -o hello.o hello.ll

llc 是 LLVM 的静态编译器。它读入文本或 bitcode 格式的 IR，执行指令选择、寄存器分配、指令调度，输出目标平台的机器码。-filetype=obj 指定输出为目标文件（.o），而不是汇编文本。

目标文件里包含几个关键部分：.text 段存放机器指令，符号表记录 main 函数的名字、地址偏移和绑定属性，重定位表记录需要链接器填充的外部引用地址。可以用 objdump -d hello.o 查看反汇编输出，确认 main 函数的机器指令确实只做了"把 42 放进返回值寄存器（x86-64 上是 eax），然后执行 retq"。

在 x86-64 Linux 上，llc 默认生成 ELF64 格式的目标文件，目标三元组（target triple）类似 x86_64-unknown-linux-gnu。在 ARM macOS 上则生成 Mach-O 格式，目标三元组为 aarch64-apple-darwin。Windows 使用 COFF 格式。但 LLVM IR 本身是平台无关的——同一份 .ll 文件可以通过不同的 -mtriple 参数编译到不同目标架构。这种前端与后端的解耦正是 LLVM 架构的核心价值：前端只需要生成一份 IR，后端负责适配具体硬件。

目标文件到可执行文件

cc -o hello hello.o

cc 调用系统链接器，把目标文件与 C 运行时启动代码（crt0、crti 等）链接成可执行文件。链接器做三件事：解析符号引用、合并段、确定最终地址。

这里有一个隐含的约定：系统的 C 运行时期望入口函数名为 main，返回类型为 int（在大多数平台上是 32 位）。我们的 main 返回 i64，在 x86-64 上 i64 和 long 都是 64 位，返回值通过 rax 寄存器传递，低 32 位会被 C 运行时当作 int 使用。对 return 42 来说，低 32 位就是 42，没有问题。但如果返回值超过 32 位范围，截断就会出现。这一点在后续的 ABI 篇会正式处理——源语言的 main() -> i64 会通过一个包装函数转换到宿主 C main 的返回约定。

链接完成后，hello 就是一个本机可执行文件。

运行并验证

./hello
echo $?

输出：

42

echo $? 打印的是上一个命令的退出码。Unix 进程的退出码来自 main 的返回值（或 exit() 的参数），范围是 0–255，因为 wait 系统调用只保留低 8 位。42 落在这个范围内，原样传递。

从字符串 return 42; 到屏幕上的数字 42，经过了词法分析、语法分析、IR 生成、机器码编译、链接、操作系统加载、CPU 执行、进程退出、Shell 取退出码这一连串步骤。编译器负责前半段，操作系统和硬件负责后半段。

搭建 Rust 项目

现在用 Rust 把上面的手动过程自动化。

cargo new sproutc
cd sproutc

项目结构的起点：

sproutc/
├── Cargo.toml
├── src/
│   ├── main.rs      # 入口：读文件、调各阶段、写 .ll、调 llc 和 cc
│   ├── lexer.rs     # 词法分析
│   ├── parser.rs    # 语法分析
│   └── codegen.rs   # 代码生成

四个文件，每个都极简。lexer.rs 导出 fn tokenize(source: &str) -> Vec<Token>。parser.rs 导出 fn parse(tokens: &[Token]) -> Program。codegen.rs 导出 fn emit_llvm_ir(program: &Program) -> String。main.rs 串联它们，再调用 llc 和 cc。

Token 类型用 Rust 枚举表达：

#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Span {
    pub start: usize,
    pub end: usize,
}

pub enum TokenKind {
    Fn,
    Ident(String),
    LParen,
    RParen,
    Arrow,
    LBrace,
    Return,
    Int(i64),
    Semi,
    RBrace,
}

pub struct Token {
    pub kind: TokenKind,
    pub span: Span,
}

注意这里没有 I64 关键字变体——i64 在词法阶段视为普通标识符 Ident("i64")，由后续的类型解析阶段识别。Span 记录每个 Token 在源文本中的字节偏移范围，下一篇会详细展开。

AST 节点同样用枚举和结构体：

struct Function {
    name: String,
    return_type: Type,
    body: Vec<Stmt>,
}

enum Stmt {
    Return(Expr),
}

enum Expr {
    IntLiteral(i64),
}

struct Program {
    functions: Vec<Function>,
}

代码生成只需要对 AST 做一次遍历，按格式拼出 LLVM IR 文本。当前只有一种函数、一种语句、一种表达式，遍历逻辑就是三层 match。

main.rs 的流程：

fn main() {
    let source = std::fs::read_to_string(&args[1]).unwrap();
    let tokens = lexer::tokenize(&source);
    let program = parser::parse(&tokens);
    let ir = codegen::emit_llvm_ir(&program);
    std::fs::write("output.ll", &ir).unwrap();
    // 调用 llc 和 cc
    Command::new("llc").args(["-filetype=obj", "-o", "output.o", "output.ll"]).status().unwrap();
    Command::new("cc").args(["-o", "output", "output.o"]).status().unwrap();
}

运行整个编译器：

cargo run -- program.spr
./output
echo $?
# 42

从源文件到可运行二进制，一条命令完成。

端到端流水线一览

program.spr          "fn main() -> i64 { return 42; }"
     │
     ▼
  Lexer              [FN, IDENT("main"), LPAREN, RPAREN, ARROW, IDENT("i64"),
                      LBRACE, RETURN, INT(42), SEMI, RBRACE]
     │
     ▼
  Parser             Program { Function { ReturnStmt(IntLiteral(42)) } }
     │
     ▼
  Codegen            "define i64 @main() { ret i64 42 }"
     │
     ▼
  llc                output.o  (ELF64 目标文件)
     │
     ▼
  cc (linker)        output    (本机可执行文件)
     │
     ▼
  OS + CPU           exit code = 42

这条流水线就是整个系列的骨架。词法分析、语法分析、代码生成三个模块各自独立，通过明确的数据结构（Token 列表、AST、IR 文本）串联。后续每篇文章的改动都定位在某一个或某几个模块里：加一种 Token，加一条文法规则，加一段 IR 生成逻辑。流水线本身不变。

退出码的秘密

Unix 退出码只有 8 位无符号整数的空间，即 0–255。如果 main 返回 256，echo $? 会显示 0——因为 256 % 256 == 0。返回 -1，显示 255——因为 -1 的低 8 位按无符号解释是 255。返回 257，显示 1。

这不是编译器的行为，而是操作系统和 Shell 的约定。wait 系统调用的返回状态只用低 8 位存放退出码，高位用于信号信息。所以退出码不适合传递任意计算结果，它只是一个状态标志。后续会引入 print_i64 运行时函数来输出完整的 64 位整数值。

这也解释了为什么大多数程序用 return 0 表示成功——0 是通用的"没有错误"退出码，Shell 脚本和构建工具依赖这个约定判断上一步是否成功。

练习

练习一：改返回值

把 return 42 改成 return 0，重新编译运行，确认 echo $? 输出 0。再改成 return 256，确认输出是 0（退出码取模 256）。改成 return 300，预测输出是多少，再验证。

练习二：手写不同的 LLVM IR

直接编辑 .ll 文件，把 ret i64 42 改成 ret i64 100，用 llc 和 cc 重新编译链接，验证退出码。再试一次 ret i64 -1，看退出码是不是 255。

这两个练习的目的是确认：编译器前端（lexer、parser、codegen）和后端（llc、cc）是独立的。前端的输出是文本 IR，后端不关心 IR 是怎么生成的。手写 IR 和编译器生成的 IR，对后端来说没有区别。

这个脚手架还缺什么

当前的编译器只接受一种输入：一个无参数函数，返回一个整数字面量。缺的东西太多了：

• 不能做算术运算（return 1 + 2 会被拒绝）
• 不能声明变量
• 不能调用函数
• 不能有条件分支或循环
• 错误信息只有 panic，没有源码位置
• 没有测试

但骨架已经立起来了。下一篇开始加东西——先加词法分析的完整实现和源码位置追踪，让错误信息能指回源码的具体行列。

上一篇：00 - 这门语言准备编译什么
下一篇：02 - 词法分析器：把文本切成 Token