第七章——语义和中间代码生成

1、第七章 语义分析和中间代码生成静态语义检查n类型检查。验证程序中执行的每个操作是否遵守语言的类型系统的过程.，编译程序必须报告不符合类型系统的信息。 n控制流检查。控制流语句必须使控制转移到合法的地方。例如，在C语言中break语句使控制跳离包括该语句的最小while、for或switch语句。如果不存在包括它的这样的语句，则报错。 n一致性检查。在很多场合要求对象只能被定义一次。例如Pascal语言规定同一标识符在一个分程序中只能被说明一次，同一case语句的标号不能相同，枚举类型的元素不能重复出现等等。n相关名字检查。有时，同一名字必须出现两次或多次。例如，Ada 语言程序中，循环或程序块

2、可以有一个名字，出现在这些结构的开头和结尾，编译程序必须检查这两个地方用的名字是相同的。中间语言常见的中间语言的形式：n后缀式（逆波兰式）n三地址代码 三元式 四元式 间接三元式nDAG图后缀式n又称逆波兰表示法，把运算量（操作数）写在前面，把算符写在后面（后缀）。 如：ab 写成 ab ab*c 写成 abc*+n定义：1.如果表达式E是一个变量或常量，则E的后缀式是E自身；2.如果E是E1 op E2形式的表达式 (op为二元操作符) ，则E的后缀式为E1E2op。E1 、E2分别为E1、E2的后缀式；3.如果E式(E1)形式的表达式，则E1的后缀式就是E的后缀式。这种表达式不需要括号这种

3、表达式不需要括号n如a*(b+c) 写成 (a+b)*(c+d) 写成 abc*abcd*+a*bc+*cdab将表达式翻译为后缀式的语义规则nE.code表示E的后缀式，op为二元操作符，“|”表示后缀形式的连接。图表示法 DAG 抽象语法树nDAG: 无循环有向图。对表达式的每个子表达式，DAG中都有一个结点。一个内部结点代表一个操作符，它的孩子代表操作数。n在一个DAG图中，代表公共子表达式的结点具有多个父结点。如表达式a+a*(b-c)+(b-c)*d的DAG图为：+*d*abc又如 a:=b*-c+b*-cassignuminus*abcassignuminus*abcuminus*

4、bcDAG图抽象语法树一目“”运算符用uminus或表示，用以和二目“”运算符区分。a:=b*-c+b*-c的抽象语法树可表示为：assign ida*idbidbuminus uminus idcidc或三地址代码n三地址代码是由下面一般形式的语句构成的序列：X :=Y op Z。其中，X,Y,Z为名字，常数或编译时产生的临时变量，op代表运算符号。 每个语句右边只能有一个运算符。n如：x+y*z 可翻译为：T1 :y*zT2 :x+T1T1，T2为编译时产生的临时变量。a:=b*-c+b*-c的三地址代码为：T1 : -cT2 :b*T1T3 : -cT4 :b*T3T5 :T2 +T4a

5、 : T5 assignuminus*abcuminus*bc对于抽象语法树的代码a:=b*-c+b*-c的三地址代码为：T1 : -cT2 :b*T1T5 :T2 +T2a : T5 对于DGA的代码assignuminus*abca:=b*-c+b*-c的三地址代码为：T1 : -cT2 :b*T1T3 : -cT4 :b*T3T5 :T2 +T4a : T5 对于抽象语法树的代码T1 : -cT2 :b*T1T5 :T2 +T2a : T5 对于DGA的代码三地址语句的种类nX :=Y op ZnX := op YnX :=Yngoto Lnif x relop y goto L 或if

