编译原理与技术
2020/8/3
docin/sundae_meng
17
短路计算及回填的翻译方案
(1) EE1 or M E2 { backpatch( E1.falselist, M.code); E.truelist := merge( E1.truelist,E2.truelist); E.falselist := E2.falselist; }
2020/8/3
docin/sundae_meng
5
布尔表达式的翻译
数值表示法
(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; }
(108)
if e>f goto 111
(109) (110)
t3 := 0 goto 112
(111)
t3 := 1
//以上为e>f的翻译
(112)
t4 := not t3
//以上为 not e>f 的翻译
(113)
t5 := t2 and t4
//以上为 c=d and not e>f 的翻译
(115)
2020/8/3
docin/sundae_meng
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(); }
2020/8/3
docin/sundae_meng
16
回填技术 -相关符号属性及语义函数:
E.truelist :布尔表达式代码中所有转向真出口的代码语句链; E.falselist :所有转向假出口的代码语句链;
backpatch( code-list, target-code ) //将目标地址target-code填回code-list中每条语句
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
2020/8/3
docin/sundae_meng
13
短路计算
true
真出口
false
E1 or M E2
not E1
L_true-真出口:整个布尔表达式为真时,控制流应转移到 的目标语句(代码);反之为假时则转到 L_false-假出口。
表示转移到的目标语句在有关布尔表达式翻译时尚未确定。
2020/8/3
docin/sundae_meng
12
布尔表达式的翻译
短路计算 e.g.17 a<b or c=d and not e>f的短路计算三 地址码:
假出口
true
false
false
false
假出口
true
E1 and M E2
( E1 )
true
2020/8/3
true
真出口
docin/sundae_meng
false
真出口 假出口 真出口 假出口
14
短路计算
true
真出口
true 真出口
id1 relop id2
false
假出口
true goto -
18
(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” -); }
2020/8/3
docin/sundae_meng
4
布尔表达式的翻译
数值表示法
用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 )
if id1 relop id2 goto - goto -
false
false 假出口
goto -
2020/8/3
docin/sundae_meng
15
短路计算
回填技术 -布尔表达式短路计算翻译中,产生了转移 目标不明确的条件或无条件代码; -当有关目标地址确定后,可将这些目标地 址填回到有关代码中。 -将有相同转移目标的转移代码的编号串起 来形成链;可以方便回填目标地址。
merge( code-list1, code-list2 ) //合并链code-list1和code-list2(它们包含的语句转移目标相同) makelist( code-No ) , makelist()-建立含语句编号为code-No
的链或空链
M { M.code := nextcode } // 获取下一三地址代码(语句)的编号(作为转移目标来 回填)
t6 := t1 or t5
//以上为 a<b or c=d and not e>f 的翻译
2020/8/3
docin/sundae_meng
11
布尔表达式的翻译-短路计算
true
L_true
true
false
a<b or c=d and not e>f
false
true L_false
false
(101) (102)
t1 := 0 goto 104
(103)
t1 := 1
//以上为a<b的翻译
(104)
if c=d goto 107
(105) (106)
t2 := 0 goto 108
(107)
t2 := 1
//以上为c=d的翻译
2020/8/3
docin/sundae_meng
10
e.g.16 a<b or c=d and not e>f 的三地址码:
2020/8/3
docin/sundae_meng
20
控制流语句的翻译
描述控制流语句的文法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
if E then S1 else S2的代码结构
E.truelist
M1 S1.nextlist
E.code
S1.code t: goto - S2.code
E.falselist M2
在代码标号t处强制产生 无条件转移代码,转移 目标待回填。
S2.nextlist
? 未知目标地址
2020/8/3
false or ( 2>1 )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
借助控制流语句的思路,部分(不完全地-用 转移语句)“计算”布尔表达式的值以确定整个表 达式的真、假。
22
条件语句的翻译(1)
(1) S if E then M S1 { backpatch( E.truelist, M.code ); S.nextlist := merge( E.falselist, S1.nextlist ) }
2020/8/3
docin/sundae_meng
23
条件语句的翻译(2)
(2) EE1 and M E2 { backpatch( E1.truelist, M.code); E.falselist := merge( E1.falselist,E2.falselist); E.truelist := E2.truelist; }
2020/8/3
docin/sundae_meng
编译原理与技术
中间代码生成
2020/8/3
docin/sundae_meng
1
中间代码生成
-布尔表达式翻译 -控制流语句翻译
2020/8/3
docin/sundae_meng
2
布尔表达式的翻译
布尔表达式文法G4 EE1 or E2 | E1 and E2 | not E1 | ( E1 ) | id1 relop id2 | true | false | id3
t := 1