中间代码汇总课件.ppt

《中间代码汇总课件.ppt》由会员分享，可在线阅读，更多相关《中间代码汇总课件.ppt（54页珍藏版）》请在三一办公上搜索。

1、2022/12/6,北京电子科技学院,1,2022/12/6,北京电子科技学院,2,语义分析的工作有：类型检查、控制流检查，一致性检查，作用域分析等。 可以在语法分析的基础上加上语义规则，直接产生机器语言或汇编语言形式的目标代码。但这种编译方式不利于优化和移植，目标代码质量不高。 现在的编译系统，一般都是将源程序先翻译为某种中间代码，然后再将中间代码翻译成目标代码。这样使得编译程序在逻辑结构上更简单，同时也为代码优化和移植创造了条件。,第七章 语义分析及中间代码生成,2022/12/6,北京电子科技学院,3,本章各种语句的代码生成将结合SPL代码生成的方式对照分析,开展课堂讨论。,2022/1

2、2/6,北京电子科技学院,4,中间代码(Intermediate code)是源程序的一种内部表示，不依赖目标机的结构，易于生成。中间代码的几种形式：逆波兰式四元式三元式间接三元式树图。,7.1中间代码,2022/12/6,北京电子科技学院,5,逆波兰式：A B C D - * + E C D -N / +四元式： ( - C D T1) ( * B T1 T2) ( + A T2 T3) ( - C D T4) ( T4 N T5) ( / E T5 T6) ( + T3 T6 T7),例 : A + B * ( C - D ) + E / ( C - D ) N,四元式是一个带有四个域的记

3、录结构，这四个域分别称为: op、arg1, arg2 及result.op代表运算符。语句x:y op z 可表示为(op,y,z,x)。= (op,y,z,T1) (:=,T1, ,x)一目运算符的语句如：x:= -y 或者x:=y 表示为: (,y, ,x) 或(:=,y, ,x)条件和无条件转移语句将目标标号置于result域中。 (j, , ,标号)或(jrop, , ,标号)。,2022/12/6,北京电子科技学院,6,例 : A + B * ( C - D ) + E / ( C - D ) N,三元式： ( - C D ) ( * B (1) ) ( + A (2) ) ( -

4、 C D ) ( (4) N ) ( / E (5) ) ( + (3) (6) ),为了避免把临时变量填入到符号表，可以通过计算这个临时变量值的语句的位置来引用这个临时变量。这样表示三地址代码的记录只需三个域：op 、argl和 arg2,2022/12/6,北京电子科技学院,7,间接三元式：,间接三元式序列：,间接码表：(1)(2)(3)(1)(4)(5)(6),(1) ( - C D ),(2) ( * B (1) ),(3) ( + A (2) ),(4) ( (1) N ),(5) ( / E (4) ),(6) ( + (3) (5 ) ),例 : A + B * ( C - D

5、) + E / ( C - D ) N,为了便于代码优化处理，有时不直接使用三元式表，而是另设一张指示器（称为间接码表），它将按运算的先后顺序列出有关三元式在三元表中的位置。换句话说就是，用一张间接码表辅以三元式表的办法来表示中间代码。这种表示法称为间接三元式。,2022/12/6,北京电子科技学院,8,四元式与三元式和间接三元式作一些比较,四元式之间的联系是通过临时变量实现的。这一点和三元式不同。要更动一张三元表是很困难的，它意味着必须改变其中一系列指示器的值。但要更动四元式表是很容易的，因为调整四元式之间的相对位置并不意味着必须改变其中一系列指示器的值。因此，当需要对中间代码进行优化处理时

6、，四元式比三元式要方便得多。对优化这一点而言，四元式和间接三元式同样方便。,2022/12/6,北京电子科技学院,9,例 : A + B * ( C - D ) + E / ( C - D ) N,2022/12/6,北京电子科技学院,10,DAG图表示:,例 : A + B * ( C - D ) + E / ( C - D ) N,2022/12/6,北京电子科技学院,11,(1)语句：可执行语句：生成四元式不可执行语句（说明语句）：填写符号表(2)翻译的要点：确定语句的目标代码结构确定中间代码形式添加语义动作(3)数据结构：符号表、四元式表、临时变量表,7.2语句的翻译,2022/12/

