直观地说,Foo语言的编译器本身似乎不能用Foo来编写。更具体地说,Foo语言的第一个编译器不能用Foo编写,但任何后续的编译器都可以为Foo编写。
但这是真的吗?我隐约记得读过一种语言,它的第一个编译器是用“自身”编写的。这可能吗?如果可能,如何实现?
直观地说,Foo语言的编译器本身似乎不能用Foo来编写。更具体地说,Foo语言的第一个编译器不能用Foo编写,但任何后续的编译器都可以为Foo编写。
但这是真的吗?我隐约记得读过一种语言,它的第一个编译器是用“自身”编写的。这可能吗?如果可能,如何实现?
当前回答
请注意,从技术上讲,您可以用一种仍然不存在的语言编写编译器。为了做到这一点,你创建了一个解释器,它是原始语言的一个下级,通常是缓慢和无用的,因为它在执行任何东西之前解释语言的每个语句。
如果你阅读它,它看起来确实完全像预期的语言,但它的执行要经过一些过程,将其转换为可执行的不止一个步骤。
这个编译器通常非常慢,因为它使用了一些适用于几乎所有现有语言的通用数学过程,但优点是下次除了在现有代码上使用生成的编译器外,什么也不用做。
当然这一次不需要解释。
其他回答
我记得我听过一个软件工程广播播客,其中Dick Gabriel谈到了如何在纸上用LISP编写一个最简单的版本,然后手工将其组装成机器代码,从而引导最初的LISP解释器。从那时起,其余的LISP特性都是用LISP编写和解释的。
这是一个dump(实际上很难搜索的话题):
闲聊 C
这也是PyPy和Rubinius的想法:
(我想这也适用于Forth,但我对Forth一无所知。)
实际上,大多数编译器都是用它们所编译的语言编写的,原因如上所述。
第一个引导编译器通常是用C、c++或Assembly编写的。
请注意,从技术上讲,您可以用一种仍然不存在的语言编写编译器。为了做到这一点,你创建了一个解释器,它是原始语言的一个下级,通常是缓慢和无用的,因为它在执行任何东西之前解释语言的每个语句。
如果你阅读它,它看起来确实完全像预期的语言,但它的执行要经过一些过程,将其转换为可执行的不止一个步骤。
这个编译器通常非常慢,因为它使用了一些适用于几乎所有现有语言的通用数学过程,但优点是下次除了在现有代码上使用生成的编译器外,什么也不用做。
当然这一次不需要解释。
当你为C编写第一个编译器时,你是用其他语言编写的。现在,你有一个C语言的编译器,比如说,汇编器。最终,您将不得不解析字符串,特别是转义序列。您将编写代码将\n转换为十进制代码10(和\r转换为13,等等)的字符。
编译器准备好后,你将开始用c重新实现它,这个过程被称为“引导”。
字符串解析代码将变成:
...
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”作为普通密码。
如果你编译它并以二进制文件的形式传播,就无法通过查看源代码来找到病毒。
这个想法的最初来源是:https://web.archive.org/web/20070714062657/http://www.acm.org/classics/sep95/