第八章语法制导和中间代码生成

1、第八章第八章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成学习目标：学习目标：v掌握：掌握：常见语法成分的中间代码形式；常见语法成分的中间代码形式；常见语法成分的属性文法或翻译方案常见语法成分的属性文法或翻译方案v理解：理解：属性文法、语法制导翻译方法属性文法、语法制导翻译方法目标程序目标程序源程序源程序词法分析词法分析语法分析语法分析语义分析语义分析中间代码生成中间代码生成代码优化代码优化目标代码生成目标代码生成表格管理表格管理出错处理出错处理语义分析基础语义分析基础语义分析的内容语义分析的内容 主要是类型相容检查，有以下几种：主要是类型相容检查，有以下几种：1) 各种条件表达式的类

2、型是不是各种条件表达式的类型是不是boolean型？型？2) 运算符的分量类型是否相容？运算符的分量类型是否相容？3) 赋值语句的左右部的类型是否相容？赋值语句的左右部的类型是否相容？4) 形参和实参的类型是否相容形参和实参的类型是否相容?5) 下标表达式的类型是否为所允许的类型？下标表达式的类型是否为所允许的类型？6) 函数说明中的函数类型和返回值的类型是否一函数说明中的函数类型和返回值的类型是否一致？致？其它语义检查：其它语义检查：1)VE中的中的V是不是变量，而且是数组类型？是不是变量，而且是数组类型？2)V.i中的中的V是不是变量，而且是记录类型？是不是变量，而且是记录类型？i是不是不

3、是该记录的域名？是该记录的域名？3)x+f()中的中的f是不是函数名？形参个数和实参个是不是函数名？形参个数和实参个数是否一致？数是否一致？4)每个使用性标识符是否都有声明？有无标识符每个使用性标识符是否都有声明？有无标识符的重复声明？的重复声明？在语义分析同时产生中间代码，在这种模式下，在语义分析同时产生中间代码，在这种模式下，语义分析的主要功能如下：语义分析的主要功能如下：语义审查语义审查在扫描声明部分时构造标识符的符号表在扫描声明部分时构造标识符的符号表在扫描语句部分时产生中间代码在扫描语句部分时产生中间代码语义分析方法语义分析方法语法制导翻译语法制导翻译方法方法使用使用属性文法属性文法

4、为工具来说明程序设计语言的语义。为工具来说明程序设计语言的语义。8.1属性文法属性文法8.2语法制导翻译概论语法制导翻译概论8.3中间代码形式中间代码形式8.4基本语言成分的自下而上语法制导翻译基本语言成分的自下而上语法制导翻译8.5自上而下的语法制导翻译自上而下的语法制导翻译8.1 8.1 属性文法属性文法( (Attribute Grammar)Attribute Grammar)属性属性对文法的每一个符号，引进一些属性，这些属性对文法的每一个符号，引进一些属性，这些属性代表与文法符号相关的信息，如类型、值、存储代表与文法符号相关的信息，如类型、值、存储位置等。位置等。语义规则语义规则为文

5、法的每一个产生式配备的计算属性的计算规为文法的每一个产生式配备的计算属性的计算规则，称为语义规则。则，称为语义规则。属性文法是带属性的一种文法属性文法是带属性的一种文法它的主要思想：它的主要思想：首先对于每个文法符号引进相关的属性符号；首先对于每个文法符号引进相关的属性符号；其次对于每个产生式写出计算属性值的语义规则其次对于每个产生式写出计算属性值的语义规则属性文法的形式定义属性文法的形式定义一个属性文法是一个三元组一个属性文法是一个三元组, ,A A(G, V, F)(G, V, F) G G是一个上下文无关文法；是一个上下文无关文法； V V是属性的有穷集；是属性的有穷集； F F是关于属

6、性的断言的有穷集。是关于属性的断言的有穷集。说明：说明：1.1. 每个每个属性属性与文法符号相联，与文法符号相联，N.tN.t表示文法符号表示文法符号N N的的属性属性t t。属性值属性值又称又称语义值语义值。存储属性值的变量。存储属性值的变量又称又称语义变量语义变量。2.2. 每个断言与文法的某个产生式相联，写在每个断言与文法的某个产生式相联，写在 内。内。属性的断言又称属性的断言又称语义规则语义规则，它所描述的工作可以，它所描述的工作可以包括属性计算、静态语义检查、符号表的操作、包括属性计算、静态语义检查、符号表的操作、代码生成等，有时写成函数或过程段。代码生成等，有时写成函数或过程段。例

