编译原理与技术 中间代码生成 2018/9/17 《编译原理与技术》讲义.

Presentation on theme: "编译原理与技术 中间代码生成 2018/9/17 《编译原理与技术》讲义."— Presentation transcript:

1 编译原理与技术 中间代码生成 2018/9/17 《编译原理与技术》讲义

2 中间代码生成 －布尔表达式翻译 －控制流语句翻译 2018/9/17 《编译原理与技术》讲义

3 布尔表达式的翻译 布尔表达式文法G4 EE1 or E2 | E1 and E2 | not E1 | ( E1 )
| id1 relop id2 | true | false | id3 布尔运算符 or 、and 和 not（优先级、结合性） 关系运算符 relop：＜、≤、＝、≠、＞和≥ 布尔常量：true和false 布尔变量：id3 2018/9/17 《编译原理与技术》讲义

4 布尔表达式的翻译 两种翻译方法 － 数值表示法（完全计算） 类似算术表达式的翻译，如布尔表达式
true and false or ( 2 > 1 )的计算为 false or ( 2>1 )false or truetrue － 短路计算法（不完全计算或解释法） 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 借助控制流语句的思路，部分（不完全地－用转移语句）“计算”布尔表达式的值以确定整个表达式的真、假。 2018/9/17 《编译原理与技术》讲义

5 布尔表达式的翻译 数值表示法 用1表示true，0代表false。 （1）EE1 or E2 { t := newtemp;
emit( t “:=” E1.place “or” E2.place); E.place := t } （2）EE1 and E2 （3）Enot E1 （4）E( E1 ) 2018/9/17 《编译原理与技术》讲义

6 布尔表达式的翻译 数值表示法 nextcode : emit产生三地址语句的编号;产生后，nextcode++
（5）E id1 relop id2 { t:= newtemp; emit( “if” id1.place relop.op id2 .place goto nextcode+3 ); emit( t “:=” 0 ); emit( “goto” nextcode＋2); emit( t “:=” 1 ); E.place := t; } nextcode : emit产生三地址语句的编号;产生后，nextcode++ 2018/9/17 《编译原理与技术》讲义

7 id1 relop id2 （关系表达式） i : if id1 relop id2 goto i+3 i+1: t := 0 i+2:
false true i+1: t := 0 i+2: goto i+4 i+3: t := 1 i+4: 2018/9/17 《编译原理与技术》讲义

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 } 2018/9/17 《编译原理与技术》讲义

9 id（布尔变量） i : if id goto i+3 i+1: t := 0 i+2: goto i+4 i+3: t := 1 i+4:
false true i+1: t := 0 i+2: goto i+4 i+3: t := 1 i+4: 2018/9/17 《编译原理与技术》讲义

10 e.g.16 a<b or c=d and not e>f 的三地址码： (100) if a<b goto 103
(104) if c=d goto 107 (105) t2 := 0 (106) goto 108 (107) t2 := 1 //以上为c=d的翻译 2018/9/17 《编译原理与技术》讲义

11 e.g.16 a<b or c=d and not e>f 的三地址码： (108) if e>f goto 111
(112) t4 := not t3 //以上为 not e>f 的翻译 (113) t5 := t2 and t4 //以上为 c=d and not e>f 的翻译 (115) t6 := t1 or t5 //以上为 a<b or c=d and not e>f 的翻译 2018/9/17 《编译原理与技术》讲义

12 布尔表达式的翻译－短路计算 a<b or c=d and not e>f true L_true true false true
L_false false false L_true-真出口：整个布尔表达式为真时，控制流应转移到的目标语句（代码）；反之为假时则转到 L_false-假出口。 表示转移到的目标语句在有关布尔表达式翻译时尚未确定。 2018/9/17 《编译原理与技术》讲义

13 布尔表达式的翻译 短路计算 e.g.17 a<b or c=d and not e>f的短路计算三地址码：
if a<b goto L_true goto L1 L1: if c=d goto L2 goto L_false L2: if e>f goto L_false goto L_true 2018/9/17 《编译原理与技术》讲义

14 短路计算 not E1 E1 or M E2 E1 and M E2 ( E1 ) false 真出口 true 真出口 假出口 true
2018/9/17 《编译原理与技术》讲义

15 短路计算 true id1 relop id2 goto － if id1 relop id2 goto － false goto －
真出口 true 真出口 true id1 relop id2 goto － 假出口 false if id1 relop id2 goto － goto － false false 假出口 goto － 2018/9/17 《编译原理与技术》讲义

16 短路计算 回填技术 －布尔表达式短路计算翻译中，产生了转移目标不明确的条件或无条件代码；
－当有关目标地址确定后，可将这些目标地址填回到有关代码中。 －将有相同转移目标的转移代码的编号串起来形成链；可以方便回填目标地址。 2018/9/17 《编译原理与技术》讲义

17 E.truelist ：布尔表达式代码中所有转向真出口的代码语句链； E.falselist ：所有转向假出口的代码语句链；
回填技术 －相关符号属性及语义函数： 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 } // 获取下一三地址代码（语句）的编号（作为转移目标来回填） 2018/9/17 《编译原理与技术》讲义

