中科大2021－2022学年秋季第一学期《编译原理与技术》第十讲 中间代码生成（2）

1、2022/7/25编译原理与技术讲义1编译原理与技术中间代码生成2022/7/25编译原理与技术讲义2中间代码生成布尔表达式翻译控制流语句翻译2022/7/25编译原理与技术讲义3布尔表达式的翻译布尔表达式文法G4EE1 or E2 | E1 and E2 | not E1 | ( E1 )| id1 relop id2 | true | false | id3布尔运算符 or 、and 和 not（优先级、结合性）关系运算符 relop：、和布尔常量：true和false布尔变量：id32022/7/25编译原理与技术讲义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借助控制流语句的思路，部分（不完全地用转移语句）“计算”布尔表达式的值以确定整个表达式的真、假。2022/7/25编译原理与技术讲义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 )2022/7/25编译原理与技术讲义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产生三地

4、址语句的编号;产生后，nextcode+2022/7/25编译原理与技术讲义7id1 relop id2 （关系表达式）if id1 relop id2 goto i+3i :t := 0i+1:goto i+4i+2:t := 1i+3:i+4:truefalse2022/7/25编译原理与技术讲义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

5、;emit( if id.place “goto” nexcode+3);emit( t “:=” 0 );emit( “goto” nextcode+2);emit( t “:=” 1);E.place := t 2022/7/25编译原理与技术讲义9id（布尔变量）if id goto i+3i :t := 0i+1:goto i+4i+2:t := 1i+3:i+4:truefalse2022/7/25编译原理与技术讲义10e.g.16 af 的三地址码：(100)if ab goto 103(101)t1 := 0(102) goto 104(103)t1 := 1 /以上为ab的翻译

6、(104) if c=d goto 107(105)t2 := 0(106)goto 108(107)t2 := 1/以上为c=d的翻译2022/7/25编译原理与技术讲义11e.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 的翻译2022/7/25编译原理与技术讲义12 af布尔表

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

8、ot E1 false真出口假出口true( E1 )假出口false真出口true2022/7/25编译原理与技术讲义15短路计算id1 relop id2if id1 relop id2 goto goto true真出口假出口false truetrue真出口 falsefalse假出口goto goto 2022/7/25编译原理与技术讲义16短路计算回填技术布尔表达式短路计算翻译中，产生了转移目标不明确的条件或无条件代码；当有关目标地址确定后，可将这些目标地址填回到有关代码中。将有相同转移目标的转移代码的编号串起来形成链；可以方便回填目标地址。2022/7/25编译原理与技术讲义17

9、回填技术相关符号属性及语义函数：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 / 获取下一三地址代码

10、（语句）的编号（作为转移目标来回填）2022/7/25编译原理与技术讲义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;

11、 2022/7/25编译原理与技术讲义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( “go

12、to” ); 2022/7/25编译原理与技术讲义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(); 更精简的短路代码生成习题7.8（第三版）E E1 E2被翻译为两条指令：if E1.place E2.place goto /真出口链goto /假出口链它们可以用一条指令来取代：if E

13、1.place E2.place goto /假出口链/ 真出口链为空 2022/7/25编译原理与技术讲义21更精简的短路代码生成辅助函数reverseCOND(lastCodeIdx, list)if(codelastCodeIdx.target = lastCodeIdx+1)if(codelastCodeIdx.op = GOTO) codelastCodeIdx.op := NOP /空操作相当于删除原有的goto指令else /relop, 条件转移指令codelastCodeIdx.op := NEG(codelastCodeIdx.op)/NEG意为取“反”操作，原来为现在变为

14、list := makelist(lastCodeIdx) 2022/7/25编译原理与技术讲义222022/7/25编译原理与技术讲义23更精简短路计算及回填翻译方案(1) EE1 or M E2 t := makelist(); backpatch( E1.falselist, M.code);reverseCOND(M.code-1, t);E.truelist := merge( E1.truelist,E2.truelist, t ); E.falselist := E2.falselist; 2022/7/25编译原理与技术讲义24更精简短路计算及回填翻译方案(2) EE1 and

15、 M E2 t := makelist(); backpatch( E1.truelist, M.code);reverseCOND(M.code-1, t);E.falselist := merge( E1.falselist,E2.flaselist, t ); E.truelist := E2.truelist; 更精简短路计算及回填翻译方案2022/7/25编译原理与技术讲义25(3) Enot E1 E.truelist := E1.falselist;E.falselist := E1.truelist; (4) E( E1 ) E.truelist := E1.truelist;

16、E.falselist := E1.falselist; (5) E id1 relop id2 E.falselist := makelist( nextcode );/假出口链emit( “if” id1.place NEG(relop.op) id2.place “goto” ）;E.truelist:=makelist();/真出口链为空更精简短路计算及回填翻译方案2022/7/25编译原理与技术讲义26(6) E true E.truelist := makelist( nextcode );emit( “goto” ); E.falselist := makelist(); (7)

17、 E false E.falselist := makelist( nextcode );emit( “goto” ); E.truelist := makelist(); 2022/7/25编译原理与技术讲义27更精简的短路代码生成e.g.17 af的精简短路计算三地址码：100:if a E2.place goto S1.codeid := id + 1goto tid := E1.placeFALSETRUE?未知目标地址待回填的目标地址S1.nextlist2022/7/25编译原理与技术讲义36循环语句的翻译（2）(4) F for id := E1 to E2 do p := lo

18、okup( ); 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; 2022/7/25编

19、译原理与技术讲义37循环语句的翻译（3）如何翻译C语言的for语句？S for ( E1 ; E2 ; E3 ) S12022/7/25编译原理与技术讲义38文法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 2022/7/25

20、编译原理与技术讲义39CASE/SWITCH语句的翻译（0）(9) S switch E begincase C1 : S1;case C2 : S2;case Cn-1 : Sn-1;default : Sn; end2022/7/25编译原理与技术讲义40 E.codet: goto test ( 待回填） Li : Si.codeti : goto next ( 待回填） test : if E.place = C1 goto L1 if E.place = C2 goto L2 if E.place = Cn-1 goto Ln-1 goto Lnnext: CASE/SWITCH语句

21、代码结构2022/7/25编译原理与技术讲义41CASE/SWITCH语句的翻译（1）(1) 分析完 SWITCH E 产生 E.codet: goto test ( 待回填） (2) 分析完一个 case Ci: Si 产生如下代码，并将标号Li和常量Ci保存到case 情况常量表Li : Si.codeti : goto next ( 待回填） 常量标号C1L1CiLi情况常量表.LnSWITCH中default2022/7/25编译原理与技术讲义42CASE/SWITCH语句的翻译（2）(3) 分析完 end（SWITCH结束） ，此时可以查看情况常量表产生如下代码，并将标号test回填

22、到包含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: 常量标号C1L1CiLi情况常量表.Ln2022/7/25编译原理与技术讲义43e.g.17 控制流语句的翻译翻译以下语句序列：if ( ab or cd and ec ) do c := c +1else d := d + 1;e := e + d; 2022/7/25编译原理与技术讲义44e.g.17 控制流语句的翻译L2L1S5;S4ifE1thenS2elseS3whileE2doS1A1A2A32022/7/25编译原理与技术讲义45e.g.17 控制流语句的翻译一、翻译 E1：( ab or cd and ef )(100) if ab goto 106 (101) goto 102/用102回填(101)(102) if cd goto 104/用104