7、例 完成类型检查的属性文法完成类型检查的属性文法1)1) E ET T1 1+T+T2 2TT1 1.t.tint AND Tint AND T2 2.t.tintint2)2) E ET T1 1 or T or T2 2TT1 1.t.tbool AND Tbool AND T2 2.t.tboolbool3)3) T TnumnumT.t :T.t :intint4)4) T TtruetrueT.t :T.t :boolbool5)5) T TfalsefalseT.t :T.t :boolbool 属性的分类：属性的分类：1.1. 综合属性综合属性： 从语法树的角度来看，如果一个结点

8、的某一从语法树的角度来看，如果一个结点的某一属性值是由该结点的子结点的属性值计算来属性值是由该结点的子结点的属性值计算来的，则称该属性为综合属性。的，则称该属性为综合属性。 内在属性是综合属性。内在属性是综合属性。 用于用于“自下而上自下而上”传递信息传递信息2.2. 继承属性继承属性 从语法树的角度来看，若一个结点的某一属从语法树的角度来看，若一个结点的某一属性值是由该结点的兄弟结点和（或）父结点性值是由该结点的兄弟结点和（或）父结点的属性值计算来的，则称该属性为继承属性。的属性值计算来的，则称该属性为继承属性。 用于用于“自上而下自上而下”传递信息传递信息说明：说明：v终结符终结符只有综合

9、属性，它们由词法分析器提供只有综合属性，它们由词法分析器提供v非终结符非终结符既有综合属性也有继承属性，但既有综合属性也有继承属性，但文法开文法开始符始符没有继承属性没有继承属性例例 简单算术表达式求值的属性文法简单算术表达式求值的属性文法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

10、、F.val都是综合属性都是综合属性终结符终结符digit只有综合属性，它的值由词法分析提供只有综合属性，它的值由词法分析提供例例 描述变量类型说明的属性文法描述变量类型说明的属性文法1) DTL L.type:T.type 2) Tint T.type:int 3) Treal T.type:real 4) LL1,id L1.type:L.type；addtype( id.entry，L.type )5) Lid addtype( id.entry，L.type ) id1DTLL1id2，intL.type是继承属性是继承属性T.type是综合属性是综合属性 int id1,id2的语法

11、树的语法树:用用表示属性的传递情况表示属性的传递情况8.2 语法制导翻译概论语法制导翻译概论1.语法制导翻译语法制导翻译基本思想：基本思想：在语法分析过程中，随着分析的步步进展，每当在语法分析过程中，随着分析的步步进展，每当使用一条产生式进行使用一条产生式进行推导推导（对于自上而下分析）（对于自上而下分析）或或归约归约（对于自下而上分析），就执行该产生式（对于自下而上分析），就执行该产生式所对应的所对应的语义动作语义动作，完成相应的翻译工作。，完成相应的翻译工作。语法制导翻译法不论对语法制导翻译法不论对自上而下分析自上而下分析或或自下而上自下而上分析分析都适用都适用例例 简单算术表达式求值的属

12、性文法简单算术表达式求值的属性文法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自下而上语法制导翻译过程：自下而上语法制导翻译过程：一旦语法分析确认输入符号串是一个句子，它的值也同时由一旦语法分析确认输入符号串是一个句子，它的值也同时由语义规则计算出来语义规则计算出来2. 语法制导翻

13、译的实现途径语法制导翻译的实现途径以自下而上（以自下而上（ LR分析）的语法制导翻译来说明分析）的语法制导翻译来说明 将将LR分析器能力扩大，增加在归约后调用语义规分析器能力扩大，增加在归约后调用语义规则的功能则的功能 增加语义栈，语义值放到与符号栈同步操作的语增加语义栈，语义值放到与符号栈同步操作的语义栈中，多项语义值可设多个语义栈义栈中，多项语义值可设多个语义栈 ，栈结构为：栈结构为：状态栈状态栈符号栈符号栈语义栈语义栈SmXmXm.valS1X1X1.valS0#-例例 简单算术表达式求值的属性文法简单算术表达式求值的属性文法1)L Eprint(E.val)2)EE1+T E.val

14、:E1.val +T.val 3)ET E.val :T.val 4)TT1*digit T.val :T1.val * digit.lexval 5)Tdigit T.val :digit.lexval 状态状态ACTION GOTO d+*#ET0S3 12 1S4 acc2r3 S5r3 33r5r5 r54S3 75S6 6 r4r4 r47r2S5r2S5*5#E+-2-0146acc#-0101r2#E+-2-01497712GOTOr4S6r5S3S4r3r5S3Action#E+T*5- 2-3-501475685#E+T*-2-3-014757*5#E+3-2- 301435

