第6章 语法制导翻译和中间代码生成

1、天津财经大学信息科学与技术系第六章第六章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成学习目标：学习目标：v掌握：掌握：常见语法成分的中间代码形式；常见语法成分的中间代码形式；常见语法成分的属性文法或翻译方法常见语法成分的属性文法或翻译方法v理解：理解：属性文法、语法制导翻译方法属性文法、语法制导翻译方法天津财经大学信息科学与技术系主要内容主要内容属性文法和语法制导翻译：属性文法和语法制导翻译：属性文法属性文法语法制导翻译基本思想语法制导翻译基本思想中间代码的表示形式（逆波兰式、四元中间代码的表示形式（逆波兰式、四元式、三元式、间接三元式、树结构等等）式、三元式、间接三元式、树结构等等

2、）简单算术表达式和赋值语句的翻译简单算术表达式和赋值语句的翻译布尔表达式到四元式的翻译布尔表达式到四元式的翻译控制结构翻译成四元式控制结构翻译成四元式天津财经大学信息科学与技术系目标程序目标程序源程序源程序词法分析词法分析语法分析语法分析语义分析语义分析中间代码生成中间代码生成代码优化代码优化目标代码生成目标代码生成表格管理表格管理出错处理出错处理天津财经大学信息科学与技术系语义分析基础语义分析基础n语义分析的内容语义分析的内容主要是类型相容检查，有以下几种：主要是类型相容检查，有以下几种：1)各种条件表达式的类型是不是各种条件表达式的类型是不是boolean型？型？2)运算符的分量类型是否相

3、容？运算符的分量类型是否相容？3)赋值语句的左右部的类型是否相容？赋值语句的左右部的类型是否相容？4)形参和实参的类型是否相容形参和实参的类型是否相容?5)下标表达式的类型是否为所允许的类型？下标表达式的类型是否为所允许的类型？6)函数说明中的函数类型和返回值的类型是否一函数说明中的函数类型和返回值的类型是否一致？致？天津财经大学信息科学与技术系语义分析基础语义分析基础-语义分析的内容（续）语义分析的内容（续）其它语义检查：其它语义检查：1)VE中的中的V是不是变量，而且是数组类型？是不是变量，而且是数组类型？2)V.i中的中的V是不是变量，而且是记录类型？是不是变量，而且是记录类型？i是是不

4、是该记录的域名？不是该记录的域名？3)x+f()中的中的f是不是函数名？形参个数和实参是不是函数名？形参个数和实参个数是否一致？个数是否一致？4)每个使用性标识符是否都有声明？有无标识每个使用性标识符是否都有声明？有无标识符的重复声明？符的重复声明？天津财经大学信息科学与技术系语义分析基础语义分析基础在语义分析同时产生中间代码，在这种模式下，在语义分析同时产生中间代码，在这种模式下，语义分析的主要功能如下：语义分析的主要功能如下：语义审查语义审查在扫描声明部分时构造标识符的符号表在扫描声明部分时构造标识符的符号表在扫描语句部分时产生中间代码在扫描语句部分时产生中间代码中间代码：中间代码：独立于

5、机器，复杂性介于源语言和机独立于机器，复杂性介于源语言和机器语言之间，十分接近目标机器指令的一种表示器语言之间，十分接近目标机器指令的一种表示形式。形式。对于中间代码的产生，是很困难的，因为语义形式化对于中间代码的产生，是很困难的，因为语义形式化比语法形式化难得多。目前普遍采用的比语法形式化难得多。目前普遍采用的语义分析方法语义分析方法语法制导翻译语法制导翻译方法方法使用使用属性文法属性文法为工具来说明程序设计语言的语义。为工具来说明程序设计语言的语义。天津财经大学信息科学与技术系6.1属性文法属性文法(Attribute Grammar) )属性属性对文法的每一个符号，引进一些属性，这些属性

6、对文法的每一个符号，引进一些属性，这些属性代表与文法符号相关的信息，如类型、值、存储代表与文法符号相关的信息，如类型、值、存储位置等。位置等。n语义规则语义规则为文法的每一个产生式配备的计算属性的计算规为文法的每一个产生式配备的计算属性的计算规则，称为语义规则。则，称为语义规则。n属性文法属性文法是带属性的一种文法是带属性的一种文法它的主要思想：它的主要思想：首先对于每个文法符号引进相关的属性符号；首先对于每个文法符号引进相关的属性符号；其次对于每个产生式写出计算属性值的语义规则其次对于每个产生式写出计算属性值的语义规则天津财经大学信息科学与技术系6.1 属性文法属性文法(续续)属性文法的形式

