直观上来看，对于语言Foo的编译器不能用Foo自身来编写。更具体地说，第一个Foo编译器不能用Foo自身写出来，但是任何后续的编译器都可以用Foo编写。
但这是真的吗？我非常模糊地记得读过一种语言，其第一个编译器是用“它本身”编写的。这是否可能，如果可能，又是如何实现的呢？
用其自身语言编写编译器
231
- Don
3
可能是 引导仍需要外部支持 的重复。 - nbro
这是一个非常老的问题，但是假设我在Java中为语言Foo编写了一个解释器。那么用语言Foo编写它自己的解释器，Foo仍然需要JRE对吗？ - George Xavier
你可以用Foo语言本身编写第一个“Foo”编译器。你的源代码将是一个“Foo”程序，其中包含有关如何生成机器代码（或更现代化的术语，其他后端代码）的“Foo”指令，以给定“Foo”源代码输入为基础。现在，您需要某个东西或某个人，足够了解“Foo”的规范，以手动跟踪该程序的正确输出，并运行程序自身。就我所知，然而，对于任何一种语言，我所描述的精确内容从未真正完成，原因显而易见。 - Marcel Besixdouze
14个回答
265
这被称为“自举”。你必须先用某种其他语言（通常是Java或C）构建你的语言的编译器（或解释器）。完成后，您可以使用语言Foo编写编译器的新版本。您使用第一个自举编译器来编译编译器，然后使用这个已编译的编译器来编译其他所有内容（包括其未来版本）。
大多数语言确实是以这种方式创建的，部分原因是语言设计者喜欢使用他们正在创建的语言，另一方面是因为复杂的编译器通常作为衡量语言“完整性”的有用基准。
Scala就是一个例子。其第一个编译器是由Martin Odersky使用实验性语言Pizza创建的。在2.0版本中，编译器完全重写了Scala。从那时起，旧的Pizza编译器可以完全丢弃，因为新的Scala编译器可以用于编译将来的迭代。
- Daniel Spiewak
3
2也许这是一个愚蠢的问题：如果你想将你的编译器移植到另一种微处理器架构上，那么引导应该从该架构的工作编译器重新开始。这是正确的吗？
如果是这样的话，这意味着最好保留第一个编译器，因为它可能对将你的编译器移植到其他架构（特别是如果它是用某种“通用语言”如C编写的）非常有用。 - piertoni
6通常来说，将编译器后端重新定位到新的微处理器上会更加容易。 - bstpierre
1使用LLVM作为后端，例如。 - user985399
80
我记得听过一期软件工程广播节目，Dick Gabriel在其中谈到通过在纸上用LISP编写一个基础的版本，然后手工汇编成机器码，从而引导原始的LISP解释器。 从那时起，其余的LISP功能都是使用LISP编写和解释的。
- Alan
1
1一切都是从一个起源晶体管开始引导的，需要大量的实践操作。 - user985399
49
当你编写第一个C编译器时，你会使用其他语言编写它。现在，你已经有了一个用汇编语言编写的C编译器。最终，你将到达一个地方，需要解析字符串，特别是转义序列。你将编写代码将
在准备好该编译器后，你将开始在C中重新实现它。这个过程称为"引导"
字符串解析代码如下:
当编译完成后，你将得到一个理解'\n'的二进制文件。这意味着你可以更改源代码：
所以 '\n' 是表示 13 的代码在哪里呢？它在二进制代码中！这就像 DNA：使用此二进制文件编译 C 源代码将继承此信息。如果编译器编译自身，则将向其后代传递此知识。从此时起，仅从源代码无法看出编译器将做什么。
如果您想在某个程序的源代码中隐藏病毒，可以采用以下方法：获取编译器的源代码，找到编译函数的函数并将其替换为此函数：
有趣的部分是A和B。A是
B对于我们想要用病毒替换的函数也是一样。例如，它可以是来自Linux内核的源文件“login.c”中的函数“login”。我们可以将其替换为一个版本，该版本将接受“joshua”密码作为root帐户的密码，除了正常的密码之外。
如果您编译它并将其传播为二进制文件，则没有办法通过查看源代码找到病毒。
原始想法来源：https://web.archive.org/web/20070714062657/http://www.acm.org/classics/sep95/
\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对于我们想要用病毒替换的函数也是一样。例如，它可以是来自Linux内核的源文件“login.c”中的函数“login”。我们可以将其替换为一个版本，该版本将接受“joshua”密码作为root帐户的密码，除了正常的密码之外。
如果您编译它并将其传播为二进制文件，则没有办法通过查看源代码找到病毒。
原始想法来源：https://web.archive.org/web/20070714062657/http://www.acm.org/classics/sep95/
- Aaron Digulla
2
1第二部分关于编写带病毒的编译器有什么意义呢？ :) - mhvelplund
7@mhvelplund在传播关于引导法如何危及生命的知识。 - Aaron Digulla
47
在之前的回答中增加一些好奇心。
以下是来自Linux From Scratch手册的一句话，位于从源代码构建GCC编译器的步骤处。(Linux From Scratch是一种安装Linux的方式，它与安装发行版完全不同，因为你必须编译目标系统中的每一个二进制文件。)
make bootstrap'bootstrap'目标不仅编译GCC，而是编译了多次。它使用第一轮编译的程序来第二次编译自己，然后再第三次编译自己。然后比较这些第二次和第三次编译结果，以确保可以无缺陷地再现自己。这也意味着已正确地编译。
使用'bootstrap'目标的原因在于，用于构建目标系统工具链的编译器可能没有完全相同版本的目标编译器。通过这种方式进行操作，可以确保在目标系统中获得一个可以编译自身的编译器。
- Federico Ramponi
2
12“你需要编译目标系统的每一个二进制文件，然而你必须从某个地方得到一个gcc二进制文件开始，因为源代码本身无法编译。我想知道如果你追溯每个被用来重新编译gcc的gcc二进制文件的来源，是否可以追溯到K＆R的原始C编译器？” - robru
@robru 我不知道K&R的过程，我确定这不是它的情况，但从理论上讲，源代码可以从一开始就编译自己。只要你有某个东西或某个人能够正确执行程序并推断出输出应该是什么并将其写下来，你就可以得到一个可执行二进制文件。只是：当你有像Dennis Ritchie这样擅长汇编代码的人可以手工编写汇编代码，然后从那里引导时，为什么还要费心去做呢？ - Marcel Besixdouze
20
你不能使用自身编写编译器，因为没有任何东西可以用于编译起始源代码。解决这个问题有两种方法。
最不受欢迎的方法是：你在汇编语言中（呕吐）编写一个仅支持基本功能的最小编译器，然后使用该编译器来实现该语言的其他特性，逐步构建直到拥有支持自身所有语言特性的编译器。这是一种痛苦的过程，通常只有在没有其他选择时才会这样做。
首选的方法是使用交叉编译器。在不同机器上更改现有编译器的后端，以创建在目标机器上运行的输出。然后您就可以在目标机器上使用完整的编译器了。最流行的语言是C语言，因为有许多现有的编译器具有可插拔的后端，可以进行交换。
一个鲜为人知的事实是GNU C++编译器有一种仅使用C子集的实现。原因在于往往很容易找到新目标机器的C编译器，从而允许您从中构建完整的GNU C++编译器。现在，您已经将自己引导到目标机器上拥有C++编译器了。
- Phil Wright
1
3从技术上讲，你可以手动编译起始源代码。你是否了解C语言足够好，能够阅读一些C源代码并手动跟踪它以确定其输出结果？一个用
foo编写的foo编译器只是另一个foo程序，其输出在这种情况下是机器代码或其他后端代码。理论上来说，如果你有信心能够正确地从规范中推导出输出应该是什么，并且有耐心手动追踪它，你可以开始用foo自己编写第一个foo编译器。 - Marcel Besixdouze15
一般来说，你需要先有一个工作的（即使是原始的）编译器版本，然后才能开始考虑让它自举。在某些语言中，这实际上被认为是一个重要的里程碑。
从我对“mono”的记忆中得知，他们可能需要添加一些内容到反射中使其工作: Mono团队一直指出，使用Reflection.Emit有些事情根本不可能；当然，微软团队可能会证明他们错了。
这有一些真正的优势：首先，它是相当好的单元测试！并且你只需要担心一种语言（即可能C#专家可能不了解很多C++，但现在他们可以修复C#编译器）。但我想知道是否存在一些职业自豪感：他们只是希望它是自主的。
虽然不是编译器，但我最近一直在研究一个自主的系统；代码生成器用于生成代码生成器......所以如果方案发生变化，我只需要在它自身上运行：新版本。如果有错误，我只需回到早期版本并再次尝试。非常方便，也很容易维护。
更新1
我刚看完 Anders 在 PDC 上的这个视频，（大约一个小时后）他给出了一些更加有效的原因，都关于编译器作为服务。仅供参考。
- Marc Gravell
7
我使用SLIC（用于实现编译器的语言系统）编写了SLIC本身，并将其手动编译为汇编语言。 SLIC是一个包含五个子语言的单一编译器，其中包括：
- SYNTAX解析器程序设计语言PPL
- GENERATOR基于LISP 2的树形遍历伪代码生成语言
- ISO按顺序、伪代码、优化语言
- PSEUDO类似宏的汇编代码生成语言。
- MACHOP汇编机器指令定义语言。
SLIC的灵感来自于CWIC（编写和实现编译器的编译器）。与大多数编译器开发包不同，SLIC和CWIC使用专门的领域特定语言处理代码生成。SLIC扩展了CWIC的代码生成功能，增加了ISO、PSEUDO和MACHOP子语言，将目标机器细节从树形遍历代码生成器语言中分离出来。
LISP 2树和列表
基于LISP 2的生成器语言的动态内存管理系统是其关键组成部分。列表在该语言中用方括号表示，其中的组件由逗号分隔，例如三元素[a,b,c]列表。
树:
ADD
/ \
MPY 3
/ \
5 x
- 节点对象是列表的第一个条目表示：
[ADD,[MPY,5,x],3]
树通常显示为节点在分支之前：
ADD[MPY[5,x],3]
LISP 2基于生成器函数的反解析
生成器函数是一个命名的、包含(unparse)=>action>对的集合...
<NAME>(<unparse>)=><action>;
(<unparse>)=><action>;
...
(<unparse>)=><action>;
未解析表达式是一种测试，可以匹配树模式和/或对象类型，将它们拆分并将这些部分分配给本地变量以便通过其过程性动作进行处理。有点像一个接受不同参数类型的重载函数。除了 ()=> ... 测试是按编码顺序尝试的。第一个成功的未解析执行对应的操作。未解析表达式是拆卸测试。ADD [x，y] 匹配两个分支 ADD 树，并将其分支分配给本地变量 x 和 y。操作可以是一个简单的表达式或一个 .BEGIN ... .END 限定代码块。我今天会使用c风格 { ... } 块。树匹配，[]，未解析规则可能调用生成器，并将返回的结果传递到操作：
expr_gen(ADD[expr_gen(x),expr_gen(y)])=> x+y;
上述的expr_gen unparse匹配了一个两枝ADD树。在测试模式中，一个放置在树枝上的单参数生成器将被调用，并用该分支作为其参数。不过其参数列表是本地变量，分配返回对象。上面的unparse指定了一个两枝ADD树的反汇编，递归地按压每个分支到expr_gen。左分支的返回值被放入本地变量x中。同样，右分支传递给expr_gen，返回对象为y。以上内容可能是数字表达式评估器的一部分。这里有一些名为向量的快捷功能，在上述情况下，可以使用节点向量和相应操作的向量，而不是节点字符串。
expr_gen(#node[expr_gen(x),expr_gen(y)])=> #action;
node: ADD, SUB, MPY, DIV;
action: x+y, x-y, x*y, x/y;
(NUMBER(x))=> x;
(SYMBOL(x))=> val:(x);
以上更完整的表达式解析器将expr_gen左分支的返回值赋给x，右分支的返回值赋给y。对于x和y执行相应的操作向量并返回结果。最后的unparse=>action对匹配数字和符号对象。
符号和符号属性
符号可以有命名属性。val:(x)访问包含在x中的符号对象的val属性。一个通用符号表堆栈是SLIC的一部分。SYMBOL表可以被推入和弹出，为函数提供本地符号。新创建的符号被分类到顶层符号表中。符号查找从最上面的符号表开始向下遍历符号表堆栈。生成机器无关代码
SLIC的生成语言生成PSEUDO指令对象，并将它们附加到一个部分的代码列表上。一个.FLUSH 会导致它的PSEUDO代码列表被运行，从列表中删除每个PSEUDO指令并调用它。执行后释放PSEUDO对象的内存。PSEUDO和GENERATOR操作的过程体基本上是相同的语言，除了它们的输出。PSEUDO旨在充当汇编宏，提供机器无关代码的序列化。它们将特定目标机器的分离从树形爬行生成器语言中提供。PSEUDO调用MACHOP函数输出机器码。MACHOP用于定义汇编伪操作（如dc、define constant等）和机器指令或一组格式相似的指令，使用向量入口。它们只是将其参数转换为构成指令的位字段序列。MACHOP调用旨在模仿汇编，并为在编译清单中显示汇编时提供字段的打印格式。在示例代码中，我使用了C风格的注释，这很容易添加，但原始语言中没有。MACHOP正在将代码生成到一个可寻址的位内存中。SLIC链接器处理编译器的输出。使用向量入口的DEC-10用户模式指令的MACHOP：.MACHOP #opnm register,@indirect offset (index): // Instruction's parameters.
.MORG 36, O(18): $/36; // Align to 36 bit boundary print format: 18 bit octal $/36
O(9): #opcd; // Op code 9 bit octal print out
(4): register; // 4 bit register field appended print
(1): indirect; // 1 bit appended print
(4): index; // 4 bit index register appended print
O(18): if (#opcd&&3==1) offset // immediate mode use value else
else offset/36; // memory address divide by 36
// to get word address.
// Vectored entry opcode table:
#opnm := MOVE, MOVEI, MOVEM, MOVES, MOVS, MOVSI, MOVSM, MOVSS,
MOVN, MOVNI, MOVNM, MOVNS, MOVM, MOVMI, MOVMM, MOVMS,
IMUL, IMULI, IMULM, IMULB, MUL, MULI, MULM, MULB,
...
TDO, TSO, TDOE, TSOE, TDOA, TSOA, TDON, TSON;
// corresponding opcode value:
#opcd := 0O200, 0O201, 0O202, 0O203, 0O204, 0O205, 0O206, 0O207,
0O210, 0O211, 0O212, 0O213, 0O214, 0O215, 0O216, 0O217,
0O220, 0O221, 0O222, 0O223, 0O224, 0O225, 0O226, 0O227,
...
0O670, 0O671, 0O672, 0O673, 0O674, 0O675, 0O676, 0O677;
.MORG 36, O(18)：$/36；将位置对齐到36位边界，打印位置$/36的18位八进制字地址。9位opcd、4位寄存器、间接位和4位索引寄存器被合并并打印为单个18位字段。18位地址/36或立即值被输出并以八进制形式打印。以下是一个MOVEI示例，其中r1 = 1，r2 = 2：
400020 201082 000005 MOVEI r1,5(r2)
使用编译器汇编选项，您可以在编译列表中获得生成的汇编代码。
链接在一起
SLIC链接器作为一个库提供，处理链接和符号解析。但是必须为目标机器编写特定的输出加载文件格式，并将其与链接器库一起链接。
生成语言能够将树写入文件并读取它们，从而实现多遍编译器。
代码生成和起源的简要概述
首先我介绍了代码生成，以确保理解SLIC是真正的编译器编译器。SLIC的灵感来自于上世纪60年代后期在Systems Development Corporation开发的CWIC（用于编写和实现编译器的编译器）。 CWIC仅具有SYNTAX和GENERATOR语言，可以从GENERATOR语言产生数字字节码。 字节码被放置或“种植”（CWIC文档中使用的术语）到与命名部分关联的内存缓冲区中，并通过.FLUSH语句写出。ACM对CWIC的论文可从ACM档案馆获取。
成功实现主要编程语言
在1970年代末期，SLIC被用于编写COBOL跨编译器。由一个程序员在大约3个月内完成，我按需与该程序员一起工作。另一个程序员为目标TI-990迷你计算机编写了运行时库和MACHOPs。该COBOL编译器每秒编译的代码行比使用汇编语言编写的DEC-10本地COBOL编译器多得多。
比通常谈论的更多的编译器内容
从零开始编写编译器的一个重要部分是运行时库。您需要一个符号表，需要输入和输出，动态内存管理等。编写运行时库很容易比编写编译器更费力。但是，对于使用SLIC开发的所有编译器，该运行时库都是公共的。请注意，有两个运行时库。一个针对语言（例如COBOL）的目标机器。另一个是编译器编译器的运行时库。
我认为我已经说明了这些不是解析生成器。因此，现在有了一点关于后端的理解，我可以解释解析器编程语言了。
解析器编程语言
解析器是使用以简单方程式形式编写的公式编写的。
<name> <formula type operator> <expression> ;
在语言的最低级别，是字符。记号由该语言的字符子集组成。字符类用于命名和定义这些字符子集。字符类定义运算符是冒号（:）字符。属于该类的字符编码记录在定义的右侧。可打印字符用单引号包括。非打印和特殊字符可以通过它们的数字序数来表示。类成员由可选的 | 运算符分隔。类公式以分号结尾。字符类可以包括先前定义的类：
/* Character Class Formula class_mask */
bin: '0'|'1'; // 0b00000010
oct: bin|'2'|'3'|'4'|'5'|'6'|'7'; // 0b00000110
dgt: oct|'8'|'9'; // 0b00001110
hex: dgt|'A'|'B'|'C'|'D'|'E'|'F'|'a'|'b'|'c'|'d'|'e'|'f'; // 0b00011110
upr: 'A'|'B'|'C'|'D'|'E'|'F'|'G'|'H'|'I'|'J'|'K'|'L'|'M'|
'N'|'O'|'P'|'Q'|'R'|'S'|'T'|'U'|'V'|'W'|'X'|'Y'|'Z'; // 0b00100000
lwr: 'a'|'b'|'c'|'d'|'e'|'f'|'g'|'h'|'i'|'j'|'k'|'l'|'m'|
'n'|'o'|'p'|'q'|'r'|'s'|'t'|'u'|'v'|'w'|'x'|'y'|'z'; // 0b01000000
alpha: upr|lwr; // 0b01100000
alphanum: alpha|dgt; // 0b01101110
skip_class 0b00000001是预定义的，但可以通过定义skip_class来覆盖它。
总之，字符类是一组备选项，只能是字符常量、字符序数或先前定义的字符类。在我实现字符类时：将为类公式分配一个类位掩码。(如上所示的注释)任何包含任何字符字符文字或序数的类公式都会导致分配一个类位。通过将所包括的类的类掩码(如果有)与分配的位进行or运算，得到一个掩码。从字符类创建一个类表。由字符序数索引的条目包含指示字符类成员身份的位。类测试是在线完成的。 IA-86代码示例中eax中的字符序数说明了类测试：
test byte ptr [eax+_classmap],dgt
接下来是:
jne <success>
或者
je <failure>
我使用IA-86指令代码示例，因为我认为现在更广泛地知道IA-86指令。将类名评估为其类掩码，非破坏性地与由字符序数（在eax中）索引的类表进行AND运算。非零结果表示类成员资格。（除包含该字符的al（EAX的低8位）外，EAX被清零）。
在这些旧编译器中，标记有点不同。关键字没有以标记的形式解释。它们只是在解析器语言中通过引用字符串常量进行匹配。引用字符串通常不被保留。可以使用修饰符。+保留匹配的字符串。(例如，+'-'匹配一个-字符，在成功时保留该字符)逗号操作(例如，,'E')将字符串插入标记中。空格由标记公式处理，跳过前导SKIP_CLASS字符，直到第一个匹配。请注意，显式skip_class字符匹配会停止跳过，允许标记以skip_class字符开头。字符串标记公式跳过前导skip_class字符，匹配单引号引用的字符或双引号引用的字符串。有趣的是，在“引用的字符串”中匹配“字符：
string .. (''' .ANY ''' | '"' $(-"""" .ANY | """""","""") '"') MAKSTR[];
第一个替代方案匹配任何单引号引用的字符。右侧的替代方案匹配双引号引用的字符串，该字符串可以使用两个 " 字符来表示一个 " 字符。这个公式定义了它自己定义中使用的字符串。内部右边的替代方案 '"' $(-"""" .ANY | """""","""") '"' 匹配双引号引用的字符串。我们可以使用一个单引号字符来匹配双引号 " 字符。但是，在双引号 " 引用字符串内部，如果我们希望使用 " 字符，则必须使用两个 " 字符才能得到一个。例如，在内部左边的替代方案中匹配除引号之外的任何字符：
-"""" .ANY
使用负向预查-"-""来匹配字符，当成功匹配（不匹配"字符）时，接下来匹配任何字符（因为-"-"排除了这种情况）。正确的替代方案是匹配-"-"来匹配"字符，并且失败是正确的选择。
"""""",""""
尝试匹配两个“字符”，将它们替换为一个双引号，使用, """"插入单个"字符。在两个内部备选项都失败后，关闭字符串引号字符会被匹配，并调用MAKSTR []创建字符串对象。在匹配序列时，使用$序列循环成功的操作符。令牌公式跳过前导跳过类字符（空格）。一旦进行了第一次匹配，跳过类跳过就被禁用了。我们可以使用[]调用在其他语言中编程的函数。MAKSTR []、MAKBIN []、MAKOCT []、MAKHEX []、MAKFLOAT []和MAKINT []是提供的库函数，它们将匹配的标记字符串转换为类型化对象。下面的数字公式说明了一个相当复杂的令牌识别：
number .. "0B" bin $bin MAKBIN[] // binary integer
|"0O" oct $oct MAKOCT[] // octal integer
|("0H"|"0X") hex $hex MAKHEX[] // hexadecimal integer
// look for decimal number determining if integer or floating point.
| ('+'|+'-'|--) // only - matters
dgt $dgt // integer part
( +'.' $dgt // fractional part?
((+'E'|'e','E') // exponent part
('+'|+'-'|--) // Only negative matters
dgt(dgt(dgt|--)|--)|--) // 1 2 or 3 digit exponent
MAKFLOAT[] ) // floating point
MAKINT[]; // decimal integer
上述数字令牌公式可以识别整数和浮点数。备选项始终成功。数字对象可用于计算。成功匹配该公式后，标记对象被推送到解析堆栈中。指数引导符（+'E'|'e','E'）很有意思。我们希望始终使用大写字母E来表示MAKEFLOAT[]。但是我们允许使用小写字母'e'代替它，使用逗号','分隔。
您可能已经注意到了字符类和令牌公式的一致性。解析公式不断添加回溯备选项和树形构造运算符。在表达式级别中，不能混合使用回溯和非回溯备选项运算符。您不能将非回溯|与\混合使用（a | b \ c）。(a\b\c)、(a|b|c)和((a|b)\c)是有效的。 A \回溯备选项在尝试其左侧备选项之前保存解析状态，在失败时还原解析状态以尝试其右侧备选项。在备选项序列中，第一个成功的备选项满足组条件。后续备选项不会尝试。简化和分组提供了连续的高级解析。回溯备选项在尝试其左侧备选项之前创建解析的保存状态。当解析可能进行部分匹配然后失败时，需要回溯。
(a b | c d)\ e
若a返回失败，则尝试进行备选项c d。如果c也失败，则将尝试回溯备选项。如果a成功，但b失败，则会回溯解析并尝试e。同样地，如果c失败而a成功且b失败，则会回溯解析并采用备选项e。回溯不仅限于公式中。如果任何解析公式在任何时间做出了部分匹配，然后失败，则解析将重置到顶部回溯并采用其备选项。如果代码自创建回溯以来已输出，则可能会发生编译失败。在开始编译之前，会设置回溯点。返回失败或回溯到该点属于编译器错误。回溯点是堆叠的。我们可以使用负面的-和正面的？peek/look ahead操作符来测试而不推进解析。being字符串测试只需要保存并重置输入状态的peek ahead。查找将是一个在失败之前先做出部分匹配的解析表达式。查找是使用回溯实现的。
解析器语言既不是LL解析器也不是LR解析器。而是一种用于编写递归下降解析器的编程语言，在其中可以编写树构造程序。
:<node name> creates a node object and pushes it onto the node stack.
.. Token formula create token objects and push them onto
the parse stack.
!<number> pops the top node object and top <number> of parstack
entries into a list representation of the tree. The
tree then pushed onto the parse stack.
+[ ... ]+ creates a list of the parse stack entries created
between them:
'(' +[argument $(',' argument]+ ')'
could parse an argument list. into a list.
一个常用的解析示例是算术表达式：
Exp = Term $(('+':ADD|'-':SUB) Term!2);
Term = Factor $(('*':MPY|'/':DIV) Factor!2);
Factor = ( number
| id ( '(' +[Exp $(',' Exp)]+ ')' :FUN!2
| --)
| '(' Exp ')" )
(^' Factor:XPO!2 |--);
使用循环的Exp和Term会创建一个左手树。使用右递归的Factor会创建一个右手树：
d^(x+5)^3-a+b*c => ADD[SUB[EXP[EXP[d,ADD[x,5]],3],a],MPY[b,c]]
ADD
/ \
SUB MPY
/ \ / \
EXP a b c
/ \
d EXP
/ \
ADD 3
/ \
x 5
这是cc编译器的一部分，更新了带有C风格注释的SLIC版本。函数类型（语法、标记、字符类、生成器、伪指令或机器码）由它们的标识符后面的初始语法确定。使用这些自顶向下的解析器，您可以从定义公式的程序开始：
program = $((declaration // A program is a sequence of
// declarations terminated by
|.EOF .STOP) // End Of File finish & stop compile
\ // Backtrack: .EOF failed or
// declaration long-failed.
(ERRORX["?Error?"] // report unknown error
// flagging furthest parse point.
$(-';' (.ANY // find a ';'. skiping .ANY
| .STOP)) // character: .ANY fails on end of file
// so .STOP ends the compile.
// (-';') failing breaks loop.
';')); // Match ';' and continue
declaration = "#" directive // Compiler directive.
| comment // skips comment text
| global DECLAR[*1] // Global linkage
|(id // functions starting with an id:
( formula PARSER[*1] // Parsing formula
| sequencer GENERATOR[*1] // Code generator
| optimizer ISO[*1] // Optimizer
| pseudo_op PRODUCTION[*1] // Pseudo instruction
| emitor_op MACHOP[*1] // Machine instruction
) // All the above start with an identifier
\ (ERRORX["Syntax error."]
garbol); // skip over error.
// 注意如何将id分解，然后在创建树时再合并。
formula = ("==" syntax :BCKTRAK // backtrack grammar formula
|'=' syntax :SYNTAX // grammar formula.
|':' chclass :CLASS // character class define
|".." token :TOKEN // token formula
)';' !2 // Combine node name with id
// parsed in calling declaration
// formula and tree produced
// by the called syntax, token
// or character class formula.
$(-(.NL |"/*") (.ANY|.STOP)); Comment ; to line separator?
chclass = +[ letter $('|' letter) ]+;// a simple list of character codes
// except
letter = char | number | id; // when including another class
syntax = seq ('|' alt1|'\' alt2 |--);
alt1 = seq:ALT!2 ('|' alt1|--); Non-backtrack alternative sequence.
alt2 = seq:BKTK!2 ('\' alt2|--); backtrack alternative sequence
seq = +[oper $oper]+;
oper = test | action | '(' syntax ')' | comment;
test = string | id ('[' (arg_list| ,NILL) ']':GENCALL!2|.EMPTY);
action = ':' id:NODE!1
| '!' number:MAKTREE!1
| "+[" seq "]+" :MAKLST!1;
// C style comments
comment = "//" $(-.NL .ANY)
| "/*" $(-"*/" .ANY) "*/";
值得注意的是，解析器语言处理注释和错误恢复的方式。
我认为我已经回答了这个问题。在这里，我写了SLIC的继任者——cc语言的大部分内容。目前还没有针对它的编译器。但是我可以手动将其编译为汇编代码、裸的asm c或者c++函数。
- G K
1
你有公共代码仓库或文档吗？我很想看看。 - gust
1
是的，你可以用该语言编写一个编译器。不需要为该语言编写第一个编译器来引导。
你需要引导的是该语言的实现。这可以是编译器或解释器。
从历史上看，语言通常被认为是解释型语言或编译型语言。解释器只针对前者编写，而编译器只针对后者编写。因此，如果要为一种语言编写编译器，通常会先用其他语言编写第一个编译器来引导它，然后再选择性地为该语言重新编写编译器。但是，也可以选择使用其他语言编写解释器。
这不仅仅是理论上的。我目前正在做这件事情。我正在开发一种名为Salmon的语言的编译器。我首先在C中创建了一个Salmon编译器，现在我正在使用Salmon编写编译器，以便在没有使用任何其他语言编写的Salmon编译器的情况下使Salmon编译器正常工作。
- Chris Wilson
1
GNAT，GNU Ada编译器，需要一个Ada编译器来完全构建。当将其移植到没有现成的GNAT二进制文件的平台时，这可能会很麻烦。
- David Holm
1
1我不明白为什么？没有规定你必须每次都引导启动（比如对于每个新平台），你也可以使用当前的平台进行交叉编译。 - Marco van de Voort
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接