15、3*5#E+-2-01443*5#-033*5#-023*5#2- 203123*5#-00剩余输入串剩余输入串符号栈符号栈语义栈语义栈状态栈状态栈步骤步骤分析并计算分析并计算23*5的过程如下的过程如下:22T12E73T7T15117EL E EE1+T ETTT1*digit Tdigit8.3 中间代码的形式中间代码的形式定义：定义：中间代码是一种复杂性介于源程序语言和机器中间代码是一种复杂性介于源程序语言和机器语言之间的一种表示形式。语言之间的一种表示形式。使用中间代码的好处：使用中间代码的好处：中间代码与具体机器无关中间代码与具体机器无关对中间代码进行与机器无关的优化对中间代码进行

16、与机器无关的优化形式：形式：逆波兰记号、三元式、间接三元式、四元式和逆波兰记号、三元式、间接三元式、四元式和树形表示树形表示8.3.1 逆波兰记号逆波兰记号 逆波兰表示法逆波兰表示法将运算对象写在前面，把运算符写在后面，将运算对象写在前面，把运算符写在后面，因而也称后缀式。因而也称后缀式。例如：例如：程序设计语言中的表示程序设计语言中的表示 逆波兰表示逆波兰表示a+bab+a+b*c abc * +(a+b)*cab+c *后缀式的计算机处理后缀式的计算机处理后缀式的最大优点是易于计算机处理后缀式的最大优点是易于计算机处理处理过程：处理过程：从左到右扫描后缀式，每碰到运算对象就推进栈；从左到右

17、扫描后缀式，每碰到运算对象就推进栈；碰到运算符就从栈顶弹出相应目数的运算对象施碰到运算符就从栈顶弹出相应目数的运算对象施加运算，并把结果推进栈。最后的结果留在栈加运算，并把结果推进栈。最后的结果留在栈顶。顶。 bt1dct1t2t1t3t1= - bt2= c*dt3= t1+t2例：表达式例：表达式bc*d的后缀式的后缀式 bcd*+的计值过程的计值过程逆波兰表示法的扩充逆波兰表示法的扩充逆波兰表示法很容易扩充到表达式以外的范围逆波兰表示法很容易扩充到表达式以外的范围 例如：例如：语句语句逆波兰表示逆波兰表示备注备注a:=b+cabc+:=:=看作二目运算符看作二目运算符GOTO LL ju

18、mpjump看成一目运看成一目运算符，表示算符，表示GOTOIf E then S1 else S2ES1S2￥把￥把￥ 看成三目运看成三目运算符，表示算符，表示if then else8.3.2 三元式和树形表示三元式和树形表示三元式三元式(算符算符op，第一个运算对象第一个运算对象ARG1,第二个运算对象第二个运算对象ARG2)说明：说明：三元式的某些运算对象是另一三元式的某些运算对象是另一个三元式的编号（代表其结果）个三元式的编号（代表其结果）一目算符只需选用一个运算对一目算符只需选用一个运算对象（象（ARG1）多目算符可用连续几个三元式多目算符可用连续几个三元式表示表示例：例： a :

