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

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

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

解决方案

回答

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

这是自举的定义：

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

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

回答

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

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

回答

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

否则它将如何工作？我认为，从概念上讲，甚至不可能做到这一点。

回答

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

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

回答

在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.

回答

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上找到。

回答

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

回答

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