如何启动一个简单的（也许是最简单的）C编译器？

Question

我看到了这篇文章：使用 Turbo Pascal 编写编译器。

我很好奇是否有任何教程或参考资料可以解释如何创建一个简单的 C 编译器。如果能让它理解算术运算，就足够了。在阅读 Ken Thompson 的一篇文章后，我变得非常好奇。编写能够理解自己的东西似乎很令人兴奋。

为什么我要提出这个问题而不是问 Google？我试过 Google，但 Turbo Pascal 那个链接是第一个显示的。其他的链接似乎与此无关，再加上我不是计算机科学专业的学生（所以我还需要学习像 yacc 这样的工具都是做什么用的），我希望通过实践来学习，并希望有更多经验的人比 Google 更擅长这些事情。我想阅读一些像我上面列出的那篇文章一样的文章，至少强调构建简单的 C 编译器的引导阶段。

此外，我不知道最好的学习方式。我应该用 C 或其他语言开始构建 C 编译器？我应该编写 C 编译器还是其他语言的编译器？我觉得这样的问题最好在我有了一些探索方向后再回答。有什么建议吗？

任何建议？

- Legend

---

尝试使用初学者标志创建C（甚至是子集）编译器有点令人惊讶。您应该先尝试一些更简单的东西。 - Phong

编写自己的编译器可以非常有趣。但最好先考虑获得计算机科学学位，这样才有足够的武器来战胜困难。 - Hans Passant

经典编译器参考问题在https://dev59.com/x3VD5IYBdhLWcg3wXaed。顺便说一句 - 作为第一个入门的引子，我是Crenshaw编译器的忠实粉丝。将Pascal翻译成C并不困难，所以请放心操作。不过，如果您想坚持编译器，很快就需要更完整的参考资料了。 - dmckee --- ex-moderator kitten

另外请参见我的SmallerC，它与Small C不同，但精神上类似。 - Alexey Frunze

@Legend 这是Imagist的答案的一部分。解析器和编译器是两个不同的问题。例如，我可能会用C语言编写一个编译器，但我永远不会用C语言编写一个解析器（我会使用解析器生成器）。对于非常简单的解析器，速度不是很重要的情况下，我可能会在Perl或Python中手动编写解析器，因为它们具有良好的文本处理功能。 - user3095977

Answer 1

编译器由三个部分组成：

1. 解析器
2. 抽象语法树（AST）
3. 汇编代码生成器

有许多好的解析器生成器可以从语言语法开始。也许ANTLR是您入门的好地方。如果您想坚持C语言的根源，请尝试lex/yacc或bison。

有关C的语法，但我认为整个C语言很复杂。您最好从语言子集开始，逐步提高难度。

一旦有了AST，就可以使用它来生成将要运行的机器码。

这是可行的，但并不简单。

我还建议在亚马逊上查找有关编写编译器的书籍。《龙书》是经典之作，但现代的书籍也很多。

更新：Stack overflow 上有类似的问题，比如这个。也请查看那些资源。

- duffymo

---

太棒了！非常感谢...那个线程看起来像是一个庞然大物..我会开始深入挖掘它... - Legend

+1 for ANTLR。它可能不是最好的解析器生成器，但调试和测试工具难以超越。 - Ron Warholic

Answer 2

我建议你学习这个教程：

• LLVM 教程

它是一个实现“小型语言”编译器的简单示例。源代码非常小，逐步进行了解释。

此外，还有 LLVM (低级虚拟机，代表程序的内部结构) 库的 C 前端库：

• Clang

- Phong

---

@duffymo：谢谢，我真正喜欢这个教程的是它们没有依赖任何外部软件来进行词法分析和解析函数。 - Phong

是的，这真的很棒。不错的发现。谢谢你发布它。 - duffymo

Answer 3

值得一提的是，Tiny C Compiler 是一个相对较小的源代码包中具备非常完善功能的C语言编译器。你可以通过研究该源代码来获益，因为相比之下理解GCC的全部源码要困难得多。

- Mark Rushakoff

Answer 4