19、b*c+b*d表示为表示为 (1) (* ,b,c)(2) (* ,b,d)(3) (+ ,(1),(2)(4) (:,(3),a)间接三元式间接三元式和三元式类似，只是合并相同的三元式，并和三元式类似，只是合并相同的三元式，并在三元式后面加一列执行序列在三元式后面加一列执行序列例：例： a :b*c+b*c表示为表示为 (1) (* ,b,c)(2) (* ,b,c)(3) (+ ,(1),(2)(4) (:,(3),a)(1) (* ,b,c)(2) (+ ,(1),(1)(3) (:,(2),a)执行序列执行序列（1）（）（1）（）（2）（3）三元式序列三元式序列间接三元式序列间接三元式

20、序列树形表示树形表示二目运算对应二叉子树，多目运算对应多叉子二目运算对应二叉子树，多目运算对应多叉子树，但通常通过引入新结点表示成二叉子树。树，但通常通过引入新结点表示成二叉子树。例如：例如：a:b*c+b*d 表示成表示成:=a+*bcbd8.3.3 四元式四元式四元式表示四元式表示四元式是一种比较普遍采用的中间代码形式四元式是一种比较普遍采用的中间代码形式(算符算符op，ARG1，ARG2，运算结果运算结果RESULT）例如：例如：a:b*c+b*d的四元式表示如下：的四元式表示如下： 1) (*,b,c,t1 )2) (*,b,d,t2 )3) (+,t1,t2,t3 )4) (:, t

21、3 ,a ) 其中其中t i（i1,2,3）是编译程序引入的临时变量是编译程序引入的临时变量四元式的优点：四元式的优点：四元式比三元式更便于优化。四元式比三元式更便于优化。优化要求改变运算顺序或删除某些运算，引起编号优化要求改变运算顺序或删除某些运算，引起编号的变化。的变化。三元式通过编号引用中间结果，编号的变化引起麻三元式通过编号引用中间结果，编号的变化引起麻烦；四元式通过临时变量引用中间结果，编号变化烦；四元式通过临时变量引用中间结果，编号变化无影响。无影响。四元式对生成目标代码有利。四元式对生成目标代码有利。四元式表示很类似于三地址指令，很容易转换成机四元式表示很类似于三地址指令，很容易

22、转换成机器代码。器代码。 例如：例如：a:b*c+b*d的四元式表示如下：的四元式表示如下： 1) (*,b,c,t1 )2) (:=, t1,t2 )3) (*,b,d,t3 )4) (+,t1,t3,t4 )5) (:,t4 ,a ) 例如：例如：a:b*c+b*d的三元式表示如下：的三元式表示如下： 1) (*,b,c )2) (:=, 1）, 2）)3) (*,b,d)4) (+,1）,3） )5) (:,4）, a ) 四元式的另一种表示四元式的另一种表示有时为了更直观，把四元式写成简单赋值形式有时为了更直观，把四元式写成简单赋值形式或更易理解的形式或更易理解的形式四元式四元式直观形

23、式直观形式（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( jump,，L)goto L( jrop, B，C，L)if B rop C goto L8.4 基本语言成分的自下而上语法制导翻译基本语言成分的自下而上语法制导翻译8.4.1 简单赋值语句的翻译简单赋值语句的翻译8.4.2 布尔表达式的翻译布尔表达式的翻译8.4.3 控制结构的翻译控制结构的翻译8.4.4 简单说明语句的翻译简单说明语句

24、的翻译8.4.1 简单赋值语句的翻译简单赋值语句的翻译简单赋值语句简单赋值语句是指不含复杂数据类型（如数组，记录等）的是指不含复杂数据类型（如数组，记录等）的赋值语句。赋值语句。赋值语句的语义审查包括：赋值语句的语义审查包括：1. 每个使用性标识符是否都有声明？每个使用性标识符是否都有声明？2. 运算符的分量类型是否相容？运算符的分量类型是否相容？3. 赋值语句的左右部的类型是否相容？赋值语句的左右部的类型是否相容？赋值语句的翻译目标：赋值语句的翻译目标：在赋值语句右部表达式产生的四元式序列后加在赋值语句右部表达式产生的四元式序列后加一条赋值四元式一条赋值四元式1属性和语义规则中用到的变量、过

25、程和函数属性和语义规则中用到的变量、过程和函数属性：属性：用用表示单词表示单词id的名字。的名字。用用E.place表示存放表示存放E值的变量名在符号表的入口地址值的变量名在符号表的入口地址或临时变量编码。或临时变量编码。变量、函数和过程变量、函数和过程：用用nextstat变量给出在输出序列中下一个四元式的序号变量给出在输出序列中下一个四元式的序号用用lookup（）函数审查函数审查是否出现在符是否出现在符号表中，是则返回号表中，是则返回id的入口地址，否则返回的入口地址，否则返回nil。用用emit过程向输出序列输出一个四元式，过程向输出序列输出一

