编译第七章语法制导翻译课件.ppt

1、精选PPT1第七章语法制导翻第七章语法制导翻译和中间代码生成译和中间代码生成精选PPT2第一节第一节 概述概述v 语法分析之后，编译的任务是由已识别为正确的源程语法分析之后，编译的任务是由已识别为正确的源程序生成一组规格一致，便于计算机加工的指令形式。序生成一组规格一致，便于计算机加工的指令形式。一、中间代码生成方法一、中间代码生成方法语法制导翻译，属性文法制导翻译语法制导翻译，属性文法制导翻译二、中间代码二、中间代码中间代码：不是机器语言，便于生成机器语言，便于代中间代码：不是机器语言，便于生成机器语言，便于代码优化。码优化。中间代码的形式：中间代码的形式：-逆波兰式逆波兰式-树形表示法树形

2、表示法-三元式三元式-四元式：最常用的形式四元式：最常用的形式第七章中间代码的生成 1精选PPT3第一节第一节 概述概述v二、翻译方法二、翻译方法1 1、语法制导翻译、语法制导翻译-在语法分析的基础上进行边分析边翻译。在语法分析的基础上进行边分析边翻译。注：注：1 1）语法制导翻译时会根据文法产生式右部符）语法制导翻译时会根据文法产生式右部符号串的含义进行翻译，翻译的结果是生成相应中间号串的含义进行翻译，翻译的结果是生成相应中间代码。代码。2 2）语法制导翻译的依据是语义子程序。）语法制导翻译的依据是语义子程序。3 3）具体做法：为每个产生式配置一个语义子程序，）具体做法：为每个产生式配置一个

3、语义子程序，当语法分析进行归约或推导时，调用语义子程序，当语法分析进行归约或推导时，调用语义子程序，完成一部分翻译任务。完成一部分翻译任务。4 4）语法分析完成，翻译工作也告结束。）语法分析完成，翻译工作也告结束。第七章中间代码的生成 2精选PPT4第一节第一节 概述概述v二、翻译方法二、翻译方法1 1、语法制导翻译、语法制导翻译-语法制导翻译适用于多种语法分析语法制导翻译适用于多种语法分析-语法制导翻译种类语法制导翻译种类1 1、自上而下语法制导翻译：对每个文法符号配以、自上而下语法制导翻译：对每个文法符号配以语义动作。语义动作。2 2、自下而上语法制导翻译：我们主要讨论、自下而上语法制导翻

4、译：我们主要讨论LRLR语法语法制导翻译制导翻译第七章中间代码的生成 3精选PPT5第一节第一节 概述概述v三、语义子程序三、语义子程序1 1、作用、作用用来描述一个产生式所对应的翻译工作。用来描述一个产生式所对应的翻译工作。-如：改进某些变量的值；查填各种符号表；发现如：改进某些变量的值；查填各种符号表；发现并报告源程序错误；产生中间代码等。并报告源程序错误；产生中间代码等。注；这些翻译工作很大程度上决定了要产生什么形注；这些翻译工作很大程度上决定了要产生什么形式的中间代码式的中间代码精选PPT6v三、语义子程序三、语义子程序2 2、写法、写法语义子程序写在该产生式后面的花括号内。语义子程序

5、写在该产生式后面的花括号内。X X a a 语义子程序语义子程序 注：在一个产生式中同一个文法符号可能出现多次，但它们注：在一个产生式中同一个文法符号可能出现多次，但它们代表的是不同的语义值，要区分可以加上角标。代表的是不同的语义值，要区分可以加上角标。如：如：E EE E(1)(1)+E+E(2)(2)3 3、语义值、语义值为了描述语义动作，需要为每个文法符号赋予不同的语义值：为了描述语义动作，需要为每个文法符号赋予不同的语义值：类型，地址，代码值等。类型，地址，代码值等。第一节第一节 概述概述精选PPT7第一节第一节 概述概述v三、语义子程序三、语义子程序4 4、语义栈、语义栈各个符号的语

6、义值放在语义栈中各个符号的语义值放在语义栈中-当产生式进行归约时，需对产生式右部符号的语义值进行当产生式进行归约时，需对产生式右部符号的语义值进行综合，综合，其结果作为左部符号的语义值保存到语义栈中。其结果作为左部符号的语义值保存到语义栈中。下推栈包含下推栈包含3 3部分：部分：-状态栈、符号栈和语义栈状态栈、符号栈和语义栈-注：语义栈与状态栈和符号栈是同步变化的。注：语义栈与状态栈和符号栈是同步变化的。精选PPT8第一节第一节 概述概述v三、语义子程序三、语义子程序注：注：1 1）若把语义子程序改成产生某种中间代）若把语义子程序改成产生某种中间代码的动作，就能在语法分析制导下，随着分码的动作

