Part V:语义检查 & 中间代码生成
这次晚了一点...考试真是件可怕的事,它真的妨碍了一些有用的东西.
是的,上次我承诺了结果,你想要得到它们.也许多过你的希望 ;-)
首先是关于这个教程的一个备注.我是想要写一个非常紧凑的解释.所有的信息都在这里,但是常常是每个句子有两个重要的事情..这样作的缺点是是否有些事不大清楚,你可能没有跟上这个教程.当我进行的太快时请告诉我,好让我能够把事情说清楚.
回到这部分.它是关于语义和中间代码的.语义检查将确认你的程序是真正的正确,中间代码将是向虚拟执行(virtual executable)的一个巨大飞跃.
让我们开始检查吧!
语义检查不单单是检查程序语法的正确性,它还要确认语句有意义.例如,提供给函数的参数的个数应该是函数所预期的.
语义检查的主要部分是类型检查:决定表达式的类型和报告任何的不一致,如想要比较一个布尔值和一个字符串,或者传给函数错误的参数.
当然,也许你想要允许某些"不一致":例如有人使用了下面的语句
print "a and b equal: " + (a == b);
他的意思可能是表达式(a == b)应该被自动转换成一个字符串,最后成为字符串"true"或"false".这称为强制类型转换.在我们这个简单的编译器中我只允许布尔到字符串的强制转换,但是如果你认为字符串到布尔的强制转换有用,你可以轻松的加上它.
我们的语义检查器的代码并不复杂.我为TreeNode加了一个名为Check()的成员函数(在synttree.cpp文件中),它检查一个结点的语义,我们假定它的所有孩子结点都已经被检查了.Chech()在TreeNode的构造函数中自动调用,所以这个假定是安全的.
检查设置了一个名为rettype的新成员变量,表达式的"返回类型".例如,一个条件,当一个字符串连接另一个字符串时,布尔是它的返回类型.rettype用来检查父结点的语义.CoerceToString函数通过插入一个作为被强制转换的结点的父结点的新结点,COERCE_TO_STR,来强制转换任何的表达式为字符串类型(如果它还不是).
对一个简单的编译器这是很轻松,但是通常它不是这样.如果你的语言包含更多的基本类型,索引(references),数组,类和(操作符)重载,事情很快就变得非常的可怕;如果你希望你的程序能够运行,那么你最好有一个坚实的检查系统.
在一个真正的编译器中它从事更多的工作:有更多的强制转换,你必须计算出要使用哪个重载函数,类型等价不是再是这么平常,等等.
在这儿它是很简单,并且它对于用更多的类型来膨胀这个系统的学习经验很有用,但是在一些地方你应该更接近一般情况.
代码应该足够说明它们.它只执行一些简单的事,如if条件应该是布尔型,赋值表达式应该是字符串,等等.
中间代码在我们程序中表示为一个有序的图:每一条指令有一个指向下一条指令的指针,跳转有一个指向它的目标指令的指针.
我能想出两个这么做(使用指针)而不是立即产生代码到一个大的数组的两个好处:第一,使用指针便于把代码片段的连接,而且去掉某些指令时不用更新所有的跳转,等等.优化也因此相应的简单了.第二,如果你想要更改虚拟机的一些指令,这使你的编译器更容易改写来适应新的VM,因为你只需改变从中间代码到最终代码的翻译步骤,这相对的简单.
于是,基于上面的思想,我们设计了我们的中间代码语言.这个语言的操作码(opcode)将与我们的虚拟机要执行的即使不完全一致也是十分的相似.看一下它们:
enum Opcode {
OP_NOP, // no operation
OP_PUSH, // push string [var]
OP_GETTOP, // get string from top of stack (=assign) [var]
OP_DISCARD, // discard top value from the stack
OP_PRINT, // print a string
OP_INPUT, // input a string [var]
OP_JMP, // unconditional jump [dest]
OP_JMPF, // jump if false [dest]
OP_STR_EQUAL, // test whether two strings are equal
OP_BOOL_EQUAL, // test whether two bools are equal
OP_CONCAT, // concatenate two strings
OP_BOOL2STR, // convert bool to string
JUMPTARGET // not an opcode but a jump target;
// the target field points to the jump instruction
};
你将看到我们的VM是一个堆栈机器(a stack machine):操作码对堆栈中的值进行操作,把值放回堆栈.我想对产生代码和执行代码来说这是都最简单的机器类型了.
一个关于JUMPTARGET操作码的说明:每当我们的代码中有一个(条件)跳转时,它并不指向一条实际的指令而是指向一个有"JUMPTARGET"前缀的指令.这么做的原因是当我们优化时我们必须知道代码中的每个跳转的目的指针,或者我们也许会把一条目的指令优化掉并且混乱(mess
up)我们的程序.这些JUMPTARGET将不出现再我们最终的字节码中.
一般而言,所有的操作码操作堆栈顶端的项目.OP_STR_EQUAL从堆栈中弹出顶端的两个项目(必须是字符串),检查它们是否相等,然后把结果的布尔值进栈.你的程序接着可以使用OP_JMPF指令来使用这个结果:如果栈顶的布尔值是false跳转到目标指令(由本指令提供,而不是在栈中),如果栈顶是true就继续执行.
指令被存储到一个非常简单的中间指令类中,它只是保存操作码,一个符号--操作数(例如OP_INPUT),如果需要还有一个跳转目的指令,一个下一指令指针和一个行号.行号实际上只是在使用Show()函数时使代码可读.
现在让我们看看如何产生中间代码(intcode.cpp).通常我们为语法树中的所有子树产生代码.所以main以树根来调用GenIntCode()函数;GenIntCode处理并且返回一个中间代码的起始指针.
先看个简单的例子,INPUT_STMT结点:
case INPUT_STMT:
return new IntInstr (OP_INPUT, root->symbol);
这产生一个新的OP_INPUT指令并且返回它.注意这个指令也是一个长度为1的指令块(block
of instructions) ,next指针默认为NULL.
PRINT_STMT更困难一点:
case PRINT_STMT:
blk1 = GenIntCode (root->child[0]);
blk2 = new IntInstr (OP_PRINT);
return Concatenate (blk1, blk2);
首先我们产生代码来计算表达式提供给print语句(root->child[0]).接着我们产生一个新指令OP_PRINT来打印栈顶的字符串.注意我们假设表达式把它的值放到栈顶.当然,我们得自己来保证这一点.最后我们连接两个代码块,然后返回结果.
现在是一个真正难的:IFTHEN_STMT.我产生所有需要的块,然后把它们都连到一起.它检查条件,如果它是false调换到结尾,如果它是true就执行then部分.
case IFTHEN_STMT:
// First, create the necessary code parts
cond = GenIntCode (root->child[0]);
jump2end = new IntInstr (OP_JMPF); // set target below
thenpart = GenIntCode (root->child[1]);
endif = new IntInstr (JUMPTARGET, jump2end);
jump2end->target = endif;
// Now, concatenate them all
Concatenate (cond, jump2end);
Concatenate (jump2end, thenpart);
Concatenate (thenpart, endif);
return cond;
记住root->child[0]是条件子树,root->child[1]是then子树.
好的,如果明白了那个,对与剩余的代码你就没问题了.所有树的结点都使用这个方法翻译.Show()函数显示我们产生的代码.看一下所有这些:
Program:
if (a==b) a; else b;
Intermediate code:
1: OP_NOP
2: OP_PUSH a
3: OP_PUSH b
4: OP_STR_EQUAL
5: OP_JMPF 9
6: OP_PUSH a
7: OP_DISCARD
8: OP_JMP 12
9: JUMPTARGET 5
10: OP_PUSH b
11: OP_DISCARD
12: JUMPTARGET 8
这看上去非常的象汇编代码,是吧?这是因为它就是.它是虚拟汇编(Virtual
Assembly),本质上我们只需要写一个汇编程序来产生虚拟执行代码.
那进行的很快,不是吗?刚才我们还想我们是否将作一些有趣的事,突然我们就产生了虚拟汇编代码.我们几乎完成了.
下次我们将看一下优化(我确信如果你观察这部分的输出你能想到一些).很快我们将产生真正的虚拟机代码--但是我猜我们最好先有一个虚拟机!我们将看到从那我们去哪里.欢迎你发给我一些想法或建议.
Bottom line: some interesting stuff is coming up. Stay tuned!
See you next time.
The story so far:
In the beginning the Universe was created.
This has made a lot of people very angry and been widely regarded as a bad move.
HHG 2:1
Download the tutorial code (tut5.zip) (10k)
返回目录
diamond Garden制作 2000年1月