《第6章语法制导翻译和中间代码生成课件.ppt》由会员分享，可在线阅读，更多相关《第6章语法制导翻译和中间代码生成课件.ppt（52页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第6章语法制导翻译和中间代码章语法制导翻译和中间代码生成生成第1页，此课件共52页哦主要内容主要内容属性文法和语法制导翻译：属性文法和语法制导翻译：n属性文法属性文法n语法制导翻译基本思想语法制导翻译基本思想n中间代码的表示形式（逆波兰式、四元中间代码的表示形式（逆波兰式、四元式、三元式、间接三元式、树结构等等式、三元式、间接三元式、树结构等等）n简单算术表达式和赋值语句的翻译简单算术表达式和赋值语句的翻译n布尔表达式到四元式的翻译布尔表达式到四元式的翻译n控制结构翻译成四元式控制结构翻译成四元式第2页，此课件共52页哦目标程序源程序词法分析语法分析语义分析中间代码生成代码优化目标代码生成表
2、格管理出错处理第3页，此课件共52页哦语义分析基础语义分析基础n语义分析的内容语义分析的内容主要是类型相容检查，有以下几种：主要是类型相容检查，有以下几种：n各种条件表达式的类型是不是各种条件表达式的类型是不是boolean型？型？n运算符的分量类型是否相容？运算符的分量类型是否相容？n赋值语句的左右部的类型是否相容？赋值语句的左右部的类型是否相容？n形参和实参的类型是否相容形参和实参的类型是否相容?n下标表达式的类型是否为所允许的类型？下标表达式的类型是否为所允许的类型？n函数说明中的函数类型和返回值的类型是否一函数说明中的函数类型和返回值的类型是否一致？致？第4页，此课件共52页哦语义分析
3、基础语义分析基础-语义分析的内容（续）语义分析的内容（续）其它语义检查：其它语义检查：nVE中的中的V是不是变量，而且是数组类型？是不是变量，而且是数组类型？nV.i中的中的V是不是变量，而且是记录类型？是不是变量，而且是记录类型？i是不是不是该记录的域名？是该记录的域名？nx+f()中的中的f是不是函数名？形参个数和实参个是不是函数名？形参个数和实参个数是否一致？数是否一致？n每个使用性标识符是否都有声明？有无标识符的重复每个使用性标识符是否都有声明？有无标识符的重复声明？声明？第5页，此课件共52页哦语义分析基础语义分析基础n在语义分析同时产生中间代码，在这种模式下，语义在语义分析同时产生
4、中间代码，在这种模式下，语义分析的主要功能如下：分析的主要功能如下：语义审查语义审查在扫描声明部分时构造标识符的符号表在扫描声明部分时构造标识符的符号表在扫描语句部分时产生中间代码在扫描语句部分时产生中间代码n中间代码：中间代码：独立于机器，复杂性介于源语言和机器语独立于机器，复杂性介于源语言和机器语言之间，十分接近目标机器指令的一种表示形式。言之间，十分接近目标机器指令的一种表示形式。对于中间代码的产生，是很困难的，因为语义形式化比语法形对于中间代码的产生，是很困难的，因为语义形式化比语法形式化难得多。目前普遍采用的式化难得多。目前普遍采用的n语义分析方法语义分析方法语法制导翻译语法制导翻译
5、方法方法使用使用属性文法属性文法为工具来说明程序设计语言的语义。为工具来说明程序设计语言的语义。第6页，此课件共52页哦6.1属性文法属性文法(Attribute Grammar)n属性属性对文法的每一个符号，引进一些属性，这些属性代表与文对文法的每一个符号，引进一些属性，这些属性代表与文法符号相关的信息，如类型、值、存储位置等。法符号相关的信息，如类型、值、存储位置等。n语义规则语义规则为文法的每一个产生式配备的计算属性的计算规则，称为为文法的每一个产生式配备的计算属性的计算规则，称为语义规则。语义规则。n属性文法属性文法是带属性的一种文法是带属性的一种文法它的主要思想：它的主要思想：n首先
6、对于每个文法符号引进相关的属性符号；首先对于每个文法符号引进相关的属性符号；其次对于每个产生式写出计算属性值的语义规则其次对于每个产生式写出计算属性值的语义规则第7页，此课件共52页哦6.1 属性文法属性文法(续续)n属性文法的形式定义属性文法的形式定义一个属性文法是一个三元组一个属性文法是一个三元组,A,A(G,V,F)(G,V,F)nG G是一个上下文无关文法；是一个上下文无关文法；nV V是属性的有穷集；是属性的有穷集；nF F是关于属性的断言的有穷集。是关于属性的断言的有穷集。说明：说明：n每个每个属性属性与文法符号相联，与文法符号相联，N.tN.t表示文法符号表示文法符号N N的属性
7、的属性t t。属性值属性值又称又称语义值语义值。存储属性值的变量又称。存储属性值的变量又称语义变量语义变量。n每个断言与文法的某个产生式相联，写在每个断言与文法的某个产生式相联，写在 内。属性内。属性的断言又称的断言又称语义规则语义规则，它所描述的工作可以包括属性，它所描述的工作可以包括属性计算、静态语义检查、符号表的操作、代码生成等，有计算、静态语义检查、符号表的操作、代码生成等，有时写成函数或过程段。时写成函数或过程段。第8页，此课件共52页哦6.1 属性文法属性文法(续续)例例 完成类型检查的属性文法完成类型检查的属性文法nE ET T1 1+T+T2 2TT1 1.t.tint AND
8、 Tint AND T2 2.t.tintintnE ET T1 1 or T or T2 2TT1 1.t.tbool AND Tbool AND T2 2.t.tboolboolnT TnumnumT.t:T.t:intintnT Ttruetrue T.t:T.t:boolbool1)1)T TfalsefalseT.t:T.t:boolbool第9页，此课件共52页哦6.1 属性文法属性文法(续续)n属性的分类：属性的分类：n综合属性：综合属性：从语法树的角度来看，如果一个结点的某一从语法树的角度来看，如果一个结点的某一属性值是由该结点的子结点的属性值计算来属性值是由该结点的子结点的属
9、性值计算来的，则称该属性为综合属性。的，则称该属性为综合属性。内在属性是综合属性。内在属性是综合属性。用于用于“自下而上自下而上”传递信息传递信息第10页，此课件共52页哦6.1 属性文法属性文法(续续)n继承属性继承属性从语法树的角度来看，若一个结点的某一属从语法树的角度来看，若一个结点的某一属性值是由该结点的兄弟结点和（或）父结点性值是由该结点的兄弟结点和（或）父结点的属性值计算来的，则称该属性为继承属性的属性值计算来的，则称该属性为继承属性。用于用于“自上而下自上而下”传递信息传递信息特别说明：特别说明：n终结符终结符只有综合属性，它们由词法分析器提供只有综合属性，它们由词法分析器提供2
10、.2.非终结符非终结符既有综合属性也有继承属性，但既有综合属性也有继承属性，但文法开始文法开始符符没有继承属性没有继承属性第11页，此课件共52页哦6.1 属性文法属性文法(续续)例例 简单算术表达式求值的属性文法简单算术表达式求值的属性文法nLE Print(E.val)nEE1+T E.val:E1.val+T.val nET E.val:T.val nTT1*F T.val:T1.val*F.val nTF T.val:F.val nF(E)F.val:E.val 1)Fdigit F.val:digit.lexval E.val、T.val、F.val都是综合属性终结符digit只有综
11、合属性lexval，它的值由词法分析器提供第12页，此课件共52页哦6.2 语法制导翻译概论语法制导翻译概论n 语法制导翻译语法制导翻译基本思想：基本思想：在语法分析过程中，随着分析的步步进展，每当使用一在语法分析过程中，随着分析的步步进展，每当使用一条产生式进行条产生式进行推导推导（对于自上而下分析）或（对于自上而下分析）或归约归约（对于（对于自下而上分析），就执行该产生式所对应的自下而上分析），就执行该产生式所对应的语义动作语义动作（语义子程序）语义子程序），完成相应的翻译工作，完成相应的翻译工作（产生中间代码）（产生中间代码）。语法制导翻译法不论对语法制导翻译法不论对自上而下分析自上而下
12、分析或或自下自下而上分析而上分析都适用。都适用。第13页，此课件共52页哦例 简单算术表达式求值的属性文法EE1+T E.val:E1.val+T.val ET E.val:T.val TT1*digit T.val:T1.val*digit.lexval 1)Tdigit T.val:digit.lexval 2+3*5的语法树：EE1+TT1*5T23T.val=2T.val=3T.val=15E.val=2E.val=17自下而上语法制导翻译过程：一旦语法分析确认输入符号串是一个句子，它的值也同时由语义规则计算出来第14页，此课件共52页哦6.3 中间代码的形式中间代码的形式n定义：定义
13、：中间代码是独立于机器，复杂性介于源语言和机器中间代码是独立于机器，复杂性介于源语言和机器语言之间，十分接近目标机器指令的一种表示形式语言之间，十分接近目标机器指令的一种表示形式。n使用中间代码的好处：使用中间代码的好处：n中间代码与具体机器无关，便于编译程序改变目标机中间代码与具体机器无关，便于编译程序改变目标机n便于对中间代码进行与机器无关的优化便于对中间代码进行与机器无关的优化n表示形式：表示形式：逆波兰式、四元式、三元式、间接三元式和树形表逆波兰式、四元式、三元式、间接三元式和树形表示示第15页，此课件共52页哦6.3.1 逆波兰表示法（后缀式）逆波兰表示法（后缀式）n 逆波兰表示法逆
14、波兰表示法将运算对象写在前面，把运算符写在后面将运算对象写在前面，把运算符写在后面，因而也称后缀式。，因而也称后缀式。例如：例如：程序设计语言中的表示逆波兰表示a+bab+a+b*c abc*+(a+b)*cab+c*第16页，此课件共52页哦bt1dct1t2t1t3t1=-bt2=c*dt3=t1+t2例：表达式bc*d的后缀式 bcd*+的计值过程n后缀式的计算机处理后缀式的计算机处理n后缀式的最大优点是易于计算机处理后缀式的最大优点是易于计算机处理n处理过程：处理过程：从左到右扫描后缀式，每碰到运算对象就推进栈；碰从左到右扫描后缀式，每碰到运算对象就推进栈；碰到运算符就从栈顶弹出相应目
15、数的运算对象施加运算到运算符就从栈顶弹出相应目数的运算对象施加运算，并把结果推进栈。最后的结果留在栈顶。，并把结果推进栈。最后的结果留在栈顶。第17页，此课件共52页哦n逆波兰表示法的扩充逆波兰表示法很容易扩充到表达式以外的范围 例如：语句逆波兰表示备注a:=b+cabc+:=:=看作二目运算符GOTO LL jumpjump看成一目运算符，表示GOTOIf E then S1 else S2ES1S2￥把￥看成三目运算符，表示if then else第18页，此课件共52页哦6.3.2 三元式三元式n三元式三元式(算符算符op，第一个运算对象，第一个运算对象ARG1,第二个运算对象第二个运算
16、对象ARG2)说明：三元式的某些运算对象是另一个三元式的编号（代表其结果）一目算符只需选用一个运算对象（ARG1）多目算符可用连续几个三元式表示例：a:b*c+b*d表示为(1)(*,b,c)(2)(*,b,d)(3)(+,(1),(2)(4)(:,(3),a)第19页，此课件共52页哦6.3.3 树形表示树形表示n树形表示二目运算对应二叉子树，多目运算对应多叉子树，但通常通过引入新结点表示成二叉子树。例如：a:b*c+b*d 表示成:=a+*bcbd叶子结点代表运算量，非叶子结点代表运算符第20页，此课件共52页哦6.3.4 四元式四元式n四元式四元式四元式是一种比较普遍采用的中间代码形式四
17、元式是一种比较普遍采用的中间代码形式(算符算符op，ARG1，ARG2，运算结果，运算结果RESULT）例如：a:b*c+b*d的四元式表示如下：(*,b,c,t1)(*,b,d,t2)(+,t1,t2,t3)(:,t3,a)1)其中t i（i1,2,3）是编译程序引入的临时变量第21页，此课件共52页哦6.3.4 四元式（续）四元式（续）n四元式的优点：四元式的优点：n四元式比三元式更便于优化四元式比三元式更便于优化优化要求改变运算顺序或删除某些运算，引起编号的变化优化要求改变运算顺序或删除某些运算，引起编号的变化。三元式通过编号引用中间结果，编号的变化引起麻烦三元式通过编号引用中间结果，编
18、号的变化引起麻烦；四元式通过临时变量引用中间结果，编号变化无影；四元式通过临时变量引用中间结果，编号变化无影响。响。n四元式对生成目标代码有利四元式对生成目标代码有利四元式表示很类似于三地址指令，很容易转换成机器代码。四元式表示很类似于三地址指令，很容易转换成机器代码。第22页，此课件共52页哦6.3.4 四元式（续）四元式（续）n四元式的另一种表示四元式的另一种表示有时为了更直观，把四元式写成简单赋值形式或更易理有时为了更直观，把四元式写成简单赋值形式或更易理解的形式解的形式(三地址码三地址码)四元式直观形式（1）（*,b,c,t1）（1）t1:b*c（2）（*,b,d,t2）（2）t2:b
19、*d（3）（+,t1,t2,t3）（3）t3:t1+t2（4）（:,t3,a）（4）a:t3第23页，此课件共52页哦6.3.5 间接三元式间接三元式n为了便于优化处理，不直接使用三元式为了便于优化处理，不直接使用三元式，而是另设一张指示器表（称为间接码，而是另设一张指示器表（称为间接码表），它按照运算的先后顺序列出有关表），它按照运算的先后顺序列出有关三元式在三元式表中的位置。即：三元式在三元式表中的位置。即：用一用一张间接码表辅以三元式表的方法来表示张间接码表辅以三元式表的方法来表示中间代码。中间代码。n四元式、间接三元式的优化同样方便，四元式、间接三元式的优化同样方便，三元式的优化十分困
20、难。三元式的优化十分困难。第24页，此课件共52页哦举例：举例：给出A+B*(C-D)+E/(C-D)N的逆波兰式、四元式、三元式、间接三元式的表示1、逆波兰式：ABCD-*+ECD-N/+2、四元式：(-,C,D,T1)(*,B,T1,T2)(+,A,T2,T3)(-,C,D,T4)(,T4,N,T5)(/,E,T5,T6)1)(+,T3,T6,T7)第25页，此课件共52页哦举例：举例：给出A+B*(C-D)+E/(C-D)N的逆波兰式、四元式、三元式、间接三元式的表示3、三元式：(-,C,D)(*,B,1)(+,A,2)(-,C,D)(,4),N)(/,E,5)1)(+,3),6)4、间
21、接三元式：(-,C,D)(*,B,1)(+,A,2)(,1),N)(/,E,4)1)(+,3),5)间接码表1)2)3)1)4)5)6)第26页，此课件共52页哦6.4 语法制导翻译语法制导翻译n主要讨论主要讨论自下而上自下而上的语法制导翻译的语法制导翻译n在一个产生式进行归约时，执行相应的在一个产生式进行归约时，执行相应的语义动作进行翻译（产生中间代码）语义动作进行翻译（产生中间代码）第27页，此课件共52页哦6.4.1简单赋值语句到四元式的翻译简单赋值语句到四元式的翻译简单赋值语句简单赋值语句是指不含复杂数据类型（如数组，记录等）的赋值是指不含复杂数据类型（如数组，记录等）的赋值语句。语句
22、。赋值语句的语义检查包括赋值语句的语义检查包括：n每个使用性标识符是否都有声明？每个使用性标识符是否都有声明？n运算符的分量类型是否相容？运算符的分量类型是否相容？n赋值语句的左右部的类型是否相容？赋值语句的左右部的类型是否相容？赋值语句的翻译目标：赋值语句的翻译目标：在赋值语句右部表达式产生的四元式序列后加一条赋在赋值语句右部表达式产生的四元式序列后加一条赋值四元式值四元式第28页，此课件共52页哦6.4.1简单赋值语句到四元式的翻译简单赋值语句到四元式的翻译考虑如下文法描述的简单赋值句的翻译：Ai:=E EE+E|E*E|-E|(E)|i (6.1)A代表赋值语句，设只含整型变量的运算1、
23、需要定义一系列的语义变量和语义过程：NEWTEMP：函数，生成临时变量，每次调用生成一个新的临时变量，如t1,t2,返回一个整数码作为函数值。ENTRY(i)：函数过程，查找并取得与i相对应的标识符在符号表中的位置（入口），简称i值。E.PLACE：与E相联系的语义变量，表示存放E值的变量名在符号表的入口。GEN(OP,ARG1,ARG1,RESULT)：语义过程，将四元式(OP,ARG1,ARG1,RESULT)填进四元式表中。第29页，此课件共52页哦n使用上述变量和过程，对文法使用上述变量和过程，对文法6.1所定义的赋值语句所定义的赋值语句的翻译算法可由下述语义动作予以描述的翻译算法可由
24、下述语义动作予以描述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).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)
25、第30页，此课件共52页哦输入串栈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:=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+EA_T1 _ _C_D(+,C,D,T2)i:=E*(EA_T1 _ _T2i:=E*(E)
26、A_T1 _ _T2 _i:=E*EA_T1 _T2(*,T1,T2,T3)i:=EA_ T3(:=,T3,-,A)A2例：写出下面赋值语句A:=-B*(C+D)的自下而上语法制导翻译的过程，及生成的四元式。Ai:=E EE+E|E*E|-E|(E)|i 四元式为:(1)(,B,-,T1)(2)(+,C,D,T2)(3)(*,T1,T2,T3)(4)(:=,T3,-,A)第31页，此课件共52页哦3、类型转换、类型转换表达式中可能出现不同类型的变量和常量表达式中可能出现不同类型的变量和常量若不接受不同类型的运算对象混合运算，则应指出错误；若不接受不同类型的运算对象混合运算，则应指出错误；若接受
27、混合运算则要进行类型转换处理。若接受混合运算则要进行类型转换处理。例：假定表达式可以有混合运算，变量可以是整型和实型，且例：假定表达式可以有混合运算，变量可以是整型和实型，且当两个不同类型的变量进行运算时先把整型变量转换成实型，当两个不同类型的变量进行运算时先把整型变量转换成实型，再进行运算。再进行运算。用用+i,*i,i 表示整型运算，用表示整型运算，用+r,*r,r表示实型运算表示实型运算，用一目算符，用一目算符 itr 表示将整型量转换成实型量的运算表示将整型量转换成实型量的运算令文法令文法6.1中的中的 i 既可以是整型也可以是实型既可以是整型也可以是实型n用用E.MODE表示表示E的
28、类型信息，其值为的类型信息，其值为int或或r，则，则产生式产生式EE(1)op E(2)的语义动作中，关于的语义动作中，关于E.MODE的语义规则可定义的语义规则可定义为：为：if E1.MODE int AND E2.MODE int then E.MODE:=int else E.MODE:=r 第32页，此课件共52页哦3、类型转换（续）、类型转换（续）nEE(1)op E(2)的语义程序应该修改，必要时产生的语义程序应该修改，必要时产生对运算量进行类型转换的四元式：对运算量进行类型转换的四元式：(itr,A,-,T)，表，表示把整型示把整型A转换成实型量，结果存于转换成实型量，结果存
29、于T中。中。n例：假定输入串为例：假定输入串为X:=Y+I*J，其中，其中X,Y为实型，为实型，I,J为整型，则其产生的四元式为：为整型，则其产生的四元式为：(1)(*i ,I,J,T1)(2)(itr,T1,-,T2)(3)(+r,Y,T2,T3)(4)(:=,T3,-,X)n例：关于产生式例：关于产生式EE(1)op E(2)的语义子程序更为的语义子程序更为具体的描述为：具体的描述为：第33页，此课件共52页哦T:=NEWTEMP;IF E1.MODE=int AND E2.MODE=int THEN BEGIN GEN(opi ,E1.PLACE,E2.PLACE,T);E.MODE:=
30、int ENDELSE IF E1.MODE=r AND E2.MODE=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
31、);E.MODE:=r ENDE.PLACE:=TEE(1)op E(2)第34页，此课件共52页哦布尔表达式的两个作用：布尔表达式的两个作用：用于逻辑运算，计算逻辑值用于逻辑运算，计算逻辑值 作为控制语句作为控制语句(如如if-then,while)的条件表达的条件表达式式布尔表达式由布尔算符（布尔表达式由布尔算符（not,and,or）作）作用于布尔变量（或常数）或关系表达式用于布尔变量（或常数）或关系表达式而形成的。而形成的。关系表达式的形式：关系表达式的形式：E1 rop E2，rop是是关关系算符系算符(如如,=)6.4.2布尔表达式到四元式的翻译布尔表达式到四元式的翻译第35页，此
32、课件共52页哦为简单起见，只考虑如下形式的布尔表达式的翻译为简单起见，只考虑如下形式的布尔表达式的翻译，文法，文法(6.2)EE or E|E and E|not E|(E)|id rop id|id布尔算符布尔算符的优先顺序（从高到低）为：的优先顺序（从高到低）为：not,and,or，且且and和和or都服从左结合，都服从左结合，not服从右结合服从右结合关系算符关系算符的优先级都相同，而且高于任何布尔算符，的优先级都相同，而且高于任何布尔算符，低于任何算术算符低于任何算术算符6.4.2布尔表达式到四元式的翻译布尔表达式到四元式的翻译-续续第36页，此课件共52页哦1.布尔表达式的计算方法
33、：布尔表达式的计算方法：采用两种方法：数值表示的采用两种方法：数值表示的直接计算直接计算与逻辑表示的与逻辑表示的短短路计算路计算n直接计算与算术表达式计算方法基本相同直接计算与算术表达式计算方法基本相同如：如：1 or 0 and 1=1 or 0 的结果为：的结果为：1短路计算即布尔表达式计算到某一部分就可以得到短路计算即布尔表达式计算到某一部分就可以得到结果，而无需对布尔表达式进行完全计算。可以用结果，而无需对布尔表达式进行完全计算。可以用if-then-else来解释来解释A or B if A then true else BA and Bif A then B else falsen
34、ot Aif A then false else true第37页，此课件共52页哦2、直接计算的语法制导翻译、直接计算的语法制导翻译布尔表达式有两种翻译方法。（视计算机硬件条件来布尔表达式有两种翻译方法。（视计算机硬件条件来确定，如果执行条件转移效率较低，就用第一种方确定，如果执行条件转移效率较低，就用第一种方法）法）n直接计算的语法制导翻译直接计算的语法制导翻译 如同翻译算术表达式一样来翻译布尔表达式如同翻译算术表达式一样来翻译布尔表达式如：A or B and not C被翻译成：(1)(not,C,-,T1)(2)(and,B,T1,T2)(3)(or,A,T2,T3)第38页，此课件
35、共52页哦3.作为条件控制的布尔式翻译作为条件控制的布尔式翻译基本翻译方法基本翻译方法当布尔表达式用于控制条件时，并不需要计算表达式的值当布尔表达式用于控制条件时，并不需要计算表达式的值，而是一旦确定了表达式为真或为假，就将控制转向相应，而是一旦确定了表达式为真或为假，就将控制转向相应的代码序列。的代码序列。S2 的代码S1 的代码E的代码E.false E.true if E then S1 else S2为布尔表达式E引入两个新的属性：E.true：表达式的真出口，它指向表达式为真时的转向E.false：表达式的假出口，它指向表达式为假时的转向第39页，此课件共52页哦把布尔表达式把布尔表
36、达式E翻译成下述形式的条件转移和无条件转移翻译成下述形式的条件转移和无条件转移的四元式序列：的四元式序列：n(jnz,A,-,p)若若A为真，则转向四元式为真，则转向四元式pn(jrop,A,B,p)若若A rop B为真，则转向四元式为真，则转向四元式pn(j,-,-,p)无条件转向四元式无条件转向四元式p3.作为条件控制的布尔式翻译作为条件控制的布尔式翻译-续续第40页，此课件共52页哦(1)(jnz,A,-,5)A的真出口为的真出口为5(2)(j,-,-,3)A的假出口为的假出口为3(3)(j,B,D,5)BD的真出口为的真出口为5(4)(j,-,-,p+1)BD的假出口为的假出口为(p
37、+1)(5)(关于关于S1的四元式序列的四元式序列)(p)(j,-,-,q)跳过跳过S2的代码段的代码段(p+1)(关于关于S2的四元式序列的四元式序列)(q)(1)-(4)是布尔式A or BD 翻译产生的代码，全部是条件转移和无条件转移四元式，没有布尔运算。例：if A or BD then S1 else S2翻译成如下四元式序列第41页，此课件共52页哦具体说明如下：具体说明如下：用用E.true和和E.false 分别表示分别表示E的的“真真”和和“假假”出口转移目标，在翻译出口转移目标，在翻译E时并未能确定时并未能确定。n对于对于E为为 a rop b 形式，生成代码如下：形式，生
38、成代码如下：(jrop,a,b,E.true)(j,E.false)以结构图表示：以结构图表示：E的代码E.falseE.true第42页，此课件共52页哦对于E为 E1 or E2的形式，生成代码结构如下：E1.的代码E2.的代码E1.falseE2.falseE.falseE1.trueE2.trueE.true若E1为真，则可知E为真，即E1的真出口和E的真出口一样；若E1为假，则必须计算E2，因此E1的假出口应是E2代码的第一个四元式序号；E2的真出口和假出口分别与E的真出口和假出口一样第43页，此课件共52页哦E1.的代码E2.的代码E1.falseE2.falseE.falseE1
39、.trueE2.trueE.true 对于E为 E1 and E2的形式，生成代码结构如下：对于E为 not E1形式，只需调换E1的真假出口，即可得到E的真假出口。第44页，此课件共52页哦例：E 为 ab or cf，翻译为四元式序列：（1）(j,a,b,E.true)（2）(j,-,-,(3)（3）(j,e,f,E.true)（6）(j,-,-,E.false)举例真假出口的拉链与回填在把布尔式翻译成一串条件转和无条件转四元式时，真假出口未能在生成四元式时确定；而且多个四元式可能有相同的出口第45页，此课件共52页哦说明：E.true和E.false不能在产生四元式的同时确定，要等将来目
40、标明确时再回填，为此要记录这些要回填的四元式。通常采用“拉链”的办法，把需要回填E.true的四元式拉成一条“真”链，把需要回填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)第46页，此课件共52页哦练习：练习：把下面的语句翻译成四元式序列：If AB or CD then X:=Y else X:=Y=1100(j,A
41、,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)。但这些是下一阶段代码优化要讨论的问题，暂不讨论。第47页，此课件共52页哦6.4.3 控制语句的翻译控制语句的翻译n以以if 语句，语句，while语句为例说明控制语句的翻译方法语句为例说明控制语句的翻译方法S if E then S1 if语句|if E then S1 else S2if语句|while E do
42、Swhile语句其中：E:布尔表达式，S，S1,S2 为语句第48页，此课件共52页哦E1=1E2=1S1S2S3endstartYesNoYesNo条件转移语句的共同特点是：根据布尔表达式取值，分条件转移语句的共同特点是：根据布尔表达式取值，分别执行不同的语句序列。别执行不同的语句序列。问题问题：不同的语句序列结束后，如何使控制转向语句的结束：不同的语句序列结束后，如何使控制转向语句的结束。例如：。例如：if E1 then if E2 then S1 else S2 else S3If-then,if-then-else的翻译参见上面的方法。下面主要考虑while语句的翻译第49页，此课件
43、共52页哦While语句的翻译语句的翻译qwhile E do S1 代码结构E.true S1 的代码E 的代码E.false begin：第50页，此课件共52页哦考虑如下语句while ab do if cd then x:=y+z else x:=y-z的翻译模式。L1:if ab goto L2goto LnextL2:if cd goto L3goto L4L3:T1:=y+zx:=T1goto L1L4:T1:=y-zx:=T1goto L1Lnext:L1,L2,L3,L4,Lnext：语句标号；L1:while条件成立时，则去执行L2(if条件判断)，否则，退出while循环
44、语句；L2:if条件语句成立，则去执行then语句L3，不成立则去执行else语句L4，执行完返回while；L3:then语句的四元式序列；L4:else语句的四元式序列；Lnext:while后的语句序列。第51页，此课件共52页哦把上述语句翻译成四元式为：把上述语句翻译成四元式为：while ab do if cd then x:=y+z else x:=y-z100(j,a,b,102)101(j,-,-,110)102(j,c,d,104)103(j,-,-,107)104(+,y,z,T1)105(:=,x,-,T1)106(j,-,-,100)107(-,y,z,T2)108(:=,x,-,T2)109(j,-,-,100)110L1L2L3L4Lnext第52页，此课件共52页哦