这是我的意见（和猜测），如果不了解本科（高等教育）计算机科学课程中通常涵盖的数据结构，编写编译器将会很困难。这并不意味着你不能编写，但你需要了解基本的数据结构，如链表和树。

与其编写一个完整或符合标准的C语言编译器（至少在一开始），我建议您将自己限制在语言的基本子集上，例如常见运算符、仅支持整数以及基本函数和指针。其中一个经典的例子是Ron Cain的Small-C，它因在我认为的1980年代写在Dr. Dobbs Journal上的一系列文章而广受欢迎。他们发布了一个CD，其中包括James Hendrix的绝版书籍A Small-C Compiler。

我建议您遵循Crenshaw的教程，但将其编写为类似C的语言编译器，并选择任何CPU目标（Crenshaw的目标是Motorola 68000 CPU）。为了做到这一点，您将需要了解您想要运行已编译程序的目标的基本汇编语言。这可能包括模拟器，例如用于68000或MIPS的模拟器，它们的汇编指令集比Intel x86（16/32位）的古老CISC指令集更好。

有许多潜在的书籍可用作学习编译器/翻译器理论（和实践）的起点。阅读comp.compilers FAQ以及各种在线书店的评论。大多数入门书籍都是为大二到大四的本科计算机科学课程编写的教科书，所以如果没有计算机科学背景，阅读起来可能会比较困难。一本比“The Dragon Book”更入门，但阅读起来更容易的旧书是Thomas Parsons的Introduction to Compiler Construction。它比较老，因此您应该能够以合理的价格从您选择的在线书店中找到二手副本。

所以我建议，尝试从Jack Crenshaw的Let's Build a Compiler教程开始，按照他的示例编写自己的编译器，并构建一个简单的编译器的基础知识。一旦你做到了这一点，你就可以更好地决定从那个点开始往哪里走。

添加：

关于引导过程。由于现有的C编译器是免费提供的，您不需要担心引导问题。使用独立的现有工具（GCC、Visual C++ Express、Mingw / djgpp、tcc）编写编译器，您可以在后期担心自我编译项目。我对这个问题的一部分感到惊讶，直到我意识到你是通过阅读Ken Thomas的ACM Turing奖演讲Reflections on Trusting Trust而被带到编写自己的编译器的想法中，其中涉及了编译器引导过程。这是一个高级话题，并且也非常麻烦。即使在旧的Unix系统（64位Alpha上的Digital OSF/1）下引导GCC C编译器，其中包括C编译器，也是一个缓慢而耗时，容易出错的过程。

另一个问题是像Yacc这样的编译器工具实际上是做什么的。Yacc（或GNU的Bison）是一种旨在使编写编译器（或翻译器）解析器更容易的工具。基于您输入到yacc的目标语言的正式语法，它会生成一个解析器，这是编译器整体设计的一部分。接下来是Lex（或GNU的flex），用于生成词法分析器或扫描器，通常与由yacc生成的解析器结合使用，形成编译器前端的框架。这些工具使得编写前端比自己编写词法分析器和解析器要容易得多。Crenshaw的教程没有使用这些工具，您也不需要使用它们，许多编译器编写者并不总是使用它们。当然，Crenshaw承认教程的解析器非常基础。

Crenshaw的教程还跳过了生成AST（抽象语法树），这简化了但也限制了教程编译器。它缺乏大部分甚至所有的优化，并且与特定的编程语言和编译器“后端”发出的特定汇编语言非常相关。通常，AST是中间件，其中可以执行一些优化，并且在设计上有助于解耦编译器前端和后端。对于没有计算机科学背景的初学者，我建议您不要担心第一个编译器（或至少其第一个版本）没有AST。我认为保持它小而简单将有助于您完成编写编译器的第一个版本，然后您可以从那里决定如何继续。

- mctylr

---

我花了相当长的时间来消化你所写的内容。非常有启发性的帖子。谢谢你的时间... - Legend

谢谢，我很高兴你觉得它有用。我希望我的回答能够对你有所帮助，并鼓励你取得成功。 - mctylr

Answer 5

