Chapter 3. 编译原理

这一章，我们会退一步，从“写代码”这件事本身，回到一个更加基础的问题：

我们在编辑器里写下的一串串字符，究竟是怎样一步步变成 CPU 可以执行的指令的？

第 1 章中，我们从宏观角度说明了为什么编译器在今天依然重要；第 2 章中，我们带你熟悉了 MoonBit 与 MiniMoonBit 本身的语法与特性。本章则相当于一次“鸟瞰”：用一门最简单的函数作为线索，把一个现代编译器的大致流水线从头到尾走一遍。

后面的章节会对每一个阶段展开详细讨论（词法分析、语法分析、类型检查、中间代码、Machine IR、寄存器分配、RISC‑V 汇编……），本章的目标不是讲清所有细节，而是帮你建立一个完整而清晰的全局图景：当我们说“编译器在工作”时，它都在忙些什么。

编译器是什么

为什么我们在 VS Code 里点一下 Run，或者在终端中敲下一行：

moon run main

屏幕上就乖乖地打印出了结果？为什么我们只是输入了一些看起来只是“文本”的东西，冷冰冰的 CPU 芯片就开始运转了？

从物理世界的角度看，CPU 只认识非常简单的电信号模式：一条条机器指令（Machine Code），表达的都是“把哪个寄存器里的数字加到哪个寄存器上”“从内存某个位置读 8 个字节”“如果某个条件成立就跳转到那一行”等等。而从程序员的角度看，我们希望使用的是高层抽象：函数、结构体、泛型、闭包、模式匹配，乃至更高阶的“张量操作”“神经网络”“光线追踪”。

编译器就是这两者之间的翻译官。更准确一点说：

编译器（Compiler） ：把一种“源语言”（如 MiniMoonBit）的程序，翻译成另一种“目标形式”（如机器指令、LLVM IR、WebAssembly、C 代码等），同时在翻译过程中尽量发现错误、做优化。

在本书中，我们会实现一个完整的 MiniMoonBit 编译器：它的输入是 MiniMoonBit 源代码，输出既可以是 LLVM IR，也可以是我们自己设计的 CIR、Machine IR，最后再变成 RISC‑V 汇编。

编译器的大致工作流程

我们写的源代码，本质上就是一串字符串。编译器拿到这串字符串之后，并不会一次性“跳”到机器码，而是分阶段、一步一步地把它变成越来越接近硬件的表示。

下面我们用一个极小的例子来串起整个流程：

fn muladd(a: Int, b: Int, c: Int) -> Int {
  return a * b + c;
}

大多数现代编译器都会经历大致类似的阶段：

词法分析（Lexing / Tokenization）
语法分析（Parsing）
类型检查 / 语义分析（Type / Semantic Checking）
中间代码生成（IR Generation）及优化
Machine IR 与寄存器分配
汇编代码生成与后端处理

接下来，我们就以 muladd 这个函数为主角，依次看看每个阶段发生了什么。

词法分析：从字符到 Token

编译的第一个环节是词法分析。所谓词法分析，就是把源代码这串“字符流”，切分成一个个有意义的词法单元（Token） 。

你可以把它想象成对自然语言进行“分词”和“标注”：一句话 "我/ 喜欢/ 编译器"，在中文 NLP 里会被拆成若干词，并给出词性标记。在编译器里也是类似的，只不过“词性”是关键字、标识符、运算符、括号等。

对上面的 muladd 函数，如果我们只做最粗糙的切分，大致会得到：

"fn"  "muladd"  "(" "a"  ":"  "Int" "," "b" ":" "Int"
","  "c" ":"  "Int"  ")"  "->"  "Int"  "{"  "return"
"a" "*" "b"   "+"   "c"   ";"   "}"

更进一步，为了让后续分析更方便，我们通常会为每个 Token 标注上“种类”和必要的附加信息（例如源代码位置），于是会变成类似下面的形式：

