第8章语法制导翻译和中间代码生成(lly2)

1、第八章第八章 语法制导翻译和中间代码语法制导翻译和中间代码n中间代码中间代码：n常见语句的翻译常见语句的翻译（控制语句，控制语句，循循环，数组环，数组 语义分析语义分析语义分析的任务：语义分析的任务：在词法分析和语法分析的基础上，分析所写源程序的含义，在理解含义的基础上为生成相应的目标代码作好准备或直接生成目标代码。1）静态语义检查静态语义检查例：类型检查、运算、维数、越界2）语义翻译语义翻译（具体的动作具体的动作）例：语句的翻译（中间代码中间代码或目标代码生成）语义分析方法：语义分析方法：大多编译器采用语法制导翻译语法制导翻译方法语义分析工具：语义分析工具：在在语法制导翻译方法中，常用属性文

2、法属性文法来说明程序设计语言语义 8.1 属性文法属性文法属性文法属性文法(attribute grammar)是一个三元是一个三元组组:A=(G,V,F)表达式文法表达式文法 ET+T| T or T T n | true|falsetruefalse类型检查类型检查的属性文法：的属性文法： （值的属性值的属性？ 设计?） 语 义 规 则 L EE E1+TE TT T1 * FT FF (E)F digitPrint(E.val) E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val F.val T.val:=F.valF.val:=E.valF.v

3、al:=digit.lexval产 生 式综合属性val综合属性综合属性n在分析树中，如果一个结点的某一个属性在分析树中，如果一个结点的某一个属性由其子结点的属由其子结点的属性确定性确定，则称这种属性为该结点的综合属性，则称这种属性为该结点的综合属性。过程过程Print打印打印E表达表达式式 的值。的值。以以3*5+4为例说明为例说明 在语法制导定义中，一条语义规则完成一个计算属性在语法制导定义中，一条语义规则完成一个计算属性值的动作。值的动作。digit是终结符，只使用综合属性，且其属是终结符，只使用综合属性，且其属性值由词法分析器提供，通常不要计算属性值性值由词法分析器提供，通常不要计算属

4、性值。LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的带注释的分析树的带注释的分析树如果一个语法制如果一个语法制导定义仅仅使用导定义仅仅使用综合属性，则称综合属性，则称这种语法制导定这种语法制导定义为义为S属性定义属性定义。通常采用通常采用自底向自底向上的方法上的方法对其分对其分析树加注释，即析树加注释，即从树叶到树根，从树叶到树根，按照语义规则计按照语义规则计算每个节点的属算每个节点的属性值。性值。继承属性继承属性n一个结

5、点的继承属性值是由此结点的父结点和父结点和/或或兄弟结点的某些属性来决定兄弟结点的某些属性来决定的。生 产 式语 义 规 则D TL T int T real L L1,idL idL.in:=T.typeT.type=integerT.type:=real L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)继承属性继承属性L.in以说明语句以说明语句real a1,a2,a3为例为例过程过程addtypeaddtype是把每个标是把每个标志符的类型志符的类型信息登录在信息登录在符号表中相符号表中相关项中。关项中。语句语句real

6、 a1,a2,a3的分析树，采用的分析树，采用自上自上而下而下的分析方法的分析方法 产 生 式语 义 规 则D TL T int T real L L1,idL idL.in:=T.typeT.type=integerT.type:=real L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)DL.in= realL.in= realL.in= realT.type=realreala2a1a3.， 8.2 语法制导翻译概论语法制导翻译概论n在语法分析过程中，随着分析的步步进展，根据每个产在语法分析过程中，随着分析的步步进展，根据

7、每个产生式所对应的生式所对应的语义子程序语义子程序（或语义规则描述的（或语义规则描述的语义动作语义动作）进行翻译的办法称作进行翻译的办法称作语法制导翻译语法制导翻译。说明说明：定义理解：定义理解： 语法制导翻译是在语法制导翻译是在语法分析过程语法分析过程中同时进行的；中同时进行的； 一旦用到某个产生式一旦用到某个产生式推导推导/归约归约时，调用相应的时，调用相应的语义子语义子程序程序进行翻译。进行翻译。目的目的：用语法制导翻译的方法来说明程序设计语言的结构：用语法制导翻译的方法来说明程序设计语言的结构怎样被翻译成中间形式怎样被翻译成中间形式参见参见P.157-159对表达式对表达式2+3*5进

