直观上来看,对于语言Foo
的编译器不能用Foo自身来编写。更具体地说,第一个Foo
编译器不能用Foo自身写出来,但是任何后续的编译器都可以用Foo
编写。
但这是真的吗?我非常模糊地记得读过一种语言,其第一个编译器是用“它本身”编写的。这是否可能,如果可能,又是如何实现的呢?
直观上来看,对于语言Foo
的编译器不能用Foo自身来编写。更具体地说,第一个Foo
编译器不能用Foo自身写出来,但是任何后续的编译器都可以用Foo
编写。
但这是真的吗?我非常模糊地记得读过一种语言,其第一个编译器是用“它本身”编写的。这是否可能,如果可能,又是如何实现的呢?
这被称为“自举”。你必须先用某种其他语言(通常是Java或C)构建你的语言的编译器(或解释器)。完成后,您可以使用语言Foo编写编译器的新版本。您使用第一个自举编译器来编译编译器,然后使用这个已编译的编译器来编译其他所有内容(包括其未来版本)。
大多数语言确实是以这种方式创建的,部分原因是语言设计者喜欢使用他们正在创建的语言,另一方面是因为复杂的编译器通常作为衡量语言“完整性”的有用基准。
Scala就是一个例子。其第一个编译器是由Martin Odersky使用实验性语言Pizza创建的。在2.0版本中,编译器完全重写了Scala。从那时起,旧的Pizza编译器可以完全丢弃,因为新的Scala编译器可以用于编译将来的迭代。
我记得听过一期软件工程广播节目,Dick Gabriel在其中谈到通过在纸上用LISP编写一个基础的版本,然后手工汇编成机器码,从而引导原始的LISP解释器。 从那时起,其余的LISP功能都是使用LISP编写和解释的。
\n
转换为具有十进制代码10的字符(\r
转换为13等)。...
if (c == 92) { // backslash
c = getc();
if (c == 110) { // n
return 10;
} else if (c == 92) { // another backslash
return 92;
} else {
...
}
}
...
...
if (c == '\\') {
c = getc();
if (c == 'n') {
return '\n';
} else if (c == '\\') {
return '\\';
} else {
...
}
}
...
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" ...
}
compileFunction
的源代码,包括病毒,可能以某种方式进行了加密,因此从搜索结果二进制文件中不容易发现。这确保了使用自身编译编译器时会保留病毒注入代码。在之前的回答中增加一些好奇心。
以下是来自Linux From Scratch手册的一句话,位于从源代码构建GCC编译器的步骤处。(Linux From Scratch是一种安装Linux的方式,它与安装发行版完全不同,因为你必须编译目标系统中的每一个二进制文件。)
make bootstrap
'bootstrap'目标不仅编译GCC,而是编译了多次。它使用第一轮编译的程序来第二次编译自己,然后再第三次编译自己。然后比较这些第二次和第三次编译结果,以确保可以无缺陷地再现自己。这也意味着已正确地编译。
使用'bootstrap'目标的原因在于,用于构建目标系统工具链的编译器可能没有完全相同版本的目标编译器。通过这种方式进行操作,可以确保在目标系统中获得一个可以编译自身的编译器。
你不能使用自身编写编译器,因为没有任何东西可以用于编译起始源代码。解决这个问题有两种方法。
最不受欢迎的方法是:你在汇编语言中(呕吐)编写一个仅支持基本功能的最小编译器,然后使用该编译器来实现该语言的其他特性,逐步构建直到拥有支持自身所有语言特性的编译器。这是一种痛苦的过程,通常只有在没有其他选择时才会这样做。
首选的方法是使用交叉编译器。在不同机器上更改现有编译器的后端,以创建在目标机器上运行的输出。然后您就可以在目标机器上使用完整的编译器了。最流行的语言是C语言,因为有许多现有的编译器具有可插拔的后端,可以进行交换。
一个鲜为人知的事实是GNU C++编译器有一种仅使用C子集的实现。原因在于往往很容易找到新目标机器的C编译器,从而允许您从中构建完整的GNU C++编译器。现在,您已经将自己引导到目标机器上拥有C++编译器了。
foo
编写的foo
编译器只是另一个foo
程序,其输出在这种情况下是机器代码或其他后端代码。理论上来说,如果你有信心能够正确地从规范中推导出输出应该是什么,并且有耐心手动追踪它,你可以开始用foo
自己编写第一个foo
编译器。 - Marcel Besixdouze一般来说,你需要先有一个工作的(即使是原始的)编译器版本,然后才能开始考虑让它自举。在某些语言中,这实际上被认为是一个重要的里程碑。
从我对“mono”的记忆中得知,他们可能需要添加一些内容到反射中使其工作: Mono团队一直指出,使用Reflection.Emit
有些事情根本不可能;当然,微软团队可能会证明他们错了。
这有一些真正的优势:首先,它是相当好的单元测试!并且你只需要担心一种语言(即可能C#专家可能不了解很多C++,但现在他们可以修复C#编译器)。但我想知道是否存在一些职业自豪感:他们只是希望它是自主的。
虽然不是编译器,但我最近一直在研究一个自主的系统;代码生成器用于生成代码生成器......所以如果方案发生变化,我只需要在它自身上运行:新版本。如果有错误,我只需回到早期版本并再次尝试。非常方便,也很容易维护。
我刚看完 Anders 在 PDC 上的这个视频,(大约一个小时后)他给出了一些更加有效的原因,都关于编译器作为服务。仅供参考。
我使用SLIC(用于实现编译器的语言系统)编写了SLIC本身,并将其手动编译为汇编语言。 SLIC是一个包含五个子语言的单一编译器,其中包括:
SLIC的灵感来自于CWIC(编写和实现编译器的编译器)。与大多数编译器开发包不同,SLIC和CWIC使用专门的领域特定语言处理代码生成。SLIC扩展了CWIC的代码生成功能,增加了ISO、PSEUDO和MACHOP子语言,将目标机器细节从树形遍历代码生成器语言中分离出来。
基于LISP 2的生成器语言的动态内存管理系统是其关键组成部分。列表在该语言中用方括号表示,其中的组件由逗号分隔,例如三元素[a,b,c]列表。
树:
ADD
/ \
MPY 3
/ \
5 x
[ADD,[MPY,5,x],3]
树通常显示为节点在分支之前:
ADD[MPY[5,x],3]
生成器函数是一个命名的、包含(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);
.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
:<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
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) "*/";
是的,你可以用该语言编写一个编译器。不需要为该语言编写第一个编译器来引导。
你需要引导的是该语言的实现。这可以是编译器或解释器。
从历史上看,语言通常被认为是解释型语言或编译型语言。解释器只针对前者编写,而编译器只针对后者编写。因此,如果要为一种语言编写编译器,通常会先用其他语言编写第一个编译器来引导它,然后再选择性地为该语言重新编写编译器。但是,也可以选择使用其他语言编写解释器。
这不仅仅是理论上的。我目前正在做这件事情。我正在开发一种名为Salmon的语言的编译器。我首先在C中创建了一个Salmon编译器,现在我正在使用Salmon编写编译器,以便在没有使用任何其他语言编写的Salmon编译器的情况下使Salmon编译器正常工作。