编译原理第八章剖析.ppt

* 四元式采用赋值形式，即result：=arg1 op arg2 * if ab then x:=a+b else x:=a+b*3 对应的四元式： (100) if ab goto (104) (101) t1:=a+b (102) x:=t1 (103) goto (107) (104) t1:=b*3 (105) t2:=a+t1 (106) x:=t2 (107)… * 语句 if ab or cd and ef then S 1 else S 2 的四元式 (1 ) if ab goto (7) //转移至(E.true ) (2) goto (3) (3) if cd goto (5) (4) goto (p+1) //转移至(E.false) (5) if ef goto (7) (6) goto (p+1) (7) ( S 1 的四元式 …… (p-1) ……） ( p ) goto (q) (p+1) ( S 2 的四元式 …… (q-1) ……） (q) //转移至(E.true ) //转移至(E.false) //(E.false)入口 // (E.true ) 入口 E.true和E.false的值不能在产生四元式的同时就知道，要在整个布尔表达式（或语句）的四元式产生完毕之后才得知，因此要回填这个地址。 为了记录需回填地址的四元式，常采用一种拉链的办法：把需回填E.true的四元式拉成一链，称为“真”链，把需回填E.false的四元式拉成一链，称为“假”链。 若有四元式序列： （10） …goto E.true （20） …goto E.true （30） …goto E.true （10） …goto （0） （20） …goto （10） （30） …goto （20） 其中链首为（30），链尾为（10），0为链尾标志。 则链成: 使用： E.true 和 E.false：分别表示“真”链和“假”链 nextstat：下一四元式地址 emit：输出四元式 merge（p1,p2）：合并p1、p2两条链，即将p2的链尾链接到p1链首，合并后p2为链首。 例： merge(p1, p2) ( p10) goto ( 0) …… p1 链 (p 10 0 ) goto (p10) …… ` ( p1) goto (p100) (p20) goto( 0) (p1) …… p2 链 (p200) goto (p20) …… ( p2) goto (p200) backpatch（p，t）：把p所链接的每个四元式的第四区段都填为t E.codebegin：E的第一个四元式序号（语义值） 自下而上的分析中布尔表达式的一种翻译方案，如p167图8.13所示 （1）E→ E1 or E2 { backpatch( E1.false, E2.codebegin); E.codebegin := E1.codebegin; E.true := merge（E1.true, E2.true）; E.false := E2.false； } （2）E→ E1 and E2 { backpatch( E1.true, E2.codebegin); E.codebegin := E1.codebegin; E.true := E2.true; E.false :=merge（E1.false, E2.false）； } （3）E→ not E1 { E.true := E1.false; E.codebegin := E1.codebegin; E.false := E1.t