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

1、第六章 语法制导翻译和中间代码生成学习目标：掌握：常见语法成分的中间代码形式；常见语法成分的属性文法或翻译方法理解：属性文法、语法制导翻译方法天津财经大学信息科学与技术系主要内容属性文法和语法制导翻译：属性文法语法制导翻译基本思想中间代码的表示形式（逆波兰式、四元式、三元式、间接三元式、树结构等等）简单算术表达式和赋值语句的翻译布尔表达式到四元式的翻译控制结构翻译成四元式天津财经大学信息科学与技术系目标程序源程序词法分析语法分析语义分析中间代码生成代码优化目标代码生成表格管理出错处理天津财经大学信息科学与技术系语义分析基础语义分析的内容主要是类型相容检查，有以下几种：各种条件表达式的类型是不是

2、boolean型？运算符的分量类型是否相容？赋值语句的左右部的类型是否相容？形参和实参的类型是否相容?下标表达式的类型是否为所允许的类型？函数说明中的函数类型和返回值的类型是否一致？天津财经大学信息科学与技术系语义分析基础-语义分析的内容（续）其它语义检查：VE中的V是不是变量，而且是数组类型？V.i中的V是不是变量，而且是记录类型？i是不是该记录的域名？x+f()中的f是不是函数名？形参个数和实参个数是否一致？每个使用性标识符是否都有声明？有无标识符的重复声明？天津财经大学信息科学与技术系语义分析基础在语义分析同时产生中间代码，在这种模式下，语义分析的主要功能如下：语义审查在扫描声明部分时构

3、造标识符的符号表在扫描语句部分时产生中间代码中间代码：独立于机器，复杂性介于源语言和机器语言之间，十分接近目标机器指令的一种表示形式。对于中间代码的产生，是很困难的，因为语义形式化比语法形式化难得多。目前普遍采用的语义分析方法语法制导翻译方法使用属性文法为工具来说明程序设计语言的语义。天津财经大学信息科学与技术系6.1属性文法(Attribute Grammar)属性对文法的每一个符号，引进一些属性，这些属性代表与文法符号相关的信息，如类型、值、存储位置等。语义规则为文法的每一个产生式配备的计算属性的计算规则，称为语义规则。属性文法是带属性的一种文法它的主要思想：首先对于每个文法符号引进相关的

4、属性符号；其次对于每个产生式写出计算属性值的语义规则天津财经大学信息科学与技术系6.1 属性文法(续)属性文法的形式定义一个属性文法是一个三元组,A(G, V, F)G是一个上下文无关文法；V是属性的有穷集；F是关于属性的断言的有穷集。说明：每个属性与文法符号相联，N.t表示文法符号N的属性t。属性值又称语义值。存储属性值的变量又称语义变量。每个断言与文法的某个产生式相联，写在 内。属性的断言又称语义规则，它所描述的工作可以包括属性计算、静态语义检查、符号表的操作、代码生成等，有时写成函数或过程段。天津财经大学信息科学与技术系6.1 属性文法(续)例 完成类型检查的属性文法ET1+T2T1.t

5、int AND T2.tintET1 or T2T1.tbool AND T2.tboolTnumT.t :intTtrueT.t :boolTfalseT.t :bool天津财经大学信息科学与技术系6.1 属性文法(续)属性的分类：综合属性：从语法树的角度来看，如果一个结点的某一属性值是由该结点的子结点的属性值计算来的，则称该属性为综合属性。内在属性是综合属性。用于“自下而上”传递信息天津财经大学信息科学与技术系6.1 属性文法(续)继承属性从语法树的角度来看，若一个结点的某一属性值是由该结点的兄弟结点和（或）父结点的属性值计算来的，则称该属性为继承属性。用于“自上而下”传递信息特别说明：终

6、结符只有综合属性，它们由词法分析器提供非终结符既有综合属性也有继承属性，但文法开始符没有继承属性天津财经大学信息科学与技术系6.1 属性文法(续)例 简单算术表达式求值的属性文法LE Print(E.val) EE1+T E.val :E1.val +T.val ET E.val :T.val TT1*F T.val :T1.val * F.val TF T.val :F.val F(E) F.val :E.val Fdigit F.val :digit.lexval E.val、T.val、F.val都是综合属性终结符digit只有综合属性lexval ，它的值由词法分析器提供天津财经大学信

