跳到主要内容

TinyC

TinyC:一个极简的 C 编译器​

学编译原理最容易陷入的坑,是被龙书里成堆的形式化定义压得喘不过气,最后知道了什么是"LL(1)"和"活动记录",却还是不知道一个编译器到底怎么把 int a = 3 + 4 * 2; 变成 CPU 能执行的机器码。所以在这个系列的开头,我们先不谈理论,先亲手描述一门语言、走一遍完整流水线,把编译器的骨架搭起来。

通俗理解:编译器就像一条食品加工流水线,原料是源代码,成品是机器指令。中间要经过洗、切、腌、炒、装盘好几道工序。你可以直接把生食倒进锅里,也确实能做出勉强能吃的东西,但工序拆开之后每一步都可以独立优化、独立更换厨师。TinyC 就是我们用来练手的一小锅家常菜。

TinyC 是我们自定义的 C 语言极简子集,只保留刚够写出"有意思的程序"的最小语法。它不是一门真语言,也不打算兼容 C 标准,它的唯一作用是让这个系列的每一章都有一个可以动手实现的目标。

TinyC 是什么​

TinyC 支持的特性大致如下:

  • 只有一种基本类型:int
  • 变量声明与赋值:int x = 1;
  • 四则运算与括号:+ - * / ( )
  • 条件与循环:if / else / while
  • 函数定义与调用:int add(int a, int b) { return a + b; }
  • 一个内置函数:printf,只支持打印整数

一个能跑的 TinyC 程序看起来是这样:

int fact(int n) {
if (n <= 1) return 1;
return n * fact(n - 1);
}

int main() {
int i = 1;
while (i <= 5) {
printf(fact(i));
i = i + 1;
}
return 0;
}

麻雀虽小,五脏俱全。递归、循环、条件、算术表达式全都有,覆盖了编译器最核心的几类难点。后面每一章我们要做的事,就是把这样一段代码往下推一层,直到变成汇编。

编译器的完整流水线​

从源代码到目标代码,中间有若干个阶段,每个阶段处理一种特定形式的输入,产出一种更接近机器的输出:

源代码
└─ 词法分析(Lexer) → Token 流
└─ 语法分析(Parser)→ 抽象语法树 AST
└─ 语义分析 → 带类型标注的 AST + 符号表
└─ 中间代码生成 → 三地址码 IR
└─ 代码生成 → 目标汇编

通俗理解:词法分析把源代码从"一串字符"变成"一串单词";语法分析再把这些单词按语法组成"树";语义分析给这棵树补充"这个变量是什么类型、在哪定义"的信息;中间代码把树打平成一条条简单的三元操作;最后代码生成把这些操作翻译成目标 CPU 的汇编。

每一阶段的输入输出都是明确定义的数据结构,这让编译器天然可拆、可测、可替换。

一句代码走完整个流水线​

用最简单的一句 int a = 3 + 4 * 2; 走一遍,感受各个阶段的输出形态。

1. 词法分析:把字符流切成 Token

INT       "int"
IDENT "a"
ASSIGN "="
NUMBER 3
PLUS "+"
NUMBER 4
STAR "*"
NUMBER 2
SEMICOLON ";"

词法分析不关心语法,只关心"这个字符片段是关键字、标识符、运算符还是字面量"。

2. 语法分析:Token 流变 AST

VarDecl(type=int, name="a")
└─ init:
BinaryOp(+)
├─ left: Number(3)
└─ right: BinaryOp(*)
├─ left: Number(4)
└─ right: Number(2)

优先级问题在这里被解决——* 的子树在 + 的下面,天然表达了"先乘后加"。

3. 语义分析:类型检查和符号表

Parser 只保证代码"长得像 C",不保证"意义合理"。语义分析给每个节点标上类型,同时把 a 登记进符号表:

symbol_table: { a: int, scope=global, offset=0 }
BinaryOp(+ : int)
├─ Number(3 : int)
└─ BinaryOp(* : int) ...

如果这里写的是 int a = "hello" + 1;,就应该在这一步报错。

4. 中间代码:三地址码

复杂表达式被拆成一条条只做一件事的指令,每条指令最多三个操作数:

t1 = 4 * 2
t2 = 3 + t1
a = t2

中间代码的意义在于——它既不绑定源语言,也不绑定目标机器,是做优化(常量折叠、公共子表达式消除等)最方便的层次。

5. 目标代码:x86-64 汇编

    mov eax, 4
imul eax, 2 ; eax = 8
add eax, 3 ; eax = 11
mov [rbp-4], eax ; a = 11

从这里再往下,就是汇编器和链接器的事了。

为什么要拆这么多阶段​

一步到位当然可以,早期编译器确实这么写过。分阶段的好处在别的地方:

  • 关注点分离:写 parser 时不用操心汇编长什么样,改代码生成器时也不必回头改词法规则。
  • 可复用:GCC 有一套统一的中间表示 GIMPLE/RTL,前端支持 C、C++、Fortran,后端支持 x86、ARM、RISC-V。前后端组合是加法而不是乘法,跟我们讲过的桥接模式思路一致。
  • 可优化:大部分优化都发生在中间代码层,因为那里既没有源语言的语法糖,又不用考虑寄存器分配,是做变换最舒服的形态。
  • 可诊断:每一阶段都能独立打印中间结果,出问题时能精确定位是哪一环节错了。

后面的章节会讲什么​

有了 TinyC 这个靶子,系列后面的章节各自负责流水线的一段:

  • 词法分析:正则、DFA、如何用状态机把字符流切成 Token
  • 语法分析:上下文无关文法、LL 与 LR、如何递归下降地构造 AST
  • 语法制导翻译与语义分析:属性文法、类型系统、符号表的作用域管理
  • 中间代码生成:三地址码、控制流图、SSA 形式
  • 运行时环境:栈帧、活动记录、函数调用约定
  • 代码生成:指令选择、寄存器分配、栈布局
  • 优化:机器无关优化、指令级并行、循环变换

每一章都会围绕 TinyC 展开,能跑、能看输出。等把这条链走完,回头再看龙书里那些定义,就不再是符号游戏,而是"我知道它在解决什么问题"。

注意事项​

TinyC 是教学用的玩具,不是工程用的语言。它故意省掉了指针、结构体、预处理、多文件编译这些真实 C 的核心复杂度,就是为了让每一章的实现能压缩在几百行代码内。真要写一个能编 Linux 内核的 C 编译器,光是前端就得处理上千种 corner case。但那些复杂度都是在 TinyC 这样的骨架上一层层加出来的——先把骨架看清楚,再往上加肉才不会迷路。