7、定义属性文法的形式定义一个属性文法是一个三元组一个属性文法是一个三元组,A,A(G, V, F)(G, V, F)G G是一个上下文无关文法；是一个上下文无关文法；V V是属性的有穷集；是属性的有穷集；F F是关于属性的断言的有穷集。是关于属性的断言的有穷集。说明：说明：1.1.每个每个属性属性与文法符号相联，与文法符号相联，N.tN.t表示文法符号表示文法符号N N的的属性属性t t。属性值属性值又称又称语义值语义值。存储属性值的变量。存储属性值的变量又称又称语义变量语义变量。2.2.每个断言与文法的某个产生式相联，写在每个断言与文法的某个产生式相联，写在 内。内。属性的断言又称属性的断言又

8、称语义规则语义规则，它所描述的工作可以，它所描述的工作可以包括属性计算、静态语义检查、符号表的操作、包括属性计算、静态语义检查、符号表的操作、代码生成等，有时写成函数或过程段。代码生成等，有时写成函数或过程段。天津财经大学信息科学与技术系6.1 属性文法属性文法(续续)例例 完成类型检查的属性文法完成类型检查的属性文法1)1)E ET T1 1+T+T2 2TT1 1.t.tint int AND TAND T2 2.t.tintint 2)2)E ET T1 1 or T or T2 2TT1 1.t.tbool bool AND TAND T2 2.t.tboolbool 3)3)T Tn

9、umnumT.t :T.t :intint 4)4)T TtruetrueT.t :T.t :boolbool 5)5)T TfalsefalseT.t :T.t :boolbool天津财经大学信息科学与技术系6.1 属性文法属性文法(续续)属性的分类：属性的分类：1.1.综合属性：综合属性：从语法树的角度来看，如果一个结点的某一从语法树的角度来看，如果一个结点的某一属性值是由该结点的子结点的属性值计算来属性值是由该结点的子结点的属性值计算来的，则称该属性为综合属性。的，则称该属性为综合属性。内在属性是综合属性。内在属性是综合属性。用于用于“自下而上自下而上”传递信息传递信息天津财经大学信息科

10、学与技术系6.1 属性文法属性文法(续续)2.2.继承属性继承属性从语法树的角度来看，若一个结点的某一属从语法树的角度来看，若一个结点的某一属性值是由该结点的兄弟结点和（或）父结点性值是由该结点的兄弟结点和（或）父结点的属性值计算来的，则称该属性为继承属性。的属性值计算来的，则称该属性为继承属性。用于用于“自上而下自上而下”传递信息传递信息特别说明：特别说明：v终结符终结符只有综合属性，它们由词法分析器提供只有综合属性，它们由词法分析器提供v非终结符非终结符既有综合属性也有继承属性，但既有综合属性也有继承属性，但文法开文法开始符始符没有继承属性没有继承属性天津财经大学信息科学与技术系6.1 属

11、性文法属性文法(续续)例例 简单算术表达式求值的属性文法简单算术表达式求值的属性文法1)LE Print(E.val) 2)EE1+T E.val :E1.val +T.val 3)ET E.val :T.val 4)TT1*F T.val :T1.val * F.val 5)TF T.val :F.val 6)F(E) F.val :E.val 7)Fdigit F.val :digit.lexval E.val、T.val、F.val都是综合属性都是综合属性终结符终结符digit只有综合属性只有综合属性lexval ，它的值由词法分，它的值由词法分析器提供析器提供天津财经大学信息科学与技术

12、系6.2 语法制导翻译概论语法制导翻译概论1. 语法制导翻译语法制导翻译基本思想：基本思想：在语法分析过程中，随着分析的步步进展，每当在语法分析过程中，随着分析的步步进展，每当使用一条产生式进行使用一条产生式进行推导推导（对于自上而下分析）（对于自上而下分析）或或归约归约（对于自下而上分析），就执行该产生式（对于自下而上分析），就执行该产生式所对应的所对应的语义动作语义动作（语义子程序）（语义子程序），完成相应的，完成相应的翻译工作翻译工作（产生中间代码（产生中间代码）。语法制导翻译法不论对语法制导翻译法不论对自上而下分析自上而下分析或或自下自下而上分析而上分析都适用。都适用。天津财经大学信息

