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

作者 | Theia Vogel
译者｜Ric Guan 责编 | 屠敏
出品 | CSDN（ID：CSDNnews）
几月前，在挑战用 46 行 Python/ target=_blank class=infotextkey>Python 写有符号距离函数（Signed Distance Function）后，我为自己设下了用 500 行 Python 写一个 C 编译器的挑战，那这一次能有多难呢？
事实证明，即便是放弃了相当多的功能，实现起来还是相当困难！但整个过程也非常有趣，而且最终结果出乎意料，非常实用的同时还并不难理解！
由于我的代码比较多，所以无法在一篇文章中全面涵盖，因此我将在本篇文章中概述我所做的决定、我必须删除的内容，以及分享编译器的总体架构和涉及每部分的代表性代码。希望读完这篇文章后，你对我开源的代码会更容易理解！
Github 地址：https://github.com/vgel/c500/blob/mAIn/compiler.py
找准定位，做决定！
第一个也是最关键的决定就是将本次的目标设定为开发一个 Single pass 编译器（只通过每个编译单元的各个部分一次，立即将每个代码部分转换为其最终的机器代码）。
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）。