26、个四元式，emit每调用每调用一次，一次，nextstat的值增加的值增加1用用newtemp函数生成临时变量，每次调用生成一个新函数生成临时变量，每次调用生成一个新的临时变量，如的临时变量，如t1, t2 , 用用error过程进行错误处理。过程进行错误处理。 (1) Sid:E p:lookup ( ) ; if pnil then emit (:, E.place , - , p ) else error 2简单赋值语句的翻译（假定变量只有一种类型）简单赋值语句的翻译（假定变量只有一种类型）(2)EE1+E2 E.place:newtemp ; emit ( + , E1

27、.place , E2.place , E.place ) 此情况下的语义审查只有：此情况下的语义审查只有：每个使用性标识符是否都有声明？每个使用性标识符是否都有声明？(4)EE1 E.place:newtemp ; emit ( , E1.place , - , E.place ) (5)E(E1)E.place:newtemp ; E.place:E1.place (6)Eid p:lookup ( ) ; if pnil then E.place:p else error (3)EE1*E2 E.place:newtemp ; emit ( * , E1.place ,

28、E2.place , E.place ) 例例 翻译赋值语句翻译赋值语句A:B+C （A、B、C为标识符为标识符id）E1.placePBE2.placePCE.placet1；(, PB ,PC , t1)(:, t1 , - , PA)SA:=EBE1+E2C(为了直观，用为了直观，用PB和和PC分别表示分别表示B和和C在符号表的入在符号表的入口地址口地址) 表达式中可能出现不同类型的变量和常量表达式中可能出现不同类型的变量和常量 语义审查包括：语义审查包括：1. 每个使用性标识符是否都有声明？每个使用性标识符是否都有声明？2. 运算符的分量类型是否相容？运算符的分量类型是否相容？若不接受

29、不同类型的运算对象混合运算，则应指出错误；若不接受不同类型的运算对象混合运算，则应指出错误；若接受混合运算则要进行类型转换处理。若接受混合运算则要进行类型转换处理。 例例：假定表达式可以有混合运算，：假定表达式可以有混合运算，id可以是整型可以是整型和实型，且当两个不同类型的和实型，且当两个不同类型的id进行运算时先把进行运算时先把整型整型id转换成实型，再进行运算。转换成实型，再进行运算。用用E.type表示表示E的类型信息，其值为的类型信息，其值为int或或real。用用 +i , *i 表示整型运算，用表示整型运算，用 +r , *r 表示实型运算。表示实型运算。用一目算符用一目算符 i

30、tr 表示将整型量转换成实型量的运算。表示将整型量转换成实型量的运算。3 简单赋值语句的四元式翻简单赋值语句的四元式翻译译E.place:newtemp ;if E1.typeint AND E2.typeint thenbegin emit ( +i , E1.place , E2.place , E.place) ; E.type:int endelse if E1.typereal AND E2.typereal thenbegin emit ( +r , E1.place , E2.place , E.place ) ; E.type:real end else if E1.typei

31、nt then begin t:newtemp ; emit ( itr , E1.place , - , t ) ; emit ( +r , t , E2.place , E.place ) ; E.type:real end else begin t:newtemp ; emit ( itr , E2.place , - , t ) ; emit ( +r , E1.place , t , E.place ) ; E.type:real end ;产生式产生式EE1+E2的包含类型属性的语义规则为：的包含类型属性的语义规则为：E.place=newtemp ;if (E1.type=int

32、 & E2.type=int) emit ( +i , E1.place , E2.place , E.place) ; E.type=intelse if (E1.type=real & E2.type=real) emit ( +r , E1.place , E2.place , E.place ) ; E.type:real else if (E1.type=int) t=newtemp ; emit ( itr , E1.place , - , t ) ; emit ( +r , t , E2.place , E.place ) ; E.type=real else t=newtemp

33、 ; emit ( itr , E2.place , - , t ) ; emit ( +r , E1.place , t , E.place ) ; E.type=real ;产生式产生式EE1+E2的包含类型属性的语义规则为：的包含类型属性的语义规则为：属性文法的构造属性文法的构造属性：根据语义处理的需要，设计文法符号的相属性：根据语义处理的需要，设计文法符号的相应属性（包括：属性的个数和属性的符号表示）应属性（包括：属性的个数和属性的符号表示）语义规则：满足语义处理的要求，并生成相应的语义规则：满足语义处理的要求，并生成相应的中间代码中间代码8.4.2 布尔表达式的翻译布尔表达式的翻译1

34、. 布尔表达式的作用与结构布尔表达式的作用与结构布尔表达式的两个作用：布尔表达式的两个作用： 计算逻辑值计算逻辑值 作为控制语句作为控制语句(如如if-then,while)的条件表达式的条件表达式布尔表达式的语法：布尔表达式的语法： or | and | not | () | true | false（布尔表达式）布尔表达式） relop | () （关系表达式）关系表达式） op | - | () | id | num （算术表达式）算术表达式）其中：其中：relop是是关系算符关系算符(如如, , =)op是是算术算符算术算符(+ , - , * , / )只考虑如下形式的布尔表达式的翻