13、科学与技术系例例 简单算术表达式求值的属性文法简单算术表达式求值的属性文法1)EE1+T E.val :E1.val +T.val 2)ET E.val :T.val 3)TT1*digit T.val :T1.val * digit.lexval 4)Tdigit T.val :digit.lexval 2+3*5的语法树：的语法树：EE1+TT1*5T23T.val=2T.val=3T.val=15E.val=2E.val=17自下而上语法制导翻译过程：自下而上语法制导翻译过程：一旦语法分析确认输入符号串是一个句子，它的值也同时由一旦语法分析确认输入符号串是一个句子，它的值也同时由语义规则

14、计算出来语义规则计算出来天津财经大学信息科学与技术系6.3 中间代码的形式中间代码的形式n定义：定义：中间代码是独立于机器，复杂性介于源语言和中间代码是独立于机器，复杂性介于源语言和机器语言之间，十分接近目标机器指令的一种机器语言之间，十分接近目标机器指令的一种表示形式。表示形式。n使用中间代码的好处：使用中间代码的好处：中间代码与具体机器无关，便于编译程序改变中间代码与具体机器无关，便于编译程序改变目标机目标机便于对中间代码进行与机器无关的优化便于对中间代码进行与机器无关的优化n表示形式：表示形式：逆波兰式、四元式、三元式、间接三元式和树逆波兰式、四元式、三元式、间接三元式和树形表示形表示天

15、津财经大学信息科学与技术系6.3.1 逆波兰表示法（后缀式）逆波兰表示法（后缀式）n 逆波兰表示法逆波兰表示法将运算对象写在前面，把运算符写在后面，将运算对象写在前面，把运算符写在后面，因而也称后缀式。因而也称后缀式。例如：例如：程序设计语言中的表示程序设计语言中的表示 逆波兰表示逆波兰表示a+bab+a+b*c abc * +(a+b)*cab+c *天津财经大学信息科学与技术系bt1dct1t2t1t3t1= - bt2= c*dt3= t1+t2例：表达式例：表达式bc*d的后缀式的后缀式 bcd*+的计值过程的计值过程n后缀式的计算机处理后缀式的计算机处理后缀式的最大优点是易于计算机处

16、理后缀式的最大优点是易于计算机处理处理过程：处理过程：从左到右扫描后缀式，每碰到运算对象就推进栈；从左到右扫描后缀式，每碰到运算对象就推进栈；碰到运算符就从栈顶弹出相应目数的运算对象施碰到运算符就从栈顶弹出相应目数的运算对象施加运算，并把结果推进栈。最后的结果留在栈顶。加运算，并把结果推进栈。最后的结果留在栈顶。天津财经大学信息科学与技术系n逆波兰表示法的扩充逆波兰表示法的扩充逆波兰表示法很容易扩充到表达式以外的范围逆波兰表示法很容易扩充到表达式以外的范围 例如：例如：语句语句逆波兰表示逆波兰表示备注备注a:=b+cabc+:=:=看作二目运算符看作二目运算符GOTO LL jumpjump看

17、成一目运看成一目运算符，表示算符，表示GOTOIf E then S1 else S2ES1S2￥把￥把￥ 看成三目运看成三目运算符，表示算符，表示if then else天津财经大学信息科学与技术系6.3.2 三元式三元式n三元式三元式(算符算符op，第一个运算对象，第一个运算对象ARG1,第二个运算对象第二个运算对象ARG2)说明：说明：三元式的某些运算对象是三元式的某些运算对象是另一个三元式的编号（代表另一个三元式的编号（代表其结果）其结果）一目算符只需选用一个运一目算符只需选用一个运算对象（算对象（ARG1）多目算符可用连续几个三多目算符可用连续几个三元式表示元式表示例：例： a :b

