编译器如何自行编译？

我正在研究咖啡脚本的网站 http://coffeescript.org/，它有文字

CoffeeScript 编译器本身是用 CoffeeScript 编写的

编译器如何自行编译，或者这个语句是什么意思？

12819 次浏览
小开
最佳答案

编译器的第一版不能由特定于它的编程语言机器生成; 您的困惑是可以理解的。可以由第一个编译器构建具有更多语言特性的更新版本的编译器(使用新语言的第一个版本重写源代码)。然后该版本可以编译下一个编译器，以此类推。这里有一个例子:

  1. 第一个 CoffeeScript 编译器是用 Ruby 编写的，生成了 CoffeeScript 的第一个版本
  2. CS 编译器的源代码在 CoffeeScript1中重写
  3. 原来的 CS 编译器将新代码(用 CS 1编写)编译成编译器的版本2
  4. 更改编译器源代码以添加新的语言特性
  5. 第二个 CS 编译器(用 CS 编写的第一个)将修订后的新源代码编译成编译器的版本3
  6. 对每个迭代重复步骤4和5

注意: 我不确定 CoffeeScript 版本是如何编号的，这只是一个例子。

这个过程通常称为 自力更生。另一个引导编译器的例子是 rustc，生锈的语言的编译器。

小开

你已经得到了一个非常好的答案，但是我想给你一个不同的视角，希望能给你一些启发。让我们首先确定两个我们都同意的事实:

  1. CoffeeScript 编译器是一个可以编译用 CoffeeScript 编写的程序的程序。
  2. CoffeeScript 编译器是用 CoffeeScript 编写的程序。

我相信你会同意第一和第二条都是正确的。现在，看看这两条陈述。现在您看到 CoffeeScript 编译器能够编译 CoffeeScript 编译器是完全正常的了吗？

编译器不关心它所编译的 什么。只要是用 CoffeeScript 编写的程序，就可以编译它。CoffeeScript 编译器本身就是这样一个程序。CoffeeScript 编译器并不关心它正在编译的是 CoffeeScript 编译器本身。它看到的只是一些 CoffeeScript 代码。就这样。

编译器如何自行编译，或者这个语句是什么意思？

是的，这正是那句话的意思，我希望你现在能明白那句话是怎么回事。

小开

一个小而重要的澄清

这里术语 编译器掩盖了有 二文件参与的事实。一种是可执行文件，它接受用 CoffeScript 编写的输入文件，并生成另一个可执行文件、可链接对象文件或共享库作为其输出文件。另一个是 CoffeeScript 源文件，它恰好描述了 CoffeeScript 的编译过程。

您将第一个文件应用于第二个文件，生成第三个文件，该文件能够执行与第一个文件相同的编译操作(如果第二个文件定义了第一个文件未实现的特性，则可能执行更多的编译操作) ，因此，如果您愿意，可以替换第一个文件。

小开

在 关于信任的思考这篇论文中，Unix 的创始人之一 Ken Thompson 写了一篇关于 C 编译器如何编译自身的引人入胜(且易于阅读)的概述。类似的概念可以应用到 CoffeeScript 或任何其他语言。

编译器编译自己的代码的想法大致类似于 Quine: 源代码，在执行时，生成原始源代码作为输出。一个 CoffeeScript quine 的 这里有一个例子。汤普森举了一个 C 奎因的例子:

char s[] = {
'\t',
'0',
'\n',
'}',
';',
'\n',
'\n',
'/',
'*',
'\n',
… 213 lines omitted …
0
};


/*
* The string s is a representation of the body
* of this program from '0'
* to the end.
*/


main()
{
int i;


printf("char\ts[] = {\n");
for(i = 0; s[i]; i++)
printf("\t%d,\n", s[i]);
printf("%s", s);
}

接下来，您可能想知道如何告诉编译器像 '\n'这样的转义序列表示 ASCII 代码10。答案是，在 C 编译器的某个地方，有一个解释字符文字的例程，包含一些像这样的条件来识别反斜杠序列:

…
c = next();
if (c != '\\') return c;        /* A normal character */
c = next();
if (c == '\\') return '\\';     /* Two backslashes in the code means one backslash */
if (c == 'r')  return '\r';     /* '\r' is a carriage return */
…

因此，我们可以向上面的代码添加一个条件..。

if (c == 'n')  return 10;       /* '\n' is a newline */

生成一个编译器，它知道 '\n'代表 ASCII 10。有趣的是，编译器 以及它编译的所有后续编译器“知道”那个映射，所以在下一代源代码中，您可以将最后一行更改为

if (c == 'n')  return '\n';

它会做正确的事！10来自编译器，不再需要在编译器的源 code.1中显式定义

这是用 C 代码实现的 C 语言特性的一个例子。现在，对每一个语言特性重复这个过程，您就有了一个“自托管”编译器: 一个用 C 编写的 C 编译器。

文中描述的情节扭曲是，由于编译器可以像这样被“教授”事实，它也可以被错误地教授以一种难以检测的方式生成木马可执行文件，这种破坏行为可以持续存在于所有由受污染的编译器生成的编译器中。

小开

编译器如何自行编译，或者这个语句是什么意思？

就是这个意思。首先，我们需要考虑一些事情。我们需要看四个对象:

  • 任意 CoffeScript 程序的源代码
  • 任意 CoffeScript 程序的(生成的)程序集
  • CoffeScript 编译器的源代码
  • CoffeScript 编译器的(生成的)程序集

现在，很明显，您可以使用 CoffeScript 编译器生成的程序集(可执行文件)来编译任何任意的 CoffeScript 程序，并为该程序生成程序集。