7、6,北京电子科技学院,12,1.简单算术表达式和赋值语句的四元式翻译,文法：Sid:=E EE1+E2 |E1 *E2 |-E1|(E1)|id四元式形式:(op,arg1,arg2,result) result:=arg1 op arg2语义属性：id.name表示id所代表的名字本身 E.place表示存放E值的变量名在符号表的入口或整数码(若此变量是一个临时变量);,2022/12/6,北京电子科技学院,13,函数：newtemp,每次调用它都返回一个代表新临时变量名的整数码,临时变量名按产生的顺序可想象为T1,T2 Tn 。过程：lookup(id.name)检查变量名是否在符号表中。

8、在，则返回地址；否，则返回nil。 emit (op, arg1, arg2, result)将四元式放入中间代码序列中。,2022/12/6,北京电子科技学院,14,例：(1)S id:=E p:=lookup(id.name); if nil then emit(:=, E.place, , p) else error (2) EE1+E2 E.place:= newtemp; emit(+, E1.place, E2.place ,E.place) (3) EE1*E2 E.place:= newtemp; emit(*, E1.place, E2.place ,E.place) (4)

9、 E - E1 E.place:=newtemp; emit(,E1.PLACE, ,E.PLACE) (5) E( E1) E.place:= E1.place (6) Eid E.place:=newtemp; P:=lookup(id.name); if Pnil then E.place:=P else error,2022/12/6,北京电子科技学院,15,输入 栈 PLACE 四元式A:=-B*(C*D):=-B*(C+D) id A-B*(C+D) id:= A_B*(C+D) id:=- A_ _*(C+D) id:=-id A_ _B*(C+D) id:=-E A_ _B (

10、,B,_,T1)*(C+D) id:=E A_T1(C+D) id:=E* A_T1_C+D) id:=E*( A_T1_ _+D) id:=E*(id A_T1_ _C+D) id:=E*(E A_T1_ _CD) id:=E*(E+ A_T1_ _C_) id:=E*(E+id A_T1_ _C_D) id:=E*(E+E A_T1_ _C _D ) id:=E*(E A_T1_ _ T2 (+,C,D,T2) id:=E*(E) A_T1_ _T2 _ id:=E*E A_T1_ T2 (* ,T1,T2,T3) id:=E A_T3 (:=,T3,_,A) S,例:自下而上分析时赋值句

11、的翻译步骤,2022/12/6,北京电子科技学院,16,布尔表达式的基本作用：计算逻辑值用作控制流语句if-then、if-then-else、while-do等之中的条件表达式布尔表达式文法：EE and E|E or E | not E|(E)| i | i rop i rop为关系运算符(),2.布尔表达式的翻译,2022/12/6,北京电子科技学院,17,布尔表达式的翻译：第一种翻译法,如同算术表达式一样，一步不差地从表达式各部分的值计算出整个表达式的值;例： 1 or (not 0 and 0)or 0 =1 or (1 and 0) or 0 =1 or 0 or 0 =1 or

12、0 =1例:A or B and C=D被翻译为如下四元式 OP ARG1 ARG2 RESULT = C D T1 and B T1 T2 or A T2 T3,2022/12/6,北京电子科技学院,18,第二种翻译法:采取某种优化措施。例如，假定要计算A or B，如果计算出A的值为1，B的值就无需再计算了。同理，在计算A and B时，若发现A的值为0，则B的值也无需计算。可以用if-then-else结构来翻译布尔表达式：把 A or B 解释成：if A then true else B把 A and B 解释成：if A then B else false把 not A 解释成：i

13、f A then false else true,2022/12/6,北京电子科技学院,19,布尔表达式的四元式翻译：EE1 or E2 E.place:=newtemp; emit(or, E1.place , E2.place ,E.place )EE1 and E2 E.place:=newtemp; emit(and, E1.place , E2.place ,E.place )Enot E1 E.place:=newtemp; emit(not, E1.place , _ ,E.place )E(E1) E.place:= E1.place,2022/12/6,北京电子科技学院,20

14、,Eid1 rop id2 E.place:=newtemp; emit(jrop, id1.place ,id2.place, nextstat+3 ); emit(:=, 0 , _,E.place); emit(j, _ ,_ , nextstat+2); emit(:=, 1 , _,E.place)Etrue E.place:=newtemp; emit(:= , 1,_ ,E.place)Efalse E.place:=newtemp; emit(:= ,0,_ ,E.place),nextsta为四元式序列号,每生成一条四元式,nextsta便加1。,2022/12/6,北京电子

15、科技学院,21,例：ab or cd and ef的四元式：100： (j,a,b,103)101: (:=,0,_,T1)102: (j ,_,_,104)103: (:=,1,_,T1)104: (j,c,d,107)105: (:=,0,_,T2)106: (j ,_,_,108)107： (:=,1,_,T2)108: (j,e,f,111)109: (:=,0,_,T3)110: (j ,_,_,112)111: (:=,1,_,T3)112: (and,T2,T3 ,T4)113: (or,T1,T4 ,T5),2022/12/6,北京电子科技学院,22,控制语句中布尔表达式的翻译

16、,条件表达式E的作用仅在于控制对S1和S2的选择，只要能完成这一使命，E的值就无须最终保留在某个临时单元之中。因此，作为转移条件的布尔式E，赋予它两种“出口”，一种是“真”出口，转向S1;一是“假”出口，转向S2.,2022/12/6,北京电子科技学院,23,对于转移条件的布尔式 E,翻译成仅含下述三种形式的四元式序列：(jnz,a,_,p) 表示 if a goto p /(p=E.true)(jrop,a,b,p) 表示if a rop b goto p (j,_,_,p) 表示goto p /无条件转向四元式p,2022/12/6,北京电子科技学院,24,例如：可把语句 if A or

17、BD then S1 else S2 翻译成如下的一串四元式：,(1) (jnz,A,_,5) A的真出口为5(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),2022/12/6,北京电子科技学院,25,对于E=E1 or E2的形式：如果E1为真，则E为真。即 E1的真出口就是E的真出口；如果E1为假，必须计算E2。E1的假出口是E2的第一个四元式序号，这时E2的真假出口就是E

18、的真假出口。,例：af if af goto E.true(6) goto E.false,E.true, E.false是E的继承属性, E.true是E为真时控制流转向的标号; E.false是E为假时控制流转向的标号,函数newlabel返回新的标号，将放在某个四元式序列号前.,2022/12/6,北京电子科技学院,26,语法制导定义,2022/12/6,北京电子科技学院,27,2022/12/6,北京电子科技学院,28,（接上页）,函数gen生成一个四元式, E.code是E的四元式序列。,2022/12/6,北京电子科技学院,29,表达式 ab or cd and ef的中间代码翻译

19、：两遍扫描:1.构造语法树；2.按深度优先遍历翻译。假定整个条件表达式的真、假出口为LT和LF,则：,L2: (5)if ef goto LT (6)goto LF,.true=LT.false=LF,LTL1,LTLF,L2LF,LTLF,(1)if ab goto LT(2)goto L1,L1: (3)if cd goto L2 (4)goto LF,问题：LT、LF何时才能知道？,2022/12/6,北京电子科技学院,30,上述四元式(1)和(5)(真出口)、(4)和(6) (假出口)的转移地址并不能在四元式产生的同时得知。例如(1)和(5)的转移地址是在整个布尔表达式产生完毕才能得知

20、。因此要回填这个地址。为了记录回填地址的四元式，常常采用“拉链”的办法，把需要回填E.true的四元式拉成一条链，把需要回填E.false的四元式拉成一条链,分别称作“真”链和“假”链。,(p) (,0)(q)(,p)(r)(,q) 地址(r)是E.true链头,2022/12/6,北京电子科技学院,31,例：(10)goto E.true(20)goto E.true(30)goto E.true,拉链成：(10)goto 0(20)goto (10)(30)goto (20)(30)是链头， (10)为链尾。0是链尾标志。,又例：goto 语句（前向转移，后向转移）,一遍扫描翻译： 先产生

21、暂时没有填写目标标号的转移指令。 对于每一条这样的指令作适当的记录， 一旦目标标号被确定下来，再将它“回填”到相应的指令中。,2022/12/6,北京电子科技学院,32,标号和转移语句： . goto L; . goto L; . goto L; .L: .,goto nil,.,L,goto,.,goto,L: .,2022/12/6,北京电子科技学院,33,与拉链返填技术相关变量和函数：nextquad指示器:指向下一个将要形成但尚未形成的四元式的地址. nextquad初值为1,每执行一次emit之后, nextquad将自动增加1.,merge(p1,p2):/函数过程,把p1,p2为

22、链首的两条链合并为一,返回链首p2(p1);POINTER PROCEDURE merge(p1,p2);IF p2=0 THEN merge:=p1 ELSEBEGIN p:=p2; WHILE 四元式p的第四区段的内容不为0 DO P:=四元式p的第四区段的内容; /找p2尾把p1填进四元式p的第四区段; merge:=p2END,2022/12/6,北京电子科技学院,34,makelist(i)：创建一个仅包含i的新表，i是四元式数组的一个索引(下标)，或说i是四元式代码序列的一个标号。,backpatch(p,t)：/过程”回填”,把p所链接的每个四元式的第四区段都填为t;PROCED

23、URE backpatch(p,t);BEGIN Q:=p; WHILE Q0 DO BEGIN q:=四元式Q的第四区段的内容; 把t填进四元式Q的第四区段; Q:=q END OF WHILEEND,2022/12/6,北京电子科技学院,35,自下而上分析中使用回填翻译布尔表达式 布尔表达式文法： （1）EE1 or M E2 （2） |E1 and M E2 （3） |not E1 （4） |(E1) （5） |id1 rop id2 （6） |true （7） |false （8）M插入非终结符号M是为了引入一个语义动作，以便在适当的时候获得即将产生的下一个四元式的序号。,2022/1

24、2/6,北京电子科技学院,36,使用一遍扫描的布尔表达式的翻译模式：/ M.quad记录E2代码序列的第一条四元式序号。,EE1 or M E2 backpatch(E1.falselist，M.quad); E.truelist:=merge(E1.truelist，E2.truelist); E.falselist:=E2.falselist ,EE1 and M E2 backpatch(E1.truelist，M.quad); E.truelist:=E2.truelist; E.falselist:=merge(E1.falselist，E2.falselist);,2022/12/

25、6,北京电子科技学院,37,Enot E1 E.truelist:=E1.falselist; E.falselist:=E1.truelist ,E ( E ) E.truelist:= E1.truelist; E.falselist:=E1.falselist,E id1 rop id2 E.truelist:= makelist(nextquad); E.falselist:= makelist(nextquad+1); emit(j rop.op，id1.place ，id2.place，0 ); emit(j, _，_， 0 ); ,2022/12/6,北京电子科技学院,38,E

26、true E.truelist:= makelist(nextquad); emit(j，_，_，0); E false E.falselist:= makelist(nextquad); emit(j，_，_，0); M M.quad:=nextquad / M.quad记录E2代码序列的第一条四元式序号。,2022/12/6,北京电子科技学院,39,表达式ab or cd and ef加了注释的分析树如图所示：,E.t=100,104E.f=103,105,E.t=100E.f=101,E.t=104E.f=103,105,or,M.q=102,E.t=102E.f=103,E.t=104

27、E.f=105,and,M.q=104,(100),104,102,2022/12/6,北京电子科技学院,40,依次分析,得到如下四元式： 100 ： if ab goto- 101 ： goto- 102 ：if cd goto- 103 ： goto- 104 ： if ef goto- 105 ： goto-,经过回填得到： 100 ： if ab goto 101 ： goto l02 102 ： if cd goio l04 103 ： goto 104 ： if ef goto 105 ： goto ,根据上述语义动作的描述，当整个表达式所相应的四元式都产生后，作为整个表达式的真、

28、假出口仍没有填上，他们分别由E.true和E.false记录。一旦整个布尔式的真假出口确定后，则可沿“真”，“假”链为相应的四元式填上。例如if-then-else语句，那么当分别扫描到then 和else之后，便可回填真假出口。,2022/12/6,北京电子科技学院,41,3.控制语句的翻译,控制流语句文法： Sif E then S1 | if E then S1 else S2 | while E do S1,2022/12/6,北京电子科技学院,42,2022/12/6,北京电子科技学院,43,语法制导定义：,产生式,语义规则,Sif E then S1,E.true:=newlabe

29、l; E.false:=S.next; S1.next:=S.next S.code:=E.code| gen(E.true:)|S1.code,2022/12/6,北京电子科技学院,44,产生式,语义规则,Sif E then S1else S2,E.true:=newlabel; E.false:=newlabel; S1.next:=S.next; S2.next:=S.next; S.code:=E.code| gen(E.true:)|S1.code gen(gotoS.next)| gen(E.false:)|S2.code,(接上页）,2022/12/6,北京电子科技学院,45,

30、产生式,语义规则,Swhile E do S1,S.begin:=newlabel; E.true:=newlabel; E.false:= S.next; S1.next:=S.begin; S.code:=gen(S.begin: E.code gen(E.true:) S1.code gen(gotoS.begin),(接上页）,2022/12/6,北京电子科技学院,46,例：考虑如下语句 while ab do if cd then x：= yz else x：y-z 根据前面所述，生成代码如右：,L1 ： if ab goto L2 goto Lnext L2 ： if cd got

31、o L3 goto L4 L3 ： T1:= yz x:T1 goto L1 L4 ： T2:=y-z x:T2 goto L1 Lnext：,2022/12/6,北京电子科技学院,47,文法：（1）Sif E then S （2） | if E then S else S （3） | while E do S （4） | begin L end （5） | A （6）LL；S （7） |S S表示语句L表示语句表A为赋值语句E为一个布尔表达式,常用语句的翻译,2022/12/6,北京电子科技学院,48,控制流语句的翻译模式：Sif E then M1 S1 N else M2 S2 back

32、patch( E.truelist，M1.quad); backpatch( E.falselist， M2.quad); S.nextlist:=merge(S1.nextlist,N.nextlist, S2.nextlist)2.N N.nextlist:=makelist(nextquad); emit(j, _,_, 0 ) /当真语句段执行完后,跳出3.M M.quad:=nextquad 4.Sif E then M S1 backpatch( E.truelist，M.quad); S.nextlist:=merge(E.falselist，S1.nextlist),2022/

33、12/6,北京电子科技学院,49,5.Swhile M1 E do M2 S1/M1处生成标号S.begin,反填S1.nextlist, M2处反填E.truelist backpatch(S1.nextlist，M1.quad); backpatch(E.truelist，M2.quad); S.nextlist:=E.falselist; emit(j，_，_，M1.quad) 6.S begin L end S.nextlist:=L.nextlist7.S A S.nextlist:=makelist( )/初始化为空表8.LL1;M S backpatch(L1.nextlist，

34、M.quad); L.nextlist:=S.nextlist 9.LS L.nextlist:=S.nextlist ,2022/12/6,北京电子科技学院,50,翻译模式结构图：Sif E then M1 S1 N else M2 S2,to E.true,M1处反填E.truelistM2处反填E.falselistN处生成(j,_,_,S.next),先记录要回填的转移指令地址，在适当的时候进行回填，以便赋值和布尔表达式的求值得到合适的连接，以完成程序的控制流程。,2022/12/6,北京电子科技学院,51,例:用自底向上的分析法生成四元式代码,其中A1, A2和A3 均表示赋值语句(

35、假设各含10个四元式)。 if ab or cd and ef then A1 else A2； while ab do A3;,100: (j , a, b , 106 )101: (j , _, _, l02 )102: (j , c, d , 104 )103: (j , _, _, l17 )104: (j , e, f , 106 ) 105: (j , _, _, l17 )106 反填E.truelist (关于A1的四元式 )116: (j , _, _, l27 ),117: 反填E.falselist (关于A2的四元式 ) 127: 反填S.nextlist (j , a

36、, b , 129 )128: (j , _, _, l40 )129: 反填E.truelist (关于A3的四元式 ) 139: (j , _, _, l27 ) 140: 反填E.falselist,2022/12/6,北京电子科技学院,52,例：语句:while (AB) do if (CD) then X:=Y+Z 被翻译成如下一串四元式：100 (j,A,B,102)101 (j ,_ ,_,107) (j ,C,D,104)103 (j ,_ ,_,100)104 (+ ,Y,Z, T )105 (:= ,T,_, X )106 (j ,_,_, 100)107,2022/12/6,北京电子科技学院,53,本章重点,了解各种中间代码形式，掌握四元式；掌握拉链返填技术；掌握控制语句的四元式生成。了解说明语句的处理和类型检查,2022/12/6,北京电子科技学院,54,HOMEWORK,P217#3,6,7,