18、*c+b*d表示为表示为 (1) (* ,b,c)(2) (* ,b,d)(3) (+ ,(1),(2)(4) (:,(3),a)天津财经大学信息科学与技术系6.3.3 树形表示树形表示n树形表示树形表示二目运算对应二叉子树，多目运算对应多叉子二目运算对应二叉子树，多目运算对应多叉子树，但通常通过引入新结点表示成二叉子树。树，但通常通过引入新结点表示成二叉子树。例如例如：a:b*c+b*d 表示成表示成:=a+*bcbd叶子结点代表运算量，叶子结点代表运算量，非叶子结点代表运算符非叶子结点代表运算符天津财经大学信息科学与技术系6.3.4 四元式四元式n四元式四元式四元式是一种比较普遍采用的中间

19、代码形式四元式是一种比较普遍采用的中间代码形式(算符算符op，ARG1，ARG2，运算结果，运算结果RESULT）例如：例如：a:b*c+b*d的四元式表示如下：的四元式表示如下： 1)(*,b,c,t1 )2)(*,b,d,t2 )3)(+,t1,t2,t3 )4)(:, t3 ,a ) 其中其中t i（i1,2,3）是编译程序引入的临时变量）是编译程序引入的临时变量天津财经大学信息科学与技术系6.3.4 四元式（续）四元式（续）n四元式的优点：四元式的优点：四元式比三元式更便于优化四元式比三元式更便于优化优化要求改变运算顺序或删除某些运算，引起编号优化要求改变运算顺序或删除某些运算，引起编

20、号的变化。的变化。三元式通过编号引用中间结果，编号的变化引起麻三元式通过编号引用中间结果，编号的变化引起麻烦；四元式通过临时变量引用中间结果，编号变化烦；四元式通过临时变量引用中间结果，编号变化无影响。无影响。四元式对生成目标代码有利四元式对生成目标代码有利四元式表示很类似于三地址指令，很容易转换成机四元式表示很类似于三地址指令，很容易转换成机器代码。器代码。天津财经大学信息科学与技术系6.3.4 四元式（续）四元式（续）n四元式的另一种表示四元式的另一种表示有时为了更直观，把四元式写成简单赋值形式有时为了更直观，把四元式写成简单赋值形式或更易理解的形式或更易理解的形式(三地址码三地址码)四元

21、式四元式直观形式直观形式（1）（）（ * , b , c , t1） （1） t1:b*c（2）（）（ * , b , d , t2）（2） t2:b*d（3）（）（ +, t1 , t2 , t3） （3） t3:t1+t2（4）（）（:, t3 , a）（4） a:t3天津财经大学信息科学与技术系6.3.5 间接三元式间接三元式n为了便于优化处理，不直接使用三元式，为了便于优化处理，不直接使用三元式，而是另设一张指示器表（称为间接码而是另设一张指示器表（称为间接码表），它按照运算的先后顺序列出有关表），它按照运算的先后顺序列出有关三元式在三元式表中的位置。即：三元式在三元式表中的位置。即：

22、用一用一张间接码表辅以三元式表的方法来表示张间接码表辅以三元式表的方法来表示中间代码。中间代码。n四元式、间接三元式的优化同样方便，四元式、间接三元式的优化同样方便，三元式的优化十分困难。三元式的优化十分困难。天津财经大学信息科学与技术系举例：举例：给出给出A+B*(C-D)+E/(C-D)N的逆波兰式、的逆波兰式、四元式、三元式、间接三元式的表示四元式、三元式、间接三元式的表示1、逆波兰式：、逆波兰式：ABCD-*+ECD-N/+2、四元式：、四元式：1)(-,C,D,T1)2)(*,B,T1,T2)3)(+,A, T2, T3)4)(-,C,D, T4)5)(, T4,N, T5)6)(/

23、,E, T5, T6)7)(+, T3, T6, T7)天津财经大学信息科学与技术系举例：举例：给出给出A+B*(C-D)+E/(C-D)N的逆波兰式、的逆波兰式、四元式、三元式、间接三元式的表示四元式、三元式、间接三元式的表示3、三元式：、三元式：1)(-,C,D)2)(*,B,1)3)(+,A, 2)4)(-,C,D)5)(, 4),N)6)(/,E,5)7)(+, 3),6)4、间接三元式：、间接三元式：1)(-,C,D)2)(*,B,1)3)(+,A, 2)4)(, 1),N)5)(/,E,4)6)(+, 3),5)间接码表间接码表1)2)3)1)4)5)6)天津财经大学信息科学与技术

