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

2019/10/28,编译原理与技术讲义,1,编译原理与技术,中间代码生成,2019/10/28,编译原理与技术讲义,2,中间代码生成,布尔表达式翻译 控制流语句翻译,2019/10/28,编译原理与技术讲义,3,布尔表达式的翻译,布尔表达式文法G4 EE1 or E2 | E1 and E2 | not E1 | ( E1 ) | id1 relop id2 | true | false | id3 布尔运算符 or 、and 和 not（优先级、结合性） 关系运算符 relop：、和 布尔常量：true和false 布尔变量：id3,2019/10/28,编译原理与技术讲义,4,布尔表达式的翻译,两种翻译方法 数值表示法（完全计算） 类似算术表达式的翻译，如布尔表达式 true and false or ( 2 1 )的计算为 false or ( 21 )false or truetrue 短路计算法（不完全计算或解释法） 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 true 借助控制流语句的思路，部分（不完全地用转移语句）“计算”布尔表达式的值以确定整个表达式的真、假。,2019/10/28,编译原理与技术讲义,5,布尔表达式的翻译,数值表示法 用1表示true，0代表false。 （1）EE1 or E2 t := newtemp; emit( t “:=” E1.place “or” E2.place); E.place := t （2）EE1 and E2 （3）Enot E1 （4）E( E1 ),2019/10/28,编译原理与技术讲义,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+,2019/10/28,编译原理与技术讲义,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,2019/10/28,编译原理与技术讲义,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 “:=” 0 ); emit( “goto” nextcode+2); emit( t “:=” 1); E.place := t ,2019/10/28,编译原理与技术讲义,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,2019/10/28,编译原理与技术讲义,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) t2 := 1 /以上为c=d的翻译,2019/10/28,编译原理与技术讲义,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 的翻译,2019/10/28,编译原理与技术讲义,12,af,布尔表达式的翻译短路计算,true,L_true,false,true,false,L_false,false,true,L_true-真出口：整个布尔表达式为真时，控制流应转移到的目标语句（代码）；反之为假时则转到 L_false-假出口。,表示转移到的目标语句在有关布尔表达式翻译时尚未确定。,2019/10/28,编译原理与技术讲义,13,布尔表达式的翻译,短路计算 e.g.17 af的短路计算三地址码： if af goto L_false goto L_true,2019/10/28,编译原理与技术讲义,14,短路计算,E1 or M E2,true,false,真出口,假出口,E1 and M E2,false,true,假出口,真出口,false,true,not E1,false,真出口,假出口,true,( E1 ),假出口,false,真出口,true,2019/10/28,编译原理与技术讲义,15,短路计算,id1 relop id2,true,真出口,假出口,false,true,true,真出口,false,false,假出口,goto ,goto ,2019/10/28,编译原理与技术讲义,16,短路计算,回填技术 布尔表达式短路计算翻译中，产生了转移目标不明确的条件或无条件代码； 当有关目标地址确定后，可将这些目标地址填回到有关代码中。 将有相同转移目标的转移代码的编号串起来形成链；可以方便回填目标地址。,2019/10/28,编译原理与技术讲义,17,回填技术 相关符号属性及语义函数： E.truelist ：布尔表达式代码中所有转向真出口的代码语句链； 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 / 获取下一三地址代码（语句）的编号（作为转移目标来回填）,2019/10/28,编译原理与技术讲义,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; ,2019/10/28,编译原理与技术讲义,19,(3) Enot E1 E.truelist := E1.falselist; 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” ); ,2019/10/28,编译原理与技术讲义,20,(6) E true E.truelist := makelist( nextcode ); emit( “goto” ); E.falselist := makelist(); (7) E false E.falselist := makelist( nextcode ); emit( “goto” ); E.truelist := makelist(); ,2019/10/28,编译原理与技术讲义,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 / Statements List (8) L S,2019/10/28,编译原理与技术讲义,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执行结束后应执行的下一代码的位置。,未知目标地址,2019/10/28,编译原理与技术讲义,23,条件语句的翻译（1）,(1) S if E then M S1 backpatch( E.truelist, M.code ); S.nextlist := merge( E.falselist, S1.nextlist ) ,2019/10/28,编译原理与技术讲义,24,条件语句的翻译（2）,E.code,S1.code t: goto ,if E then S1 else S2的代码结构,E.truelist,E.falselist,S2.nextlist,S2.code,S1.nextlist,?,未知目标地址,在代码标号t处强制产生无条件转移代码，转移目标待回填。,M1,M2,2019/10/28,编译原理与技术讲义,25,条件语句的翻译（2）,(2) S if 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” ）; ,2019/10/28,编译原理与技术讲义,26,循环语句的翻译（1）,M1: E.code,S1.code goto M1,while E do S1 的代码结构,E.truelist,E.falselist,S1.nextlist,?,M2,产生无条件转移语句 goto M1（跳转至循环条件测试代码开始处）,未知目标地址,M1,2019/10/28,编译原理与技术讲义,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 ); ,2019/10/28,编译原理与技术讲义,28,循环语句的翻译（2）,for id := E1 to E2 do S1的代码结构,t: if id E2.place goto ,S1.code,id := id + 1 goto t,id := E1.place,FALSE,TRUE,?,未知目标地址,待回填的目标地址,S1.nextlist,2019/10/28,编译原理与技术讲义,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.place “+” 1); emit( “goto” F.again); backpatch( S1.nextlist, t ); S.nextlist := F.falselist; ,2019/10/28,编译原理与技术讲义,30,循环语句的翻译（3）,如何翻译C语言的for语句？ S for ( E1 ; E2 ; E3 ) S1,2019/10/28,编译原理与技术讲义,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.nextlist, M.code); L.nextlist := S.nextlist ; (8) L S L.nextlist := S.nextlist ,2019/10/28,编译原理与技术讲义,32,CASE/SWITCH语句的翻译（0）,(9) S switch E begin case C1 : S1; case C2 : S2; case Cn-1 : Sn-1; default : Sn; end,2019/10/28,编译原理与技术讲义,33,E.code t: goto test ( 待回填）,Li : Si.code ti : goto next ( 待回填）,test : if E.place = C1 goto L1 if E.place = C2 goto L2 if E.place = Cn-1 goto Ln-1 goto Ln next:,CASE/SWITCH语句 代码结构,2019/10/28,编译原理与技术讲义,34,CASE/SWITCH语句的翻译（1）,(1) 分析完 SWITCH E 产生,E.code t: goto test ( 待回填）,(2) 分析完一个 case Ci: Si 产生如下代码，并将标号Li和常量Ci保存到case 情况常量表,Li : Si.code ti : goto next ( 待回填）,情况常量表,SWITCH中default,2019/10/28,编译原理与技术讲义,35,CASE/SWITCH语句的翻译（2）,(3) 分析完 end（SWITCH结束） ，此时可以查看情况常量表产生如下代码，并将标号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 Ln next:,情况常量表,2019/10/28,编译原理与技术讲义,36,e.g.17 控制流语句的翻译,翻译以下语句序列： if ( ac ) do c := c +1 else d := d + 1; e := e + d;,2019/10/28,编译原理与技术讲义,37,e.g.17 控制流语句的翻译,L2,L1,S5,;,S4,if,E1,then,S2,else,S3,while,E2,do,S1,A1,A2,A3,2019/10/28,编译原理与技术讲义,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 111 truelist: 100, 104 falselist: 103, 105 ,2019/10/28,编译原理与技术讲义,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=,2019/10/28,编译原理与技术讲义,40,e.g.17 控制流语句的翻译,三、分析完S4 用106回填(100)和(104)；用111回填(103)和(105) S4.nextlist: 107, 110 四、分析完L1 L1.nextlist: 107, 110 五、分析S5 (112) e := e + d / S5A3 S5.nextlist=,2019/10/28,编译原理与技术讲义,41,e.g.17 控制流语句的翻译,六、分析完L2 用112回填(107)和(110) L2.nextlist: ,2019/10/28,编译原理与技术讲义,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 控制流语句的翻译,2019/10/28,编译原理与技术讲义,43,e.g.18 Linux下C语言控制流语句的翻译,1）if语句 2）for语句 3）do-while 语句,