(Keyword "fn")
(Identifier "muladd")
(Bracket '(')
(Identifier "a")
(Symbol ':')
(Identifier "Int")
(Symbol ',')
(Identifier "b")
(Symbol ':')
(Identifier "Int")
(Symbol ',')
(Identifier "c")
(Symbol ':')
(Identifier "Int")
(Bracket ')')
(Symbol "->")
(Identifier "Int")
(Bracket '{')
(Keyword "return")
(Identifier "a")
(Symbol "*")
(Identifier "b")
(Symbol "+")
(Identifier "c")
(Symbol ';')
(Bracket '}')

在一个工程级的编译器中，我们还会为每个 Token 记录它所在的行号、列号、文件名等，以便将来报错时能精确地指出：“第几行第几列这里有问题”。 MiniMoonBit 的实现中也会采用类似的做法，我们会在第 4 章（词法分析）中详细展开这一部分的设计与实现。

语法分析：从 Token 到语法树

当我们得到了按种类标好记号的 Token 序列之后，下一步要做的是语法分析：把“扁平的序列”按照语言的语法规则，组合成有层次结构的 抽象语法树（AST, Abstract Syntax Tree） 。

直觉上，你可以把这一步理解成“给一句话画出语法树”：

谁是主语，谁是谓语，谁修饰谁；
哪一段是一整个从句，哪一部分是嵌套在里面的小句子。

对于我们的 muladd 函数来说，语法分析要完成的事情大致包括：

把最外层识别为一个 函数定义（Function Definition） ：
- 函数名：muladd
- 参数列表：三个参数，每个参数包含“参数名 + 参数类型”
  - a: Int
  - b: Int
  - c: Int
- 返回类型：Int
函数体（{ ... } 中的部分）被识别为一个 语句块（Block） ：
- 里面有一条 return 语句
  - 这条 return 语句里包含一个 表达式（Expression） ：a * b + c
表达式 a * b + c 又会被进一步分解：
- 这是一个以 + 为根的 二元表达式：
  - 左边是另一个二元表达式：a * b
  - 右边是一个变量引用：c

把这些结构用树形方式画出来，大致是这样的：

function definition: muladd
├─ params:
│  ├─ a: Int
│  ├─ b: Int
│  └─ c: Int
├─ return type: Int
└─ block
   └─ return statement
      └─ binary expr: +
         ├─ binary expr: *
         │  ├─ variable a
         │  └─ variable b
         └─ variable c

在一个真实的编译器实现中，我们不会真的“字符串化”一棵树，而是会用结构体和枚举（ADT）来表示这些节点。例如：

函数定义节点会记录：
- 名称、参数列表、返回类型、函数体语句块；
语句块节点会记录：
- 若干条语句的列表；
表达式节点则可能是：
- 变量引用、字面量、二元运算、函数调用等不同的形态。

在第 5 章中，我们会从 MiniMoonBit 的文法规则出发，一步步构造出语法分析器，并在 MoonBit 里用代数数据类型清晰地表示 AST 结构。

类型检查：让程序“有类型地”站稳脚跟

当我们有了 AST 之后，下一步就是让这棵树“长肉长骨”：检查它是否合理，并为其中的每一个表达式节点标注上精确的类型信息。

在不同的语言和教材中，这一阶段的名称会略有差异：

对于像 C、C++ 这类历史悠久、语义规则复杂的语言，人们常常说它做的是 语义分析（Semantic Analysis） ；
对于类型系统比较严格而现代的语言（比如 MiniMoonBit），我们往往更关注 类型系统本身是否一致，因此更喜欢称之为 类型检查（Type Checking） 。

无论名字如何，这一阶段的两个核心目标都非常相似：

发现并报告不合法的程序结构，给出清晰的错误信息；
为每个表达式节点推断或检查出一个类型，并把这些类型信息写入树中，得到一棵“带类型标记的语法树”（Typed AST）。

常见的检查包括（但远远不限于）：

是否使用了未定义的标识符 例如，在没有声明变量 a 的情况下使用表达式 a + 1，编译器必须指出错误，并标明这个 a 来自哪里。
是否出现了重名的标识符 比如函数参数重名，或者参数名与函数名重名等。像 fn add(add: Int) -> Int 这样的声明，就可能让人困惑，编译器通常会拒绝它。
二元运算两侧的类型是否匹配 在许多静态类型严格的语言中，加减乘除、位运算、比较运算等的两侧操作数类型必须一致，或者至少要能在清晰的规则下进行转换。在 Rust 中，如果 a: i32 而 b: f64，那么 a + b 就是不被允许的，因为两个类型属于完全不同的数值体系。
函数的返回类型是否与声明一致 假设函数标注的返回类型是 Int，却出现了 return 1.0 这样的语句，很多语言会认为这是错误，要求你要么修改返回类型，要么修改返回值。

