用 Python 编写一个 C 编译器的 500 行挑战

tokens 被词法分析，然后解析器运行它们并构建相当小的语法树：

这里重要的是有两遍编译 （two-passes）：首先解析构建语法树，然后第二遍通过该树并将其转换为机器代码。

这对于大多数编译器来说确实很有用！它将解析和代码生成分开，因此每个都可以独立发展。这还意味着你可以在使用语法树生成代码之前对其进行转换，例如，通过对其应用优化。事实上，大多数编译器在语法树和代码生成之间都有多个级别的“IR”（中间表示，Intermediate Representation）！

这真的很棒，很好的工程、最佳实践、专家推荐等等。但是……它需要太多代码，所以在这里我做不到。

因此，我选择了挑战单程编译器：代码生成在解析期间发生。我们解析一点，发出一些代码，再解析一点，发出更多代码。例如，下面是来自 c500 编译器的一些实际代码，用于解析前缀 ~ op：

请注意，没有语法树，没有 PrefixNegateOp 节点。我们看到一些token，立即吐出相应的指令。

你可能已经注意到这些指令是基于 WebAssembly 的，这将引导我们进入下一部分......

出于某种原因使用 WebAssembly？

我决定让编译器以 WebAssembly 为目标。老实说，我不知道为什么要这么做，这并没有让事情变得更容易——我想我只是好奇？

WebAssembly 是一个非常奇怪的目标，尤其是对于 C 语言。一些外部问题让我感到很困惑，例如在我意识到 WebAssembly v2 与 WebAssembly v1 之间非常不同，除此之外，指令集本身也很奇怪。

其一，没有 goto。相反，它有块（结构化汇编，想象一下！）和跳转到特定嵌套级别块的开头或结尾的“中断”指令。这对于 if 和 while 来说基本上是无关紧要的，但是对于极端诅咒来说，它的实现是非常糟糕的，我们稍后会讨论。

此外，WebAssembly 没有寄存器，它有一个堆栈，并且是一个堆栈结构机器。起初你可能会觉得这很棒，对吧？C需要一个堆栈！我们可以使用 WebAssembly 堆栈作为我们的 C 堆栈！但是不可以，因为你无法引用 WebAssembly 堆栈。因此，我们无论如何都需要维护自己的内存堆栈，然后将其移入和移出 WASM 参数堆栈。

所以最后，我认为我最终得到的代码比针对 x86 或 ARM 等更普通的 ISA 所需的代码稍多。但这很有趣！理论上，你可以在浏览器中运行用 c500 编译的代码，尽管我没有尝试过（我只是使用 wasmer CLI）。

处理错误

要说 Bug，其实基本上没有。有一个函数 die（），当发生任何奇怪的事情时就会调用它并转储编译器堆栈跟踪 - 如果幸运的话，会得到一个行号和一条有点模糊的错误消息。

该舍弃什么？

最后，我必须决定不支持哪些内容，因为将所有 C 语言放入 500 行是不可行的。我决定想要一个真正像样的功能样本，以测试一般实现方法的能力。例如，如果我跳过了指针，我就可以通过 WASM 参数堆栈并摆脱很多复杂性，但这感觉就像作弊。

我最终实现了以下功能：

• 算术运算和二元运算符，具有适当的优先级

• int、short 和 char 类型

• 字符串常量（带转义）

• 指针（无论多少层），包括正确的指针算术（递增 int* 加 4）

• 数组（仅单级，不是 int[][]）

• 功能

• typedefs（以及词法分析器 hack！）

值得注意的是，它不支持：

• 结构，可以使用更多代码，基础知识就在那里，我只是无法将其压缩

• 枚举（enum）/联合（union）

• 预处理器指令（这本身可能有 500 行......）

• 浮点。也有可能，wasm_type的东西在里面，又无法将其挤进去

• 8 字节类型（long/long long 或 double）

• 其他一些小事情，例如就地初始化，这些都不太合适

• 任何类型的标准库或 i/o 不从 main() 返回整数

• Casting 表达式

编译器通过了 c-testsuite 中的 34/220 个测试用例。对我来说更重要的是，它可以成功编译并运行以下程序。

好了，决定都做完了，让我们来看看代码吧！

Helper 类型

编译器使用一小部分辅助类型和类。它们都不是特别奇怪，所以我会快速地略过它们。

Emitter 类

这是一个单程帮助器，用于发出格式良好的 WebAssembly 代码。

WebAssembly，至少文本格式，被格式化为 s 表达式，但单个指令不需要加括号：