24、系6.4 语法制导翻译语法制导翻译n主要讨论主要讨论自下而上自下而上的语法制导翻译的语法制导翻译n在一个产生式进行归约时，执行相应的在一个产生式进行归约时，执行相应的语义动作进行翻译（产生中间代码）语义动作进行翻译（产生中间代码）天津财经大学信息科学与技术系6.4.1简单赋值语句到四元式的翻译简单赋值语句到四元式的翻译简单赋值语句简单赋值语句是指不含复杂数据类型（如数组，记录等）的是指不含复杂数据类型（如数组，记录等）的赋值语句。赋值语句。赋值语句的语义检查包括赋值语句的语义检查包括：1.每个使用性标识符是否都有声明？每个使用性标识符是否都有声明？2.运算符的分量类型是否相容？运算符的分量类型

25、是否相容？3.赋值语句的左右部的类型是否相容？赋值语句的左右部的类型是否相容？赋值语句的翻译目标：赋值语句的翻译目标：在赋值语句右部表达式产生的四元式序列后加在赋值语句右部表达式产生的四元式序列后加一条赋值四元式一条赋值四元式天津财经大学信息科学与技术系6.4.1简单赋值语句到四元式的翻译简单赋值语句到四元式的翻译考虑如下文法描述的简单赋值句的翻译：考虑如下文法描述的简单赋值句的翻译：Ai:=E EE+E|E*E|-E|(E)|i (6.1)A代表赋值语句，设只含整型变量的运算代表赋值语句，设只含整型变量的运算1、需要定义一系列的语义变量和语义过程：、需要定义一系列的语义变量和语义过程：NEW

26、TEMP：函数，生成临时变量，每次调用生成一个：函数，生成临时变量，每次调用生成一个新的临时变量，如新的临时变量，如t1, t2 , 返回一个整数码作为函数值。返回一个整数码作为函数值。ENTRY(i)：函数过程，查找并取得与：函数过程，查找并取得与i相对应的标识符相对应的标识符在符号表中的位置（入口），简称在符号表中的位置（入口），简称i值。值。E.PLACE：与：与E相联系的语义变量，表示存放相联系的语义变量，表示存放E值的变量值的变量名在符号表的入口。名在符号表的入口。GEN(OP,ARG1,ARG1,RESULT)：语义过程，将四元式：语义过程，将四元式(OP,ARG1,ARG1,RE

27、SULT)填进四元式表中。填进四元式表中。 天津财经大学信息科学与技术系n使用上述变量和过程，对文法使用上述变量和过程，对文法6.1所定义的赋值所定义的赋值语句的翻译算法可由下述语义动作予以描述语句的翻译算法可由下述语义动作予以描述6.4.1简单赋值语句到四元式的翻译简单赋值语句到四元式的翻译产生式产生式语义动作语义动作Ai:=E GEN(:=,E.PLACE,-,ENTRY(i) EE(1)+E (2) E.PLACE:=NEWTEMP; GEN(+,E(1).PLACE,E(2).PLACE,E.PLACE) EE(1)*E (2) E.PLACE:=NEWTEMP; GEN(*,E(1)

28、.PLACE,E(2).PLACE,E.PLACE) E-E(1) E.PLACE:=NEWTEMP; GEN(,E(1).PLACE,-,E.PLACE) E(E(1) E.PLACE:=E(1).PLACE Ei E.PLACE:=ENTRY(i) 天津财经大学信息科学与技术系输入串输入串栈栈PLACE四元式四元式A:=-B*(C+D):=-B*(C+D) iA-B*(C+D) i:=A_B*(C+D) i:= -A_ _*(C+D) i:= -iA_ _B*(C+D) i:= -EA_ _B(,B,-,T1)*(C+D) i:= EA_T1(C+D) i:= E*A_T1 _C+D) i

29、:= E*(A_T1 _ _+D) i:= E*( iA_T1 _ _C+D) i:= E*( EA_T1 _ _CD) i:= E*( E+A_T1 _ _C_) i:= E*( E+iA_T1 _ _C_D) i:= E*( E+E A_T1 _ _C_D (+,C,D,T2) i:= E*( EA_T1 _ _T2i:= E*( E)A_T1 _ _T2 _i:= E* EA_T1 _T2(*, T1 ,T2,T3)i:=EA_ T3(:=, T3, - ,A)A2例例：写出下面赋值语句：写出下面赋值语句A:=-B*(C+D)的自下而的自下而上语法制导翻译的过程，上语法制导翻译的过程，及

30、生成的四元式。及生成的四元式。Ai:=E EE+E|E*E|-E|(E)|i 四元式为四元式为:(1)(,B,-,T1) (2) (+,C,D,T2) (3)(*, T1 ,T2,T3) (4) (:=, T3, - ,A)天津财经大学信息科学与技术系3、类型转换、类型转换表达式中可能出现不同类型的变量和常量表达式中可能出现不同类型的变量和常量若不接受不同类型的运算对象混合运算，则应指出错误；若不接受不同类型的运算对象混合运算，则应指出错误；若接受混合运算则要进行类型转换处理。若接受混合运算则要进行类型转换处理。例：假定表达式可以有混合运算，变量可以是整型和实例：假定表达式可以有混合运算，变量

31、可以是整型和实型，且当两个不同类型的变量进行运算时先把整型变量型，且当两个不同类型的变量进行运算时先把整型变量转换成实型，再进行运算。转换成实型，再进行运算。用用 +i , *i , i 表示整型运算，用表示整型运算，用 +r , *r, r表示实型表示实型运算，用一目算符运算，用一目算符 itr 表示将整型量转换成实型量表示将整型量转换成实型量的运算的运算令文法令文法6.1中的中的 i 既可以是整型也可以是实型既可以是整型也可以是实型1)用用E.MODE表示表示E的类型信息，其值为的类型信息，其值为int或或r，则，则产生式产生式EE(1) op E(2)的语义动作中，关于的语义动作中，关于

32、E.MODE的语义规的语义规则可定义为：则可定义为： if E1. MODE int AND E2. MODE int then E. MODE :=int else E. MODE :=r 天津财经大学信息科学与技术系3、类型转换（续）、类型转换（续）2)EE(1) op E(2) 的语义程序应该修改，必要的语义程序应该修改，必要时产生对运算量进行类型转换的四元式：时产生对运算量进行类型转换的四元式：(itr,A,-,T)，表示把整型，表示把整型A转换成实型量，结转换成实型量，结果存于果存于T中。中。3)例：假定输入串为例：假定输入串为X:=Y+I*J，其中，其中X,Y为为实型，实型，I,J