当这些检查完成之后，我们就得到了一棵“类型都标注清楚”的语法树。对于前面的 muladd，可以把大致的结构想象成下面这样：

function definition: muladd
├─ params:
│  ├─ a: Int
│  ├─ b: Int
│  └─ c: Int
├─ return: Int
└─ block (type: Any)
   └─ return statement
      └─ binary expr: + (type: Int)
         ├─ binary expr: * (type: Int)
         │  ├─ variable a (type: Int)
         │  └─ variable b (type: Int)
         └─ variable c (type: Int)

与最初的 AST 相比，最大的变化在于：每一个表达式节点现在都“带着一个类型” 。这些类型信息并不会直接出现在源代码中，但它们会在后续的优化和代码生成阶段发挥重要作用。

你可能已经开始好奇：

“这些类型是怎么推出来的？”
“如果有泛型、trait 约束、闭包捕获等复杂特性，又该怎么办？”
“这些 Typed AST 在代码里具体长什么样？”

这些问题，我们会在第 6 章“类型检查与解糖”中集中回答。本章你只需要记住：类型检查阶段就是让语法树变得‘有类型’且自洽的一步。

另外，在这一阶段我们还会做一件重要的事：语法解糖（Desugaring） 。为了让语言更易用，设计者往往会引入各种语法糖（例如 for 循环的高级写法、某些模式匹配的简化形式等），而编译器在更后面的阶段只需要理解一套更小、更“核心”的语法。解糖就是把“甜甜的高级写法”系统地还原成“比较原始但规则简单”的形式的过程。MiniMoonBit 中的一些解糖步骤也会在第 6 章中介绍。

中间代码生成：从树到“线性”的 IR

完成类型检查之后，我们手中已经有了一棵结构清晰、类型完备的语法树。但从编译器工程的角度看，树状结构适合分析，不太适合做复杂的变换和优化。

因此，大多数编译器都会引入一个或多个层次的 中间表示（Intermediate Representation，简称 IR） 。 IR 的设计是编译器实现中的“核心艺术之一”：它既要足够接近源语言，便于保持语义不变；又要足够接近目标机器，便于做优化和生成高效代码。

在编译理论和工业实践中，人们提出过很多著名的 IR 形式，例如：

ANF（A‑normal Form）
CPS（Continuation‑Passing Style）
SSA（Static Single Assignment）
各种三地址码（Three‑Address Code）

本书不会试图把所有 IR 形式讲全，而是会重点关注与 MiniMoonBit 关系最紧密的几种。感兴趣的读者可以参考下面一些经典资料继续深入：

Andrew W. Appel, Modern Compiler Implementation in ML/Java/C
Andrew W. Appel & Jens Palsberg, Modern Compiler Implementation in Java (2nd Edition)
Steven Muchnick, Advanced Compiler Design and Implementation
中译本《编译原理：技术与工具》（俗称“龙书”）

在本书中，我们会依次使用几种不同层次的 IR：

针对 MiniMoonBit 的 K 正规形式（KNF） ；
工业级的 LLVM IR；
我们为教学目的专门设计的、类似 C 的 CIR；
更接近机器、但仍与具体架构解耦的 Machine IR。

下面我们先从最贴近 MiniMoonBit 源语言的 KNF 说起。

KNF：拆解复合表达式

KNF（K Normal Form）可以粗略理解为：把复杂的复合表达式拆成若干串行的简单赋值语句，让每一步都只做一件很小的事。

还是用我们的 muladd 例子。原始的源代码是：

fn muladd(a: Int, b: Int, c: Int) -> Int {
  return a * b + c;
}

在 KNF 形式下，它会被转换为：

fn muladd(a: Int, b: Int, c: Int) -> Int {
  let tmp$1: Int = a * b;
  let tmp$2: Int = tmp$1 + c;
  return tmp$2;
}