7、息科学与技术系6.2 语法制导翻译概论语法制导翻译基本思想：在语法分析过程中，随着分析的步步进展，每当使用一条产生式进行推导（对于自上而下分析）或归约（对于自下而上分析），就执行该产生式所对应的语义动作（语义子程序），完成相应的翻译工作（产生中间代码）。语法制导翻译法不论对自上而下分析或自下而上分析都适用。天津财经大学信息科学与技术系例 简单算术表达式求值的属性文法EE1+T E.val :E1.val +T.val ET E.val :T.val TT1*digit T.val :T1.val * digit.lexval Tdigit T.val :digit.lexval 2+3*5的语

8、法树：EE1+TT1*5T23T.val=2T.val=3T.val=15E.val=2E.val=17自下而上语法制导翻译过程：一旦语法分析确认输入符号串是一个句子，它的值也同时由语义规则计算出来天津财经大学信息科学与技术系6.3 中间代码的形式定义：中间代码是独立于机器，复杂性介于源语言和机器语言之间，十分接近目标机器指令的一种表示形式。使用中间代码的好处：中间代码与具体机器无关，便于编译程序改变目标机便于对中间代码进行与机器无关的优化表示形式：逆波兰式、四元式、三元式、间接三元式和树形表示天津财经大学信息科学与技术系6.3.1 逆波兰表示法（后缀式） 逆波兰表示法将运算对象写在前面，把运

9、算符写在后面，因而也称后缀式。例如：程序设计语言中的表示逆波兰表示a+bab+a+b*c abc * +(a+b)*cab+c *天津财经大学信息科学与技术系bt1dct1t2t1t3t1= - bt2= c*dt3= t1+t2例：表达式bc*d的后缀式 bcd*+的计值过程后缀式的计算机处理后缀式的最大优点是易于计算机处理处理过程：从左到右扫描后缀式，每碰到运算对象就推进栈；碰到运算符就从栈顶弹出相应目数的运算对象施加运算，并把结果推进栈。最后的结果留在栈顶。天津财经大学信息科学与技术系逆波兰表示法的扩充逆波兰表示法很容易扩充到表达式以外的范围 例如：语句逆波兰表示备注a:=b+cabc+

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

11、3 树形表示树形表示二目运算对应二叉子树，多目运算对应多叉子树，但通常通过引入新结点表示成二叉子树。例如：a:b*c+b*d 表示成:=a+*bcbd叶子结点代表运算量，非叶子结点代表运算符天津财经大学信息科学与技术系6.3.4 四元式四元式四元式是一种比较普遍采用的中间代码形式(算符op，ARG1，ARG2，运算结果RESULT）例如：a:b*c+b*d的四元式表示如下： (*,b,c,t1 )(*,b,d,t2 )(+,t1,t2,t3 )(:,t3 ,a ) 其中t i（i1,2,3）是编译程序引入的临时变量天津财经大学信息科学与技术系6.3.4 四元式（续）四元式的优点：四元式比三元式

12、更便于优化优化要求改变运算顺序或删除某些运算，引起编号的变化。三元式通过编号引用中间结果，编号的变化引起麻烦；四元式通过临时变量引用中间结果，编号变化无影响。四元式对生成目标代码有利四元式表示很类似于三地址指令，很容易转换成机器代码。天津财经大学信息科学与技术系6.3.4 四元式（续）四元式的另一种表示有时为了更直观，把四元式写成简单赋值形式或更易理解的形式(三地址码)四元式直观形式（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）

13、（4） a:t3天津财经大学信息科学与技术系6.3.5 间接三元式为了便于优化处理，不直接使用三元式，而是另设一张指示器表（称为间接码表），它按照运算的先后顺序列出有关三元式在三元式表中的位置。即：用一张间接码表辅以三元式表的方法来表示中间代码。四元式、间接三元式的优化同样方便，三元式的优化十分困难。天津财经大学信息科学与技术系举例：给出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,

14、T5, T6)(+, T3, T6, T7)天津财经大学信息科学与技术系举例：给出A+B*(C-D)+E/(C-D)N的逆波兰式、四元式、三元式、间接三元式的表示3、三元式：(-,C,D)(*,B,1)(+,A, 2)(-,C,D)(, 4),N)(/,E,5)(+, 3),6)4、间接三元式：(-,C,D)(*,B,1)(+,A, 2)(, 1),N)(/,E,4)(+, 3),5)间接码表1)2)3)1)4)5)6)天津财经大学信息科学与技术系6.4 语法制导翻译主要讨论自下而上的语法制导翻译在一个产生式进行归约时，执行相应的语义动作进行翻译（产生中间代码）天津财经大学信息科学与技术系6.