33、为整型，则其产生的四元式为：为整型，则其产生的四元式为：(1) (*i ,I,J,T1) (2)(itr,T1,-,T2) (3) (+r ,Y,T2,T3) (4) (:=,T3,-,X)4)例：关于产生式例：关于产生式EE(1) op E(2) 的语义子程的语义子程序更为具体的描述为：序更为具体的描述为：天津财经大学信息科学与技术系T:=NEWTEMP;IF E1.MODE=int AND E2.MODE=int THEN BEGIN GEN(opi , E1.PLACE, E2.PLACE,T); E.MODE:=int ENDELSE IF E1.MODE=r AND E2.MODE=

34、r THEN BEGIN GEN(opr , E1.PLACE, E2.PLACE,T); E.MODE:=r ENDELSE IF E1.MODE=int /*AND E2.MODE=r */ THEN BEGIN U:=NEWTEMP; GEN(itr, E1.PLACE,-,U);GEN(opr , U,E2.PLACE,T); E.MODE:=r ENDELSE /* E1.MODE=r AND E2.MODE=int */ BEGINU:=NEWTEMP; GEN(itr, E2.PLACE,-,U);GEN(opr , E2.PLACE, U, T); E.MODE:=r ENDE

35、.PLACE:=TEE(1) op E(2)天津财经大学信息科学与技术系布尔表达式的两个作用：布尔表达式的两个作用： 用于逻辑运算，计算逻辑值用于逻辑运算，计算逻辑值 作为控制语句作为控制语句(如如if-then,while)的条件的条件表达式表达式布尔表达式由布尔算符（布尔表达式由布尔算符（not,and,or）作）作用于布尔变量（或常数）或关系表达式用于布尔变量（或常数）或关系表达式而形成的。而形成的。关系表达式的形式：关系表达式的形式：E1 rop E2，rop是是关关系算符系算符(如如, , =)6.4.2布尔表达式到四元式的翻译布尔表达式到四元式的翻译天津财经大学信息科学与技术系为简