7、，就能在语法分析制导下，随着分析的进展逐步生成中间代码。析的进展逐步生成中间代码。2 2）若把语义子程序改成产生某种机器的）若把语义子程序改成产生某种机器的汇编语言指令，就能随着分析的进展逐步生汇编语言指令，就能随着分析的进展逐步生成某机器的汇编语言代码。成某机器的汇编语言代码。精选PPT9第一节第一节 概述概述v例如：例如：v产生式产生式 语义子程序语义子程序v(0)S E PRINT E(0)S E PRINT E VALVALv(1)E E(1)E E(1)(1)+E+E(2)(2)E EVAL=E(1)VAL=E(1)VAL+E(2)VAL+E(2)VALVALv(2)E E(2)E

8、E(1)(1)*E E(2)(2)E EVAL=E(1)VAL=E(1)VALVAL*E(2)E(2)VALVALv(3)E (E(3)E (E(1)(1)E)EVAL=E(1)VAL=E(1)VALVALv(4)E i E(4)E i EVAL=LEXVALVAL=LEXVALv注：注：LEXVALLEXVAL指的是词法分析送来的机内二进制整数。指的是词法分析送来的机内二进制整数。精选PPT10v下推栈SmE(2)E(2).VALSm-1+E(1)E(1).VAL.S0#状态符号VAL(语义）精选PPT11第一节第一节 概述概述v注：由于语义值是放在语义栈中的，它也可以用栈顶指针注：由于语义

9、值是放在语义栈中的，它也可以用栈顶指针TOPTOP指出，语义子程序改写为：指出，语义子程序改写为：v产生式产生式 语义子程序语义子程序v(0)S E PRINT VALTOP(0)S E PRINT VALTOPv(1)E E(1)E E(1)(1)+E+E(2)(2)VALTOP=VALTOP+VALTOP+2 VALTOP=VALTOP+VALTOP+2v(2)E E(2)E E(1)(1)*E E(2)(2)VALTOP=VALTOP VALTOP=VALTOP*VALTOP+2VALTOP+2v(3)E (E(3)E (E(1)(1)VALTOP=TOP+1)VALTOP=TOP+1v

10、(4)E i VALTOP=LEXVAL(4)E i VALTOP=LEXVALv注：注：LEXVALLEXVAL指的是词法分析送来的机内二进制整数。指的是词法分析送来的机内二进制整数。精选PPT12第一节第一节 概述概述v例如：分析输入串例如：分析输入串(7+9)(7+9)*5#,5#,并给出它的计算过程。并给出它的计算过程。分析表如下：分析表如下：精选PPT13状态状态ACTIONGOTOi+*()#S0S3S211S4S5acc2S3 S2 63r4r4r4r4 4S3S275S3S2 8 6S4 S5 S9 7 r1(S4)S5(r1)r1r1 8r1(S4)r2(S5)r2r2 9

11、r3 r3r3r3精选PPT14步骤步骤状态状态SYMSYMVALVALINPUTINPUTACTIONACTION1 10 0#-(7+9)(7+9)*5#5#2 20,20,2#(#(-7+9)7+9)*5#5#移进移进3 30,2,30,2,3#(7#(7-+9)+9)*5#5#移进移进4 40,2,60,2,6#(E#(E-7-7+9)+9)*5#5#r r4 45 50,2,6,40,2,6,4#(E+#(E+-7-7-9)9)*5#5#移进移进6 60,2,6,4,30,2,6,4,3#(E+9#(E+9-7-7-)*5#5#移进移进7 70,2,6,4,70,2,6,4,7#(E

12、+E#(E+E-7-9-7-9)*5#5#r r4 48 80,2,60,2,6#(E#(E-16-16)*5#5#r r1 19 90,2,6,90,2,6,9#(E)#(E)-16-16-*5#5#移进移进10100,10,1#E#E-16-16*5#5#r r3 311110,1,50,1,5#E#E*-16-16-5#5#移进移进精选PPT15第一节第一节 概述概述四、常见的中间代码形式四、常见的中间代码形式1.1.四元式形式四元式形式（Operator,Operand1,Operand2,Result)Operator,Operand1,Operand2,Result)注：注：1 1

13、）Operand1,Operand2,ResultOperand1,Operand2,Result可能是用户自定义的变可能是用户自定义的变量，也可能是编译时引进的变量，这里量，也可能是编译时引进的变量，这里OperatorOperator是双目运算是双目运算符，若只有一个运算量，则是单目运算符。符，若只有一个运算量，则是单目运算符。2 2）四元式中变量采用符号表入口的地址，而不用变良的）四元式中变量采用符号表入口的地址，而不用变良的地址，因为语义分析不仅需要变量的地址，还需要从符号表地址，因为语义分析不仅需要变量的地址，还需要从符号表查到的变量的属性，类型和地址等。查到的变量的属性，类型和地址

14、等。精选PPT16第一节第一节 概述概述v四、常见的中间代码形式四、常见的中间代码形式v2.2.三元式三元式v（Operator,Operand1,Operand2Operator,Operand1,Operand2）v注：注：1 1）这里三元式本身作为存放结果的单元。）这里三元式本身作为存放结果的单元。2 2）为了在其它三元式中利用当前三元式的结果，）为了在其它三元式中利用当前三元式的结果，需要对三元式进行遍号。三元式的编号就作为相应需要对三元式进行遍号。三元式的编号就作为相应三元式的结果值。三元式的结果值。精选PPT17第一节第一节 概述概述v四、常见的中间代码形式四、常见的中间代码形式v

15、3 3、后缀表示式（逆波兰表示式）、后缀表示式（逆波兰表示式）vOperand1 Operand2 OperatorOperand1 Operand2 Operatorv4 4、树型表示法、树型表示法OperatorOperand2Operand1注：常用中间代码表示法是四元式注：常用中间代码表示法是四元式精选PPT18第二节第二节 简单算术表达式和赋值语句的翻译简单算术表达式和赋值语句的翻译v一、赋值语句的翻译赋值语句的翻译v-仅含简单变量的表达式和赋值语句的翻译仅含简单变量的表达式和赋值语句的翻译v1 1、赋值语句的文法、赋值语句的文法v A i=EA i=Ev E E+E|E E E+E

16、|E*E|-E|(E)|iE|-E|(E)|iv2 2、需要的语义过程、需要的语义过程vNEWTEMONEWTEMO函数：每次使用送回一个代表新临时变量的函数：每次使用送回一个代表新临时变量的序号，可认为是送回序号，可认为是送回T1,T2T1,T2这样的一些临时变量；这样的一些临时变量；vENTRY(i)ENTRY(i)函数：用于查变量函数：用于查变量i i的符号表入口地址；的符号表入口地址；vGEN(OP,ARG1,ARG2,RESULT)GEN(OP,ARG1,ARG2,RESULT)过程：产生一个四元式，过程：产生一个四元式，并填入四元式序列表并填入四元式序列表精选PPT19第二节第二节

17、 简单算术表达式和赋值语句的翻译简单算术表达式和赋值语句的翻译v一、赋值语句的翻译一、赋值语句的翻译v3 3、需要的语义变量、需要的语义变量vE EPLACE:PLACE:与非终结符与非终结符E E相联系的语义变量相联系的语义变量v-值为某变量的符号表入口地址或临时变量值为某变量的符号表入口地址或临时变量序号。序号。v-它与文法的非终结符相联，分析过程就建它与文法的非终结符相联，分析过程就建立，不需要就消亡。立，不需要就消亡。精选PPT20v产生式产生式 语义子程序语义子程序v(1)A i=E GEN(=,E(1)A i=E GEN(=,EPLACE,_,ENTRY(i)PLACE,_,ENT

18、RY(i)v(2)E -E(2)E -E(1)(1)T=NEWTEMP;T=NEWTEMP;v-GEN(,E-GEN(,E(1)(1)PLACE,_,T);PLACE,_,T);v-E-EPLACE=TPLACE=Tv(3)E E(3)E E(1)(1)*E E(2)(2)T=NEWTEMP;T=NEWTEMP;v GEN(GEN(*,E,E(1)(1)PLACE,EPLACE,E(2)(2)PLACE,T);PLACE,T);v E EPLACE=TPLACE=Tv(4)E E(4)E E(1)(1)+E+E(2)(2)T=NEWTEMP;T=NEWTEMP;v GEN(+,E GEN(+,

19、E(1)(1)PLACE,EPLACE,E(2)(2)PLACE,T);PLACE,T);v E EPLACE=TPLACE=Tv(5)E (E(5)E (E(1)(1)E)EPLACE=EPLACE=E(1)(1)PLACEPLACEv(6)E i E(6)E i EPLACE=ENTRY(i)PLACE=ENTRY(i)精选PPT21输入符号串SYM栈PLACE栈生成四元式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)

20、#i=E*(-T1-+D)#i=E*(i-T1-C+D)#i=E*(E-T1-C精选PPT22v注：注：1 1、符号栈是为了介绍才列出的，实际上不存、符号栈是为了介绍才列出的，实际上不存在。在。v2 2、由于语义分析是在语法分析的过程中进行的，、由于语义分析是在语法分析的过程中进行的，所以状态栈实际上是需要的，这里没有写出来。所以状态栈实际上是需要的，这里没有写出来。v3 3、这个分析过程是针对整型变量做的。实际上在、这个分析过程是针对整型变量做的。实际上在一个表达式中，可能出现各种不同类型的变量或常一个表达式中，可能出现各种不同类型的变量或常量，所以，编译程序要么拒绝接受某种混合运算，量，所

21、以，编译程序要么拒绝接受某种混合运算，要么能产生有关类型转换的指令。要么能产生有关类型转换的指令。精选PPT23第二节第二节 简单算术表达式和赋值语句的翻译简单算术表达式和赋值语句的翻译v类型转换类型转换v对于表达式文法中的对于表达式文法中的i i是实型又可以是整型。是实型又可以是整型。v对这种混合运算，我们要先把整型量转化为实型量，就需要对这种混合运算，我们要先把整型量转化为实型量，就需要为每个非终结符的语义值添加类型信息，用为每个非终结符的语义值添加类型信息，用E EMODEMODE表示非终表示非终结符结符E E的类型信息。的类型信息。v1 1、定义各非终结符的类型信息、定义各非终结符的类

22、型信息v产生式产生式E EE E(1)(1)op Eop E(2)(2)的语义动作中要加入关于的语义动作中要加入关于E EMODEMODE的语的语义规则的定义；义规则的定义；v-IF E-IF E(1)(1)MODE=int AND EMODE=int AND E(2)(2)MODE=intMODE=intv-IF E-IF EMODE=int ELSE EMODE=int ELSE EMODE=rMODE=r精选PPT24第二节第二节 简单算术表达式和赋值语句的翻译简单算术表达式和赋值语句的翻译v2 2、对运算量进行类型转换、对运算量进行类型转换v例如：例如：X=Y+IX=Y+I*J,J,其

23、中其中X,YX,Y是实型，是实型，I,JI,J是整型。是整型。v其四元式为：其四元式为：v-(-(*I,I,J,TI,I,J,T1 1)v-(itr,T-(itr,T1 1,_,T,_,T2 2)v-(+r,Y,T-(+r,Y,T2 2,T,T3 3)v-(=,T-(=,T3 3,_,X),_,X)精选PPT25第二节第二节 简单算术表达式和赋值语句的翻译简单算术表达式和赋值语句的翻译v注：注：1)1)对运算符也要指出相应的类型（运算对运算符也要指出相应的类型（运算符上加角标），说明是定点还是浮点远算。符上加角标），说明是定点还是浮点远算。v2)2)由于非终结符由于非终结符E E的语义值有的语

24、义值有E EPLACEPLACE和和E EMODEMODE两个，这两者都要保存在语义栈中。两个，这两者都要保存在语义栈中。v3)3)在运算量的类型较多的情况下，需要仔细在运算量的类型较多的情况下，需要仔细推敲语义规则，否则语义子程序会变置累赘推敲语义规则，否则语义子程序会变置累赘不填。不填。精选PPT26第三节第三节 布尔表达式的翻译布尔表达式的翻译v一、布尔表达式在程序设计语言中的作用布尔表达式在程序设计语言中的作用v-用作控制语句中的条件表达式用作控制语句中的条件表达式v-用于逻辑赋值语句中布尔表达式演算用于逻辑赋值语句中布尔表达式演算v二、布尔表达式的组成二、布尔表达式的组成v-由布尔算

25、符作用于布尔变量（或常量）或关系表由布尔算符作用于布尔变量（或常量）或关系表达式而形成的。达式而形成的。v-布尔算符：布尔算符：,v-关系表达式的形式：关系表达式的形式：E E(1)(1)rop Erop E(2)(2),其中其中roprop是关是关系运算符（如系运算符（如,=,=,=,),E,=,=,=,),E(1)(1)和和E E(2)(2)是算术是算术表达式。表达式。精选PPT27第三节第三节 布尔表达式的翻译布尔表达式的翻译v三、三、布尔表达式的文法：布尔表达式的文法：v-G(B):E EE|EE|E|(E)|i|Ea rop Ea-G(B):E EE|EE|E|(E)|i|Ea ro