15、4.1简单赋值语句到四元式的翻译简单赋值语句是指不含复杂数据类型（如数组，记录等）的赋值语句。赋值语句的语义检查包括：每个使用性标识符是否都有声明？运算符的分量类型是否相容？赋值语句的左右部的类型是否相容？赋值语句的翻译目标：在赋值语句右部表达式产生的四元式序列后加一条赋值四元式天津财经大学信息科学与技术系6.4.1简单赋值语句到四元式的翻译考虑如下文法描述的简单赋值句的翻译：Ai:=E EE+E|E*E|-E|(E)|i (6.1)A代表赋值语句，设只含整型变量的运算1、需要定义一系列的语义变量和语义过程：NEWTEMP：函数，生成临时变量，每次调用生成一个新的临时变量，如t1, t2 ,

16、返回一个整数码作为函数值。ENTRY(i)：函数过程，查找并取得与i相对应的标识符在符号表中的位置（入口），简称i值。E.PLACE：与E相联系的语义变量，表示存放E值的变量名在符号表的入口。GEN(OP,ARG1,ARG1,RESULT)：语义过程，将四元式(OP,ARG1,ARG1,RESULT)填进四元式表中。 天津财经大学信息科学与技术系使用上述变量和过程，对文法6.1所定义的赋值语句的翻译算法可由下述语义动作予以描述6.4.1简单赋值语句到四元式的翻译产生式语义动作Ai:=E GEN(:=,E.PLACE,-,ENTRY(i) EE(1)+E (2) E.PLACE:=NEWTEMP

17、; 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) 天津财经大学信息科学与技术系输入串栈PLACE四元式A:=-B*(C+D):=-B*(C+D)iA-B*(C+D)i:=A_B*(C+D)i:= -A_ _*(C+D)i:= -iA_ _

18、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)A_T1 _ _T2 _i:= E* EA_T1 _T2(*, T1 ,T2,T3)i:=EA_ T3(:=, T3, - ,A)A2例：写出下面

19、赋值语句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)天津财经大学信息科学与技术系3、类型转换表达式中可能出现不同类型的变量和常量若不接受不同类型的运算对象混合运算，则应指出错误；若接受混合运算则要进行类型转换处理。例：假定表达式可以有混合运算，变量可以是整型和实型，且当两个不同类型的变量进行运算时先把整型变量转换成实型，再进行运算。用 +i , *i , i 表示整型运算，用 +r ,

20、*r, r表示实型运算，用一目算符 itr 表示将整型量转换成实型量的运算令文法6.1中的 i 既可以是整型也可以是实型用E.MODE表示E的类型信息，其值为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 天津财经大学信息科学与技术系3、类型转换（续）EE(1) op E(2) 的语义程序应该修改，必要时产生对运算量进行类型转换的四元式：(itr,A,-,T)，表示把整型A转换成实型量，结果存于T中。例：假定

21、输入串为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)例：关于产生式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=r THEN BEGIN