你可能会对这本/门课程感兴趣：《计算机系统要素：从基础原理构建现代计算机》。请注意，这不是关于用你在新蛋上买的东西构建“个人电脑”的内容。它从布尔逻辑基础开始描述，并从抽象的最低级别逐步构建虚拟计算机到更高级别的抽象。课程材料全部在线提供，而且这本书在亚马逊上价格相当便宜。在这门课程中，除了“构建硬件”之外，您还将分阶段实现汇编器、虚拟机、编译器和基本操作系统。我认为这将为您提供足够的背景知识，以深入研究其他答案中列出的一些常见推荐资源。

- Joe Internet

---

我知道我并没有真正地提出这个问题，但您已经为我提供了一系列问题的解决方案，这些是我将来可能会问的。这似乎是一本非常有趣的书籍。昨天订购了它...只是想看看从基础开始的感觉如何...再次感谢... - Legend

这本书看起来就是我长期以来一直想要的东西。虽然我已经在攻读计算机科学硕士，但是我的本科并非计算机科学专业，因此我知道我缺乏大量底层知识。这本书似乎是一个很好的起点。谢谢。 - The111

@The111 - 还可以看看这个... http://www.joelonsoftware.com/navLinks/fog0000000262.html - Joe Internet

Answer 6

编译器是一个复杂的主题，涵盖了以下方面：

• 输入处理，包括词法分析和语法分析
• 构建每个使用变量的符号存储，如抽象语法树（AST）
• 从AST树中转置并基于语法构建机器代码二进制文件

这绝不是详尽无遗的，因为它是从山顶上的抽象鸟瞰图，归结为正确获取语法符号并确保畸形输入不会使其失效。实际上，良好的输入处理应该永远不会崩溃，无论输入有多么畸形、可怕、滥用。此外，在决定和知道输出内容时，是否是机器代码，这意味着您可能需要深入了解处理器指令...包括变量的内存寻址等。

以下是一些让您开始的链接：

• 我记得几个月前曾经下载过杰克·克伦肖的C语言代码端口......
• 这里有一个类似的问题链接在SO上。
• 此外，这里还有一个基于Basic到x86汇编语言编译器的编译器教程。
• Tiny C Compiler
• Hendrix的Small C Compiler可以在这里找到链接。

- t0mm13b

Answer 7

在《Unix编程环境》一书中，Kernighan和Pike通过5个迭代的方式讲解了如何从基于C的简单词法分析和即时执行开始制作计算器，到使用yacc/lex进行解析并生成抽象机器的代码。由于他们写得非常好，我无法提出更流畅的介绍。它肯定比C更小，但这可能对您有利。

- msw

---

哦...我觉得我在某个地方有那本书！谢谢。 - Legend

Answer 8

我该如何开始编写一个简单的C编译器？

编写C编译器并不简单。Chris Fraser和David Hanson的lcc是最好的简单C编译器。他们花了10年时间设计，尽可能地使其简单，同时生成合理的代码。如果您可以访问大学图书馆，应该能够获取到他们的书。

我是从C语言还是其他语言开始构建C编译器？

从其他语言开始。有一次我问Hanson和Fraser在lcc项目上花费10年时间学到了什么教训。Hanson说的主要是：

使用C语言编写编译器很糟糕。

如果你想写编译器，最好使用Haskell或某种ML方言。这两种语言都提供了对代数数据类型的函数支持，这与编译器编写者面临的问题完美匹配。如果你仍然想追求C语言，可以从George Necula的CIL开始，它是一个用ML编写的大块C编译器。

我想读一些与上面列出的文章相同精神的文章，但至少要突出引导阶段......

你不会找到另一篇像Ken的文章那样的文章。但是Andrew Appel写了一篇很好的文章，名为Axiomatic Bootstrapping: A Guide for Compiler Hackers。我找不到免费版本，但许多人可以访问ACM数字图书馆。

有什么建议吗？

如果你想写编译器，

• 使用 Haskell 或 ML 作为你的实现语言。

• 对于你的第一个编译器，选择一个非常简单的语言，比如 Oberon 或者 Niklaus Wirth 的书 Algorithms + Data Structures = Programs 中的 P0。Wirth 以设计易于编译的语言而闻名。