26、p Eav-i-i为布尔变量或常量；为布尔变量或常量；EaEa为算术表达式。为算术表达式。v注：注：1)1)此文法为二义文法，一般布尔算符的优先顺序此文法为二义文法，一般布尔算符的优先顺序为：为：,服从左结合律；关系运算优先级别高于布尔运服从左结合律；关系运算优先级别高于布尔运算。算。v 2)2)由于布尔表达式有两种用途，所以有两种不同的翻译由于布尔表达式有两种用途，所以有两种不同的翻译方法。方法。精选PPT28第三节第三节 布尔表达式的翻译布尔表达式的翻译v四、布尔表达式在逻辑演算中的翻译布尔表达式在逻辑演算中的翻译v1 1、语义子程序、语义子程序v由于布尔表达式演算与算术表达式计算非常由于

27、布尔表达式演算与算术表达式计算非常类似，可以仿照算术表达式的翻译方法，为类似，可以仿照算术表达式的翻译方法，为每个产生式写出语义子程序。每个产生式写出语义子程序。精选PPT29v 产生式产生式 语义子程序语义子程序v(1)E E(1)E Ea a(1)(1)ropEropEa a(2)(2)T=NEWTEMP;T=NEWTEMP;v GEN(rop,E GEN(rop,Ea a(1)(1)PLACE,EPLACE,Ea a(2)(2)PLACE,T);PLACE,T);v E EPLACE=TPLACE=Tv(2)E E(2)E Ea a(1)(1)bopEbopEa a(2)(2)T=NEW