6、 a goto Ln用于过程调用的param x 和call p，n及return ynx :=yi 及 xi :=ynx :=&y， x :=*y， *x :=y四元式n带有四个记录域：op，arg1，arg2，result。n一元运算符不用arg2n条件或无条件转移语句将目标标号置于resultnparam类运算符仅使用arg1域如a:=b*-c+b*-cT1 : -cT2 :b*T1T3 : -cT4 :b*T3T5 :T2 *T4 a : T5uminus C T1 * b T1 T2uminus C T3 * b T3 T4 + T2 T4 T5:= T5a三元式n带有三个记录域：o

7、p，arg1，arg2。n对一目运算符arg1，arg2只用其一，多目运算符可用若干相继三元式表示。n如：xi :=y x := yi (0) (= ，x，i)(1) (:=，(0)，y)(0) ( =，y，i)(1) (:=，x，(0)( =，y，xi) /变址存数四元式(= ，yi ，x) /变址取数四元式n如a:=b*-c+b*-cuminus C T1 * b T1 T2uminus C T3 * b T3 T4 + T2 T4 T5:= T5a四元式三元式uminus C * b (0)uminus C * b (2) + (1) (3) := a (4) 间接三元式n不直接使用三元

8、式，而是另设一张指示器（称为间接码表），它将按运算的先后顺序列出有关三元式在三元式表中的位置。n如： X:=(A+B)*C Y:=D*(A+B) 表示为：三元式表 A B * (1) C * D (1) := X (2) := Y (4) 间接代码（1）（2）（3）（1）（4）（5）当要调整运算顺序时，只需要重新安排间接码表。说明语句n说明语句的翻译模式 PD offset:=0 DD;D Did:T enter(,T.type,offset); offset:=offset+T.width Tinteger T.type:=integer T.width:=4 Treal T.

9、type:=real T.width:=8 Tarraynum of T1 T.type:=array(num.val,T1.type); T.width:=num.valT1.width TT1 T.type:=pointer(T1.type); T.width:=4赋值语句的翻译1.简单算术表达式和赋值语句S id := E P:=lookup () ; if Pnil then emit( P“:=”E.place) else error EE1+E2 E.place:= newtemp; emit(E.place“:=” E1.place“+”E2.place)EE1*E

10、2 E.place:= newtemp; emit(E.place“:=” E1.place“*”E2.place)E - E1 E.place:=newtemp; emit(E.place“:=”“uminus” E1.place)E( E1) E.place:= E1.placeEid E.place:=newtemp; P:=lookup(); if Pnil then E.place:=P else error数组元素的引用n数组在存储器中的存放方式决定了数组元素的地址计算法。若数组存放在一片连续单元。假设A每个元素宽度为w，则Ai的起始地址为： base(i-low)w

11、iw(base-loww)多维数组：按列存放 按行存放记为C，可在数组说明时计算出来多维数组的地址计算n二维数组若按行存放：Ai1,i2的相对地址为： (i1n2)+i2)w+(base-(low1n2)+low2)wn将数组元素加入赋值语句后的翻译模式n在算术表达式中，当有两种不同类型的量进行运算时，如整型量和实型量，规定首先必须把整型转换成实型。在编译时可确定S L:= E if L.offset=null then emit( L.place“:=”E.place) else emit( L.place L.offset :=E.place)EE1+E2 E.place := newte