36、单起见，只考虑如下形式的布尔表达式的为简单起见，只考虑如下形式的布尔表达式的翻译，文法翻译，文法(6.2)EE or E | E and E | not E | (E ) | id rop id |id布 尔 算 符布 尔 算 符 的 优 先 顺 序 （ 从 高 到 低 ） 为 ：的 优 先 顺 序 （ 从 高 到 低 ） 为 ：not,and,or，且，且and和和or都服从左结合，都服从左结合，not服服从右结合从右结合关系算符关系算符的优先级都相同，而且高于任何布尔的优先级都相同，而且高于任何布尔算符，低于任何算术算符算符，低于任何算术算符6.4.2布尔表达式到四元式的翻译布尔表达式到四

37、元式的翻译-续续天津财经大学信息科学与技术系1.布尔表达式的计算方法：布尔表达式的计算方法： 采用两种方法：数值表示的采用两种方法：数值表示的直接计算直接计算与逻辑表与逻辑表示的示的短路计算短路计算直接计算与算术表达式计算方法基本相同直接计算与算术表达式计算方法基本相同如：如：1 or 0 and 1=1 or 0 的结果为：的结果为：1短路计算即布尔表达式计算到某一部分就可以得短路计算即布尔表达式计算到某一部分就可以得到结果，而无需对布尔表达式进行完全计算。可到结果，而无需对布尔表达式进行完全计算。可以用以用if-then-else来解释来解释A or B if A then true el

38、se BA and Bif A then B else falsenot Aif A then false else true天津财经大学信息科学与技术系2、直接计算的语法制导翻译、直接计算的语法制导翻译布尔表达式有两种翻译方法。（视计算机硬件条布尔表达式有两种翻译方法。（视计算机硬件条件来确定，如果执行条件转移效率较低，就用件来确定，如果执行条件转移效率较低，就用第一种方法）第一种方法）n直接计算的语法制导翻译直接计算的语法制导翻译 如同翻译算术表达式一样来翻译布尔表达式如同翻译算术表达式一样来翻译布尔表达式如：如：A or B and not C被翻译成：被翻译成：(1) (not,C,-

39、 ,T1)(2) (and,B,T1,T2)(3) (or,A,T2,T3)天津财经大学信息科学与技术系3.作为条件控制的布尔式翻译作为条件控制的布尔式翻译基本翻译方法基本翻译方法当布尔表达式用于控制条件时，并不需要计算表当布尔表达式用于控制条件时，并不需要计算表达式的值，而是一旦确定了表达式为真或为假，达式的值，而是一旦确定了表达式为真或为假，就将控制转向相应的代码序列。就将控制转向相应的代码序列。S2 的代码的代码S1 的代码的代码E的代码的代码E.false E.true if E then S1 else S2为布尔表达式为布尔表达式E引入两个新的引入两个新的属性：属性：E.true：

40、表达式的真出口，：表达式的真出口，它指向表达式为真时的转向它指向表达式为真时的转向E.false：表达式的假出口，：表达式的假出口，它指向表达式为假时的转向它指向表达式为假时的转向天津财经大学信息科学与技术系把布尔表达式把布尔表达式E翻译成下述形式的条件转移和无条翻译成下述形式的条件转移和无条件转移的四元式序列：件转移的四元式序列：1.( jnz , A , - , p )若若A为真，则转向四元式为真，则转向四元式p2.( jrop , A , B , p )若若A rop B为真，则转向四元式为真，则转向四元式p3.( j , - , - , p )无条件转向四元式无条件转向四元式p3.作为

41、条件控制的布尔式翻译作为条件控制的布尔式翻译-续续(1) ( jnz , A , - , 5 )A的真出口为的真出口为5(2) ( j , - , - , 3 )A的假出口为的假出口为3(3) ( j , B , D , 5 )BD的真出口为的真出口为5(4) ( j , - , - , p+1 ) BD的假出口为的假出口为(p+1)(5) (关于关于S1的四元式序列的四元式序列)(p)( j , - , - , q )跳过跳过S2的代码段的代码段(p+1) (关于关于S2的四元式序列的四元式序列)(q)(1) - (4)是布尔式是布尔式A or BD 翻译产生的代码，全部是条翻译产生的代码，

