大学课件编译原理与技术

1、2021-10-21http:/ or e2 | e1 and e2 | not e1 | ( e1 )| id1 relop id2 | true | false | id3布尔运算符 or 、and 和 not（优先级、结合性）关系运算符 relop：、和布尔常量：true和false布尔变量：id32021-10-21http:/ 数值表示法（完全计算）类似算术表达式的翻译，如布尔表达式true and false or ( 2 1 )的计算为false or ( 21 )false or truetrue 短路计算法（不完全计算或解释法）a or b if a then true el

2、se ba and b if a then b else false not a if a then false else true借助控制流语句的思路，部分（不完全地用转移语句）“计算”布尔表达式的值以确定整个表达式的真、假。2021-10-21http:/ or e2 t := newtemp;emit( t “:=” e1.place “or” e2.place); e.place := t （2）ee1 and e2 （3）enot e1 （4）e( e1 )2021-10-21http:/ id1 relop id2 t:= newtemp;emit( “if” id1.place

3、relop.op id2 .place goto nextcode+3 );emit( t “:=” 0 );emit( “goto” nextcode2);emit( t “:=” 1 );e.place := t; nextcode : emit产生三地址语句的编号产生三地址语句的编号;产生后，产生后，nextcode+2021-10-21http:/ relop id2 （关系表达式）if id1 relop id2 goto i+3i :t := 0i+1:goto i+4i+2:t := 1i+3:i+4:truefalse2021-10-21http:/ e true t := n

4、ewtemp; 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 2021-10-21http:/ id goto i+3i :t := 0i+1:goto i+4i+2:t := 1i+3:i+4:truefal

5、se2021-10-21http:/ af 的三地址码：(100)if ab goto 103(101)t1 := 0(102) goto 104(103)t1 := 1 /以上为ab的翻译(104) if c=d goto 107(105)t2 := 0(106)goto 108(107)t2 := 1/以上为c=d的翻译2021-10-21http:/ 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

6、and t4/以上为 c=d and not ef 的翻译(115)t6 := t1 or t5/以上为 af 的翻译2021-10-21http:/ af布尔表达式的翻译短路计算truel_truefalsetruefalsel_falsefalsetruel_true-真出口：整个布尔表达式为真真时，控制流应转移到的目标语句（代码）；反之为假假时则转到 l_false-假出口。表示转移到的目标语句在有关布尔表达式翻译时尚未确定。2021-10-21http:/ af的短路计算三地址码：if af goto l_falsegoto l_true2021-10-21http:/ or m e2

7、truefalse真出口假出口e1 and m e2falsetrue假出口真出口falsetruenot e1 false真出口假出口true( e1 )假出口false真出口true2021-10-21http:/ relop id2if id1 relop id2 goto goto true真出口假出口false truetrue真出口 falsefalse假出口goto goto 2021-10-21http:/ ：布尔表达式代码中所有转向真出口的代码语句链；e.falselist ：所有转向假出口的代码语句链；backpatch( code-list, target-code )/

8、将目标地址target-code填回code-list中每条语句merge( code-list1, code-list2 )/合并链code-list1和code-list2（它们包含的语句转移目标相同）makelist( code-no ) , makelist()建立含语句编号为code-no的链或空链m m.code := nextcode / 获取下一三地址代码（语句）的编号（作为转移目标来回填）2021-10-21http:/ ee1 or m e2 backpatch( e1.falselist, m.code);e.truelist := merge( e1.truelist,

9、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; 2021-10-21http:/ enot e1 e.truelist := e1.falselist;e.falselist := e1.truelist; (4) e( e1 ) e.truelist := e1.truelist;e.falselist :

10、= 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” ); 2021-10-21http:/ e true e.truelist := makelist( nextcode );emit( “goto” ); e.falselist := makelist(); (7) e false e.falselist := mak

11、elist( nextcode );emit( “goto” ); e.truelist := makelist(); 2021-10-21http:/ 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 s2021-10-21http:/ e then s1 的代码结构e.trueliste.fa

12、lselists1.nextlist?m箭头线表示控制流方向；e.truelist和e.falselist 意义同前；s.nextlist 语句s的代码中所有跳转到未知目标地址的转移代码（如果有的话）的编号链。该未知目标地址该未知目标地址是指是指语义上语义上语句语句s执行结束执行结束后应执行的下一代码的位置。后应执行的下一代码的位置。未知目标地址2021-10-21http:/ s if e then m s1 backpatch( e.truelist, m.code ); s.nextlist := merge( e.falselist, s1.nextlist )2021-10-21ht

13、tp:/ goto if e then s1 else s2的代码结构e.trueliste.falselists2.nextlists2.codes1.nextlist?未知目标地址在代码标号t处强制产生无条件转移代码，转移目标待回填。m1m22021-10-21http:/ 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.

14、code := makelist(nextcode); /标号t emit( “goto” ）; 2021-10-21http:/ m1while e do s1 的代码结构e.trueliste.falselists1.nextlist?m2 产生无条件转移语句goto m1（跳转至循环条件测试代码开始处）未知目标地址m12021-10-21http:/ s while m1 e do m2 s1 backpatch( e.truelist, m2.code ); backpatch( s1.nextlist, m1.code ); s.nextlist := e.falselist; em

15、it( “goto” m1.code ); 2021-10-21http:/ id := e1 to e2 do s1的代码结构t: if id e2.place goto s1.codeid := id + 1goto tid := e1.placefalsetrue?未知目标地址待回填的目标地址s1.nextlist2021-10-21http:/ f for id := e1 to e2 do p := lookup( ); f.place := p; emit( id “:=” e1.place ); t := nextcode / 标号t f.again := t;

16、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; 2021-10-21http:/ for ( e1 ; e2 ; e3 ) s12021-10-21http:/ s begin l end s.nextlist := l.nextlist (6) s

17、 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 2021-10-21http:/ s switch e begincase c1 : s1;case c2 : s2;case cn-1 : sn-1;default : sn; end2021-10-21http:/ e.codet: goto test ( 待回填） li : si.code

18、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 lnnext: case/switch语句代码结构2021-10-21http:/ 分析完 switch e 产生 e.codet: goto test ( 待回填） (2) 分析完一个 case ci: si 产生如下代码，并将标号li和常量ci保存到case 情况常量表li : si.codeti : goto next ( 待回填） 常量标号c1l1cili情况常量表.l

19、nswitch中default2021-10-21http:/ 分析完 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 lnnext: 常量标号c1l1cili情况常量表.ln2021-10-21http:/ 控制流语句的翻译翻译以下语句序列：if ( ab or cd and ec ) do c := c +1else d := d + 1;e := e + d; 2021-10-21http:/ 控制流语句的翻译l2l1s5;s4ife1thens2elses3while e2dos1a1a2a32021-10-21http:/ 控制流语句的翻译一、翻译 e1：( ab or cd and ef )(100) if ab goto 106 (101) goto 102/用102回填(101)(102) if cd goto 104/用104回填(102)(103) goto 111(104) if ec goto 108 /用108回填(