《编译第七章语法制导翻译》由会员分享，可在线阅读，更多相关《编译第七章语法制导翻译（108页珍藏版）》请在金锄头文库上搜索。
1、第七章语法制导翻 译和中间代码生成第一节 概述v 语法分析之后，编译的任务是由已识别为正确的源程 序生成一组规格一致，便于计算机加工的指令形式。 一、中间代码生成方法 语法制导翻译，属性文法制导翻译 二、中间代码 中间代码：不是机器语言，便于生成机器语言，便于代 码优化。 中间代码的形式： -逆波兰式 -树形表示法 -三元式 -四元式：最常用的形式 第七章中间代码的生成 1第一节 概述v二、翻译方法 1、语法制导翻译 -在语法分析的基础上进行边分析边翻译。 注：1）语法制导翻译时会根据文法产生式右部符号 串的含义进行翻译，翻译的结果是生成相应中间代 码。 2）语法制导翻译的依据是语义子程序。
2、3）具体做法：为每个产生式配置一个语义子程序， 当语法分析进行归约或推导时，调用语义子程序， 完成一部分翻译任务。 4）语法分析完成，翻译工作也告结束。第七章中间代码的生成 2第一节 概述v二、翻译方法 1、语法制导翻译 -语法制导翻译适用于多种语法分析 -语法制导翻译种类 1、自上而下语法制导翻译：对每个文法符号配以语 义动作。2、自下而上语法制导翻译：我们主要讨论LR语法制 导翻译 第七章中间代码的生成 3第一节 概述v三、语义子程序 1、作用 用来描述一个产生式所对应的翻译工作。 -如：改进某些变量的值；查填各种符号表；发现并 报告源程序错误；产生中间代码等。 注；这些翻译工作很大程度上
3、决定了要产生什么形 式的中间代码v三、语义子程序 2、写法 语义子程序写在该产生式后面的花括号内。X a语义子程序 注：在一个产生式中同一个文法符号可能出现多次，但它们 代表的是不同的语义值，要区分可以加上角标。 如： E E(1)+E(2) 3、语义值 为了描述语义动作，需要为每个文法符号赋予不同的语义值 ：类型，地址，代码值等。第一节 概述第一节 概述v三、语义子程序 4、语义栈 各个符号的语义值放在语义栈中 -当产生式进行归约时，需对产生式右部符号的语义值进行 综合， 其结果作为左部符号的语义值保存到语义栈中。 下推栈包含3部分： -状态栈、符号栈和语义栈 -注：语义栈与状态栈和符号栈是
4、同步变化的。第一节 概述v三、语义子程序 注：1）若把语义子程序改成产生某种中间代码 的动作，就能在语法分析制导下，随着分析 的进展逐步生成中间代码。2）若把语义子程序改成产生某种机器的汇 编语言指令，就能随着分析的进展逐步生成 某机器的汇编语言代码。第一节 概述v例如：v产生式 语义子程序v(0)S E PRINT E VALv(1)E E(1) +E(2) EVAL=E(1)VAL+E(2)VALv(2)E E(1) * E(2) EVAL=E(1)VAL*E(2)VALv(3)E (E(1) EVAL=E(1)VALv(4)E i EVAL=LEXVALv注：LEXVAL指的是词法分析送
5、来的机内二进制整数。v下推栈SmE(2)E(2).VALSm-1+E(1)E(1).VAL.S0#状态符号VAL(语义）第一节 概述v注：由于语义值是放在语义栈中的，它也可以用栈顶指针 TOP指出，语义子程序改写为： v产生式 语义子程序v(0)S E PRINT VALTOPv(1)E E(1) +E(2) VALTOP=VALTOP+VALTOP+2v(2)E E(1) * E(2) VALTOP=VALTOP*VALTOP+2v(3)E (E(1) VALTOP=TOP+1v(4)E i VALTOP=LEXVALv注：LEXVAL指的是词法分析送来的机内二进制整数。第一节 概述v例如：
6、分析输入串(7+9)*5#,并给出它的计算过程。 分析表如下：状态态ACTIONGOTO i+*( )#S 0S3S21 1S4S5acc 2S3 S2 6 3r4r4r4r4 4S3S27 5S3S2 8 6S4 S5 S9 7 r1(S4) S5(r1) r1r1 8r1(S4) r2(S5) r2r2 9 r3 r3r3r3步骤状态SYMVALINPUTACTION 10#-(7+9)*5# 20,2#(-7+9)*5#移进 30,2,3#(7-+9)*5#移进 40,2,6#(E-7+9)*5#r4 50,2,6,4#(E+-7-9)*5#移进 60,2,6,4,3#(E+9-7-)*
7、5#移进 70,2,6,4,7#(E+E-7-9)*5#r4 80,2,6#(E-16)*5#r1 90,2,6,9#(E)-16-*5#移进 100,1#E-16*5#r3 110,1,5#E*-16-5#移进第一节 概述四、常见的中间代码形式 1.四元式形式 （Operator,Operand1, Operand2, Result) 注：1）Operand1, Operand2, Result可能是用户自定义的变 量，也可能是编译时引进的变量，这里Operator是双目运算 符，若只有一个运算量，则是单目运算符。2）四元式中变量采用符号表入口的地址，而不用变良的 地址，因为语义分析不仅需要
8、变量的地址，还需要从符号表 查到的变量的属性，类型和地址等。第一节 概述v四、常见的中间代码形式v2.三元式v（Operator,Operand1, Operand2）v注：1）这里三元式本身作为存放结果的单元。2）为了在其它三元式中利用当前三元式的结果 ，需要对三元式进行遍号。三元式的编号就作为相 应三元式的结果值。第一节 概述v四、常见的中间代码形式v3、后缀表示式（逆波兰表示式）vOperand1 Operand2 Operatorv4、树型表示法OperatorOperand2Operand1注：常用中间代码表示法是四元式第二节 简单算术表达式和赋值语句的翻译v一、赋值语句的翻译v-仅
9、含简单变量的表达式和赋值语句的翻译v1、赋值语句的文法v A i=Ev E E+E|E*E|-E|(E)|iv2、需要的语义过程vNEWTEMO函数：每次使用送回一个代表新临时变量的 序号，可认为是送回T1,T2这样的一些临时变量；vENTRY(i)函数：用于查变量i的符号表入口地址；vGEN(OP,ARG1,ARG2,RESULT)过程：产生一个四元式 ，并填入四元式序列表第二节 简单算术表达式和赋值语句的翻译v一、赋值语句的翻译v3、需要的语义变量vEPLACE:与非终结符E相联系的语义变量v-值为某变量的符号表入口地址或临时变量 序号。v-它与文法的非终结符相联，分析过程就建 立，不需要
10、就消亡。v产生式 语义子程序v(1)A i=E GEN(=,EPLACE,_,ENTRY(i)v(2)E -E(1) T=NEWTEMP;v- GEN(,E(1)PLACE,_,T);v- EPLACE=Tv(3)E E(1)*E(2) T=NEWTEMP;v GEN(*,E(1)PLACE,E(2)PLACE,T);v EPLACE=Tv(4)E E(1)+E(2) T=NEWTEMP;v GEN(+,E(1)PLACE,E(2)PLACE,T) ;v EPLACE=Tv(5)E (E(1) EPLACE=E(1)PLACEv(6)E i EPLACE=ENTRY(i) 输入符号串SYM栈P
11、LACE栈生成四元式 A=-B*(C+D)# =-B*(C+D)#i- -B*(C+D)#i=- B*(C+D)#i=- *(C+D)#i=-i- *(C+D)#i=-E-B *(C+D)#i=E-T1(,B,-,T1) (C+D)#i=E*-T1- C+D)#i=E*(-T1- +D)#i=E*(i-T1-C +D)#i=E*(E-T1-Cv注：1、符号栈是为了介绍才列出的，实际上不存在 。v2、由于语义分析是在语法分析的过程中进行的，所 以状态栈实际上是需要的，这里没有写出来。v3、这个分析过程是针对整型变量做的。实际上在一 个表达式中，可能出现各种不同类型的变量或常量 ，所以，编译程序要
12、么拒绝接受某种混合运算，要 么能产生有关类型转换的指令。第二节 简单算术表达式和赋值语句的翻译v类型转换v对于表达式文法中的i是实型又可以是整型。v对这种混合运算，我们要先把整型量转化为实型量，就需要 为每个非终结符的语义值添加类型信息，用EMODE表示非终 结符E的类型信息。v1、定义各非终结符的类型信息v产生式E E(1)op E(2)的语义动作中要加入关于EMODE的语 义规则的定义；v-IF E(1)MODE=int AND E(2)MODE=intv-IF EMODE=int ELSE EMODE=r第二节 简单算术表达式和赋值语句的翻译v2、对运算量进行类型转换v例如：X=Y+I*
13、J,其中X,Y是实型，I,J是整型。v其四元式为：v-(*I,I,J,T1)v-(itr,T1,_,T2)v-(+r,Y,T2,T3)v-(=,T3,_,X)第二节 简单算术表达式和赋值语句的翻译v注：1)对运算符也要指出相应的类型（运算 符上加角标），说明是定点还是浮点远算。v2)由于非终结符E的语义值有EPLACE和EMODE 两个，这两者都要保存在语义栈中。v3)在运算量的类型较多的情况下，需要仔细 推敲语义规则，否则语义子程序会变置累赘 不填。第三节 布尔表达式的翻译v一、布尔表达式在程序设计语言中的作用v-用作控制语句中的条件表达式v-用于逻辑赋值语句中布尔表达式演算v二、布尔表达式
14、的组成v-由布尔算符作用于布尔变量（或常量）或关系表 达式而形成的。v-布尔算符：, v-关系表达式的形式： E(1)rop E(2),其中rop是关系 运算符（如,=,), E(1)和E(2)是算术表达 式。第三节 布尔表达式的翻译v三、布尔表达式的文法：v-G(B):E EE|EE| E|(E)|i|Ea rop Eav-i为布尔变量或常量；Ea为算术表达式。v注：1)此文法为二义文法，一般布尔算符的优先顺序为： ,服从左结合律；关系运算优先级别高于布尔运算。v 2)由于布尔表达式有两种用途，所以有两种不同的翻译 方法。第三节 布尔表达式的翻译v四、布尔表达式在逻辑演算中的翻译v1、语义子程序v由于布尔表达式演算与算术表达式计算非常 类似，可以仿照算术表达式的翻译方法，为 每个产生式写出语义子程序。v 产生式 语义子程序v(1)E Ea(1)ropEa(2) T=NEWTEMP;v GEN(rop,Ea(1)PLACE,Ea(2)PLACE,T);v EPLACE=Tv(2)E Ea(1)bopEa(2) T=NEWTEMP;GEN(bop,Ea(1)P
