回填拉链翻译举例

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,设程序结构定义如下：,P S,S if E then S,S if E then S else S,S while E do S,S begin L end,S A,L L;S,L S,布尔表达式 E,及赋值语句 A定义见书上,为能及时地回填有关四元式串的转移地址，改写文法如下：,P S,C,if E then,S CS,1,T,p,CSelse,S T,P,S,2,W while,W,d,W E do,S W,d,S,3,S begin L end,S A,L,S,L;,L L,S,S,1,1,自底向上语法制导翻译方案实现过程分析（关于控制结构的翻译）,翻译中使用回填-拉链技术,翻译,while(ad) then x=y+z,2,步骤1：,移进while ， 并按如下产生式归约,W whileW.codebegin=nextstat;,四元式表内容如下：,nextstat 100,W.codebegin,句型变为 W (ad) then x=y+z,3,步骤2：,对于句型 W (ad) then x=y+z,移进(ab) 并按如下产生式归约,E i,1,relop,i,2, E.true= nextstat; E.false= nextstat+1;,E.codebegin= nextstat;,gen( if ab goto _ );,gen(goto _ );,E (E,1,) E.true= E,1,.true ; E.false= E,1,. false ;,E.codebegin= E,1,. codebegin ;,四元式表内容如下：,E.true 100 if ad) then x=y+z,4,步骤 3：,对于句型 W E do if (cd) then x=y+z,移进do 并按如下产生式归约,W,d,W E do backpatch(E.true, nextstat);,W,d,.chain=E.false;,W,d,. codebegin= W. codebegin;,四元式表内容如下：,100 if ad) then x=y+z,5,步骤4： 对于句型 W,d,if (cd) then x=y+z,移进if (cd), 并按如下产生式归约,E i,1,relop,i,2, E.true= nextstat; E.false= nextstat+1;,E.codebegin= nextstat;,gen( if ab goto _ );,gen(goto _ );,E (E,1,) E.true= E,1,.true ; E.false= E,1,. false ;,E.codebegin= E,1,. codebegin ;,四元式表内容：,100 if ad goto _,103 goto _,104,E.true,E.false,句型变为 W,d,if E then x=y+z,6,步骤5： 对于句型 W,d,if E then x=y+z,按如下产生式归约,C if E then,backpatch(E.true,nextstat);,C.chain=E.false;,四元式表内容：,100 if ad goto,104,103 goto _,104,C.chain,句型变为 W,d,C x=y+z,7,步骤6： 对于句型 W,d,C x=y+z,移进x=y+z ，按如下产生式归约,B i p=looku);if (p,nil) E.place=p else error,B B,1,+B,2,B.place =newtemp;gen(B.place= B,1,.place+ B,2,.place;,A i=B,p=looku);if (p,nil) gen(p=E.place) else error,四元式表内容：,100 if ad goto,104,103 goto _,104 t=y+z,C.chain,句型变为： W,d,C A,105 x=t,106,8,步骤7： 对于句型 W,d,C A , 按如下产生式归约,S A S.chain=0,S CS,1,S.chain =merge(C.chain, S,1,.chain);,/ 可能 S,1,if a then x=1elsex=2;,四元式表内容：,100 if ad goto,104,103 goto _,104 t=y+z,S.chain,句型变为： W,d,S,105 x=t,106,9,步骤8： 对于句型 W,d,S , 按如下产生式归约,S W,d,S,1, backpatch(S,1,.chain, W,d,.codebegin);,gen(goto W,d,.codebegin);,S.chain= W,d,. chain,四元式表内容：,100 if ad goto,104,103 goto,100,104 t=y+z,句型变为： S,105 x=t,106 goto,100,107,10,步骤9： 对于句型 S , 按如下产生式归约（假设忽略说明语句）,P S backpatch(S.chain, nextstat);,gen(return /返回主函数 ,四元式表内容：,100 if ad goto,104,103 goto,100,104 t=y+z,105 x=t,106 goto,100,107 return,108,11,递归下降语法制导翻译方案中实现控制结构的翻译:,翻译思路: 布尔表达式求值, 并设置标号避免回填, if (E) getlabel gen(JZ, E.place,_,label1) S,1,getlabel,gen(JP,_,_,label2) setlabel(label1:) else S,1, setlabel(label2:), while getlabel setlabel(label1:) ( E ) getlabel,gen(JZ, E.place,_,label2) do S gen(JP,_,_,label1) setlabel(label2:),label1,label2,label1,label2,12, for (E,1,; getlabel setlabel(label1:) E,2,getlabel,getlabel gen(JZ, E,2,.place,_,label2) gen(JP,_,_,label3) ;,getlabel setlabel(label4:) E,3,gen(JP,_,_,label1) ), setlabel(label3:) S gen(JP,_,_,label4) setlabel(label2:), read i look gen(IN,标准输入设备,_,i.place),label1,label2,label3,label4,write (E) gen(out, E.place, _, 标准输出设备),name,name place,13,