编译原理与技术 中间代码生成1.ppt

《编译原理与技术 中间代码生成1.ppt》由会员分享，可在线阅读，更多相关《编译原理与技术 中间代码生成1.ppt（43页珍藏版）》请在三一办公上搜索。

1、2023/4/26,编译原理与技术讲义,1,编译原理与技术,中间代码生成,2023/4/26,编译原理与技术讲义,2,中间代码生成,布尔表达式翻译控制流语句翻译,2023/4/26,编译原理与技术讲义,3,布尔表达式的翻译,布尔表达式文法G4EE1 or E2|E1 and E2|not E1|(E1)|id1 relop id2|true|false|id3布尔运算符 or、and 和 not（优先级、结合性）关系运算符 relop：、和布尔常量：true和false布尔变量：id3,2023/4/26,编译原理与技术讲义,4,布尔表达式的翻译,两种翻译方法 数值表示法（完全计算）类似算术表

2、达式的翻译，如布尔表达式true and false or(2 1)的计算为false or(21)false or truetrue 短路计算法（不完全计算或解释法）A or B if A then true else BA and B if A then B else false not A if A then false else true借助控制流语句的思路，部分（不完全地用转移语句）“计算”布尔表达式的值以确定整个表达式的真、假。,2023/4/26,编译原理与技术讲义,5,布尔表达式的翻译,数值表示法用1表示true，0代表false。（1）EE1 or E2 t:=newtemp

3、;emit(t“:=”E1.place“or”E2.place);E.place:=t（2）EE1 and E2（3）Enot E1（4）E(E1),2023/4/26,编译原理与技术讲义,6,布尔表达式的翻译,数值表示法（5）E id1 relop id2 t:=newtemp;emit(“if”id1.place relop.op id2.place goto nextcode+3);emit(t“:=”0);emit(“goto”nextcode2);emit(t“:=”1);E.place:=t;nextcode:emit产生三地址语句的编号;产生后，nextcode+,2023/4/

4、26,编译原理与技术讲义,7,id1 relop id2（关系表达式）,if id1 relop id2 goto i+3,i:,t:=0,i+1:,goto i+4,i+2:,t:=1,i+3:,i+4:,true,false,2023/4/26,编译原理与技术讲义,8,布尔表达式的翻译,数值表示法（6）E true t:=newtemp;emit(t“:=”1);E.place:=t（7）E false t:=newtemp;emit(t“:=”0);E.place:=t（8）E id3 t:=newtemp;emit(if id.place“goto”nexcode+3);emit(t“

5、:=”0);emit(“goto”nextcode+2);emit(t“:=”1);E.place:=t,2023/4/26,编译原理与技术讲义,9,id（布尔变量）,if id goto i+3,i:,t:=0,i+1:,goto i+4,i+2:,t:=1,i+3:,i+4:,true,false,2023/4/26,编译原理与技术讲义,10,e.g.16 af 的三地址码：(100)if ab goto 103(101)t1:=0(102)goto 104(103)t1:=1/以上为ab的翻译(104)if c=d goto 107(105)t2:=0(106)goto 108(107)

6、t2:=1/以上为c=d的翻译,2023/4/26,编译原理与技术讲义,11,e.g.16 af 的三地址码：(108)if ef goto 111(109)t3:=0(110)goto 112(111)t3:=1/以上为ef的翻译(112)t4:=not t3/以上为 not ef 的翻译(113)t5:=t2 and t4/以上为 c=d and not ef 的翻译(115)t6:=t1 or t5/以上为 af 的翻译,2023/4/26,编译原理与技术讲义,12,af,布尔表达式的翻译短路计算,true,L_true,false,true,false,L_false,false,tr

7、ue,L_true-真出口：整个布尔表达式为真时，控制流应转移到的目标语句（代码）；反之为假时则转到 L_false-假出口。,表示转移到的目标语句在有关布尔表达式翻译时尚未确定。,2023/4/26,编译原理与技术讲义,13,布尔表达式的翻译,短路计算e.g.17 af的短路计算三地址码：if af goto L_falsegoto L_true,2023/4/26,编译原理与技术讲义,14,短路计算,E1 or M E2,true,false,真出口,假出口,E1 and M E2,false,true,假出口,真出口,false,true,not E1,false,真出口,假出口,tru