42、全部是条件转移和无条件转移四元式，没有布尔运算。件转移和无条件转移四元式，没有布尔运算。例：例：if A or BD then S1 else S2翻译成如下四元式序列翻译成如下四元式序列天津财经大学信息科学与技术系具体说明如下：具体说明如下：用用E.true和和E.false 分别表示分别表示E的的“真真”和和“假假”出口转移目标，在翻译出口转移目标，在翻译E时并未能确时并未能确定。定。对于对于E为为 a rop b 形式，生成代码如下：形式，生成代码如下：( jrop , a , b , E.true )( j , E.false )以结构图表示：以结构图表示：E的代码的代码E.false

43、E.true天津财经大学信息科学与技术系对于对于E为为 E1 or E2的形式，生成代码结构如下：的形式，生成代码结构如下：E1.的代码的代码E2.的代码的代码E1.falseE2.falseE.falseE1.trueE2.trueE.true若若E1为真，则可知为真，则可知E为真，即为真，即E1的真出口和的真出口和E的真出口一样；的真出口一样；若若E1为假，则必须计算为假，则必须计算E2，因此，因此E1的假出口应是的假出口应是E2代码的第代码的第一个四元式序号；一个四元式序号；E2的真出口和假出口分别与的真出口和假出口分别与E的真出口和假出口一样的真出口和假出口一样天津财经大学信息科学与技

44、术系E1.的代码的代码E2.的代码的代码E1.falseE2.falseE.falseE1.trueE2.trueE.true对于对于E为为 E1 and E2的形式，生成代码结构如下：的形式，生成代码结构如下：对于对于E为为 not E1形式，只需调换形式，只需调换E1的真假出口，的真假出口，即可得到即可得到E的真假出口。的真假出口。天津财经大学信息科学与技术系例：例：E 为为 ab or cf ，翻译为四元式序列：，翻译为四元式序列：（1） (j, a,b,E.true)（2） (j, - ,- ,(3)（3） (j, e ,f ,E.true)（6） (j, - ,- ,E.false)

45、举例举例真假出口的拉链与回填真假出口的拉链与回填在把布尔式翻译成一串条件转和无条件转四元在把布尔式翻译成一串条件转和无条件转四元式时，真假出口未能在生成四元式时确定；而式时，真假出口未能在生成四元式时确定；而且多个四元式可能有相同的出口且多个四元式可能有相同的出口天津财经大学信息科学与技术系说明：说明：E.true和和E.false不能不能在产生四元式的同在产生四元式的同时确定，要等将来时确定，要等将来目标明确时再回填，目标明确时再回填，为此要记录这些要为此要记录这些要回填的四元式。回填的四元式。通常采用通常采用“拉链拉链”的办法，把需要回的办法，把需要回填填E.true的四元式拉的四元式拉成

46、一条成一条“真真”链，链，把需要回填把需要回填E.false的的四元式拉成一条四元式拉成一条“假假”链。链。if ab or cf then S1 else S2翻译为四元式序列：翻译为四元式序列：（1） (j , a ,b ,(7)（2） (jump, - ,- ,(3)（3） (j , e ,f ,(7)（6） (jump, - ,- ,(p+1) （7） (关于关于S1的四元式的四元式)（p） (jump, - ,- ,q)(p+1) (关于关于S2的四元式的四元式) (q)天津财经大学信息科学与技术系练习：练习：把下面的语句翻译成四元式序列：把下面的语句翻译成四元式序列：If AB o

47、r CD then X:=Y else X:=Y=1100 (j,A,B,104)101 (j,-,-,102)102 (j,C,D,104)103 (j,-,-,106)104 (:=,Y,-,X)105 (j,-,-,108)106 (+,Y,1,T)107 (:=,T,-,X)108说明：说明： 产生是产生是100103是对应布尔式是对应布尔式AB or C=,C,D,106)。但这些是。但这些是下一阶段代码优化要讨论的下一阶段代码优化要讨论的问题，暂不讨论。问题，暂不讨论。天津财经大学信息科学与技术系6.4.3 控制语句的翻译控制语句的翻译n以以if 语句，语句，while语句为例说明控制语句的翻译方法语句为例说明控制语句的翻译方法S if