35、译只考虑如下形式的布尔表达式的翻译EE or E | E and E | not E | (E ) | id rop id |true|false布 尔 算 符布 尔 算 符 的 优 先 顺 序 （ 从 高 到 低 ） 为 ：的 优 先 顺 序 （ 从 高 到 低 ） 为 ：notandor，且且and和和or都服从左结合，都服从左结合，not服服从右结合从右结合关系算符关系算符的优先级都相同，而且高于任何布尔的优先级都相同，而且高于任何布尔算符，低于任何算术算符。算符，低于任何算术算符。2.布尔表达式的计算方法：布尔表达式的计算方法：采用两种方法：数值表示的采用两种方法：数值表示的直接计算直

36、接计算与逻辑表示与逻辑表示的的短路计算短路计算直接计算与算术表达式计算方法基本相同直接计算与算术表达式计算方法基本相同如：如：1 or 0 and 1=1 or 0=1短路计算即布尔表达式计算到某一部分就可以得短路计算即布尔表达式计算到某一部分就可以得到结果，而无需对布尔表达式进行完全计算。可到结果，而无需对布尔表达式进行完全计算。可以用以用if-then-else来解释来解释A or B if A then 1 else BA and Bif A then B else 0not Aif A then 0 else 1 3.直接计算的语法制导翻译直接计算的语法制导翻译对关系表达式，如对关系表