8、e,(E1),假出口,false,真出口,true,2023/4/26,编译原理与技术讲义,15,短路计算,id1 relop id2,true,真出口,假出口,false,true,true,真出口,false,false,假出口,goto,goto,2023/4/26,编译原理与技术讲义,16,短路计算,回填技术布尔表达式短路计算翻译中，产生了转移目标不明确的条件或无条件代码；当有关目标地址确定后，可将这些目标地址填回到有关代码中。将有相同转移目标的转移代码的编号串起来形成链；可以方便回填目标地址。,2023/4/26,编译原理与技术讲义,17,回填技术相关符号属性及语义函数：E.true

9、list：布尔表达式代码中所有转向真出口的代码语句链；E.falselist：所有转向假出口的代码语句链；backpatch(code-list,target-code)/将目标地址target-code填回code-list中每条语句merge(code-list1,code-list2)/合并链code-list1和code-list2（它们包含的语句转移目标相同）makelist(code-No),makelist()建立含语句编号为code-No的链或空链M M.code:=nextcode/获取下一三地址代码（语句）的编号（作为转移目标来回填）,2023/4/26,编译原理与技术讲义

10、,18,短路计算及回填的翻译方案,(1)EE1 or M E2 backpatch(E1.falselist,M.code);E.truelist:=merge(E1.truelist,E2.truelist);E.falselist:=E2.falselist;(2)EE1 and M E2 backpatch(E1.truelist,M.code);E.falselist:=merge(E1.falselist,E2.falselist);E.truelist:=E2.truelist;,2023/4/26,编译原理与技术讲义,19,(3)Enot E1 E.truelist:=E1.fa