现在，CoffeScript 编译器本身只是一个任意的 CoffeScript 程序，因此，它可以由 CoffeScript 编译器进行编译。

看起来你的困惑源于这样一个事实，当你创建你自己的新语言时，你不能使用 有编译器来编译你的编译器。这肯定看起来像 先有鸡还是先有蛋的问题，对不对？

介绍称为 强 > bootstrap的过程。

  1. 您使用一种已经存在的语言编写一个编译器(对于 CoffeScript，原始编译器是用 Ruby 编写的) ，该编译器可以编译新语言的一个子集
  2. 您编写的编译器可以用新语言本身编译新语言的子集。您只能使用编译器从上面的步骤可以编译的语言特性。
  3. 使用步骤1中的编译器从步骤2中编译编译器。这样就留下了一个程序集，它最初是用新语言的一个子集编写的，并且能够编译新语言的一个子集。

现在您需要添加新的特性。假设您只实现了 while循环，但是还需要 for循环。这不是一个问题，因为您可以重写任何 for循环，使其成为 while循环。这意味着您只能在编译器的源代码中使用 while循环，因为您手边的程序集只能编译这些程序集。但是您可以在编译器中创建函数，用它来传递和编译 for循环。然后使用已有的程序集，并编译新的编译器版本。现在您有了一个编译器的程序集，它也可以解析和编译 for循环！现在，您可以返回到编译器的源文件，并将任何您不希望的 while循环重写为 for循环。

清洗并重复，直到所有需要的语言特性都可以用编译器编译。

while和 for显然只是例子，但这适用于任何你想要的新语言特性。然后您就处于 CoffeScript 现在所处的情况: 编译器自己编译自己。

市面上有很多文献，关于信托的几点思考是每个对这个话题感兴趣的人都应该至少读一遍的经典。

小开

这里不是编译器的问题，而是语言的表达能力问题，因为编译器只是用某种语言编写的程序。

当我们说“编写/实现了一种语言”时，我们实际上是指实现了该语言的编译器或解释器。有一些编程语言可以用来编写实现这种语言的程序(是同一种语言的编译器/解释器)。这些语言被称为 通用语言。

为了能够理解这一点，想象一下金属车床。它是一种用来塑造金属形状的工具。仅仅使用这个工具，通过创建它的部件来创建另一个相同的工具是可能的。因此，这个工具是一个通用的机器。当然，第一个是用其他方法(其他工具)创建的，质量可能较低。但是第一个被用来建造精度更高的新的。

3D 打印机几乎是一台万能机器。你可以使用3D 打印机打印整个3D 打印机(你不能建立熔化塑料的尖端)。

小开

数学归纳法

归纳步骤

编译器的 n + 1版本是用 X 编写的。

因此，它可以由编译器的第 n 个版本(也是用 X 编写的)进行编译。

基本情况

但是必须编译用 X 编写的编译器的第一个版本 用 X 以外的语言编写的 X 的编译器。此步骤称为引导编译器。

小开

编译器采用高级规范并将其转换为低级实现，例如可以在硬件上执行。因此，除了目标语言的语义之外，规范的格式与实际执行之间没有任何关系。

跨语言编译器从一个系统迁移到另一个系统，跨语言编译器将一种语言规范编译成另一种语言规范。

基本上，编译是一种公正的翻译，通常是语言的高层次到低层次，但也有许多变体。

当然，引导编译器是最令人困惑的，因为它们编译它们所使用的语言。不要忘记引导的最初步骤，它需要至少一个可执行的最小现有版本。许多自举编译器首先处理编程语言的最小特性，然后添加额外的复杂语言特性，只要新特性可以用以前的特性表示。如果不是这样的话，那么就需要事先用另一种语言来开发“编译器”的这一部分。

小开
  1. CoffeeScript 编译器最初是用 Ruby 编写的。
  2. 然后用 CoffeeScript 重写 CoffeeScript 编译器。

因为 CoffeeScript 编译器的 Ruby 版本已经存在，所以它被用来创建 CoffeeScript 编译器的 CoffeeScript 版本。

enter image description here 这就是所谓的 自驻留编译器自驻留编译器。

这种现象非常普遍，通常是由于作者希望使用自己的语言来保持语言的发展。

小开

虽然其他的答案涵盖了所有的要点，但我觉得如果不包括可能是已知的最令人印象深刻的编译器例子，这个例子是从它自己的源代码引导的。

几十年前，一个名叫 Doug McIlroy 的人想为一种名为 TMG 的新语言构建一个编译器。他用纸和笔为一个简单的 TMG 编译器编写了源代码... 用的是 TMG 语言本身。

现在，如果他有一个 TMG 解释器，他就可以使用它在自己的源代码上运行他的 TMG 编译器，然后他就会有一个可运行的机器语言版本。但是... 他已经有 TMG 解释器了！这是一个缓慢的，但由于输入很小，它会足够快。

Doug 在他眼窝后面的 TMG 解释器上运行了那张纸上的源代码，给它提供了与输入文件完全相同的源代码。随着编译器的工作，他可以看到从输入文件中读取的标记，调用堆栈在进入和退出子过程时不断增长和收缩，符号表不断增长... ... 当编译器开始向它的“输出文件”发出汇编语言语句时，道格拿起笔，把它们写在另一张纸上。

在编译器完成执行并成功退出之后，Doug 将产生的手写汇编列表带到计算机终端，输入它们，然后他的汇编器将它们转换成一个工作的编译器二进制文件。

所以这是另一个实用的(? ? ?)“使用编译器来编译自己”的方法: 在硬件上有一个工作语言实现，即使“硬件”是湿软的，由花生酱三明治提供动力！


提交答案