7-中间代码汇总课件

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

2、 code)是源程序的一种内部表示，不依赖目标机的结构，易于生成。中间代码的几种形式：逆波兰式四元式三元式间接三元式树图。7.1中间代码7/14/20224北京电子科技学院逆波兰式：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四元式是一个带有四个域的记录结构，这四个域分别称为: op、arg1, arg2 及result.op代

3、表运算符。语句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, , ,标号)。 7/14/20225北京电子科技学院例 : A + B * ( C - D ) + E / ( C - D ) N三元式： ( - C D ) ( * B (1) ) ( + A (2) ) ( - C D ) ( (4) N ) ( / E (5) ) ( + (3) (6) )为

4、了避免把临时变量填入到符号表，可以通过计算这个临时变量值的语句的位置来引用这个临时变量。这样表示三地址代码的记录只需三个域：op 、argl和 arg2 7/14/20226北京电子科技学院间接三元式：间接三元式序列： 间接码表：(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 ) + E / ( C - D ) N为了便于代码优化处理，有时不直接使用三元式表，而是另设一张指

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

6、院例 : A + B * ( C - D ) + E / ( C - D ) N树:+*AB-CD/EN-CD7/14/20229北京电子科技学院DAG图表示:例 : A + B * ( C - D ) + E / ( C - D ) N+*AB-CD/EN7/14/202210北京电子科技学院(1)语句：可执行语句：生成四元式不可执行语句（说明语句）：填写符号表(2)翻译的要点：确定语句的目标代码结构确定中间代码形式添加语义动作(3)数据结构：符号表、四元式表、临时变量表7.2语句的翻译7/14/202211北京电子科技学院1.简单算术表达式和赋值语句的四元式翻译文法：Sid:=E EE1+

7、E2 |E1 *E2 |-E1|(E1)|id四元式形式:(op,arg1,arg2,result) result:=arg1 op arg2语义属性：表示id所代表的名字本身 E.place表示存放E值的变量名在符号表的入口或整数码(若此变量是一个临时变量);7/14/202212北京电子科技学院函数：newtemp,每次调用它都返回一个代表新临时变量名的整数码,临时变量名按产生的顺序可想象为T1,T2 Tn 。过程：lookup()检查变量名是否在符号表中。在，则返回地址；否，则返回nil。 emit (op, arg1, arg2, result)将四元式放入

8、中间代码序列中。7/14/202213北京电子科技学院例：(1)S id:=E p:=lookup(); 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) E - E1 E.place:=newtemp; emit(,E1.PLACE, ,E.PLACE) (5) E