22、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.PLACE:=TEE(1

23、) op E(2)天津财经大学信息科学与技术系布尔表达式的两个作用：用于逻辑运算，计算逻辑值作为控制语句(如if-then,while)的条件表达式布尔表达式由布尔算符（not,and,or）作用于布尔变量（或常数）或关系表达式而形成的。关系表达式的形式：E1 rop E2，rop是关系算符(如, , =)6.4.2布尔表达式到四元式的翻译天津财经大学信息科学与技术系为简单起见，只考虑如下形式的布尔表达式的翻译，文法(6.2)EE or E | E and E | not E | (E ) | id rop id |id布尔算符的优先顺序（从高到低）为：not,and,or，且and和or都服

24、从左结合，not服从右结合关系算符的优先级都相同，而且高于任何布尔算符，低于任何算术算符6.4.2布尔表达式到四元式的翻译-续天津财经大学信息科学与技术系1.布尔表达式的计算方法： 采用两种方法：数值表示的直接计算与逻辑表示的短路计算直接计算与算术表达式计算方法基本相同如：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 falsenot Aif A then false

25、else true天津财经大学信息科学与技术系2、直接计算的语法制导翻译布尔表达式有两种翻译方法。（视计算机硬件条件来确定，如果执行条件转移效率较低，就用第一种方法）直接计算的语法制导翻译 如同翻译算术表达式一样来翻译布尔表达式如：A or B and not C被翻译成：(1) (not,C,- ,T1)(2) (and,B,T1,T2)(3) (or,A,T2,T3)天津财经大学信息科学与技术系3.作为条件控制的布尔式翻译基本翻译方法当布尔表达式用于控制条件时，并不需要计算表达式的值，而是一旦确定了表达式为真或为假，就将控制转向相应的代码序列。S2 的代码S1 的代码E的代码E.false

26、 E.true if E then S1 else S2为布尔表达式E引入两个新的属性：E.true：表达式的真出口，它指向表达式为真时的转向E.false：表达式的假出口，它指向表达式为假时的转向天津财经大学信息科学与技术系把布尔表达式E翻译成下述形式的条件转移和无条件转移的四元式序列：( jnz , A , - , p )若A为真，则转向四元式p( jrop , A , B , p )若A rop B为真，则转向四元式p( j , - , - , p )无条件转向四元式p3.作为条件控制的布尔式翻译-续天津财经大学信息科学与技术系(1) ( jnz , A , - , 5 )A的真出口为5

27、(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 翻译产生的代码，全部是条件转移和无条件转移四元式，没有布尔运算。例：if A or BD then S1 else S2翻译成如下四元式序列天津财经大学信息科学与技术系具体说明如下：用E.true和E.false 分别表示E的“真”和“假”出口

28、转移目标，在翻译E时并未能确定。对于E为 a rop b 形式，生成代码如下：( jrop , a , b , E.true )( j , E.false )以结构图表示：E的代码E.falseE.true天津财经大学信息科学与技术系对于E为 E1 or E2的形式，生成代码结构如下：E1.的代码E2.的代码E1.falseE2.falseE.falseE1.trueE2.trueE.true若E1为真，则可知E为真，即E1的真出口和E的真出口一样；若E1为假，则必须计算E2，因此E1的假出口应是E2代码的第一个四元式序号；E2的真出口和假出口分别与E的真出口和假出口一样天津财经大学信息科学与

29、技术系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)举例真假出口的拉链与回填在把布尔式翻译成一串条件转和无条件转四元式时，真假出口未能在生成四元式时确定；而且多个四元式可能

30、有相同的出口天津财经大学信息科学与技术系说明：E.true和E.false不能在产生四元式的同时确定，要等将来目标明确时再回填，为此要记录这些要回填的四元式。通常采用“拉链”的办法，把需要回填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的四元式

31、) (q)天津财经大学信息科学与技术系练习：把下面的语句翻译成四元式序列：If AB or 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 控制语句的翻译以if 语句，while语句为例说明控制语句的翻译方法S if E then S1 if语句| if E then S1 else S2if语句| while E do Swhile语句其中：E:布尔表达式， S，S1 , S2 为语句天津财经大学信息科学与技术系E1=1E2=1S1S2S3endstartYesNoYesNo条件转移语句的共同特点是：根据布尔表达式取值，分别执行不同的语句序列。问题：不同的语句序列结束后，如何使控制转向语句的结束。例如：if E1