11、lselist;E.falselist:=E1.truelist;(4)E(E1)E.truelist:=E1.truelist;E.falselist:=E1.falselist;(5)E id1 relop id2 E.truelist:=makelist(nextcode);emit(“if”id1.place relop.op id2.place“goto”）;E.falselist:=makelist(nextcode);emit(“goto”);,2023/4/26,编译原理与技术讲义,20,(6)E true E.truelist:=makelist(nextcode);emit

12、(“goto”);E.falselist:=makelist();(7)E false E.falselist:=makelist(nextcode);emit(“goto”);E.truelist:=makelist();,2023/4/26,编译原理与技术讲义,21,控制流语句的翻译,描述控制流语句的文法G5：(1)S if E then S1(2)S if E then S1 else S2(3)S while E do S1(4)S for id:=E1 to E2 do S1(5)S begin L end/compound statement(6)S A/赋值语句(7)L L1;S

13、/Statements List(8)L S,2023/4/26,编译原理与技术讲义,22,条件语句的翻译（1）,E.code,S1.code,if E then S1 的代码结构,E.truelist,E.falselist,S1.nextlist,?,M,箭头线表示控制流方向；E.truelist和E.falselist 意义同前；S.nextlist 语句S的代码中所有跳转到未知目标地址的转移代码（如果有的话）的编号链。该未知目标地址是指语义上语句S执行结束后应执行的下一代码的位置。,未知目标地址,2023/4/26,编译原理与技术讲义,23,条件语句的翻译（1）,(1)S if E t

14、hen M S1 backpatch(E.truelist,M.code);S.nextlist:=merge(E.falselist,S1.nextlist),2023/4/26,编译原理与技术讲义,24,条件语句的翻译（2）,E.code,S1.codet:goto,if E then S1 else S2的代码结构,E.truelist,E.falselist,S2.nextlist,S2.code,S1.nextlist,?,未知目标地址,在代码标号t处强制产生无条件转移代码，转移目标待回填。,M1,M2,2023/4/26,编译原理与技术讲义,25,条件语句的翻译（2）,(2)S i

15、f E then M1 S1 N else M2 S2 backpatch(E.truelist,M1.code);backpatch(E.falselist,M2.code);S.nextlist:=merge(S1.nextlist,S2.nextlist,N.code);N N.code:=makelist(nextcode);/标号t emit(“goto”）;,2023/4/26,编译原理与技术讲义,26,循环语句的翻译（1）,M1:E.code,S1.codegoto M1,while E do S1 的代码结构,E.truelist,E.falselist,S1.nextlist

16、,?,M2,产生无条件转移语句goto M1（跳转至循环条件测试代码开始处）,未知目标地址,M1,2023/4/26,编译原理与技术讲义,27,循环语句的翻译（1）,(3)S while M1 E do M2 S1 backpatch(E.truelist,M2.code);backpatch(S1.nextlist,M1.code);S.nextlist:=E.falselist;emit(“goto”M1.code);,2023/4/26,编译原理与技术讲义,28,循环语句的翻译（2）,for id:=E1 to E2 do S1的代码结构,t:if id E2.place goto,S1

17、.code,id:=id+1goto t,id:=E1.place,FALSE,TRUE,?,未知目标地址,待回填的目标地址,S1.nextlist,2023/4/26,编译原理与技术讲义,29,循环语句的翻译（2）,(4)F for id:=E1 to E2 do p:=lookup(id.name);F.place:=p;emit(id“:=”E1.place);t:=nextcode/标号t F.again:=t;F.falselist:=makelist(t);emit(“if”p E2.place“goto”);S F S1 t:=nextcode;emit(F.place“:=”F

18、.place“+”1);emit(“goto”F.again);backpatch(S1.nextlist,t);S.nextlist:=F.falselist;,2023/4/26,编译原理与技术讲义,30,循环语句的翻译（3）,如何翻译C语言的for语句？S for(E1;E2;E3)S1,2023/4/26,编译原理与技术讲义,31,文法G4中其它语句的翻译,(5)S begin L end S.nextlist:=L.nextlist(6)S A S.nextlist:=makelist();/empty/A表示赋值语句；(7)L L1;M S backpatch(L1.nextlis

19、t,M.code);L.nextlist:=S.nextlist;(8)L S L.nextlist:=S.nextlist,2023/4/26,编译原理与技术讲义,32,CASE/SWITCH语句的翻译（0）,(9)S switch E begincase C1:S1;case C2:S2;case Cn-1:Sn-1;default:Sn;end,2023/4/26,编译原理与技术讲义,33,E.codet:goto test(待回填）,Li:Si.codeti:goto next(待回填）,test:if E.place=C1 goto L1 if E.place=C2 goto L2

20、if E.place=Cn-1 goto Ln-1 goto Lnnext:,CASE/SWITCH语句代码结构,2023/4/26,编译原理与技术讲义,34,CASE/SWITCH语句的翻译（1）,(1)分析完 SWITCH E 产生,E.codet:goto test(待回填）,(2)分析完一个 case Ci:Si 产生如下代码，并将标号Li和常量Ci保存到case 情况常量表,Li:Si.codeti:goto next(待回填）,情况常量表,SWITCH中default,2023/4/26,编译原理与技术讲义,35,CASE/SWITCH语句的翻译（2）,(3)分析完 end（SWI

21、TCH结束），此时可以查看情况常量表产生如下代码，并将标号test回填到包含t处的转移代码中。合并所有Si.nextlist和标号ti 即为SWITCH语句的nextlist。,test:if E.place=C1 goto L1 if E.place=C2 goto L2 if E.place=Cn-1 goto Ln-1 goto Lnnext:,情况常量表,2023/4/26,编译原理与技术讲义,36,e.g.17 控制流语句的翻译,翻译以下语句序列：if(ac)do c:=c+1else d:=d+1;e:=e+d;,2023/4/26,编译原理与技术讲义,37,e.g.17 控制流语

22、句的翻译,L2,L1,S5,;,S4,if,E1,then,S2,else,S3,while,E2,do,S1,A1,A2,A3,2023/4/26,编译原理与技术讲义,38,e.g.17 控制流语句的翻译,一、翻译 E1：(ab or cd and ef)(100)if ab goto 106(101)goto 102/用102回填(101)(102)if cd goto 104/用104回填(102)(103)goto 111(104)if ef goto 106(105)goto 111truelist:100,104 falselist:103,105,2023/4/26,编译原理与技

23、术讲义,39,e.g.17 控制流语句的翻译,二、翻译 S2：while E2 do S1(106)if ac goto 108/用108回填(106)(107)goto 112(108)c:=c+1/S1A1 S1.nextlist=(109)goto 106/转至循环入口(106)S2.nextlist:107(110)goto 112/由N生成(111)d:=d+1/S3A2 S3.nextlist=,2023/4/26,编译原理与技术讲义,40,e.g.17 控制流语句的翻译,三、分析完S4用106回填(100)和(104)；用111回填(103)和(105)S4.nextlist:1

24、07,110 四、分析完L1L1.nextlist:107,110 五、分析S5(112)e:=e+d/S5A3 S5.nextlist=,2023/4/26,编译原理与技术讲义,41,e.g.17 控制流语句的翻译,六、分析完L2用112回填(107)和(110)L2.nextlist:,2023/4/26,编译原理与技术讲义,42,(100)if ac goto 108(101)goto 102(107)goto 112(102)if cd goto 104(108)c:=c+1(103)goto 111(109)goto 106(104)if ef goto 106(110)goto 112(105)goto 111(111)d:=d+1(112)e:=e+d,e.g.17 控制流语句的翻译,2023/4/26,编译原理与技术讲义,43,e.g.18 Linux下C语言控制流语句的翻译,1）if语句2）for语句3）do-while 语句,