可以看到，原本的复合表达式 return a * b + c 被拆成了三条顺序执行的语句：

let tmp$1: Int = a * b;
let tmp$2: Int = tmp$1 + c;
return tmp$2;

这样做有许多好处：

每一行都只包含一次运算，便于做公共子表达式消除、常量折叠等优化；
控制流结构（条件、循环）也可以被规整到相对统一的形态，方便后面映射到更底层的 IR。

不过，仅仅有 KNF 还不足以直接生成底层汇编。它主要解决的是“表达式太复杂”的问题，而一些高层特性——尤其是函数式语言里的闭包（closure） 、高阶函数、泛型等——在 KNF 层面仍然会以较高层的形式存在。

例如闭包：

fn make_adder(x: Int) -> (Int) -> Int {
  fn adder(y) {
    x + y
  }
  adder
}

经过 KNF 变换后，看上去几乎没有变化（除了类型标注等细节）：

fn make_adder(x: Int) -> (Int) -> Int {
  fn adder(y: Int) -> Int {
    x + y
  }
  adder
}

内部函数 adder 仍然捕获了外部的变量 x，从低层机器的角度看，它还是太“高级”了。如何把闭包这样的结构“摊平”为普通的结构体和函数指针，就是闭包转换要解决的问题，这部分会在第 7 章 K 正规形式以及后续章节中详细说明。

问：既然 KNF 看起来就像是一门“简化版的语言”，能不能直接把 KNF 打印成 JavaScript 或 Python 呢？

答：实际上这是完全可行的，而且很多语言的某些后端就是这么做的。只要目标语言本身支持闭包和高阶函数，你就可以把 KNF 打印成那门语言的代码，让它来承担后端角色。例如，输出到 JavaScript 或 Python 通常就比较顺畅。但如果你想在 KNF 阶段直接输出 C 代码，就会遇到麻烦：标准 C 语言不支持嵌套函数，更谈不上闭包，因此还需要额外的转换步骤才能表示捕获环境。

LLVM IR：工业界的通用“汇合点”

LLVM IR 是当今最流行的编译基础设施之一的核心中间表示。无数语言（包括 Rust、Swift、Kotlin/Native，乃至各种 DSL）都选择 LLVM 作为后端，把自己的 IR 翻译成 LLVM IR，再利用 LLVM 提供的优化和多平台代码生成能力。

MoonBit 也提供了对 LLVM 的绑定，项目名称为 llvm.mbt（仓库地址为 https://github.com/moonbitlang/llvm.mbt）。借助这个库，我们可以把 KNF 形式进一步转换成 LLVM IR，让 MiniMoonBit 也能“搭上工业级后端的快车”。

对于前面展示的 muladd 函数，一种可能的 LLVM IR 形式大致如下：

define i32 @muladd(i32 %0, i32 %1, i32 %2) {
entry:
  %3 = mul i32 %0, %1
  %4 = add i32 %3, %2
  ret i32 %4
}

乍一看，它和我们刚才的 KNF 很像：也是一步步做乘法、加法、返回。然而，LLVM IR 背后还有一整套非常强大的：

控制流图（CFG）结构；
静态单赋值形式（SSA）；
丰富的优化 Pass；
针对多种 CPU/GPU/加速器的后端。

对我们来说，使用 LLVM IR 带来的最大收益在于：

可以在不自己实现所有底层优化和指令选择的情况下，获得相当不错的性能；
还能通过 LLVM 的工具链（如 opt, llc 等）进行分析、验证和可视化。

真正有趣的部分，其实不在像 muladd 这样的简单函数，而是在于闭包的转换。还以 make_adder 为例，闭包大致会被拆成：

一个表示“闭包实例”的结构体，里面包含：
- 一个函数指针（指向真正的代码）；
- 若干个捕获的变量（如外层的 x）。
一个真正执行加法的函数 make_adder$adder，它的第一个参数是“闭包结构体的指针”，通过它来访问捕获的变量。

对应的 LLVM IR 可能类似这样（这里展示的是简化版，为了突出结构而非 LLVM 的全部语法细节）：

