编译原理与技术

Size: px

Start display at page:

Download "编译原理与技术"

什童
6 years ago
Views:

1 编译原理与技术中间代码生成 2015/11/7 编译原理与技术讲义 1

2 中间代码生成 - 布尔表达式翻译 - 控制流语句翻译 2015/11/7 编译原理与技术讲义 2

3 布尔表达式的翻译布尔表达式文法 G 4 E E 1 or E 2 E 1 and E 2 not E 1 ( E 1 ) id 1 relop id 2 true false id 3 布尔运算符 or and 和 not( 优先级结合性 ) 关系运算符 relop:< = > 和布尔常量 :true 和 false 布尔变量 :id /11/7 编译原理与技术讲义 3

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 借助控制流语句的思路, 部分 ( 不完全地 - 用转移语句 ) 计算布尔表达式的值以确定整个表达式的真假 2015/11/7 编译原理与技术讲义 4

5 数值表示法布尔表达式的翻译用 1 表示 true,0 代表 false (1)E E 1 or E 2 { t := newtemp; (2)E E 1 and E 2 (3)E not E 1 (4)E ( E 1 ) emit( t := E 1.place or E 2.place); E.place := t } 2015/11/7 编译原理与技术讲义 5

6 数值表示法 (5)E id 1 relop id 2 { 布尔表达式的翻译 t:= newtemp; emit( if id 1.place relop.op id 2.place goto nextcode+3 ); emit( t := 0 ); emit( goto nextcode+2); emit( t := 1 ); E.place := t; } nextcode : emit 产生三地址语句的编号 ; 产生后, nextcode /11/7 编译原理与技术讲义 6

7 id 1 relop id 2 ( 关系表达式 ) i : if id 1 relop id2 goto i+3 i+1: false t := 0 true i+2: goto i+4 i+3: i+4: t := /11/7 编译原理与技术讲义 7

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 id 3 { t := newtemp; emit( if id.place goto nexcode+3); emit( t := 0 ); emit( goto nextcode+2); emit( t := 1); E.place := t } 2015/11/7 编译原理与技术讲义 8

9 id( 布尔变量 ) i : if id goto i+3 i+1: false t := 0 true i+2: goto i+4 i+3: i+4: t := /11/7 编译原理与技术讲义 9

10 e.g.16 af 的三地址码 : (100) if a<b goto 103 (101) t 1 := 0 (102) goto 104 (103) t 1 := 1 // 以上为 a<b 的翻译 (104) if c=d goto 107 (105) t 2 := 0 (106) goto 108 (107) t 2 := 1 // 以上为 c=d 的翻译 2015/11/7 编译原理与技术讲义 10

11 e.g.16 af 的三地址码 : (108) if e>f goto 111 (109) t 3 := 0 (110) goto 112 (111) t 3 := 1 // 以上为 e>f 的翻译 (112) t 4 := not t 3 // 以上为 not e>f 的翻译 (113) t 5 := t 2 and t 4 // 以上为 c=d and not e>f 的翻译 (115) t 6 := t 1 or t 5 // 以上为 af 的翻译 2015/11/7 编译原理与技术讲义 11

12 布尔表达式的翻译 - 短路计算 true L_true af false false true L_false L_true- 真出口 : 整个布尔表达式为真时, 控制流应转移到的目标语句 ( 代码 ); 反之为假时则转到 L_false- 假出口表示转移到的目标语句在有关布尔表达式翻译时尚未确定 2015/11/7 编译原理与技术讲义 12

13 布尔表达式的翻译短路计算 e.g.17 af 的短路计算三地址码 : if af goto L_false goto L_true 2015/11/7 编译原理与技术讲义 13

14 短路计算 true 真出口 false 真出口 E 1 or M E 2 not E 1 false false 假出口 true 假出口 false 假出口 true 真出口 E 1 and M E 2 ( E 1 ) 真出口 false 假出口 true true 2015/11/7 编译原理与技术讲义 14

15 短路计算 true 真出口 true 真出口 id 1 relop id 2 false 假出口 true goto - if id 1 relop id 2 goto - goto - false false goto - 假出口 2015/11/7 编译原理与技术讲义 15

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