Emitter 只是帮助发出具有良好缩进的代码，以便更容易阅读。它还有一个 no_emit 方法，稍后将用于丑陋的黑客攻击 - 请继续关注！

StringPool 类

StringPool 类用于保存所有字符串常量，以便将它们排列在连续的内存区域中，并将地址分配给代码生成器使用。当你在 c500 中写 char *s = "abc" 时，真正发生的是：

• StringPool 附加一个空终止符

• StringPool 检查是否已经存储了“abc”，如果是，则将地址返回

• 否则，StringPool 将其与基地址 + 到目前为止存储的总字节长度一起添加到字典中 - 这个新字符串在池中的地址

• StringPool 手回地址

• 当所有代码完成编译后，我们使用 StringPool 生成的巨大串联字符串创建一个 rodata 部分，存储在字符串池基地址处（追溯性地使 StringPool 分发的所有地址都有效）

Lexer 类

Lexer 类很复杂，因为词法 C 很复杂 ((\([\abfnrtv'"?]|[0-7]{1,3}|x[A-Fa-f0-9]{1,2 })) 是该代码中用于字符转义的真正正则表达式），但概念上很简单：词法分析器继续识别当前位置的token是什么。调用者不仅可以查看该 token，也可以使用 next 告诉词法分析器前进，“消耗”该 token。它还可以使用 try_next 仅当下一个 token 是某种类型时有条件地前进 - 基本上，try_next 是 if self.peek().kind == token: return self.next( ）。

由于所谓的“Lexer Hack （词法分析器黑客）”，还有一些额外的复杂性。本质上，在解析 C 时，你想知道某个东西是类型名称还是变量名称（因为上下文对于编译某些表达式很重要），但它们之间没有语法区别：int int_t = 0; 是完全有效的 C，typedef int int_t 也是如此；int_t x = 0;。

要知道任意标记 int_t 是类型名称还是变量名称，我们需要将类型信息从解析/代码生成阶段反馈回词法分析器。对于想要保持其词法分析器、解析器和代码生成模块纯净且独立的常规编译器来说，这是一个巨大的痛苦，但实际上对我们来说并不难！

当我们到达 typedef 部分时，我会详细解释它，但基本上我们只是在词法分析器中保留 types: set[str] ，并且在词法分析时，在给它一个标记类型之前检查一个标记是否在该集合中：

CType 类

这只是一个用于表示有关 C 类型的信息的数据类，就像在 int **t 或短 t[5] 或 char **t[17] 中编写的那样，减去 t。

它包含了：

• 类型的名称（已解析的任何类型定义），例如 int 或 Short

• 指针的级别是（0 = 不是指针，1 = int *t，2 = int **t，依此类推）

• 数组大小是多少（None = 不是数组，0 = int t[0]，1 = int t[1]，依此类推）

值得注意的是，如前所述，该类型仅支持单级数组，而不支持像 int t[5][6] 这样的嵌套数组。

FrameVar 和 StackFrame 类

这些类处理我们的 C 堆栈帧。

正如我之前提到的，因为你无法引用 WASM 堆栈，所以我们必须手动处理 C 堆栈，我们不能使用 WASM 堆栈。

为了设置 C 堆栈，在 __main__ 中发出的前奏设置了一个全局 __stack_pointer 变量，然后每个函数调用都会将该变量减少函数参数和局部变量所需的空间（由该函数的 StackFrame 实例计算）。

当我们开始解析函数时，我将更详细地介绍该计算的工作原理，但本质上，每个参数和局部变量都会在该堆栈空间中获得一个槽，并增加 StackFrame.frame_size （从而增加下一个变量的偏移量） 取决于它的大小。每个参数和局部变量的偏移量、类型信息和其他数据都按声明顺序存储在 StackFrame.variables 中的 FrameVar 实例中。

ExprMeta 类

这个最终数据类用于跟踪表达式的结果是值还是位置。我们需要跟踪这种区别，以便根据某些表达式的使用方式以不同的方式处理它们。

例如，如果有一个 int 类型的变量 x，则可以通过两种方式使用它：

1. x + 1 想要对 x 的值（例如 1）进行运算

2. &x 想要 x 的地址，比如 0xcafedead

当我们解析 x 表达式时，我们可以轻松地从堆栈帧中获取地址：

但现在怎么办？如果我们 i32.load 这个地址来获取值，那么 &x 将无法获取该地址。但如果我们不加载它，那么 x + 1 会尝试将地址加一，结果是 0xcafedeae 而不是 2！

这就是 ExprMeta 的用武之地：我们将地址留在堆栈上，并返回一个 ExprMeta 指示这是一个地方：

然后，对于像 + 这样总是希望对值而不是位置进行操作的操作，有一个函数 load_result 可以将任何位置转换为值：

同时，像 & 这样的操作不会加载结果，而是将地址保留在堆栈上：从重要意义上讲，& 在我们的编译器中是无操作，因为它不发出任何代码！

另请注意，尽管 & 是一个地址，但它的结果并不是一个地点！（代码返回 is_place=False 的 ExprMeta。） & 的结果应该被视为一个值，因为 &x + 1 应该向地址添加 1（或者更确切地说，sizeof(x)）。这就是为什么我们需要区分位置/值，因为仅仅“作为地址”不足以知道是否应该加载表达式的结果。

好的，关于辅助类就足够了。让我们继续讨论 Codegen 的核心部分！

解析和代码生成

编译器的一般控制流程是这样的：

__main__

这一篇非常简短而且乏味。这是完整的介绍：

显然我从未完成那个 TODO！这里唯一真正有趣的是 fileinput 模块，您可能没有听说过。从模块文档中，

典型用途是：

这会迭代 sys.argv[1:] 中列出的所有文件的行，如果列表为空，则默认为 sys.stdin。如果文件名是“-”，它也会被 sys.stdin 替换，并且可选参数 mode 和 openhook 将被忽略。要指定备用文件名列表，请将其作为参数传递给 input()。也允许使用单个文件名。

这意味着，从技术上来说，c500 支持多个文件！（如果你不介意它们全部连接起来并且行号混乱:-) fileinput 实际上相当复杂并且有一个 filelineno() 方法，我只是出于空间原因没有使用它。）

compile（）

compile() 是这里第一个有趣的函数，它足够短，可以逐字包含：

该函数处理发出模块级前奏。

首先，我们为 WASM VM 发出一个编译指示以保留 3 页内存（（内存 3）），并将堆栈指针设置为从该保留区域的末尾开始（它将向下增长）。

然后，我们定义两个堆栈操作助手 __dup_i32 和 __swap_i32。如果您曾经使用过 Forth，这些应该很熟悉：dup 复制 WASM 堆栈顶部的项目 (a -- a a)，swap 交换 WASM 堆栈顶部两个项目的位置 (a b -- b a)。

接下来，我们初始化一个堆栈帧来保存全局变量，使用词法分析器黑客的内置类型名初始化词法分析器，并咀嚼全局声明，直到用完为止！

最后，我们导出 main 并转储字符串池。

global_declaration（）

这个函数太长，无法内联整个函数，但签名如下所示：

它处理 typedef、全局变量和函数。

Typedef 很酷，因为这是词法分析器黑客发生的地方！

我们再一次用了通用的类型名称解析工具，因为 typedef 继承了所有 C 奇怪的“声明反映用法”规则，这对我们来说很方便。（对于困惑的新手来说则不然！）然后我们通知词法分析器我们发现了一个新的类型名称，以便将来该标记将被词法分析为类型名称而不是变量名称。

最后，对于 typedef，我们将类型存储在全局 typedef 注册表中，使用尾随分号，然后返回到compile() 进行下一个全局声明。重要的是，我们存储的类型是一个完整解析的类型，因为如果你这样做 typedef int* int_p; 然后稍后写入 int_p *x，x 应该得到 int** 的结果类型 - 指针级别是累加的！这意味着我们不能只存储基本 C 类型名称，而是需要存储整个 CType。

如果声明不是 typedef，我们将解析变量类型和名称。如果我们找到一个 ; token 我们知道它是一个全局变量声明（因为我们不支持全局初始值设定项）。在这种情况下，我们将全局变量添加到全局堆栈帧和 bail 中。

然而，如果没有分号，我们肯定正在处理一个函数。要生成函数代码，我们需要：

1. 为该函数创建一个新的StackFrame，命名为frame

2. 然后，解析所有参数并将它们存储在框架中：frame.add_var(varname.content, type, is_parameter=True)

3. 之后，使用variable_declaration（lexer，frame）解析所有变量声明，这会将它们添加到frame中

4. 现在我们知道函数的堆栈帧需要有多大（frame.frame_size），所以我们可以开始发出前奏！

5. 首先，对于堆栈帧中的所有参数（使用 is_parameter=True 添加），我们生成 WASM 参数声明，以便可以使用 WASM 调用约定来调用该函数（在 WASM 堆栈上传递参数）：

然后，我们可以为返回类型发出结果注释，并调整 C 堆栈指针以为函数的参数和变量腾出空间：

对于每个参数（按相反顺序，因为堆栈），将其从 WASM 堆栈复制到我们的堆栈：

最后，我们可以在循环中调用statement(lexer,frame)来代码生成函数中的所有语句，直到我们到达右括号：

额外步骤：我们假设函数总是有返回值，因此我们发出(“unreachable”)，这样 WASM 分析器就不会崩溃。

很多内容，但这就是函数的全部内容，因此也是 global_declaration() 的全部内容，所以让我们继续讨论 statements()。

statement（）

statements() 中有很多代码。然而，其中大部分内容相当重复，因此我将只解释 while 和 for，这应该可以提供一个很好的概述。

还记得 WASM 没有跳转，而是有结构化控制流吗？现在这很重要。

首先我们来看看它是如何与 while 配合使用的，在那里并不会太麻烦。WASM 中的 while 循环如下所示：

正如所看到的，有两种类型的块 - 块和循环（还有 if 块类型，我没有使用）。每个语句都包含一定数量的语句，然后以 end 结束。在块内，可以使用 br 进行中断，或者使用 br_if 有条件地基于 WASM 堆栈的顶部（还有 br_table，我没有使用它）。

br 系列采用 labelidx 参数，此处为 1 或 0，表示操作适用于哪个级别的块。因此，在我们的 while 循环中，br_if 1 适用于外部块 - 索引 1，而 br 0 适用于内部块 - 索引 0。（索引始终相对于相关指令 - 0 是该指令的最内层块 .)

最后，要知道的最后一个规则是块中的 br 向前跳转到块的末尾，而循环中的 br 向后跳转到循环的开头。

希望现在再看一遍更易懂一些：

在更正常的装配中，这对应于：

但是通过跳跃，您可以表达在 WASM 中无法（轻松）表达的内容 - 例如，您可以跳到块的中间。

（这主要是编译C的goto的问题，我什至没有尝试过——有一种算法可以将任何使用goto的代码转换为使用结构化控制流的等效程序，但它很复杂，我认为它行不通 使用我们的单遍方法。）

但对于 while 循环来说，这还不算太糟糕。我们所要做的就是：

但对于 for 循环，它会变得令人讨厌。考虑这样的 for 循环：

词法分析器/代码生成器看到 for 循环各部分的顺序是：

1. i = 0i < 5i = i + 1j = j * 2 + i

但为了使用 WASM 的结构化控制流，我们需要将它们放入代码中的顺序是：

请注意，生成的代码中 3 和 4 被反转，顺序为 1、2、4、3。这对于单遍编译器来说是一个问题！与普通编译器不同，我们无法存储高级语句以供以后使用。或者……我们可以吗？

我最终处理这个问题的方法是使词法分析器可克隆，并在解析正文后重新解析进度语句。本质上，代码如下所示：

正如所看到的，技巧是保存词法分析器，然后使用它返回并稍后处理高级语句，而不是像普通编译器那样保存语法树。不是很优雅——编译 for 循环可能是编译器中最粗糙的代码——但它工作得足够好！

statements() 的其他部分大多相似，因此我将跳过它们以了解编译器的最后一个主要部分 — expression()。

expression（）

expression() 是编译器中的最后一个大方法，如您所料，它处理解析表达式。它包含许多内部方法，每个优先级都有一个方法，每个方法返回前面描述的 ExprMeta 结构（处理“位置与值”的区别，并且可以使用 load_result 将其转换为值）。

优先级堆栈的底部是 value() （命名有些令人困惑，因为它可以返回 ExprMeta(is_place=True, ...)）。它处理常量、括号表达式、函数调用和变量名。

除此之外，优先级的基本模式是这样的函数：

事实上，这种模式是如此一致，以至于大多数操作（包括 muldiv）都不会写出来，而是由高阶函数 makeop 定义：

只有少数具有特殊行为的操作需要显式定义，例如需要处理 C 指针数学的细微差别的 plusminus。

就是这样！这是编译器的最后一个主要部分。

总结

这就是我挑战在 500 行 Python 中的 C 编译器之旅！编译器以复杂而闻名——GCC 和 Clang 非常庞大，甚至 TCC（Tiny C 编译器）也有数万行代码——但如果你愿意牺牲代码质量并一次性完成所有工作，它的代码量也可以非常少！

我很想知道你是否编写过自己的单程编译器——也许是针对自定义语言？我认为这种编译器可能成为自托管语言的一个很好的阶段，因为它非常简单。