37、达式，如ab，可翻译成如下固定的三可翻译成如下固定的三地址代码序列：地址代码序列：(1) (j,a,b,(4)(2) (:=,0,- ,t1)(3) (jump, - ,- ,(5)(4) (:=,1,- ,t1)(5) 如：如：A or B and not C被翻译成：被翻译成：(not,C,- ,t1)(and, B,t1,t2)(or,A,t2,t3)PC直接计算的翻译方案直接计算的翻译方案(1)EE1 or E2 E.place :newtemp ; emit ( or , E1.place , E2.place , E.place ) (2)EE1 and E2 E.place :n

38、ewtemp ; emit ( and , E1.place , E2.place , E.place ) (3)Enot E1 E.place :newtemp ; emit ( not , E1.place , E.place ) (4)E(E1) E.place :E1.place (5)Eid1 rop id2 E.place :newtemp ; emit (jrop , id1.place , id2.place , nextstat+3 ) ; emit ( :, 0 , E.place ) ; emit ( jump , nextstat+2 ) ; emit ( :, 1 ,

39、 E.place ) (6)Etrue E.place:newtemp;emit(:=,1,- ,E.place) (7)EfalseE.place:=newtemp;emit(:=,0,- ,E.place) 例：布尔表达式例：布尔表达式ab or cf的翻译的翻译E.place=t5E1.place=t1E2.place=t4E2.place=t3E1.place=t2EE1E2E1E2oranda bc f(1)(j, a, b, (4)(2)(:=, 0, - , t1)(3)(jump,- ,- ,(5)(4)(:=, 1, - , t1)(5)(j, e, f, (12)(10)(

40、:=, 0, - , t3)(11)(jump,- ,- ,(13)(12)(:=, 1, - , t3)(13)(and, t2, t3, t4)(14)(or, t1, t4, t5)4.作为条件控制的布尔表达式的翻译作为条件控制的布尔表达式的翻译基本翻译方法基本翻译方法当布尔表达式用于控制条件时，并不需要计算表当布尔表达式用于控制条件时，并不需要计算表达式的值，而是一旦确定了表达式为真或为假，达式的值，而是一旦确定了表达式为真或为假，就将控制转向相应的代码序列。就将控制转向相应的代码序列。S2 的代码的代码S1 的代码的代码E的代码的代码E.false E.true if E then

41、S1 else S2为布尔表达式为布尔表达式E引入两个新的引入两个新的属性：属性：E.true：表达式的真出口，表达式的真出口，它指向表达式为真时的转向它指向表达式为真时的转向E.false：表达式的假出口，表达式的假出口，它指向表达式为假时的转向它指向表达式为假时的转向把把E翻译成下述形式的条件转移和无条件转移的四翻译成下述形式的条件转移和无条件转移的四元式序列：元式序列：1.( jnz , A , - , p )若若A为真，则转向四元式为真，则转向四元式p2.( jrop , A , B , p )若若A rop B为真，则转向四元式为真，则转向四元式p3.( jump , - , - ,

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

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

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

45、.falseE1.trueE2.trueE.true对于对于E为为 E1 and E2的形式，生成代码结构如下：的形式，生成代码结构如下：对于对于E为为 not E1形式，只需调换形式，只需调换E1的真假出口，的真假出口，即可得到即可得到E的真假出口。的真假出口。例：例：E 为为 ab or cf ，翻译为四元式序列：翻译为四元式序列：（1） (j, a,b,E.true)（2） (jump, - ,- ,(3)（3） (j, e ,f ,E.true)（6） (jump, - ,- ,E.false)真假出口的拉链与回填真假出口的拉链与回填原因原因在把布尔式翻译成一串条件转和无条件转四元在把

46、布尔式翻译成一串条件转和无条件转四元式时，真假出口未能在生成四元式时确定；而式时，真假出口未能在生成四元式时确定；而且多个四元式可能有相同的出口且多个四元式可能有相同的出口说明：说明：E.true和和E.false不能在不能在产生四元式的同时确定，产生四元式的同时确定，要等将来目标明确时再要等将来目标明确时再回填，为此要记录这些回填，为此要记录这些要回填的四元式。要回填的四元式。通常采用通常采用“拉链拉链”的办的办法，把需要回填法，把需要回填E.true的四元式拉成一条的四元式拉成一条“真真”链，把需要回填链，把需要回填E.false的四元式拉成一条的四元式拉成一条“假假”链。链。if ab

47、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)拉链方式：拉链方式：则链接成为：则链接成为：(10) goto (True) (20) goto (10) (30) goto (20)把地址（把地址（30）作为链首，地址（）作为链首，地址（10）作为链尾）作为链尾, True为为真

48、真链尾标志。链尾标志。四元式的第四个区段存放链指针。四元式的第四个区段存放链指针。E.true 和和E.false用于存放用于存放“真真”链和链和“假假”链的链的链首链首。若有四元式序列：若有四元式序列：(10) goto E.true (20) goto E.true (30) goto E.true 为了完成拉链和回填工作，设计以下语义变量和为了完成拉链和回填工作，设计以下语义变量和过程（函数）：过程（函数）：1) 函数函数merge ( p1, p2 ) 用于把用于把P1和和P2为链首的两为链首的两条链合并成条链合并成1条，返回合并后的链首值。条，返回合并后的链首值。其算法为：当其算法为

49、：当P2为空链时，返回为空链时，返回P1；当当P2不为空不为空链时，把链时，把P2的链尾第四区段改为的链尾第四区段改为P1，返回返回P2。2) 过程过程backpatch ( p , t ) 用于把链首用于把链首P所链接的每所链接的每个四元式的第四区段都填为转移目标个四元式的第四区段都填为转移目标t。3) 语义变量语义变量E.codebegin表示表达式表示表达式E的第一个四元的第一个四元式的序号。式的序号。 1)EE1 or E2 E.codebegin:E1.codebegin ;backpatch ( E1.false , E2.codebegin ) ;E.true:merge ( E

50、1.true , E2.true ) ; E.false:E2.false 自下而上分析中布尔表达式的一种翻译方案自下而上分析中布尔表达式的一种翻译方案2) EE1 and E2 E.codebegin:E1.codebigin ;backpatch ( E1.true , E2.codebegin ) ;E.true:E2.true ; E.false:merge ( E1.fasle , E2.false ) 3) Enot E1 E.codebegin:E1.codebigin ;E.true:E1.false ; E.false:E1.true 4)E(E1) E.codebegin:

51、E1.codebegin ;E.true:E1.true ; E.false:E1.false 5) Eid1 rop id2 E.codebegin:nextstat ; E.true:nextstat ; E.false:nextstat+1; emit ( jrop , id1.place , id2.place , true ) ; emit ( jump , false ) 6) Etrue E.codebegin:nextstat ; E.true:nextstat ;E.false:Nil;emit ( jump ,true ) 7) Efalse E.codebegin:nex

52、tstat ; E.false:nextstat ;E.true:Nil;emit ( jump ,false ) 例例 ab or cd and ef 的翻译过程的翻译过程假定四元式编号从假定四元式编号从100开始，开始，即开始时即开始时nextstat100EE1orE2E1andE2abcdefE1.begin=100E1.true=100E1.false=101E1.begin=102E1.true=102E1.false=103E2.begin=104E2.true=104E2.false=105E2.begin=102E2.true=104E2.false=103,105=105E