17 回填技术 - 相关符号属性及语义函数 : E.truelist : 布尔表达式代码中所有转向真出口的代码语句链 ; E.falselist : 所有转向假出口的代码语句链 ; backpatch( code-list, target-code ) // 将目标地址 target-code 填回 code-list 中每条语句 merge( code-list 1, code-list 2 ) // 合并链 code-list 1 和 code-list 2 ( 它们包含的语句转移目标相同 ) makelist( code-no ), makelist()- 建立含语句编号为 code-no 的链或空链 M ε { M.code := nextcode } // 获取下一三地址代码 ( 语句 ) 的编号 ( 作为转移目标来回填 ) 2015/11/7 编译原理与技术讲义 17

18 短路计算及回填的翻译方案 (1) E E 1 or M E 2 { backpatch( E 1.falselist, M.code); E.truelist := merge( E 1.truelist,E 2.truelist); E.falselist := E 2.falselist; } (2) E E 1 and M E 2 { backpatch( E 1.truelist, M.code); E.falselist := merge( E 1.falselist,E 2.falselist); E.truelist := E 2.truelist; } 2015/11/7 编译原理与技术讲义 18

19 (3) E not E 1 { E.truelist := E 1.falselist; E.falselist := E 1.truelist; } (4) E ( E 1 ) { E.truelist := E 1.truelist; E.falselist := E 1.falselist; } (5) E id 1 relop id 2 { E.truelist:=makelist(nextcode); emit( if id 1.place relop.op id 2.place goto -); E.falselist := makelist( nextcode ); emit( goto -); } 2015/11/7 编译原理与技术讲义 19

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(); } 2015/11/7 编译原理与技术讲义 20

21 控制流语句的翻译描述控制流语句的文法 G 5 : (1) S if E then S 1 (2) S if E then S 1 else S 2 (3) S while E do S 1 (4) S for id := E 1 to E 2 do S 1 (5) S begin L end // compound statement (6) S A // 赋值语句 (7) L L 1 ; S // Statements List (8) L S 2015/11/7 编译原理与技术讲义 21

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

23 条件语句的翻译 (1) (1) S if E then M S 1 { } backpatch( E.truelist, M.code ); S.nextlist := merge( E.falselist, S 1.nextlist ) 2015/11/7 编译原理与技术讲义 23

24 条件语句的翻译 (2) if E then S 1 else S2 的代码结构 E.truelist M 1 S 1.nextlist E.code S 1.code t: goto - S 2.code E.falselist M 2 在代码标号 t 处强制产生无条件转移代码, 转移目标待回填 S 2.nextlist? 未知目标地址 2015/11/7 编译原理与技术讲义 24