28、TEMP;T=NEWTEMP;GEN(bop,E GEN(bop,Ea a(1)(1)PLACE,EPLACE,Ea a(2)(2)PLACE,T);PLACE,T);v E EPLACE=TPLACE=Tv(3)E E(3)E E(1)(1)T=NEWTEMP;T=NEWTEMP;v GEN(,E GEN(,E(1)(1)PLACE,_,T);PLACE,_,T);v E EPLACE=TPLACE=Tv(4)E (E(4)E (E(1)(1)E)EPLACE=EPLACE=E(1)(1)PLACEPLACEv(5)E i E(5)E i EPLACE=ENTRY(i)PLACE=ENTRY

29、(i)精选PPT30第三节第三节 布尔表达式的翻译布尔表达式的翻译v四、布尔表达式在逻辑演算中的翻译布尔表达式在逻辑演算中的翻译v2 2、实例：对布尔式、实例：对布尔式X+YZA(BC)X+YZA(BC)进行翻进行翻译：译：v解：语法制导翻译是在语法分析下的过程中进行的，解：语法制导翻译是在语法分析下的过程中进行的，若利用若利用G(B)G(B)文法的文法的LRLR分析表对上句进行分析表对上句进行LRLR分析，在分析，在其过程中进行语义分析；则得到对上句进行其过程中进行语义分析；则得到对上句进行LRLR分析，分析，在其过程中进行语义分析；则得到的四元式序列是：在其过程中进行语义分析；则得到的四元

30、式序列是：v-(+,X,Y,T-(+,X,Y,T1 1);E+E);E+E进行归约，识别了算术运算进行归约，识别了算术运算v-(,T-(,T1 1,Z,T,Z,T2 2);EE);EE进行归约，识别了关系运算进行归约，识别了关系运算v-(,B,_,T-(,B,_,T3 3);E);E归约归约v-(,T-(,T3 3,C,T,C,T4 4);EE);EE进行归约进行归约v-(-(,A,TA,T4 4,T,T5 5););E EE E进行归约进行归约v-(-(,T T2 2,T,T5 5,T,T6 6););EEEE进行归约进行归约精选PPT31第三节第三节 布尔表达式的翻译布尔表达式的翻译v注：

31、上面的翻译质量并不高，可以采取某种优化措注：上面的翻译质量并不高，可以采取某种优化措施：施：v例如：例如：v对对AB.AB.若已知若已知A A的值是的值是1.1.那么那么 B B的值就不需要知道的值就不需要知道就能得出就能得出AB=1AB=1；v-可以表示为：可以表示为：IF A THEN TRUE ELSE BIF A THEN TRUE ELSE Bv对对ABAB若已知若已知A A的值是的值是0 0，那么，那么B B的值就不需要知道的值就不需要知道就错得出就错得出AB=0AB=0；v-可以表示为：可以表示为：IF A THEN FALSE ELSE TRUE IF A THEN FALSE

32、 ELSE TRUE精选PPT32第三节第三节 布尔表达式的翻译布尔表达式的翻译v五、控制语句中布尔式的翻译五、控制语句中布尔式的翻译v1 1、控制语句中布尔式并不需要计算表达式的值，、控制语句中布尔式并不需要计算表达式的值，只用只用if-then-elseif-then-else来解释来解释,以来控制以来控制程序流向。程序流向。vIf E then SIf E then S1 1 else S else S2 2 E的代码序列S1 1的代码序列S2 2的代码序列假假真真精选PPT33第三节第三节 布尔表达式的翻译布尔表达式的翻译v五、控制语句中的布尔式的翻译五、控制语句中的布尔式的翻译v2

33、2、控制语句中的布尔式的翻译的四元式为以下三、控制语句中的布尔式的翻译的四元式为以下三种：种：v(juz,A(juz,A1 1,_,P,_,P -if A -if A1 1 then goto P then goto P (j (jQ Q,A,A1 1,A,A2 2,-if A -if A1 1Q QA A2 2 then goto P then goto P (j,_,_,P)(j,_,_,P)-Goto P -Goto P注：这些四元式都是转移四元式，其中注：这些四元式都是转移四元式，其中P P为出口的四为出口的四元式序号，与元式序号，与E E的真假值相对应的分别为真出口和的真假值相对应的

34、分别为真出口和假出口两类四元式。假出口两类四元式。精选PPT34v例如：把语句例如：把语句if ABD then Sif ABD then S1 1 else S else S2 2翻译成四翻译成四元式元式v解解:(1)(jnz,A,_,(5);:(1)(jnz,A,_,(5);真出口真出口;若若A A为真为真,执行执行S S1 1代码代码v(2)(j,_,(3);(2)(j,_,(3);若若A A为假，看为假，看右边的表达式值右边的表达式值v(3)(j,B,D,(5);(3)(j,B,D,(5);真出口真出口,右边的表达式值为真右边的表达式值为真v(4)(j,_,_,(p+1);(4)(j,

35、_,_,(p+1);假出口假出口,右边的表达式值为假右边的表达式值为假v(5)S(5)S1 1语句的第一个四元式语句的第一个四元式v.v(p)(j,_,_,(q);(p)(j,_,_,(q);执行完执行完S S1 1代码后跳过代码后跳过S S2 2代码段代码段v(p+1)S(p+1)S2 2语句的第一个四元式语句的第一个四元式v.v(q)(q)此语句的后继语句此语句的后继语句精选PPT35第三节第三节 布尔表达式的翻译布尔表达式的翻译v五、控制语句中布尔式的翻译五、控制语句中布尔式的翻译v4 4、增加语义值、增加语义值vE ETCTC、E EFCFC的值也可以放在语义栈中，即下推栈又的值也可以

36、放在语义栈中，即下推栈又增加了两栏增加了两栏.E(1).S0#_SSYMPLACETCFC分析栈分析栈语义栈语义栈精选PPT36第三节第三节 布尔表达式的翻译布尔表达式的翻译v五、控制语句中布尔式的翻译五、控制语句中布尔式的翻译v5 5、文法、文法G(B)G(B)各产生式的语义子程序各产生式的语义子程序v-文法：文法：E EE EA AE|EE|E0 0E|E|(E)|i|EE|E|(E)|i|Ea aropEropEa av E EA A E Ev E E0 0 E Ev语义子程序：语义子程序：v-(1)E i E-(1)E i ETC=NXQ;ETC=NXQ;EFC=NXQ+1;FC=NX

37、Q+1;v-GEN(jnz,ENTRY(i),_,O);-GEN(jnz,ENTRY(i),_,O);v-GEN(j,_,_,O)-GEN(j,_,_,O)v-注：将布尔型操作数进行归约，产生两个四元式；注：将布尔型操作数进行归约，产生两个四元式；v无论真假都不知该转到哪个四元式上去，故转向无论真假都不知该转到哪个四元式上去，故转向0 0精选PPT37v例如：将控制语句中的例如：将控制语句中的ABD ABD v翻译成四元式翻译成四元式v解解:(1)(jnz,A,_,0);:(1)(jnz,A,_,0);真出口；真出口；v (2)(j,_,_,0);(2)(j,_,_,0);若若A A为假为假,

38、看看右边的表达右边的表达式的值式的值v TC:1;TC:1;v FC:2;FC:2;精选PPT38第三节第三节 布尔表达式的翻译布尔表达式的翻译v五、控制语句中布尔式的翻译五、控制语句中布尔式的翻译v5 5、文法、文法G(B)G(B)各产生式的语义子程序各产生式的语义子程序v(7)E(7)E0 0 E E(1)(1)v-BACKPATCH(E-BACKPATCH(E(1)(1)FC,NXQ);FC,NXQ);v-E-E0 0TC=ETC=E(1)(1)TC;TC;v注：对注：对进行归约之后，若进行归约之后，若E E(1)(1)=0,=0,则则运算的结果运算的结果就要看就要看右边式子的值了，所以

39、表示右边式子的值了，所以表示E E(1)(1)=0=0的四元的四元式应转移到式应转移到归约后的下一个四元式，即判断归约后的下一个四元式，即判断右右边式子的值的第一个四元式。边式子的值的第一个四元式。精选PPT39第三节第三节 布尔表达式的翻译布尔表达式的翻译v五、控制语句中布尔式的翻译五、控制语句中布尔式的翻译v5 5、文法、文法G(B)G(B)各产生式的语义子程序各产生式的语义子程序vPROCEDURE BACKPATCH(p,t)PROCEDURE BACKPATCH(p,t)vQ=P;Q=P;vWHILE(Q0)WHILE(Q0)vq=q=四元式四元式Q Q第四段的内容；第四段的内容；v

40、 把把t t填入四元式填入四元式Q Q的第四段；的第四段；v Q=q;Q=q;v注：其算法思想是：从链头算起，边找边读，直到注：其算法思想是：从链头算起，边找边读，直到链尾为止。链尾为止。精选PPT40v例如：将控制语句中的例如：将控制语句中的ABD ABD v翻译成四元式翻译成四元式v解解:(1)(jnz,A,_,0);:(1)(jnz,A,_,0);真出口；真出口；v (2)(j,_,_,(3);(2)(j,_,_,(3);若若A A为假，看为假，看右边的表右边的表达式的值达式的值v E E0 0TC:1;TC:1;vFCFC已回填已回填精选PPT41第三节第三节 布尔表达式的翻译布尔表达

41、式的翻译v五、控制语句中布尔式的翻译五、控制语句中布尔式的翻译v5 5、文法、文法G(B)G(B)各产生式的语义子程序各产生式的语义子程序 (2)E E(2)E Ea aropEropEa a-E ETC=NXQ;ETC=NXQ;EFC=NXQ+1;FC=NXQ+1;-GEN(jrop,E-GEN(jrop,Ea a(1)(1)PLACE,PLACE,E Ea a(2)(2)PLACE,0);PLACE,0);-GEN(j,_,_,0)-GEN(j,_,_,0)精选PPT42v例如：将控制语句中的例如：将控制语句中的ABD ABD v翻译成四元式翻译成四元式v解解:(1)(jnz,A,_,0)

42、;:(1)(jnz,A,_,0);真出口真出口v (2)(j,_,_,(3);(2)(j,_,_,(3);若若A A为假为假,看看右边的表达式值右边的表达式值v (3)(j,B,D,0);(3)(j,B,D,0);真出口真出口,右边的表达式值为真右边的表达式值为真v (4)(j,_,_,0);(4)(j,_,_,0);假假出口出口,右边的表达式值为假右边的表达式值为假vE ETC:3;TC:3;vE EFC:4;FC:4;精选PPT43第三节第三节 布尔表达式的翻译布尔表达式的翻译v五、控制语句中布尔式的翻译五、控制语句中布尔式的翻译v5 5、文法、文法G(B)G(B)各产生式的语义子程序各产

43、生式的语义子程序v(8)E E(8)E E0 0E E(2)(2)v-E EFC=EFC=E(2(2)FC;FC;v-E-ETC=MERG(ETC=MERG(E0 0TC,ETC,E(2)(2)TCTCv注：由于注：由于E E的真假决定于的真假决定于E E(2)(2)为假时它们的转移相同；为假时它们的转移相同；由于由于E E(1)(1)或或E E(2)(2)为真时都导致问真，所以它们为真的为真时都导致问真，所以它们为真的情况要合并起来。情况要合并起来。精选PPT44v例如：将控制语句中的例如：将控制语句中的ABD ABD v翻译成四元式翻译成四元式v解解:(1)(jnz,A,_,0);:(1)

44、(jnz,A,_,0);真出口真出口v (2)(j,_,_,(3);(2)(j,_,_,(3);若若A A为假为假,看看右边的表达式值右边的表达式值v (3)(j,B,D,0);(3)(j,B,D,0);真出口真出口,右边的表达式值为真右边的表达式值为真v (4)(j,_,_,0);(4)(j,_,_,0);假假出口出口,右边的表达式值为假右边的表达式值为假vE ETC:3TC:3，1;1;vE EFC:4;FC:4;精选PPT45vFUNCTION MERG(PFUNCTION MERG(P1 1,P,P2 2););vIF PIF P2 2=0=0v MERG=P MERG=P1 1vWH

45、ILE WHILE 四元式四元式P P的第的第4 4段内容不为段内容不为0 0v P=P=四元式四元式P P的第的第4 4段内容；段内容；v 把把P P1 1填进四元式填进四元式P P的第四段；的第四段；v MERG=PMERG=P2 2;v注：算法思想：找到注：算法思想：找到P P2 2的链尾，然后将的链尾，然后将P P1 1连接到连接到P P2 2的链尾。的链尾。精选PPT46第三节第三节 布尔表达式的翻译布尔表达式的翻译v(3)E (E(3)E (E(1)(1)E)ETC=ETC=E(1(1)TC;ETC;EFC=EFC=E(1(1)FCFCv(4)E E(4)E E(1)(1)E ET

46、C=ETC=E(1(1)FC;EFC;EFC=EFC=E(1(1)FCFCv(5)E(5)EA A E E(1)(1)v-BACKPATCH(E-BACKPATCH(ETC,NXQ);TC,NXQ);v-E-EA AFC=EFC=E(1)(1)FC;FC;v(6)E E(6)E EA AE E(2)(2)v-E-ETC=ETC=E(1)(1)TC;TC;v-E EFC=MERG(EFC=MERG(EA AFC,EFC,E(2)(2)FCFC精选PPT47第三节第三节 布尔表达式的翻译布尔表达式的翻译v五、控制语句中布尔式的翻译五、控制语句中布尔式的翻译v例如：将布尔式例如：将布尔式AB CAB

47、 C在语法制导下翻译成四元式。在语法制导下翻译成四元式。INPUTINPUTSYMSYMTCTCFCFC四元式四元式AB C#AB C#-B C#B C#i#i-B C#B C#E#E-1-1-2-21.(jnz,a,_,(3)1.(jnz,a,_,(3)B C#B C#E#E-1-1-2-2-2.(j,_,_.(5)2.(j,_,_.(5)B C#B C#E#EA A-2-2 C#C#E#EAiAi-2-2-精选PPT48INPUTINPUTSYMSYMTCTCFCFC四元式四元式 C#C#E#EA AE E-3-3-24-243.(jnz,B,_,0)3.(jnz,B,_,0)C#C#E#

48、E-3-3-4-44.(j,_,_,(5)4.(j,_,_,(5)C#C#E#E-3-3-4-4-C#C#E#E0 0-3-3-C#C#E#E0 0-3-3-#E#E0 0 i i-3-3-#E#E0 0 E E-3-5-3-5-6-65.(jnz,C,_,0)5.(jnz,C,_,0)#E E0 0E E-36-36-5-55.(j,_,_,(3)5.(j,_,_,(3)#E#E-6-6-5-5成功成功精选PPT49第四节第四节 控制语句的翻译控制语句的翻译v一、控制语句的种类：控制语句的种类：v无条件转换语句无条件转换语句v条件语句条件语句v迭代语句迭代语句v循环语句循环语句v分支语句分支

49、语句精选PPT50第四节第四节 控制语句的翻译控制语句的翻译v二、标号和转移语句二、标号和转移语句(GOTO)(GOTO)v1 1、标号和转移语句、标号和转移语句(GOTO)(GOTO)v(1)(1)标号语句标号语句v-GOTO-GOTO语句实现无条件转移，要确定转移的目的语句，需语句实现无条件转移，要确定转移的目的语句，需要给语句加标号。要给语句加标号。v-带标号的语句形式：带标号的语句形式：L:SL:SvL L是标号是标号v(2)(2)标号的定义和使用：标号的定义和使用：v-先定义后使用先定义后使用 L:S.GOTO LL:S.GOTO Lv-先使用后定义先使用后定义 GOTO LL:SG

50、OTO LL:S精选PPT51第四节第四节 控制语句的翻译控制语句的翻译v2 2、先定义后使用、先定义后使用v(1)(1)形式：形式：L:SL:Sv-.-.v-GOTO L-GOTO Lv-.-.v(2)(2)定义和使用表号的文法定义和使用表号的文法v-S goto L-S goto Lv-Label i:-Label i:v(3)(3)翻译过程：翻译过程：v-当遇到定义性的标号语句时，将当遇到定义性的标号语句时，将L L归约为归约为LabelLabel，再将再将L L填入符号表，如下：填入符号表，如下：精选PPT52NAMENAMEINFORMATIONINFORMATIONCATCAT.定