用4个函数528行代码写了个能自举的C编译器！
 - 原点技术的文章 - 知乎
https://zhuanlan.zhihu.com/p/672720180

今天的主角，是一个C语言编译器 – C4(GitHub Fork: 1.4K, Star: 8.6K)。

C4：4个函数实现的C语言编译器

C4, C in four functions。

它是一个C语言编译器项目(地址在文末)，整个实现只有：

• 一个C语言源码文件
• 528行C语言代码
• 4个函数

仅此而已。

它简洁，却不简单。

它具备简单完整的词法分析、语法分析、语义检查、代码生成、运行时环境(即虚拟机)。

与常见的C编译器不同的是，它把C语言源程序编译成字节码(bytecode)，然后在一个精简的虚拟机中执行。

你以为这就完了？No！它令人称道之处远不止如此！

C4：可以自举的C语言编译器

若只是精简，或许它还并不那么令人惊奇，毕竟网上有很多类似的编译器项目，其中不乏一些非常简单优雅，且非常出色的项目。

然而，C4最惊艳的地方在于，虽然只有五百多行代码，它却实现了自举。

所谓自举，简单来说，就是自己编译自己，这通常是用来衡量一个编译器功能是否完备的标准之一。

下面，我们演示一下“Hello, World!”的例子，和C4自举的例子。

Hello, World示例

先用GCC把C4编译成可执行文件：

gcc c4.c -o c4

编译并运行测试程序hello.c：

结果如图：

其中，”hello, world”是hello.c执行时打印的，”exit(0) cycle = 9″是c4编译器打印的，其中”exit(0)”表示程序执行正常，”cycle = 9″表示c4编译hello.c后，共生成9条字节码。

C4自举示例

我们用GCC编译c4.c生成可执行文件c4，我们称之为编译器A，然后用A来编译执行c4的源码c4.c，生成一个编译器B，然后再用B来编译执行hello.c。

./c4 c4.c hello.c

结果如图：

还可以这样：

./c4 c4.c c4.c hello.c

GCC编译生成的c4是编译器A，”./c4 c4.c”生成编译器B，”./c4 c4.c c4.c”生成编译器C，最后用编译器C来编译运行hello.c。

继续：

理论上可以一直递归下去。不过，从图中可以看出，递归的层次越深，生成的字节码越多，执行所需的时间也越多。

C4实现的C语言子集

C4致力于用最少的代码，实现一个可以自举的C编译器。它仅由528行代码，4个函数组成。可想而知，它不可能完整的实现C语言标准定义的所有特性，它只实现了自举所需的C语言最小子集。

数据类型

• char
• int
• 指针
• 枚举（enum）
• 数组
• 字符串

不支持struct、typedef、union等数据类型。

语句结构

• if-else控制语句
• while循环语句
• return语句
• 函数

不支持do-while、switch-case、for、continue、break、goto等语句结构。

运算符

它支持除+=、%=、<<=、&=等符合运算符之外的几乎所有运算符。包括：

• 算术运算符
• 关系运算符
• 逻辑运算符
• 位运算符
• 赋值运算符
• 杂项运算符（如三元运算符?:）

内建库函数

C4编译器实现时用到了一些系统库函数，因此，为了实现自举，它也内建支持了几个库函数。包括：open、read、close、printf、malloc、free、memset、memcmp、exit

需要注意的是，它不支持以#开头的预处理命令，如#include、#define、#if等。

代码注释只支持”//”开头的单行注释，不支持”/* */”标记的多行注释形式。

与传统的C语言编译器相比，C4在实现上有其独到之处。

下面，先简单介绍一下传统编译器的实现过程。

典型编译器的实现

典型的编译器的实现，一般都会有下面几个步骤：

• 词法分析
• 语法分析
• 语义分析
• 中间代码生成
• 代码优化
• 机器代码生成

如GCC、Clang、Go等均是如此。

每个阶段，会对代码进行一次或多次扫描。这里的”代码”，包括文本形式的源代码、语法树、中间代码等表示形式。

典型的实现中，词法分析和语法分析通常会糅合在一起(当然也可以分开)，在语法分析时，调用词法分析器逐个取得token。因此，理论上讲，词法分析和语法分析阶段，只需要对源码扫描一遍即可(当然也有例外)，并生成语法树，或抽象语法树AST(Abstract Syntax Tree)。