8、行的分析进行的分析8.3 中间代码的形成中间代码的形成中间代码的常见形式：中间代码的常见形式：逆波兰记号逆波兰记号三元式（树形表示）三元式（树形表示）四元式四元式逆波兰记号（逆波兰记号（后缀式后缀式）结构特点结构特点：将：将运算对象运算对象写在写在前面前面，把，把运算符号运算符号写在写在后面后面表达式逆波兰式a+bab+a+b*cabc*+(a+b)*cab+c*a:=b*c+b*d？计算方法计算方法：自左向右扫描逆波兰式，遇到运算对象则：自左向右扫描逆波兰式，遇到运算对象则入栈，遇到算符则将相应数目的运算对象出栈计算后入栈，遇到算符则将相应数目的运算对象出栈计算后结果入栈结果入栈。特点特点：

9、1）不需要括号（已考虑结合性与优先性）；）不需要括号（已考虑结合性与优先性）； 2）适合计算机运算，但不适合人。）适合计算机运算，但不适合人。逆波兰记号的扩充用途逆波兰记号的扩充用途iiGotoLLjumpifEthenS1elseS2ES1S2￥AnmnmAsubs复杂性：压栈的可能是地址（如变量赋值），不是值；栈中不一定产生结果。逆波兰示例（逆波兰示例（以算术表达式以算术表达式a+a a最左推导说明最左推导说明）把下述产生式定义的算术表达式映射到后缀波兰表示：把下述产生式定义的算术表达式映射到后缀波兰表示： EE+T E T T TF T F F (E) F a E=ET+ E=T T=T

