首页 / 知识

关于编译器构造：自举仍然需要外部支持

2023-04-12 08:38:00

Bootstrapping still requires outside support

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

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

在我看来，这两者似乎都不是在引导语言，因为它们都需要外部支持。有没有办法用自己的语言实际编写编译器？

Is there a way to actually write a compiler in its own language?

您必须使用某种现有语言来编写新的编译器。如果要编写新的C ++编译器，则只需用C ++编写，然后首先使用现有的编译器进行编译。另一方面，如果要为一种新语言创建编译器，我们称其为Yazzleof，则需要首先使用另一种语言编写新的编译器。通常，这将是另一种编程语言，但并非必须如此。它可以是汇编代码，也可以是机器代码。

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

关于从最低级别引导编译器(在现代计算机上基本上是十六进制编辑器)进行引导的文章非常不错，标题为"从零开始引导简单的编译器"。可以在https://web.archive.org/web/20061108010907/http://www.rano.org/bcompiler.html上找到。

您阅读的说明是正确的。在《编译器：原理，技巧和工具》(《龙书》)中对此进行了讨论：

用语言Y为语言X编写编译器C1
使用编译器C1以语言X编写语言X的编译器C2
现在C2是一个完全自我托管的环境。

在Unix联合创建者Ken Thompson的Turing Award演讲中，对此进行了非常有趣的讨论。

他开始时：

What I am about to describe is one of many"chicken and egg" problems that arise when compilers are written in their own language. In this ease, I will use a specific example from the C compiler.

并继续说明他如何编写Unix C编译器的版本，该版本始终允许他不用密码登录，因为C编译器会识别登录程序并添加特殊代码。

The second pattern is aimed at the C compiler. The replacement code is a Stage I self-reproducing program that inserts both Trojan horses into the compiler. This requires a learning phase as in the Stage II example. First we compile the modified source with the normal C compiler to produce a bugged binary. We install this binary as the official C. We can now remove the bugs from the source of the compiler and the new binary will reinsert the bugs whenever it is compiled. Of course, the login command will remain bugged with no trace in source anywhere.

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

这是自举的定义：

the process of a simple system activating a more complicated system that serves the same purpose.

编辑：有关编译器引导的Wikipedia文章比我更好地介绍了该概念。

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

查阅Podcast软件工程电台第61集(2007-07-06)，其中讨论了GCC编译器的内部以及GCC引导过程。

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

您可以通过阅读原始的麦卡锡论文《符号表达式的递归函数及其由机器进行的计算》(第一部分)来进行检查。

另一种选择是为您的语言创建一个字节码机器(或者，如果功能不是很特殊，则使用现有的字节码机器)，然后使用字节码或所需的语言使用另一种中间语言(例如a)将编译器写入字节码。解析器工具包，将AST输出为XML，然后使用XSLT(或另一种模式匹配语言和基于树的表示形式)将XML编译为字节码。它不会消除对另一种语言的依赖，但是可能意味着更多的引导工作最终会在最终系统中完成。

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

实际上，我认为Lisp几乎可以胜任。查看其Wikipedia条目。根据这篇文章，Lisp eval函数可以在IBM 704上用机器代码实现，而完整的编译器(由Lisp自己编写)于1962年在麻省理工学院诞生。

自举一种我能想到的语言(C，PyPy)的示例都是在有一个可用的编译器之后完成的。您必须从某个地方开始，重新实现一种语言本身首先需要用另一种语言编写编译器。

否则它将如何工作？我不认为在其他方面也没有可能。

一些自举的编译器或系统会将源表单和对象表单都保留在其存储库中：

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，鸡肉方案，...