《《编译原理实用教程》-杨德芳-电子教案 第11章 目标代码的生成》由会员分享，可在线阅读，更多相关《《编译原理实用教程》-杨德芳-电子教案 第11章 目标代码的生成（87页珍藏版）》请在金锄头文库上搜索。
1、第11章 目标代码的生成,本章学习目标 代码生成工作一般在语法分析后或优化后的中间代码形式上进行，其功能是将这种中间代码的形式转换为某种结果代码的形式。本章主要内容有： 从各种中间代码生成目标代码 代码生成程序的自动构造技术 目标代码生成实例,11.1中间代码生成目标代码,代码生成工作一般在语法分析后的中间代码形式上进行，其功能是将这种中间代码形式转换成某种结果代码形式。常用的结果代码的格式有3种： （1）可以立即执行的机器语言代码，它们通常放在固定的存储区中，编译后可以直接执行。 （2）待装配的机器语言代码，为了这种形式的代码，必须经由连接装配程序将它们与另外一些运行子程序连接装配起来，组成
2、可以执行的机器语言代码。 （3）汇编语言程序，必须通过汇编程序将其汇编成可以执行的机器语言代码。 在3种形式中，最容易生成的是汇编语言程序，它无须生成二进制形式代码，只要生成相应的符号化指令即可。,表11-1假想的计算机中的符号指令,11.1.2从四元式生成代码,在四元式序列中，运算是按照执行顺序排列的，只要顺次扫描四元式，就能逐个生成代码。由于所有的运算都要在累加器中进行，所以，在生成一条代码前，需要知道累加器的内容。为此，引进全局量ACC，它是编译时刻的变量，用以指明运行时刻累加器的状态。ACC为空，则表示运行时累加器为空。若ACC不空，则表示累加器中有变量名和临时变量的值。,过程INAC
3、C有两个参数，功能为：在生成可交换的双边运算（如*，+）指令之前，调用该过程。将其中一个参数放到累加器。对于不可交换的指令（如或），要求将第一个运算量对象放到累加器中。例如，在生成A/B时，先调用INACC(A, )，它生成把A存入累加器的指令。无论在哪种情况下，若累加器当前不为空，则INACC先生成一条保留累加器内容的指令。过程INACC如下：,procedure INACC(A,B) string A,B; begin string T; if ACC=then begin GEN(LD,A); ACC:=A; return end;,if ACC=B then begin T:=A;A:
4、=B;B:=A end else if ACC A then begin GEN(ST,ACC); GEN(LD,A); ACC:=A; end; end;,这里采用的方法是顺序扫描四元式，并逐个生成每个四元式的代码。假定用计数器i控制顺序，并假定第 i个四元式的4个字段分别为（guad(i).OP，guad(i).oper1， guad(i).oper2和guad(i).RESULT表示，即（运算符，第一操作数，第二操作数，运算结果），以下是四元式的代码生成程序，即对：+，-，*，/和单目减中的每个运算分别给出相应代码时，所要调用的代码生成程序。 （1）加法（乘法）四元式的代码生成程序。 I
5、NACC（guad(i).OPER1, guad(i).OPER2）; GEN(ADD，guad(i).OPER2); 或： GEN(MULT，guad(i).OPER2); ACC：= guad(i).RESULT；,（2）减法（除法）四元式的代码生成程序。 INACC（guad(i).OPER1,） GEN(SUB，guad(i).OPER2); GEN(DIV，guad(i).OPER2); ACC：= guad(i).RESULT； （3）单目减四元式的代码生成程序（3）。 INACC（guad(i).OPER1,） GEN(CHS，); ACC：= guad(i).RESULT； 应
6、用这些代码生成程序，表达式A*(A*B+C)-C*D)可以生成如表11-2所示的结果代码。,表11-2表达式生成的目标代码,11.1.3从三元式生成代码,从三元式生成代码需要引进和删除一些临时变量，例如，从三元式3）* X Y 生成代码时，就需要引进代表结果值的临时变量。而且对于最后一个引进三元式（3）的那个三元式，当生成的代码后，代表（3）的结果值的临时变量就不再需要了，应将其删去。假设临时变量的范围是两两不相交或嵌套的，那么，就能使用一个编译时刻栈去保存和删除这些临时变量。否则，管理就会比较复杂，在这里假设每个临时变量仅需要引用一次。,在生成三元式i的代码之前，必须检查两个运算量。如果其中
7、一个运算量引用了前面的三元式，那么就必须用分配给该三元式存放结果值的临时变量名去代替这个运算的对象。这项工作由过程GETTEMP(A，B)来完成。其中A是被检查的运算对象字段，在返回时，B中包含临时变量名或变量名。该过程的编写如下： procedure GETTEMP(A,B) If A 引用三元式 k then begin for i:=j step-1 until 1 do if trip(i)=k then begin B:=TEMP(i); goto out end; out:end else B:=A; end;,当生成三元式i的代码之后，还必须产生一个临时变量，用以描述执行该代码后
8、所得到的值。然后将该临时变量和三元式编号下推到TEMP和TRIP栈中。因为执行刚生成的代码的结果在累加器中，因此要改变累加器的状态。这些工作是由过程NEMTEMP来实现的。,procedure NEWTEMP begin T:=新的临时变量名； j:=j+1; TRIP(j):=i; TEMP(j):=T; ACC:=T end; 为了从三元式生成代码，根据计数器i的值顺次扫描三元式。假定用TR(i).OP、TR(i).OPER1和TR(i).OPER2分别引用第i个三元式的三个字段。此外，由于假设两个临时变量的范围是不相交的或嵌套的，因此，当生成引用临时变量的代码时，相应的临时变量名总是在两
9、个栈顶元素中的某一个之内。即只需要在栈顶元素查找它而无须查找整个栈。下面给出的是从三元式生成代码的程序。,1)加法三元式的代码生成程序 GETTEMP（TR(i).OPER1，Y1）； GETTEMP（TR(i).OPER2，Y2）； INACC（Y1，Y2） GEN（ADD，Y2）； If TR(i).OPER1 引用了三元式 then j:=j-1; If TR(i).OPER2 引用了三元式 then j:=j-1; NEWTEMP;,3)单目减的三元式代码生成程序 GETTEMP（TR(i).OPER1，Y1）； INACC（Y1，）； GEN（CHS，）； If TR(i).OPER
10、1 引用了三元式 then j:=j-1; NEWTEMP；,2)减法三元式的代码生成程序 GETTEMP（TR(i).OPER1，Y1）； GETTEMP（TR(i).OPER2，Y2）； INACC（Y1，）； GEN（SUB，Y2）； If TR(i).OPER1 引用了三元式 then j:=j-1; If TR(i).OPER2 引用了三元式 then j:=j-1; NEWTEMP；,11.1.4从树形表示到生成代码 把单个表达式的i个三元组序列想像成一棵树，并用TR(i)表示根的分支。 例如A*(A*B+C)-C*D)表示成三元式为: （1）* A B （2）+ （1） C （3
11、）* C D （4） （2） （3） （5）* A （4） 表示成树型如图11.2所示：,以前面的表达式A*(A*B+C)-C*D)为例，从三元式生成代码的过程如表11.3所示。 表11.3表达式生成的目标代码,根据有关的动作表，如果TR(i).OPER1和TR(i).OPER2都是变量名，那么先生成一条“LD TR(i)OPER1”指令，再生成一条“ADD TR(i)OPER2”指令。如果OPER1是一个变量，而OPER2是一个以运算符为根的子树，那么，在三元式TR的表中TR(i).OPER2是该根的序号。递归地调用COMP去生成该子树的代码。它将生成一条把相应表达式的值取进累加器的代码。从
12、COMP返回后，将生成一条以OPER1作为运算对象的加法指令。,如果两个运算符都是以运算符为根的子树，则先调用COMP，对第一个运算量生成代码；然后改变运算对象TR(i).OPER1,以表示这个值在累加器中。动作repeat指再一次使用动作表去决定所要做的工作。即执行“TR(i).OPER1=ACC”和“TR(i).OPER1=子树”所指定的动作。此时，产生一个新的临时变量名，生成一条保存累加器内容的ST指令。接着对第二个运算量生成代码，最后生产ADD指令。 表11.5是以上面树型表示为例，给出了调用COMP（5）时所需的动作序列及所生成的代码。 表11-5(c) TR(i).oper1 TR
13、(i).oper2,11.1.5从逆波兰表示生成代码,从左至右顺序扫描逆波兰式表示中的运算符和运算量。当扫描到运算量时，将运算符的名字存入运算量栈中，当扫描到一个二目运算符时，利用栈顶和两个运算量的名字生成相应的代码。生成代码后，就用存放结果值的变量名替代栈顶的两个运算量。 由于二目运算总是使用两个栈顶运算量，因此，如果任一其他栈元素描述了累加器中的内容，那么，在生成二目运算代码前，必须生成一条保存累加器的指令。由此，可以采用另外一种保存累加器内容的方法，即允许栈内容能包含“ACC”，用以指明其值在累加器中。当扫描逆波兰表示式遇到一个运算量的名字时，就做 如下的工作：,(1)若次栈顶元素是“A
14、CC”，那么，产生一个新的临时变量名Ti，生成一条“ST Ti”指令，然后把该名字Ti存入这个栈元素中。 (2)把运算量名下推进栈。 从前面的分析可以看出，对于任何算术运算或逻辑运算，其代码生成的一般过程可以归纳为： （1）生成建立运算量地址的代码。 （2）生成实现任何必要的类型转换的代码。 （3）生成把一运算量取到累加器中的代码。 （4）生成该运算的代码。 根据这个过程，可以设计一个通用的代码生成程序，用以生成所有的算术运算或逻辑运算代码。,11.1.6寄存器的分配,任何计算机系统都有寄存器，但是寄存器的数量是十分有限的。如何合理、有效的使用这些寄存器是编译程序设计中需要重视的问题。寄存器的
15、分配就是在计算一个表达式时，如何使用的寄存器的数目最少。 表达式的内部形式可以用一棵树表示出来，在此基础上另加一遍扫描，顺序扫描该树，对每个运算确定各个运算对象所需要的寄存器的个数。并标记每个运算结点，用以指示首先应该计算的运算对象，然后生成相应的代码。 从另一个角度提出的寄存器分配问题可以描述为：已知n个可以使用的寄存器R1, R2, Rn,，计算表达式如何使所需要的存取指令的条数最少。假定 （1）不允许重新排列子表达式。 （2）每个值必须先取到某个寄存器后才能使用。 那么，当计算一个表达式时，在某一时刻需要使用变量V的值，此时，会出现如下的情况：,（1）该值已经在寄存器Ri中，此时它用这个
16、寄存器。 （2）还没有给V分配寄存器，但此时有空的寄存器，此时把该寄存器分配给该值。 （3）如果没有空闲寄存器，而V需要空闲寄存器，就存起其中一个值，将该值的寄存器分配给V。 应该将哪个值的寄存器释放？把运算次序中下次使用且离现行位置最远的那个寄存器的内容保存起来。,11.2常用的代码生成程序的开发方法,由于代码生成部分与目标计算机硬件的结构紧密相关，这就导致了代码生成的可移植性及自动生成算法的研究和实现比较困难，目前常用的目标生成代码的开发方法有3种。分述如下。 11.2.1 解释性的代码生成法 解释性的代码生成法是建立一个代码生成专用语言，用这种语言以宏定义、子程序等形式描述代码生成结果。通过这些宏定义和子程序把中间语言解释为目标代码。这种方法使机器描述与代码生成算法结合在一起，与机器的联系直接反应在算法中。机器描述是通过过程的形式提供的，如采用把源程序映像成两地址代码序列的方法进行代码生成过程中，加法的代码生成算法如下：,mac