12、mp; emit(E.place := E1.place + E2.place)E( E1) E.place:= E1.placeEL if L.offset=null then E.place:=L.place; else begin E.place := newtemp; emit(E.place := L.place L.offset ) endLElist L.place := newtemp; emit(L.place := Elist.arrayC L.offset := newtemp; emit(L.offset := w *Elist.place) Lid L.place:=

13、 id.place; L.offset := null Elist Elist1,E t := newtemp; m := Elist1.ndim+1; emit(t := Elist1.place * limit(Elist1.array,m); emit(t := t + E.place); Elist.array := Elist1.array; Elist.place := t; Elist.ndim := mElist idE Elist.place := E.place; Elist.ndim := 1; Elist.array := id.place x:=Ay,z设A为1020

14、的数组，w4，则x:=Ay,z的三地址语句序列为：T1:=y*20T1:=T1+zT2:=A-84T3:=4*T1T4:=T2T3X:=T484=C=(1201)4设A为1020的数组，w4，则 Ay,z := x 的三地址语句序列为：T1:=y*20T1:=T1+zT2:=A-84T3:=4*T1T2T3:= X布尔表达式的翻译n布尔表达式的两个基本作用： 用于计算逻辑值 用于控制流语句中的条件表达式n布尔表达式是用布尔运算符号(and,or,not)作用到布尔变量或关系表达式上组成的。n关系表达式：E1 relop E2 relop为关系运算符n规定优先级not，and，or依次降低。布尔

15、表达式的翻译n如同计算算术表达式，一步步计算 如：1 and (0 or 1) and not 0 =1 and 1 and 1 =1 and 1 =1n采取某种优化措施如：A or B 若A为1，则不用计算B,可知结果为1可以if-then-else来解释 A or B if A then true else B A and B if A then B else true not A if A then false else true 数值表示法na or b and not c 翻译为三地址序列： T1:= not c T2:= b and T1 T3:= a or T2n关系表达式ab，

16、可理解为 if ab then 1 else 0，翻译为三地址序列： (1) if ab goto (4) (2) t:=0 (3) goto (5) (4) t:=1 (5) 后继语句布尔表达式的翻译模式EE1 or E2 E.place:= newtemp; emit(E.place“:=” E1.place “or” E2.place)EE1 and E2 E.place:= newtemp; emit(E.place“:=” E1.place “and” E2.place)E not E1 E.place:=newtemp; emit(E.place “:=” “not” E1.pla

17、ce)E( E1) E.place:= E1.placeEid1 relop id2 E.place:=newtemp; emit(ifid1.place relop.op id2.place goto nextstat+3); emit(E.place:=0); emit(goto nextstat+2); emit(E.place:=1);Eid E.place:=id.place例：布尔表达式ab or cd and ef (1) if ab goto (4) (2) T1:=0 (3) goto (5) (4) T1:=1 (5) if cd goto (8) (6) T2:=0 (7

18、) goto (9) (8) T2:=1 (9) if ab goto (12) (10) T3:=0 (11) goto (13) (12) T3:=1 (13) T4:=T2 and T3 (14) T5:=T1 or T4作为条件控制的布尔表达式n条件语句 if E then S1 else S2，作为转移条件的布尔表达式E，可赋予它两个出口，一个为“真”出口，出向S1；一个为“假”出口，出向S2。 如： if (ab) then x:=x+1 if ab goto E.true goto E.false (+,x,1,T1) (:=,T1,-,x)(1) ( jc or bc goto

19、 L2 goto L1 L1: if bd goto L2 goto L3 L2: S1产生的三地址代码序列 goto Lnext L3: S2产生的三地址代码序列 Lnext: 后继语句产生布尔表达式三地址代码的语义规则n例：ab or cd and ef if ab goto Ltrue goto L1 L1: if cd goto L2 goto Lfalse L2: if ef goto Ltrue goto Lfalse用四元式实现三地址代码n(jnz，a，p)表示if a goto pn(jrop，x，y，p)表示if x rop y goto pn(j，p)表示 goto pn记

20、录需回填地址的四元式，把需回填E.true的四元式拉成一链，把需回填E.false的四元式拉成一链，分别称做“真”链和“假”链。（10）goto E.true （20） goto E.true （30） goto E.true则链成（10） goto （0） （20） goto （10） （30） goto （20）把地址（30）称作“真”链链首，0为链尾标志，即地址（10）为“真”链链尾。语义描述使用的变量和过程：语义描述使用的变量和过程： E.truelist ： “真真”链，链， E.falselist ： “假假”链链 。 Nextquad： makelist(i)：下一条将要产生但尚

21、未形成的四元式的地址下一条将要产生但尚未形成的四元式的地址 emit( )： 输出一条四元式输出一条四元式 merge(p1, p2)： 把把 p1的链首填在的链首填在p2 的链尾的链尾例：例： merge(p1, p2)(p10) goto ( 0) p1 链链 (p100) goto (p10)(p1) goto (p100)(p20) goto( 0) p2 链链 (p200) goto (p20)(p2) goto (p200) backpatch(p,t)把把链首链首p所链接的每个四元式的第四区段都填为所链接的每个四元式的第四区段都填为t创建一个仅含创建一个仅含i i的新链表，的新链

22、表，i i是四元式的标号是四元式的标号语语句句 if ab or cd and ef then S1 else S2的的四四元元式式(1) if ab goto (7) (E.true ) (1)和和(5）(2) goto (3) 拉拉链链（真真）(3) if cd goto (5)(4) goto (p+1)(E.false)(4) 和和(6)(5) if ef goto (7)拉拉链链（假假）(6) goto (p+1)(7)( S1的的四四元元式式 (p-1) ）(p) goto (q)(p+1) (S2的的四四元元式式(q-1) ）(q)自下而上分析中的一种翻译方案：自下而上分析中的一

23、种翻译方案：(1) EE1 or ME2 backpatch(E1.falselist, M.quad); E.truelist:=merge(E1.truelist, E2.truelist) E.falselist:= E2.falselist(2) EE1 and ME2 backpatch(E1.truelist, M.quad); E.truelist:= E2.truelist; E.falselist:= merge(E1.falselist,E2.falselist);(3) Enot E1 E.truelist:= E1.falselist; E.falselist:= E1

24、.truelist(4) E(E1) E.truelist:= E1.truelist; E.falselist:= E1.falselist (5) Eid1 rop id2 E.truelist:=makelist(nextquad); E.false:= makelist(nextquad+1); emit(j rop , id1.place , id2.place , 0 ); emit(j,-,-,0 ) (6) Eid E.truelist:= makelist(nextquad); E.false:= makelist(nextquad+1); emit (jnz , id.pl

25、ace , , 0 ); emit(j,-,-,0 ) (7) M M.quad:= nextquad例： ab or cd and efab: (1) ( j,a,b,_ ) (2) ( j,-,-,_)cd: (3) ( j,c,d,_ ) (4) ( j,-,-,_ )ef: (5) ( j,e,f,_ ) (6) ( j,-,-,_ ) (3) ( j,c,d,(5) ) (4) ( j,-,-,_ )E.true (5) ( j,e,f,_ ) (6) ( j,-,-,(4) )相同出口(1) ( j,a,b,_ )(2) ( j,-,-,(3) ) (3) ( j,c,d,(5)

26、) (4) ( j,-,-,_ ) (5) ( j,e,f,_ ) (6) ( j,-,-,(4) )E.trueE.falseE.true控制流语句nIf-then,if-then-else,while-don文法：Sif E then S1 | if E then S1 else S2 | while E do S1E.trueE.falseE.trueE.falseifthenE.trueE.falseE.trueE.falseS.nextifthenelseE.trueE.falseE.trueE.falseS. beginwhiledon如while ab do if cd then

27、 x:=yz else x:=y-z翻译为：L1: if ab goto L2 goto LnextL2: if cd goto L3 goto L4L3: T1:=y+z x:=T1 goto L1L4: T2:=y-z x:=T2 goto L1Lnext: 后继语句翻译模式为：用四元式实现三地址代码例：nwhile (ab) do if (cd) then x:=y+z nbegin while (ab) do x:=x+y x:=x+z end用四元式实现三地址代码标号与goto语句n带标号的语句形式：L:S 当该语句被处理之后，标号L称为“定义了”的，即标号L的地址栏将登记语句S的第一个四元式的地址。goto L 产生四元式(j，P) 不完全四元式(j，)向后转移L已