10、F T=F F=E F=a 产生式 翻译成分n确定输入确定输入a+a a的输出：的输出：(E,E)(E+T,ET+)(T+T,TT+)(F+T,FT+)(a+T,aT+)(a+TF,aFF+)(a+FF,aFF+)(a+aF,aaF+)(a+aa,aaa+)三元式和树形表示三元式和树形表示n格式格式：( (算符算符, , 第一运算对象第一运算对象, , 第二运算对象第二运算对象) )注意注意：运算结果用三元式编号表示。：运算结果用三元式编号表示。n如如：a:=b*c+b*d(1) (*,b,c)(2) (*,b,d)(3) (+,(1),(2)(4) (:=,(3),a):=a+*bcbd三元

11、式表示三元式表示树形表示树形表示四元式四元式n格式格式：( (算符算符, , 第一运算对象第一运算对象, , 第二运算对象第二运算对象, , 结果结果) )注意注意：运算结果用临时变量表示。n如：a:=ba:=b* *c+bc+b* *d d (1) (1)( (* *,b,c,t1),b,c,t1) (2) (2)( (* *,b,d,t2),b,d,t2) (3) (3)(+,t1,t2,t3)(+,t1,t2,t3) (4) (4)(:=,t3,a)(:=,t3,a)n特点特点:类似于三地址指令类似于三地址指令利于优化和代码生成利于优化和代码生成四元式的直观表示四元式的直观表示na:=b

12、a:=b* *c+bc+b* *d d (1) (1)( (* *,b,c,t1),b,c,t1) (2) (2)( (* *,b,d,t2),b,d,t2) (3) (3)(+,t1,t2,t3)(+,t1,t2,t3) (4) (4)(:=,t3, ,a)(:=,t3, ,a)注意注意：x:=b*c的四元式表示（三元式，后缀式）四元式表示（三元式，后缀式）？四元式的扩展四元式的扩展n(jump, , ,L)(jump, , ,L) goto L goto Ln(jrop,B,C,L)(jrop,B,C,L) if B rop C goto L if B rop C goto Ln(jnz,

13、A, ,L) if A then L(jnz,A, ,L) if A then L思考思考：if A then L0 else L1 if A then L0 else L1 四元式四元式？t1:=b*ct2:=b*dt3:=t1+t2a:=t38.4 简单赋值语句的翻译简单赋值语句的翻译四元式形式四元式形式 : : t :=arg1 op arg2t :=arg1 op arg2语义属性语义属性：, E.place函数函数：lookup() ;过程过程：emit(t := arg1 op arg2);函数函数： newtemp;返回指向id的指针输出四元式生成临时

14、变量，返回指针E.place:值E的位置(1) S id := E P:=lookup () ; if P nil then emit( P“:=”E.place) else error (2) EE1+E2 / -，* ，/ E.place:= newtemp; emit(E.place“:=” E1.place“+”E2.place) (3) E - E1 E.place:=newtemp; emit(E.place“:=”“uminus” E1.place)(4) E( E1) E.place:= E1.place(5) Eid P:=lookup(); if

15、 P nil then E.place:=P else errorx=a+b-c 例（例（有二义，设有二义，设+优先，自下而上分析优先，自下而上分析）思考思考：人如何处理？人的思维与语义子程序设计关系？人如何处理？人的思维与语义子程序设计关系？产生式和语义描述产生式和语义描述（简单算术表达式赋值语句四元式）翻译简单算术表达式赋值语句四元式）翻译语法制导翻译思想语法制导翻译思想8.5 布尔表达式到四元式的翻译 布尔表达式的作用布尔表达式的作用 作为控制语句的条件表达式作为控制语句的条件表达式 用于逻辑计值用于逻辑计值EEE EE E (E) i rop j i注：注： rop 为关系运算符：为关

16、系运算符：= =， ，=，=， 为为“与与”运算；运算；为为“或或”运算；运算； 为为“非非”运算运算 结合性为左结合性结合性为左结合性 优先级别为：优先级别为： , rop ， 布尔表达式的计值方法布尔表达式的计值方法 方法一：方法一： 逐步计算逐步计算 方法二：方法二： 优化计算优化计算例如：例如：1 （ 0 0） 0= 1 （ 1 0） 0= 1 0 0= 1 0= 1 A B A B A解释为：解释为： if A then TRUE else B解释为：解释为： if A then B else FALSE解释为：解释为： if A then FALSE else TRUE 思考思考：

17、 优化后如何翻译为四元式？优化后如何翻译为四元式？ 作为作为逻辑计值逻辑计值的布尔表达式的翻译的布尔表达式的翻译例如例如：将：将 ABC!=D 翻译成四元式的形式翻译成四元式的形式 （逐步计算）逐步计算）（ !=， C， D， T1 ）（ ， B， T1， T2 ）（ ， A， T2， T3 ）思考思考： 优化法如何翻译为四元式？优化法如何翻译为四元式？ 布尔表达式布尔表达式的翻译的翻译 下面我们来观察下面我们来观察 “if-语句语句” 和和 “while-语句语句”中布尔表达式的作用：中布尔表达式的作用：仅仅用于执行流程的控制仅仅用于执行流程的控制 if E then S1 else S2

18、while E do SE的四元式代码的四元式代码S1的四元式代码的四元式代码GOTO L S2的四元式代码的四元式代码T TR RU UE EF FA AL LS SE EE的四元式代码的四元式代码S的四元式代码的四元式代码 GOTO L T TR RU UE EF FA AL LS SE E返回思考思考：若无：若无GOTO L，结果会如何？，结果会如何？ 我们通过观察我们通过观察 “if-语句语句” 和和 “while-语句语句”中布尔表达式的作用可以知道：中布尔表达式的作用可以知道：E的四元式代码的四元式代码T TR RU UE EF FA AL LS SE EE的真出口，用的真出口，用

19、 E.true 表示表示E的假出口，用的假出口，用 E.false 表示表示说明说明：在控制语句中：在控制语句中布尔表达式布尔表达式常采用常采用优化法优化法进行翻译进行翻译优优化化计计算算 A B A B A解释为：解释为： if A then TRUE else B解释为：解释为： if A then B else FALSE解释为：解释为： if A then FALSE else TRUE EE1E2 E1的的“真出口真出口”就是就是E2的第一个四元式编号；的第一个四元式编号； E1的的“假出口假出口”就是就是E的的“假出口假出口”； E2的的“真真/假出口假出口”就是就是E的的“真真/

20、假出口假出口”E E1E2 E1的的“真出口真出口”就是就是E的的“真出口真出口” ； E1的的“假出口假出口”就是就是E2的第一个四元式编号；的第一个四元式编号； E2的的“真真/假出口假出口”就是就是E的的“真真/假出口假出口” E E1 E1的的“真出口真出口”就是就是E的的“假出口假出口” ； E1的的“假出口假出口”就是就是E的的“真出口真出口” ； （ jnz ，A， ， p）若若A为真，则转到第为真，则转到第p号四元式去执行号四元式去执行（ jrop，A，B， p）若若A rop B为真，则到第为真，则到第p号四元式去执行号四元式去执行（ j ， ， ， p） 无条件转到第无条件

21、转到第p号四元式去执行号四元式去执行为了翻译布尔表达式，我们引入下面三种四元式：为了翻译布尔表达式，我们引入下面三种四元式：思考思考：if ABD then x:=y+z else x := y-z 如如何翻译为四元式？何翻译为四元式？E的四元式代码的四元式代码S1的四元式代码的四元式代码GOTO L S2的四元式代码的四元式代码T TR RU UE EF FA AL LS SE E if E then S1 else S2if ABD then x:=y+z else x := y-z100 （jnz，A， ，104） ； A的的“真出口真出口”101 （j ， ， ，102） ； A的的“

22、假出口假出口”102 （j ，B，D，104） ； BD的的“真出口真出口”103 （j ， ， ，107） ； Bn ) then x := x + y; else x := x-y; y := y*2; end思考题目：给出详细的翻译步骤？思考题目：给出详细的翻译步骤？while E do SE的四元式代码的四元式代码S的四元式代码的四元式代码 GOTO L T TR RU UE EF FA AL LS SE Ewhile ( A B C ) do begin k := k+1; if ( mn ) then x := x + y; else x := x-y; y := y*2; end