define ptr @make_adder(i32 %0) {
entry:
  %1 = call ptr @moonbit_malloc(i32 16)
  %2 = getelementptr { ptr, i32 }, ptr %1, i32 0, i32 0
  store ptr @make_adder$adder, ptr %2, align 8
  %4 = getelementptr { ptr, i32 }, ptr %1, i32 0, i32 1
  store i32 %0, ptr %4, align 4
  ret ptr %1
}

define i32 @make_adder$adder(ptr %0, i32 %1) {
entry:
  %2 = getelementptr { ptr, i32 }, ptr %0, i32 0, i32 1
  %3 = load i32, ptr %2, align 4
  %4 = add i32 %3, %1
  ret i32 %4
}

如果你第一次接触 LLVM IR，可能会觉得有点抽象、不太好读。没关系，我们会在第 8 章专门用一整章时间讲解 LLVM IR 的设计思想、基本语法，以及如何从 MiniMoonBit 的 KNF 生成类似的 IR。

CIR：一层接近 C 语言的中间表示

很多教材在讲完 LLVM IR 之后就会停下来：毕竟，有了 LLVM 这样强大的后端，理论上我们已经可以生成各种平台的高效机器码了。

本书会再向前迈一步：我们会抛开 LLVM IR ，自己实现一个 C 风格的IR，我们称之为 CIR。。

为什么还需要 CIR 呢？主要有两点考虑：

一方面，C 语言是很多读者最熟悉的“系统级语言”之一，用接近 C 的表示形式来理解闭包转换、栈帧布局，会比直接阅读 LLVM IR 更直观；
另一方面，只要你能从 CIR 输出“真正的 C 代码”，理论上就可以利用任何一个成熟的 C 编译器（gcc/clang/MSVC/tcc 等）作为你的后端——甚至可以进一步尝试输出 Go、Java 等其它语言。

和 LLVM IR 一样，我们在 CIR 中也需要对 KNF 做闭包转换。对于简单的 muladd，CIR 形式看起来就很直观：

int muladd(int a, int b, int c) {
  int tmp$1 = a * b;
  int tmp$2 = tmp$1 + c;
  return tmp$2;
}

而对于 make_adder，我们需要显式地表示“闭包结构体”和“函数指针”。一种可能的 CIR／C 近似形式是：

// 闭包结构体：第一个字段是函数指针，第二个字段是捕获的 x
struct make_adder_closure {
  int (*fn)(struct make_adder_closure *env, int y);
  int x;
};

// 构造闭包：在堆上分配结构体，填好函数指针和捕获的变量
struct make_adder_closure *make_adder(int x) {
  struct make_adder_closure *env =
      (struct make_adder_closure *)malloc(sizeof(struct make_adder_closure));
  env->fn = &make_adder$adder;
  env->x = x;
  return env;
}

// 闭包主体：第一个参数是环境指针，第二个参数是调用时传入的 y
int make_adder$adder(struct make_adder_closure *env, int y) {
  int captured = env->x;
  int result = captured + y;
  return result;
}

这里的关键思想非常类似于我们在 LLVM IR 段落中看到的结构：

把“闭包”表示为一个结构体指针；
结构体中既保存代码地址（函数指针），也保存捕获的变量；
真正执行的函数（make_adder$adder）总是以“环境指针 + 正常参数”的形式被调用。

在第 9 章中，我们会正式定义 CIR 的语法和语义，并展示如何从 KNF + 闭包转换的结果生成这样的 C 风格代码。

Machine IR：引入寄存器与栈的抽象机器

到了 CIR 这一层，我们其实已经可以“借用”现有的 C 编译器完成剩下的工作了：直接把 CIR 打印成 C 源码，然后交给 gcc／clang 等工具链去生成最终的二进制。

不过，为了更好地理解底层机器的工作方式，并为后续实现自有后端打下基础，本书还会再下沉一层，引入一种架构无关的机器级 IR——我们称之为 Machine IR。

从这一层开始，我们就需要正面面对那些平时被高级语言“藏起来”的细节了：

寄存器（Register）
栈（Stack）
调用约定（Calling Convention）
函数调用与返回时的寄存器保存／恢复

问：Machine IR 真的是“与底层架构无关”的吗？