9、( E1) E.place:= E1.place (6) Eid E.place:=newtemp; P:=lookup(); if Pnil then E.place:=P else error7/14/202214北京电子科技学院输入 栈 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 (,B,_,T1)*(C+D) id:=E A_T1(C+D) id:=E* A_T1_C+D) id:=E*( A_T1_

10、 _+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例:自下而上分析时赋值句的翻译步骤7/14/202215北京电子科技学院布尔表达式的基本作用：计算逻辑值用作控制流语句if-then、if-then

11、-else、while-do等之中的条件表达式布尔表达式文法：EE and E|E or E | not E|(E)| i | i rop i rop为关系运算符()2.布尔表达式的翻译7/14/202216北京电子科技学院布尔表达式的翻译：第一种翻译法,如同算术表达式一样，一步不差地从表达式各部分的值计算出整个表达式的值;例： 1 or (not 0 and 0)or 0 =1 or (1 and 0) or 0 =1 or 0 or 0 =1 or 0 =1例:A or B and C=D被翻译为如下四元式 OP ARG1 ARG2 RESULT = C D T1 and B T1 T2

12、or A T2 T37/14/202217北京电子科技学院第二种翻译法:采取某种优化措施。例如，假定要计算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 解释成：if A then false else true7/14/202218北京电子科技学院布尔表达式的四元式翻译：EE1 or E2 E.place:=n

13、ewtemp; 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.place7/14/202219北京电子科技学院Eid1 rop id2 E.place:=newtemp; emit(jrop, id1.place ,id2.place, nextstat+3 ); emit

14、(:=, 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。7/14/202220北京电子科技学院例：ab or cd and ef的四元式：100： (j,a,b,103)101: (:=,0,_,T1)102: (j ,_,_,104)103: (:=,

15、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)7/14/202221北京电子科技学院控制语句中布尔表达式的翻译控制语句Sif E then S1 else S2条件表达式E的作用仅在于控制对S1和S2的选择，只要能完成这一使命，E的值就无须最终保留在某个临时单元之中。因此，作为转移条件的布尔式

16、E，赋予它两种“出口”，一种是“真”出口，转向S1;一是“假”出口，转向S2.E.codeS1.codeE.true:S2.codeE.false:goto S.next.S.next:to E.trueto E.falseif-then-else的代码结构7/14/202222北京电子科技学院对于转移条件的布尔式 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 /无条件转向四元式p7/14/202223北京电子科技学院例如

17、：可把语句 if A or 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)7/14/202224北京电子科技学院对于E=E1 or E2的形式：如果E1为真，则E为真。即 E1的真出口就是E的真出口；如果E1为假，必须计算E2。E1的假出口是E2的第一个四元式序号，这时E

18、2的真假出口就是E的真假出口。例：ab or cf if ab goto E.true(2) goto 3(3) if cf goto E.true(6) goto E.false E.true, E.false是E的继承属性, E.true是E为真时控制流转向的标号; E.false是E为假时控制流转向的标号,函数newlabel返回新的标号，将放在某个四元式序列号前.7/14/202225北京电子科技学院产生式语义规则EE1 or E2E1.true:=E.true; E1.false:=newlabel; E2.true:=E.true; E2.false:=E.false E.code

19、:=E1.code| gen(E1.false:)|E2.code控制流语句中的布尔表达式的翻译的基本思想: 假定E 形如ad,则将生成如下的E的代码： if ab goto E.true /(j, a, b, E.true) goto E.false /(j, _,_,E.false) 语法制导定义7/14/202226北京电子科技学院产生式语义规则EE1 and E2E1.true:= newlabel; E1.false:= E.false; E2.true:=E.true; E2.false:=E.false; E.code:=E1.code gen(E1.true:) E2.code

20、（接上页）Enot E1 E1.true:= E.false; E1.false:= E.true; E.code:=E1.code 7/14/202227北京电子科技学院产生式语义规则Eid1 rop id2E.code:=gen(if id1.place rop.op id2.place goto E.true)| gen(goto E.false)Etrue E.code:=gen(goto E.true) Efalse E.code:=gen(goto E.false) E(E1) E1.true:= E.true; E1.false:= E.false; E.code:=E1.cod

21、e （接上页）函数gen生成一个四元式, E.code是E的四元式序列。7/14/202228北京电子科技学院表达式 ab or cd and ef的中间代码翻译：两遍扫描:1.构造语法树；2.按深度优先遍历翻译。假定整个条件表达式的真、假出口为LT和LF,则：EEorEEandEabcdefL2: (5)if ef goto LT (6)goto LF .true=LT.false=LFLTL1LTLFL2LFLTLF(1)if ab goto LT(2)goto L1L1: (3)if cd goto L2 (4)goto LF 问题：LT、LF何时才能知道？7/14/202229北京电子

22、科技学院上述四元式(1)和(5)(真出口)、(4)和(6) (假出口)的转移地址并不能在四元式产生的同时得知。例如(1)和(5)的转移地址是在整个布尔表达式产生完毕才能得知。因此要回填这个地址。为了记录回填地址的四元式，常常采用“拉链”的办法，把需要回填E.true的四元式拉成一条链，把需要回填E.false的四元式拉成一条链,分别称作“真”链和“假”链。(p) (,0)(q)(,p)(r)(,q) 地址(r)是E.true链头7/14/202230北京电子科技学院例：(10)goto E.true(20)goto E.true(30)goto E.true拉链成：(10)goto 0(20)

23、goto (10)(30)goto (20)(30)是链头， (10)为链尾。0是链尾标志。又例：goto 语句（前向转移，后向转移）一遍扫描翻译： 先产生暂时没有填写目标标号的转移指令。 对于每一条这样的指令作适当的记录， 一旦目标标号被确定下来，再将它“回填”到相应的指令中。7/14/202231北京电子科技学院标号和转移语句： . goto L; . goto L; . goto L; .L: .拉链返填goto nil.Lgoto .goto L: .7/14/202232北京电子科技学院与拉链返填技术相关变量和函数：nextquad指示器:指向下一个将要形成但尚未形成的四元式的地址.

24、 nextquad初值为1,每执行一次emit之后, nextquad将自动增加1.merge(p1,p2):/函数过程,把p1,p2为链首的两条链合并为一,返回链首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:=p2END7/14/202233北京电子科技学院makelist(i)：创建一个仅包含i的新表，i是四元式数组的一个索引(下标)，或说i是

25、四元式代码序列的一个标号。 backpatch(p,t)：/过程”回填”,把p所链接的每个四元式的第四区段都填为t;PROCEDURE backpatch(p,t);BEGIN Q:=p; WHILE Q0 DO BEGIN q:=四元式Q的第四区段的内容; 把t填进四元式Q的第四区段; Q:=q END OF WHILEEND7/14/202234北京电子科技学院自下而上分析中使用回填翻译布尔表达式 布尔表达式文法： （1）EE1 or M E2 （2） |E1 and M E2 （3） |not E1 （4） |(E1) （5） |id1 rop id2 （6） |true （7） |fa

26、lse （8）M插入非终结符号M是为了引入一个语义动作，以便在适当的时候获得即将产生的下一个四元式的序号。7/14/202235北京电子科技学院使用一遍扫描的布尔表达式的翻译模式：/ 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;

27、E.falselist:=merge(E1.falselist，E2.falselist);7/14/202236北京电子科技学院Enot E1 E.truelist:=E1.falselist; E.falselist:=E1.truelist E ( E ) E.truelist:= E1.truelist; E.falselist:=E1.falselistE id1 rop id2 E.truelist:= makelist(nextquad); E.falselist:= makelist(nextquad+1); emit(j rop.op，id1.place ，id2.place

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

29、3,105orM.q=102abE.t=102E.f=103E.t=104E.f=105andM.q=104cdef ( j,a,b,0 )(101) ( j ,_,_,0 )(102) ( j,c,d,0 )(103) ( j ,_,_,0 )(104) ( j,e,f,0 )(105) (106) ( j ,_,_,0 )(100) 1041027/14/202239北京电子科技学院依次分析,得到如下四元式： 100 ： if ab goto- 101 ： goto- 102 ：if cd goto- 103 ： goto- 104 ： if ef goto- 105 ： goto- 经过

30、回填得到： 100 ： if ab goto 101 ： goto l02 102 ： if cd goio l04 103 ： goto 104 ： if ef goto 105 ： goto 根据上述语义动作的描述，当整个表达式所相应的四元式都产生后，作为整个表达式的真、假出口仍没有填上，他们分别由E.true和E.false记录。一旦整个布尔式的真假出口确定后，则可沿“真”，“假”链为相应的四元式填上。例如if-then-else语句，那么当分别扫描到then 和else之后，便可回填真假出口。7/14/202240北京电子科技学院3.控制语句的翻译控制流语句文法： Sif E then

31、 S1 | if E then S1 else S2 | while E do S1 E.codeS1.codeE.true:.E.false:(a) if-thento E.trueto E.false代码结构：7/14/202241北京电子科技学院E.codeS1.codeE.true:S2.codeE.false:goto S.next.S.next:to E.trueto E.false(b)if-then-elseE.codeS1.codeE.true:E.false:goto S.begin.S.begin:to E.falseto E.true(c )while-do7/14/2

32、02242北京电子科技学院语法制导定义：产生式语义规则Sif E then S1E.true:=newlabel; E.false:=S.next; S1.next:=S.next S.code:=E.code| gen(E.true:)|S1.code7/14/202243北京电子科技学院产生式语义规则Sif E then S1else S2E.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)| ge

33、n(E.false:)|S2.code(接上页）7/14/202244北京电子科技学院产生式语义规则Swhile E do S1S.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)(接上页）7/14/202245北京电子科技学院例：考虑如下语句 while ab do if cd then x：= yz else x：y-z 根据前面所述，生成代码如右： L1 ： if a

34、b goto L2 goto Lnext L2 ： if cd goto L3 goto L4 L3 ： T1:= yz x:T1 goto L1 L4 ： T2:=y-z x:T2 goto L1 Lnext： 7/14/202246北京电子科技学院文法：（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为一个布尔表达式常用语句的翻译7/14/202247北京电子科技学院控制流语句的翻译模式：Sif E t

35、hen M1 S1 N else M2 S2 backpatch( 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)7/14/202248北京电子科技学院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，_