53、.begin=100E.true=100,104=104E.false=105100 : ( j , a , b , true )101: ( jump ,false )102: ( j , c , d , true )103: ( jump , fase )104: ( j , e , f , true )105: ( jump ,false )102 ( j , c , d ,104)105 ( jump ,103)101( jump,102)104 (j , e , f ,100)最终结果：最终结果：100：( j , a , b , true )101：( jump,102) 102：

54、( j , c , d , 104) 103：( jump, false ) 104：( j , e , f , 100) 105：( jump,103) “真真”链首链首E.true104 , “假假”链首链首E.false105。8.4.3 控制结构的翻译控制结构的翻译以以if 语句，语句，while语句为例说明控制语句的翻译方法语句为例说明控制语句的翻译方法S if E then Sif语句语句| if E then S else Sif语句语句| while E do Swhile语句语句| begin L end 复合语句复合语句| A赋值语句赋值语句A id:=EL L ; S语句

55、序列语句序列| S 语句语句 条件转移语句的共同特点是：根据布尔表达式取值，条件转移语句的共同特点是：根据布尔表达式取值，分别执行不同的语句序列。分别执行不同的语句序列。问题问题：不同的语句序列结束后，如何使控制转向语句：不同的语句序列结束后，如何使控制转向语句的结束。例如：的结束。例如：if E1 then if E2 then S1 else S2 else S3E1=1E2=1S1S2S3endstartYesNoYesNo参照布尔表达式的翻译方参照布尔表达式的翻译方法，对非终结符法，对非终结符S(和和L)，设立语义变量设立语义变量S.CHAIN（和和L.CHAIN ），用于记用于记住需

56、要在翻译完住需要在翻译完S(L)后回后回填转移目标的一串四元式填转移目标的一串四元式1. 代码结构代码结构E的代码的代码S1 的代码的代码E.false E.true S1.CHAIN S.CHAIN qif E then S1 代码结构代码结构qif E then S1 else S2 代码结构代码结构S2 的代码的代码Jump outS1 的代码的代码E的代码的代码S.CHAIN E.false E.true S1.CHAIN S2.CHAIN out:E.true qwhile E do S1 代码结构代码结构Jump beginS1 的代码的代码E 的代码的代码S.CHAIN E.fa

57、lse begin：S1.CHAIN2文法的改写文法的改写 原因：在自下而上的语法制导翻译中，语义动作的原因：在自下而上的语法制导翻译中，语义动作的执行是在使用产生式进行归约之后，并不允许在产执行是在使用产生式进行归约之后，并不允许在产生式的中间执行。为了能及时地执行语义动作（比生式的中间执行。为了能及时地执行语义动作（比如回填转移目标），需对源文法改写如回填转移目标），需对源文法改写 方法：在需要执行语义动作的地方把产生式分段，方法：在需要执行语义动作的地方把产生式分段，引入新的非终结符来表示它引入新的非终结符来表示它 需要改写的产生式：需要改写的产生式：1) 把把 Sif E then S

58、1改写成改写成Cif E then (回填回填E.true)SC S12) 把把 Sif E then S1 else S2改写成改写成Cif E then (回填回填E.true)TpC S1 else (产生无条件转移，产生无条件转移， 并回填并回填E.false) STp S23) 把把 Swhile E do S3 改写成改写成 Wwhile (记住入口记住入口) WdW E do (回填回填E.true) S Wd S3 (产生无条件转移产生无条件转移 返回循环入口返回循环入口)4) 把把 LL ; S改写成改写成LsL ; (回填前一语句的出口回填前一语句的出口)LLs S改写后的

59、文法改写后的文法(1) S C S1(2) S Tp S2(3) S Wd S3(4) S begin L end(5) S A (6) L Ls S(7) L S(8) C if E then(9) Tp C S1 else(10) W while(11) Wd W E do(12) Ls L ; 源文法：源文法：S if E then SS if E then S else SS while E do SS begin L end S AL L ; SL S(8)(1)(8)(9)(2)(10)(11)(3)(4)(5)(12)(6)(7)3安排语义动作安排语义动作Cif E then b

60、ackpatch ( E.true , nextstat ) ; C.CHAIN:=E.false SC S1/* if E then S1 */ S.CHAIN:merge ( C.CHAIN , S1.CHAIN ) TpC S1 else/* if E then S1 else */ q:=nextstat ; emit ( jump,false ) ;/*S1执行完，跳离整个执行完，跳离整个if语句语句*/backpatch ( C.CHAIN , nextstat ) ;Tp.CHAIN:merge ( q , S1.CHAIN ) STp S2/* if E then S1 els