用自己的语言编写编译器

直观地说,似乎语言的编译器Foo本身不能用Foo编写.更具体地说,语言的第一个编译器Foo不能用Foo编写,但可以编写任何后续的编译器Foo.

但这是真的吗？我对一种语言的阅读非常模糊,这种语言的第一个编译器是用"本身"编写的.这是可能的,如果是这样的话怎么样？

1> Daniel Spiew..：

---

这称为"自举".您必须首先使用其他语言(通常是Java或C)为您的语言构建编译器(或解释器).完成后,您可以用Foo语言编写新版本的编译器.您使用第一个引导编译器来编译编译器,然后使用此编译的编译器来编译其他所有内容(包括其自身的未来版本).

大多数语言确实以这种方式创建,部分原因是语言设计者喜欢使用他们正在创建的语言,并且因为非平凡的编译器通常作为语言"完整"的有用基准.

这方面的一个例子是Scala.它的第一个编译器是由Martin Odersky的实验性语言Pizza创建的.从2.0版开始,编译器完全在Scala中重写.从那时起,旧的Pizza编译器可能被完全丢弃,因为新的Scala编译器可以用于编译自己以用于将来的迭代.

2> Alan..：

---

我记得听过一个软件工程电台播客,其中Dick Gabriel谈到了通过在LISP 上写一个简单的版本在纸上并将其组装成机器代码来引导原始的LISP解释器.从那时起,其余的LISP功能都是用LISP编写和解释的.

3> Federico A. ..：

---

为先前的答案添加好奇心.

这里引用了Linux From Scratch手册,其中一个开始从源代码开始构建GCC编译器.(Linux From Scratch是一种安装Linux的方法,与安装发行版完全不同,因为你必须编译目标系统的每一个二进制文件.)

make bootstrap

'bootstrap'目标不只是编译GCC,而是编译几次.它使用第一轮编译的程序第二次编译自己,然后第三次编译.然后它比较这些第二和第三个编译,以确保它可以完美地再现自己.这也意味着它被正确编译.

使用'bootstrap'目标的动机是,用于构建目标系统的工具链的编译器可能没有与目标编译器完全相同的版本.以这种方式进行,确保在目标系统中获得可以自己编译的编译器.

---

"你必须编译目标系统的每一个二进制文件",但你必须从你从某个地方获得的gcc二进制文件开始,因为源代码无法自行编译.我想知道你是否追溯了用于重新编译每个连续gcc的每个gcc二进制文件的谱系,你会一直回到K&R的原始C编译器吗？

4> Aaron Digull..：

---

当您为C编写第一个编译器时,可以用其他语言编写它.现在,你有一个C编译器,比如汇编器.最终,您将到达必须解析字符串的位置,特别是转义序列.您将编写代码以转换\n为十进制代码10(以及\r13等)的字符.

在编译器准备好之后,您将开始在C中重新实现它.此过程称为" bootstrapping" ".

字符串解析代码将变为:

...
if (c == 92) { // backslash
    c = getc();
    if (c == 110) { // n
        return 10;
    } else if (c == 92) { // another backslash
        return 92;
    } else {
        ...
    }
}
...

编译时,你有一个理解'\n'的二进制文件.这意味着您可以更改源代码:

...
if (c == '\\') {
    c = getc();
    if (c == 'n') {
        return '\n';
    } else if (c == '\\') {
        return '\\';
    } else {
        ...
    }
}
...

那么'\n'是13的代码的信息在哪里？它在二进制文件中!它就像DNA:用这个二进制文件编译C源代码将继承这些信息.如果编译器自己编译,它会将这些知识传递给它的后代.从现在开始,没有办法从源代码单独看到编译器将做什么.

如果你想在某些程序的源代码中隐藏病毒,你可以这样做:获取编译器的源代码,找到编译函数的函数并用以下代码替换它:

void compileFunction(char * name, char * filename, char * code) {
    if (strcmp("compileFunction", name) == 0 && strcmp("compile.c", filename) == 0) {
        code = A;
    } else if (strcmp("xxx", name) == 0 && strcmp("yyy.c", filename) == 0) {
        code = B;
    }

    ... code to compile the function body from the string in "code" ...
}

有趣的部分是A和B.A是源代码 compileFunction包含病毒,可能以某种方式加密,因此搜索结果二进制文件并不明显.这确保了编译器本身的编译将保留病毒注入代码.

对于我们想要用我们的病毒取代的功能,B是相同的.例如,它可能是源文件"login.c"中的函数"login",它可能来自Linux内核.除了普通密码之外,我们可以用一个版本替换它,该版本将接受root帐户的密码"joshua".

如果你编译它并将其作为二进制文件传播,那么通过查看源代码就无法找到病毒.

这个想法的原始来源:http://cm.bell-labs.com/who/ken/trust.html

---

@mhvelplund只是传播知识如何引导可以杀死你.

5> Phil Wright..：

---

你不能自己编写编译器,因为你没有什么可以编译你的起始源代码.解决这个问题有两种方法.

最不受欢迎的是以下内容.您在汇编程序(yuck)中编写了一个最小的编译器,用于最小的语言集,然后使用该编译器来实现该语言的额外功能.建立自己的方式,直到你有一个编译器具有自己的所有语言功能.一个痛苦的过程通常只在你别无选择时才会完成.

首选方法是使用交叉编译器.您可以更改其他计算机上现有编译器的后端,以创建在目标计算机上运行的输出.然后你有一个很好的完整编译器并在目标机器上工作.最受欢迎的是C语言,因为有很多现有的编译器具有可插拔的可插拔端口.

一个鲜为人知的事实是GNU C++编译器具有仅使用C子集的实现.原因是通常很容易为新的目标机器找到C编译器,然后允许您从中构建完整的GNU C++编译器.你现在已经开始在目标机器上使用C++编译器了.

6> Marc Gravell..：

---

通常,您需要首先使用编译器的工作(如果是主要的) - 然后您可以开始考虑使其自托管.这实际上被认为是一些语言中的一个重要里程碑.

从我记得的"单声道"中,很可能他们需要添加一些东西来反思才能让它发挥作用:单声道团队一直指出有些事情是不可能的Reflection.Emit; 当然,MS团队可能会证明他们错了.

这有一些真正的优势:对于初学者来说,这是一个相当不错的单元测试!而且你只需要担心一种语言(即C#专家可能不太了解C++;但现在你可以修复C#编译器).但我想知道在这里是否有一定程度的职业自豪感:他们只是希望它能够自我托管.

不是一个编译器,但我最近一直在研究一个自托管的系统; 代码生成器用于生成代码生成器...所以如果模式更改我只是自己运行它:新版本.如果有错误,我只需返回早期版本再试一次.非常方便,而且非常容易维护.

---

更新1

我刚看过PDC上的Anders 视频,(大约一个小时后)他确实给出了一些更有效的理由 - 所有关于编译器作为服务.仅供记录.