102

我听说过引导语言的想法，即为语言本身编写编译器/解释器。我想知道如何做到这一点并环顾四周，看到有人说这只能由任何一方完成

  • 用另一种语言编写初始编译器。
  • 在 Assembly 中手动编写初始编译器，这似乎是第一个编译器的特例

对我来说，从它们都需要外部支持的意义上说，它们似乎都不是真正引导一种语言。有没有办法用自己的语言实际编写编译器？

4

11 回答 11

111

有没有办法用自己的语言实际编写编译器？

你必须有一些现有的语言来编写你的新编译器。如果你正在编写一个新的，比如 C++ 编译器，你只需用 C++ 编写它，然后先用现有的编译器编译它。另一方面，如果您正在为一种新语言创建编译器，我们称之为 Yazzleof，您需要先用另一种语言编写新编译器。通常，这将是另一种编程语言，但并非必须如此。它可以是汇编代码，或者如果需要，可以是机器代码。

如果您要为Yazzleof 引导编译器，通常最初不会为完整语言编写编译器。相反，您将为 Yazzle-lite 编写一个编译器，这是 Yazzleof 的最小可能子集（嗯，至少是一个很小的子集）。然后在 Yazzle-lite 中，您将为完整语言编写一个编译器。（很明显，这可以迭代地发生，而不是一次跳转。）因为 Yazzle-lite 是 Yazzleof 的一个真子集，所以您现在有了一个可以自行编译的编译器。

有一篇关于从可能的最低级别（在现代机器上基本上是一个十六进制编辑器）引导编译器的非常好的文章，标题为Bootstrapping a simple compiler from nothing。它可以在https://web.archive.org/web/20061108010907/http://www.rano.org/bcompiler.html找到。

于 2008-08-17T07:20:55.103 回答
20

您阅读的解释是正确的。Compilers: Principles, Techniques, and Tools (the Dragon Book)中对此进行了讨论：

  • 用语言 Y 为语言 X 编写编译器 C1
  • 使用编译器 C1 为语言 X 编写语言 X 的编译器 C2
  • 现在 C2 是一个完全自托管的环境。
于 2008-08-17T07:00:39.310 回答
8

Unix 联合创始人Ken Thompson的图灵奖讲座中对此进行了非常有趣的讨论。

他开始说：

我要描述的是当编译器用他们自己的语言编写时出现的许多“鸡和蛋”问题之一。在这种情况下，我将使用 C 编译器中的一个特定示例。

并继续展示他如何编写一个 Unix C 编译器版本，该版本始终允许他无需密码即可登录，因为 C 编译器会识别登录程序并添加特殊代码。

第二种模式针对 C 编译器。替换代码是一个第一阶段的自我复制程序，它将两个特洛伊木马都插入到编译器中。这需要一个学习阶段，就像第二阶段的例子一样。首先，我们用普通的 C 编译器编译修改后的源代码，以生成一个错误的二进制文件。我们将这个二进制文件安装为官方 C。我们现在可以从编译器的源代码中删除错误，新的二进制文件将在编译时重新插入错误。当然，login 命令将一直存在错误，并且在任何地方都没有源代码跟踪。

于 2008-08-17T07:07:05.037 回答
6

我听说的方法是用另一种语言编写一个极其有限的编译器，然后用它来编译一个更复杂的版本，用新语言编写。然后可以使用第二个版本来编译自己和下一个版本。每次编译时都会使用最后一个版本。

这是引导的定义：

一个简单系统激活一个服务于相同目的的更复杂系统的过程。

编辑：关于编译器引导的维基百科文章比我更好地涵盖了这个概念。

于 2008-08-17T07:00:23.787 回答
4

查看播客软件工程广播第 61 集(2007-07-06)，其中讨论了 GCC 编译器内部结构以及 GCC 引导过程。

于 2009-05-20T09:29:29.450 回答
4

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

于 2011-08-10T14:56:40.810 回答
3

据我了解，第一个Lisp解释器是通过手动编译构造函数和令牌读取器来引导的。然后从源代码中读入解释器的其余部分。

您可以通过阅读原始的 McCarthy 论文“符号表达式的递归函数及其机器计算，第一部分”来检查自己。

于 2011-07-09T19:54:17.183 回答
2

我能想到的每个引导语言的示例（C、PyPy）都是在有一个工作编译器之后完成的。你必须从某个地方开始，重新实现一种语言本身需要先用另一种语言编写编译器。

它还能如何工作？我认为甚至在概念上也不可能这样做。

于 2008-08-17T07:01:08.340 回答
2

这是鸡和蛋悖论的计算机科学版本。我想不出不用汇编程序或其他语言编写初始编译器的方法。如果可以做到，我应该 Lisp 可以做到。

实际上，我认为 Lisp 几乎可以胜任。查看它的维基百科条目。根据这篇文章，Lisp eval 函数可以用机器代码在IBM 704上实现，完整的编译器（用 Lisp 本身编写）于 1962 年在麻省理工学院问世。

于 2008-08-17T07:06:30.577 回答
2

另一种选择是为您的语言创建一个字节码机器（或者如果它的功能不是很不寻常，则使用现有的）并编写一个编译器到字节码，无论是在字节码中，还是在您想要的语言中使用另一种中间体 - 例如解析器工具包，它将 AST 输出为 XML，然后使用 XSLT（或另一种模式匹配语言和基于树的表示）将 XML 编译为字节码。它不会消除对另一种语言的依赖，但可能意味着更多的引导工作最终会出现在最终系统中。

于 2008-08-17T13:21:16.500 回答
0

一些自举编译器或系统将源形式和对象形式都保存在其存储库中：

  • ocaml是一种同时具有字节码解释器（即 Ocaml 字节码的编译器）和本机编译器（x86-64 或 ARM 等...汇编器）的语言。它的 svn 存储库包含编译器的源代码（文件*/*.{ml,mli}）和字节码（文件boot/ocamlc）形式。因此，当您构建它时，首先使用它的字节码（以前版本的编译器）来编译自己。后来新编译的字节码能够编译本机编译器。所以 Ocaml svn 存储库包含*.ml[i]源文件和boot/ocamlc字节码文件。

  • rust编译器下载（使用，wget因此您需要一个有效的 Internet 连接）其二进制文件的先前版本来编译自己。

  • MELT是一种类似 Lisp 的语言，用于自定义和扩展GCC。它由自举翻译器翻译成 C++ 代码。翻译器生成的 C++ 代码是分布式的，因此 svn 存储库包含翻译器的*.melt源文件和melt/generated/*.cc“目标”文件。

  • J.Pitrat 的CAIA人工智能系统完全是自我生成的。它可作为数千个[A-Z]*.c生成文件的集合（也带有生成的dx.h头文件）和数千个_[0-9]*数据文件的集合。

  • 几个 Scheme 编译器也被引导。Scheme48，鸡计划，...

于 2015-05-01T08:16:01.393 回答