logo标签列表

引导仍然需要外部支持

compiler-constructionlanguage-agnosticbootstrapping
104

我听说过“自举语言”的概念，即使用该语言编写其自身的编译器/解释器。我想知道如何实现这一点，搜索了一下，看到有人说只能通过以下两种方式之一实现：

  • 使用其他语言编写初始编译器。
  • 手动使用汇编语言编写初始编译器，这似乎是第一种情况的特例。

对我来说，这两种方法都不像真正的“自举”，因为它们都需要外部支持。是否有一种方法可以真正地使用该语言编写编译器？

1
我对这些事情并不是很有经验，但我认为初始编译器必须用另一种语言编写。我相当确定，在编译器方面，“引导”只是指使用该语言编写一个编译器，而不是在该语言中编写该语言的第一个编译器。 - jdd
2
谢谢大家提供的信息。当最初编写一个有限的编译器，然后在此基础上构建时，引导的概念就更有意义了。这学期我正在上编译器课程，这个决定很大程度上受到 Steve Yegge 在他的文章中强调编译器课程的重要性 的影响，我刚刚从亚马逊链接购买了《龙书》，之前在 SO 上被踩得很惨的那个链接。 - pbh101
2
请参阅类似问题：在自身中实现编译器 - Urban Vagabond
11个回答
114
有没有办法用某种语言来编写它自己的编译器？
你必须要有一些现有的语言来编写你的新编译器。例如，如果你正在编写一个新的C++编译器，你只需要用C++编写它，并首先使用现有的编译器进行编译。另一方面，如果你正在创建一个名为Yazzleof的新语言的编译器，你需要先用另一种语言编写新的编译器。通常情况下，这将是另一种编程语言，但也可以是汇编语言或机器语言。
如果你想要在Yazzleof上启动编译器，通常不会直接编写完整语言的编译器。相反，你会先编写Yazzle-lite的编译器，这是Yazzleof的最小可能子集（至少是“相当小”的子集）。然后在Yazzle-lite中，你会编写完整语言的编译器。（显然，这可以迭代地进行，而不是一步到位。）因为Yazzle-lite是Yazzleof的合适子集，所以你现在拥有了一个能够编译自身的编译器。
关于从最低级别开始引导编译器的非常好的文章，标题是“从零开始启动一个简单的编译器”。可以在https://web.archive.org/web/20061108010907/http://www.rano.org/bcompiler.html找到它。
23

您所读的解释是正确的。在 编译原理（龙书）中有这方面的讨论：

  • 使用语言Y编写语言X的编译器C1
  • 使用编译器C1来编写使用语言X编写语言X的编译器C2
  • 现在C2是一个完全自主托管的环境。
8
我听说的方法是用另一种语言编写极其有限的编译器，然后使用它来编译一个更复杂的版本，该版本用新语言编写。然后可以使用这个第二个版本来编译自身和下一个版本。每次编译时都使用上一个版本。
这就是引导：的定义。

简单系统启动具有相同目的的更复杂系统的过程。

编辑：维基百科关于编译器引导的文章比我解释得更好。
7

一个超级有趣的讨论在Unix的共同创始人Ken Thompson的Turing奖演讲中。

他开始说：

我即将描述的是编译器用其自身语言编写时出现的许多“鸡生蛋”问题之一。在这种情况下，我将使用C编译器的一个具体示例。

然后他展示了如何编写一个版本的Unix C编译器，该编译器总是允许他无需密码登录，因为C编译器会识别登录程序并添加特殊代码。

第二种模式针对C编译器。替换代码是一个自我复制的一阶段程序，将两个特洛伊木马插入编译器中。这需要像第二阶段示例中那样的学习阶段。首先，我们使用普通的C编译器编译修改后的源代码以生成有缺陷的二进制文件。我们将此二进制文件安装为官方C。现在，我们可以从编译器的源代码中删除错误，并且新的二进制文件将在每次编译时重新插入错误。当然，登录命令将保留错误，而在任何源代码中都没有痕迹。
11
这与主题无关。有趣，但令人困惑，且不是问题的答案。 - blueshift
5
5

Donald E. Knuth实际上是通过在WEB中编写编译器，然后手动将其编译为汇编或机器代码来构建它的。

4
第二部分和第三部分发生了什么事？我怎么没注意到@Wing在我之前3年就发布了同样的东西？我真是个蠢货。至少我链接了这篇论文（在别人的帮助下）。 - luser droog
4
我能想到的所有语言引导示例（C，PyPy）都是在有可工作编译器之后完成的。你必须从某个地方开始，而将一种语言重新实现在自身中需要先用另一种语言编写编译器。
否则它会怎样运作？我甚至认为这不可能在概念上以其他方式完成。
6
第一个 Lisp 编译器至少是使用现有的 Lisp 解释器 进行引导启动的。因此，并非使用另一种语言进行语义上的转换，而是使用另一种语言实现来完成这个过程。 - Ken
3
这是计算机科学版的“先有鸡还是先有蛋”的悖论。我想不出不用汇编或其他语言来编写最初的编译器的方法。如果可以做到，那么Lisp可能已经做到了。
实际上，我认为Lisp几乎符合要求。请查看 其维基百科条目。根据文章，Lisp eval函数可以在IBM 704的机器码上实现，并且在1962年在MIT诞生了一个完整的编译器（由Lisp本身编写）。
3

另一种选择是为您的语言创建一个字节码机器（如果它的特性不是非常不寻常，也可以使用现有的字节码机器），并编写一个编译器将源代码编译成字节码。编译器可以在字节码中实现，或者使用其他中间件（例如将AST作为XML输出的解析器工具包），然后使用XSLT（或其他基于模式匹配语言和基于树的表示）将XML编译为字节码。这并不能消除对另一种语言的依赖，但可以使更多的引导工作最终集成到系统中。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接