编译原理与技术

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

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

布尔表达式的翻译 布尔表达式文法 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 3 2015/11/7 编译原理与技术 讲义 3

布尔表达式的翻译 两种翻译方法 - 数值表示法 ( 完全计算 ) 类似算术表达式的翻译, 如布尔表达式 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

数值表示法 布尔表达式的翻译 用 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

数值表示法 (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++ 2015/11/7 编译原理与技术 讲义 6

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 := 1 2015/11/7 编译原理与技术 讲义 7

布尔表达式的翻译 数值表示法 (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

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

e.g.16 a<b or c=d and not e>f 的三地址码 : (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

e.g.16 a<b or c=d and not e>f 的三地址码 : (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 // 以上为 a<b or c=d and not e>f 的翻译 2015/11/7 编译原理与技术 讲义 11

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

布尔表达式的翻译 短路计算 e.g.17 a<b or c=d and not e>f 的短路计算三地址码 : if a<b goto L_true goto L 1 L 1 : if c=d goto L 2 goto L_false L 2 : if e>f goto L_false goto L_true 2015/11/7 编译原理与技术 讲义 13

短路计算 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

短路计算 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

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

回填技术 - 相关符号属性及语义函数 : 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

短路计算及回填的翻译方案 (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

(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

(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

控制流语句的翻译 描述控制流语句的文法 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

条件语句的翻译 (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

条件语句的翻译 (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

条件语句的翻译 (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

条件语句的翻译 (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

循环语句的翻译 (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

循环语句的翻译 (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

循环语句的翻译 (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

循环语句的翻译 (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

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

文法 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

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

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

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

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

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

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 1 2015/11/7 编译原理与技术 讲义 37

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

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

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

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

e.g.17 控制流语句的翻译 (100) if a<b goto 106 (106) if a>c 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

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