你可以为你的 第二个 编译器编写一个 C 编译器。

- Norman Ramsey

---

我不会把CIL称为C编译器。CIL由一个解析器和一个输出等效C文件的编写器组成，它确实有助于代码分析和转换。 - Wei Hu

我不认为我称CIL为编译器。它是一个前端。对于C语言来说，这是一个“大块头”，正如我所说的。 - Norman Ramsey

Answer 9

编译器是一个非常庞大的项目，虽然我想尝试一下也没什么坏处。

我知道至少有一个用Pascal编写的C编译器，所以这不是你能做的最疯狂的事情。个人而言，我会选择更现代的语言来实现我的C编译器项目，因为它更简单（可以下载Python、Ruby、C、C++或Java包）并且会让你的简历看起来更好。

然而，作为初学者项目做编译器，你需要喝下所有敏捷软件开发的“kool-aid”。

始终保持运行状态，即使它什么都不做。只通过小步骤添加编译器功能。（“频繁发布”）。先选择极其微小的语言子集并首先实现它。（最初仅支持i = 0;，然后逐步扩展功能。）

- DigitalRoss

---

抱歉，我只是想理解一下......您是在建议使用像Python或Ruby这样的高级语言编写一些东西吗？如果是的话，当然，我也愿意尝试一下......正如我所提到的，我在这个领域完全是个新手，所以任何可以让我理解主要概念的东西都是受欢迎的......另外，你能澄清一下简历部分吗？ :D - Legend

一份使用现代编程语言编写的复杂程序将会为您的简历增色不少。在诸如 Ruby 或 Python 这样的语言中实现编译器要容易得多。Haskell 确实不容易，但是也许会带给你一个更好的编译器。 - Andrew McGregor

明白了...我只听说过 Haskell，但从未尝试过。用 Python 或 Ruby 写一个从未在我脑海中浮现过。如果是这样的话，我一定会去了解一下。谢谢。 - Legend

我们可以跳过“哪种语言更好”的争论吗？尽管我个人很喜欢Perl或者Python，但是OP说C是想要的语言。 - mctylr

同意mctylr的观点，但至少我的背景让函数式语言看起来比Python更好。编译器需要快速而仔细地构建结构，而“简单”的语言在诸如标识符绑定和其内置数据结构的基本含义等方面变得过于复杂。对于敏捷开发的部分持不同意见。对于初学者项目，应该是一个人一步一步地工作。确保保存您的测试用例。不要过度关注您的计划。 - Potatoswatter

@Potatoswatter，关于敏捷开发，我知道他只是一个人，所以敏捷开发中的团队部分可能不适用。但是我认为他逐步原型化程序非常重要。他真的需要有一些微不足道的东西在运行，然后是稍微大一点的东西，再然后是更大一些的。如果他试图真正编写一款编译器，然后开始测试，那么他将彻底失败。 - DigitalRoss

Answer 10

学习函数式编程可能值得一试。函数式语言非常适合编写编译器，无论是编写内部还是外部的编译器。我的学校引导编译器班级包含函数式语言介绍，并且所有作业都是用OCaml完成的。今天你提出这个问题真巧，因为就在几天前我写了一个lambda演算解释器。Lambda演算是所有函数式语言的鼻祖。它只有200行代码（包括C++中的错误报告、一些漂亮的打印和一些Unicode），并采用两阶段结构，其中一个中间格式可用于生成代码。不仅从小处着手建立最实际的编译器，而且还可以促进良好的模块化组织实践。

- Potatoswatter

---

@Legend：顺便说一句，不要听取所有的反对者。你可能不会创造出突破性的甚至是有竞争力的编程语言，但是就算是拥有学位的人第一次尝试也不会如此。只要你玩得开心，你总能找到更多的成就。 - Potatoswatter

非常正确...有时候我看到那些真正的计算机科学专业毕业生会感到紧张...事实上，最近在slashdot上的一篇帖子：http://ask.slashdot.org/comments.pl?sid=10/02/19/147251 让我更深入地思考了这个问题。但归根结底，我想这一切都取决于我们的思维方式... :) - Legend