25 条件语句的翻译 (2) (2) S if E then M 1 S 1 N else M 2 S 2 { backpatch( E.truelist, M 1.code ); backpatch( E.falselist, M 2.code ); S.nextlist := merge( S 1.nextlist, S 2.nextlist, N.code) ; } N ε { N.code := makelist(nextcode); // 标号 t emit( goto -); } 2015/11/7 编译原理与技术讲义 25

26 循环语句的翻译 (1) while E do S 1 的代码结构 M 1 M 1 : E.truelist M 2 S 1.nextlist E.code S 1.code goto M 1 E.falselist 产生无条件转移语句 goto M 1 ( 跳转至循环条件测试代码开始处 ) 未知目标地址? 2015/11/7 编译原理与技术讲义 26

27 循环语句的翻译 (1) (3) S while M 1 E do M 2 S 1 { backpatch( E.truelist, M 2.code ); } backpatch( S 1.nextlist, M 1.code ); S.nextlist := E.falselist; emit( goto M 1.code ); 2015/11/7 编译原理与技术讲义 27

28 循环语句的翻译 (2) for id := E 1 to E 2 do S 1 的代码结构 id := E 1.place 待回填的目标地址 t: if id > E 2.place goto - FALSE TRUE S 1.code S 1.nextlist id := id + 1? 未知目标地址 goto t 2015/11/7 编译原理与技术讲义 28

29 循环语句的翻译 (2) (4) F for id := E 1 to E 2 do { p := lookup( id.name ); F.place := p; emit( id := E 1.place ); t := nextcode // 标号 t F.again := t; F.falselist := makelist( t ) ; emit( if p > E 2.place goto -); } S F S 1 { t := nextcode; emit( F.place := F.place + 1); emit( goto F.again); backpatch( S 1.nextlist, t ); S.nextlist := F.falselist; } 2015/11/7 编译原理与技术讲义 29

30 循环语句的翻译 (3) 如何翻译 C 语言的 for 语句? S for ( E 1 ; E 2 ; E 3 ) S /11/7 编译原理与技术讲义 30

31 文法 G 4 中其它语句的翻译 (5) S begin L end { S.nextlist := L.nextlist } (6) S A { S.nextlist := makelist();//empty } // A- 表示赋值语句 ; (7) L L 1 ; M S { backpatch( L 1.nextlist, M.code); L.nextlist := S.nextlist ; } (8) L S { L.nextlist := S.nextlist } 2015/11/7 编译原理与技术讲义 31

32 CASE/SWITCH 语句的翻译 (0) (9) S switch E begin case C 1 : S 1 ; case C 2 : S 2 ; case C n-1 : S n-1 ; default : S n ; end 2015/11/7 编译原理与技术讲义 32

33 E.code t: goto test ( 待回填 ) L i : S i.code t i : goto next ( 待回填 ) CASE/SWITCH 语句代码结构 test : if E.place = C 1 goto L 1 if E.place = C 2 goto L 2 if E.place = C n-1 goto L n-1 goto L n next: 2015/11/7 编译原理与技术讲义 33

34 CASE/SWITCH 语句的翻译 (1) (1) 分析完 SWITCH E 产生 E.code t: goto test ( 待回填 ) (2) 分析完一个 case C i : S i 产生如下代码, 并将标号 L i 和常量 C i 保存到 case 情况常量表 L i : S i.code t i : goto next ( 待回填 ) 情况常量表常量标号 C 1 L 1 C i L i... - L n SWITCH 中 default 2015/11/7 编译原理与技术讲义 34

35 CASE/SWITCH 语句的翻译 (2) (3) 分析完 end(switch 结束 ), 此时可以查看情况常量表产生如下代码, 并将标号 test 回填到包含 t 处的转移代码中合并所有 S i.nextlist 和标号 t i 即为 SWITCH 语句的 nextlist test : if E.place = C 1 goto L 1 next: if E.place = C 2 goto L 2 if E.place = C n-1 goto L n-1 goto L n 情况常量表常量标号 C 1 L 1 C i L i... - L n 2015/11/7 编译原理与技术讲义 35

36 e.g.17 控制流语句的翻译翻译以下语句序列 : if ( ac ) do c := c +1 else d := d + 1; e := e + d; 2015/11/7 编译原理与技术讲义 36

37 e.g.17 控制流语句的翻译 L 2 L 1 ; S 5 S 4 A 3 if E 1 then S 2 else S 3 while E 2 do S 1 A 2 A /11/7 编译原理与技术讲义 37

38 e.g.17 控制流语句的翻译一翻译 E 1 :( 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 } 2015/11/7 编译原理与技术讲义 38

39 e.g.17 控制流语句的翻译二翻译 S 2 :while E 2 do S 1 (106) if a>c goto 108 // 用 108 回填 (106) (107) goto 112 (108) c := c + 1 // S 1 A 1 S 1.nextlist={} (109)goto 106 // 转至循环入口 (106) S 2.nextlist: { 107 } (110) goto 112 // 由 N ε 生成 (111) d := d + 1 // S 3 A 2 S 3.nextlist={} 2015/11/7 编译原理与技术讲义 39

40 e.g.17 控制流语句的翻译三分析完 S 4 用 106 回填 (100) 和 (104); 用 111 回填 (103) 和 (105) S 4.nextlist: { 107, 110 } 四分析完 L 1 L 1.nextlist: { 107, 110 } 五分析 S 5 (112) e := e + d // S 5 A 3 S 5.nextlist={} 2015/11/7 编译原理与技术讲义 40

41 e.g.17 控制流语句的翻译六分析完 L 2 用 112 回填 (107) 和 (110) L 2.nextlist: {} 2015/11/7 编译原理与技术讲义 41

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

43 e.g.18 Linux 下 C 语言控制流语句的翻译 1)if 语句 2)for 语句 3)do-while 语句 2015/11/7 编译原理与技术讲义 43

Microsoft PowerPoint - ch6 [Compatibility Mode]

Microsoft PowerPoint - ch6 [Compatibility Mode] 第 6 章中间代码生成记号流分析器本章内容静态检查器中间代码生成器中间代码代码生成器介绍几种常用的中间表示 : 后缀表示图形表示和三地址代码用语法制导定义和翻译方案来说明源语言的各种构造怎样被翻译成中间形式 6.1.1 后缀表示表达式 E 的后缀表示可以如下归纳定义如果 E 是变量或常数, 那么 E 的后缀表示就是 E 本身如果 E 是形式为 E 1 ope 2 的表达式,