18 短路计算及回填的翻译方案 (1) EE1 or M E2 { backpatch( E1.falselist, M.code);
E.truelist := merge( E1.truelist,E2.truelist); E.falselist := E2.falselist; } (2) EE1 and M E2 { backpatch( E1.truelist, M.code); E.falselist := merge( E1.falselist,E2.falselist); E.truelist := E2.truelist; } 2018/9/17 《编译原理与技术》讲义

19 E.truelist := E1.falselist; E.falselist := E1.truelist; }
(3) Enot 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” －); } 2018/9/17 《编译原理与技术》讲义

20 E.truelist := makelist( nextcode ); emit( “goto” －);
E.falselist := makelist(); } (7) E false { E.falselist := makelist( nextcode ); E.truelist := makelist(); } 2018/9/17 《编译原理与技术》讲义

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 2018/9/17 《编译原理与技术》讲义

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

23 条件语句的翻译（1） (1) S if E then M S1 { backpatch( E.truelist, M.code );
S.nextlist := merge( E.falselist, S1.nextlist ) } 2018/9/17 《编译原理与技术》讲义

24 条件语句的翻译（2） if E then S1 else S2的代码结构 E.code
E.truelist E.code E.falselist 在代码标号t处强制产生无条件转移代码，转移目标待回填。 M1 S1.code t: goto － S1.nextlist M2 S2.code S2.nextlist ? 未知目标地址 2018/9/17 《编译原理与技术》讲义

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” －）; 2018/9/17 《编译原理与技术》讲义

26 循环语句的翻译（1） while E do S1 的代码结构 M1: E.code 产生无条件转移语句
E.truelist E.falselist 产生无条件转移语句 goto M1（跳转至循环条件测试代码开始处） M2 S1.code goto M1 S1.nextlist ? 未知目标地址 2018/9/17 《编译原理与技术》讲义

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 ); } 2018/9/17 《编译原理与技术》讲义

28 循环语句的翻译（2） for id := E1 to E2 do S1的代码结构 待回填的目标地址 id := E1.place
TRUE t: if id > E2.place goto － FALSE S1.code S1.nextlist id := id + 1 goto t ? 未知目标地址 2018/9/17 《编译原理与技术》讲义

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; } 2018/9/17 《编译原理与技术》讲义

30 循环语句的翻译（3） 如何翻译C语言的for语句？ S for ( E1 ; E2 ; E3 ) S1 2018/9/17
《编译原理与技术》讲义

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 } 2018/9/17 《编译原理与技术》讲义

32 CASE/SWITCH语句的翻译（0） (9) S switch E begin case C1 : S1; case C2 : S2;
… case Cn-1 : Sn-1; default : Sn; end 2018/9/17 《编译原理与技术》讲义

33 CASE/SWITCH语句 代码结构 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: 2018/9/17 《编译原理与技术》讲义

34 CASE/SWITCH语句的翻译（1） (1) 分析完 SWITCH E 产生 E.code t: goto test ( 待回填）
情况常量表 常量 标号 (2) 分析完一个 case Ci: Si 产生如下代码，并将标号Li和常量Ci保存到case 情况常量表 C1 L1 … Ci Li Li : Si.code ti : goto next ( 待回填） ... … － Ln SWITCH中default 2018/9/17 《编译原理与技术》讲义

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: 情况常量表 常量 标号 C1 L1 … Ci Li ... … － Ln 2018/9/17 《编译原理与技术》讲义

36 e.g.17 控制流语句的翻译 翻译以下语句序列： if ( a<b or c<d and e<f ) then
while ( a>c ) do c := c +1 else d := d + 1; e := e + d; 2018/9/17 《编译原理与技术》讲义

37 e.g.17 控制流语句的翻译 L2 L1 ; S5 A3 S4 if E1 then S2 else S3 while E2 do S1
2018/9/17 《编译原理与技术》讲义

38 e.g.17 控制流语句的翻译 一、翻译 E1：( a<b or c<d and e<f )
(100) if a<b goto 106 (101) goto 102 //用102回填(101) (102) if c<d goto 104 //用104回填(102) (103) goto 111 (104) if e<f goto 106 (105) goto 111 truelist: { 100, 104 } falselist: { 103, 105 } 2018/9/17 《编译原理与技术》讲义

39 e.g.17 控制流语句的翻译 二、翻译 S2：while E2 do S1
(106) if a>c goto 108 //用108回填(106) (107) goto 112 (108) c := c + 1 // S1A1 S1.nextlist={} (109)goto // 转至循环入口(106) S2.nextlist: { 107 } (110) goto // 由N生成 (111) d := d // S3A2 S3.nextlist={} 2018/9/17 《编译原理与技术》讲义

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 // S5A3 S5.nextlist={} 2018/9/17 《编译原理与技术》讲义

41 e.g.17 控制流语句的翻译 六、分析完L2 用112回填(107)和(110) L2.nextlist: {} 2018/9/17
《编译原理与技术》讲义

42 e.g.17 控制流语句的翻译 (100) if a<b goto 106 (106) if a>c goto 108
(101) goto (107) goto 112 (102) if c<d goto (108) c := c + 1 (103) goto (109) goto 106 (104) if e<f goto (110) goto 112 (105) goto (111) d := d + 1 (112) e := e + d 2018/9/17 《编译原理与技术》讲义

43 e.g.18 Linux下C语言控制流语句的翻译 1）if语句 2）for语句 3）do-while 语句 2018/9/17
《编译原理与技术》讲义