语义分析阶段，操作的主要对象就是这棵树，至少要对这棵树扫描一遍。有些实现中，在进行语义检查的同时也会直接生成中间代码。

代码优化阶段，根据编译器优化的力度的不同，可能会对中间代码进行多次扫描。

这里所谓的“扫描一遍”，在编译器术语中一般称为pass。对LLVM有了解的小伙伴应该知道，LLVM中每一种类型的优化都是一个pass，要应用多种优化技术，就需要有多个pass。

C4的独具特色之处

作为追求极简主义的C4编译器来说，它在实现上有很多独具特色之处。

把C编译为字节码，虚拟机中执行

传统的C语言编译器，最终都把C语言源码编译成可执行文件(如ELF，PE等)，也就是二进制的机器码。

而C4则是把C语言源码先编译成其专门设计的字节码(bytecode)，然后直接在虚拟机中执行，类似Java，Lua等。

C4设计了39个字节码指令，大部分与汇编指令类似，主要是内存访问指令，算术运算指令等。其中，为支持内建的库函数，还专门设计了9条特殊的库函数调用指令。

它的虚拟机是典型的栈式虚拟机（早期的Lua也是栈式虚拟机，但最新的Lua 5.x采用寄存器虚拟机），其实现也是非常精简。

此外，还支持简单的调试功能，比如可以使用-d命令，把生成的字节码dump出来。下图是hello.c的字节码：

对源码只扫描一遍

与传统的编译器实现不同，C4把词法分析、语法分析、语义分析、代码生成这几个步骤巧妙的结合在一起，在把C语言源码编译成字节码的整个过程中，只扫描了一遍源码。

Lua的解释器也是采用对源码扫描一遍的方式，因此，C4和Lua的性能都相当不错。

C4源码的可读性

当年C4发布时，在外网一些知名社区引起不小的轰动，引发了诸多讨论。对于C4的实现，有人认为C4的实现非常简洁、易读，也有人认为C4的实现稍显晦涩。

我个人观点，C4的实现确实非常简洁，毕竟只有4个函数，500多行代码。但是要想真正完全理解，需要有一定的编译原理基础知识，这也是理解C4唯一的门槛。

比如C4的语法分析过程，就是典型的递归下降和算符优先算法相结合的实现方式。只要了解这些编译器的经典算法原理，C4的实现逻辑理解起来，还是比较轻松的。

此外，C4为了追求以最少的代码实现自举，在实现上采用了一些技巧，对代码的可读性有一定影响。

比如，我们前面提到，C4不支持struct类型。这也意味着C4的源码中不能使用struct类型。为此，它选择使用数组来模拟struct结构。这样乍看起来，可能会产生一些困惑。

个人认为，C4的一个槽点，就是它变量的命名上，过于简洁。比如标记字节码的位置的变量用”e”表示，其实如果用”emit”的话，或许会清晰许多，也会更容易理解。

除了C4的原生实现外，网上各路大神也开发了很多基于C4的衍生实现。比如有人给C4额外增加了80多行代码，却让C4支持了JIT，执行速度大大提升，在我机器上验证，执行速度提高了27倍！也有人对C4做了简单扩展，使得它可以直接产生真实的机器码，并最终生成ELF可执行文件。

小结

现代的编译器项目，如GCC和Clang/LLVM，实现逻辑非常复杂，代码规模巨大，一个人几乎不可能完全搞清楚。即便是网上备受推崇的精简实现TCC和LCC，它们的实现也相对比较复杂的，对于新手来说，也很难彻底研究清楚。

个人认为，C4是非常适合新手研究的编译器项目之一，毕竟只有四个函数，500多行源码，且里面没有特别复杂难懂的算法。当然了，研究之前，最好具备一些编译器的基础知识，那样理解起来就会比较容易了。

C4虽然精简，但要完全讲清楚，也不是一篇文章能够做到的。因此，本文只对C4简单介绍，并没有对C4的具体实现做过多探讨。感兴趣的朋友可以到github上面找到它，仔细研究一下。

C4的项目地址

https://github.com/rswier/c4

---

2023年12月19日