23、100 ( jnz , A , , 102 )101 ( j , , , 104 )102 ( jnz , B , , 106 )103 ( j , , , 104 )104 ( jnz , C , , 106 )105 ( j , , , 118 )106 ( + , k , 1 , T1 )107 ( := , T1, , k )108 ( j , m , n , 110 )109 ( j , , , 113 )110 ( + , x , y , T2 )111 ( := , T2, , x )112 ( j , , , 115 )113 ( - , x , y , T3 )114 ( :

24、= , T3, , x )115 ( * , y , 2 , T4 )116 ( := , T4, , y )117 ( j , , , 100 )118FOR循环翻译C/C+语言语言 语句语句 for (E1；E2；E3) S 的翻译的翻译执行流程如下执行流程如下：语义解释如下：语义解释如下： E1SE3 E20YN E1L1: if E20 then goto L3 else goto L4 L2: E3 goto L1L3: S goto L2L4: 总结注意注意：语句翻译框架语句翻译框架由语句由语句执行流程执行流程与与从左到右扫描从左到右扫描决定决定C/C+语言语言语语 句句 for

25、(E1；E2；E3) S 的的 翻翻 译译 框框 架架 E1 的四元式代码的四元式代码(j , , , L1 )(jnz, E2, , L3 )E3 的四元式代码的四元式代码(j , , , L2 )(j , , , L4 )S1 的四元式代码的四元式代码L1总结 E1L1: if E20 then goto L3 else goto L4 L2: E3 goto L1L3: S goto L2L4: E2 的四元式代码的四元式代码L2L3L4例例： for (i=0;i5; i=i+1) x=x+10; x=x-100;其他语言其他语言 forfor语句的翻译语句的翻译例例(BASIC：翻译

26、过程与具体语言语义相关） P:=0 P:=0 for i:=1 to 20 do P:=P+10 for i:=1 to 20 do P:=P+10例例(ALGOL ：翻译过程与具体语言语义相关）for i:=1 step 1 until 20 do P:=P+10for i:=1 step 1 until 20 do P:=P+10参见参见:174 :174 注意注意：语句翻译框架语句翻译框架由语句由语句执行流程执行流程与与从左到右扫描从左到右扫描决定决定数组元素到四元式的翻译数组元素到四元式的翻译下标变量（数组元素）的地址计算下标变量（数组元素）的地址计算数组的存贮方式有两种： 按行存贮。

27、 例如：C/C+；PASCLA；ALGOL等 按列存贮 。 例如： FORTRAN 我们假定我们假定按行存贮按行存贮，每个，每个数组元素占一个字数组元素占一个字，且机，且机器是按器是按字编址字编址的，下标从的，下标从1开始开始思考思考:A20, AiA20, Ai 元素的地址元素的地址? ?A1020, Ai, jA1020, Ai, j 元素的地址元素的地址? ? 对于一个对于一个d1d2dn的的n维数组维数组A的数组元素的数组元素A i1, i2, , in 的地址计算如下的地址计算如下(其中其中a为数组的起地为数组的起地) ：D = a + (i1 1)d2d3dn + (i2 1)d3d4dn + (in-1 - 1)dn + (in 1) = a - (d2d3dn + d3d4dn + + dn + 1) + (i1d2d3dn + i2d3d4dn + + in-1dn + in )令：令： C = d2d3dn +