答：更准确地说，Machine IR 的设计尽量与具体指令集架构解耦，但在实际运行时，它仍然需要根据目标架构（如 RISC‑V、AArch64、x86‑64 等）的约束进行配置和变换。比如可用的寄存器数量、哪些寄存器必须在调用前后保存、哪些指令可用等等，都会通过配置或描述文件，影响到 Machine IR 的转换过程中。

在这一章里，我们最重要的两个主题是：

Machine IR 的设计：如何抽象寄存器、栈、基本块与指令；
寄存器分配（Register Allocation） ：在寄存器数量有限的前提下，如何尽量少地把值“溢出”到栈上。

寄存器分配本身是一门很大的学问，经典方法包括：

简单高效的线性扫描算法；
基于图着色的、适合全局优化的寄存器分配算法。

仍然以 muladd 为例，经过 Machine IR 转换以及寄存器分配之后，它可能会被表示成类似下面这样的伪代码：

fn muladd(a0, a1, a2) {
  mul.i32 a0, a0, a1
  add.i32 a0, a0, a2
  ret
}

这里的 a0, a1, a2 已经不再是抽象的变量名，而是与具体寄存器编号紧密相关的“逻辑寄存器” 。在面向 RISC‑V 的实现中，它们就会直接映射到 a0, a1, a2 这三个参数寄存器。

我们会在第 10 章和第 11 章详细讨论 Machine IR 和寄存器分配的实现细节。

汇编转换：走到 RISC‑V 的那一步

最后一步，就是把 Machine IR 转换成具体架构的汇编代码。在本书中，我们主要以 RISC‑V 为例来展示这个过程。

选择 RISC‑V 有两个主要原因：

它是一套开源指令集架构（ISA） ，任何人都可以实现和扩展；
与 x86‑64 等历史包袱较重的指令集相比，RISC‑V 的设计更加简洁规整，非常适合作为教学示例。

RISC‑V

RISC‑V 起源于加州大学伯克利分校，是一套基于 RISC（精简指令集计算机）理念设计的开源 ISA。它的核心思想包括：

指令编码规则统一、格式简洁；
把复杂功能拆解为少量简单指令的组合；
通过标准扩展（如整数乘除、原子操作、浮点、向量扩展等）来覆盖不同应用场景；
任何厂商都可以在遵循基本规范的前提下，增加自己的自定义扩展指令。

这使得 RISC‑V 在教学、研究、工业界都非常受欢迎，也非常适合作为我们这本书的目标架构。

仍然以 muladd 为例，最终得到的 RISC‑V 汇编大致如下：

.global muladd
muladd:
    mulw a0, a0, a1
    addw a0, a0, a2
    ret

这里：

a0, a1, a2 是 RISC‑V 64 位架构下约定用作函数参数和返回值的寄存器；
mulw 表示对 32 位整数进行乘法运算；
addw 表示对 32 位整数进行加法运算；
ret 则是“从当前函数返回”的汇编指令。

如果你愿意更进一步，可以继续学习汇编器（Assembler）和链接器（Linker） 的工作原理：汇编器如何把这些文本形式的指令翻译成二进制机器码，链接器又是如何把多个目标文件拼接成一个可执行文件的。不过，这些内容已经明显超出了本书的重点——我们的关注点主要在“从 Token 到各层 IR 再到汇编”的编译器前端与中端设计，因此不会在这里展开。

小结：从这一章到后面的章节

在这一章中，我们用一个简短的 muladd 函数为主线，快速走了一遍一个现代编译器的大致流水线：

从字符到 Token：词法分析；
从 Token 到 AST：语法分析；
让 AST 变得“有类型”：类型检查与解糖；
把树状结构变成更适合优化和变换的 中间表示（KNF、LLVM IR、CIR、Machine IR） ；
最终再落地到具体的 RISC‑V 汇编指令。

在接下来的章节里，我们会“放慢脚步”，逐一深入这些阶段的内部细节和代码实现方式。希望当你回过头来再看这一章时，它会成为你理解整个编译器工程的“导航图”——无论你是在调试词法分析器的一个小 Bug，还是在实验新的寄存器分配算法，都能清楚地知道：自己当前站在哪一层，又要把程序往哪一层推近一步。