《编泽技术原理及方法》习题解答 第五章习题解答

第五章——习题解答1.按照语法制导翻译的一般原理，给出表达式(5*4+8)*2的语法树各结点并注明语义值VAL。E(56)E(28)EE(56)E(28)E*()E(28)2E(28)854E(4)*E(5)E(20)E(8)+2.给出下面表达式的后缀式表示：(1)a+b*(c+d/e)(2)(a∧b)∨(¬c∨d)(3)(a∨b)∧(c∨¬d∧e)(4)if((x+y)*z!=0){(a+b)↑c}else{a↑b↑c}解：（1）a+b*(c+d/e):abcde/+*+（2）ab∧c┐d∨∨（3）ab∨cd┐e∧∨∧（4）xy+z*p1JEZab+c↑p2JUMPab↑c↑3.请将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。解：三元式：(1)(+,a,b)(2)(+,c,d)(3)(*,(1),(2))(4)(-,(3),/)(5)(+,a,b)(6)(+,(5),c)(7)(-,(4),(6))间接三元式：间接三元式序列间接码表(1)(+,a,b)(1)(2)(+,c,d)(2)(3)(*,(1),(2))(3)(4)(-,(3),/)(4)(5)(-,(4),(1))(1)(6)(-,(4),(5))(5)(6)四元式：(1)(+,a,b,t1)(2)(+,c,d,t2)(3)(*,t1,t2,t3)(4)(-,t3,/,t4)(5)(+,a,b,t5)(6)(+,t5,c,t6)(7)(-,t4,t6,t7)4.将下列后缀式改写为中缀式：(1)abc-*cd+e/-(2)ab∨c¬d∨∨(3)abc+≤a0>∧ab+0<>a0<∧∨(4)aΘbc*＋解：（1）a*(b-c)-(c+d)/e（2）(a∨b)∨(¬c∨d)（3）(ab+c∧a>0)∨(a+b<>0∧a<0)（4）-a+b*c5.将表达式-a+b*(-c+d)/e*f翻译成树形表示。解：6.写出下列赋值语句的自下而上语法制导翻译过程，并给出产生的四元式序列。a=b*(c+d)解：步骤状态栈符号栈PLACE输入串规约规则调用子程序四元式10#-a:=b*(c+d)#202#a-Va:=b*(c+d)#V∷＝iSUB8303#V-Va:=b*(c+d)#4034#V:=-Va-b*(c+d)#50349#V:=b-Va-Fb*(c+d)#F∷＝iSUB760347#V:=F-Va-Tb*(c+d)#T∷＝FSUB570346#V:=T-Va-Tb*(c+d)#803461#V:=T*-Va-Tb(c+d)#9034618#V:=T*(-Va-Tb-c+d)#100346189#V:=T*(c-Va-Tb-Fc+d)#F∷＝iSUB7110346187#V:=T*(F-Va-Tb-Tc+d)#T∷＝FSUB5120346186#V:=T*(T-Va-Tb-Ec+d)#E∷＝TSUB3130346182#V:=T*(E-Va-Tb-Ec+d)#1403461820#V:=T*(E+-Va-Tb-Ec-d)V:=T*(E+d-Va-Tb-Ec-Fd)#F∷＝iSUB716034618207#V:=T*(E+F-Va-Tb-Ec-Td)#T∷＝FSUB517034618203#V:=T*(E+T-Va-Tb-T1)#E∷＝E(1)+TSUB2(+,c,d,T1)180346182#V:=T*(E-Va-Tb-T1)#1903461825#V:=T*(E)-Va-Tb-T1#F∷＝(E)SUB620034614#V:=T*F-Va-T2#T∷＝T(1)*FSUB4(*,b,T1,T2)210346#V:=T-Va-T2#E∷＝TSUB3(*,b,T1,T2)220345#V:=E-Va-T2#A∷＝V:=ESUB1(:=,T2,,a)2301#A-#acc7.将下列布尔表达式翻译成四元式序列，并给出语法制导翻译过程（作为条件控制）。a∧b∧c>d解：四元式序列如下所示：(1)(jnz,a,,3)a的四元式，当a为真时，则转向第3个四元式(2)(j,,,0)(3)(jnz,b,,5)b的四元式，当b为真时，则转向第3个四元式(4)(j,,,2)无条件转向第2个四元式(5)(j>,c,d,0)c>d的四元式(6)(j,,,4)无条件转向第4个四元式<BE>.TC表示<BE>真出口的链首<BE>.FC表示<BE>假出口的链首，每个链尾的四元式第4分量均为0，表示结束标记语法制导翻译过程四元式a∧b∧c>d(1)E∧b∧c>d100(jnz,a,,0/102){E.TC=100;E.FC=101}101(j,,,0)(2)E∧b∧c>d{BP(E1.TC=100,NXQ=102);E∧.FC=E1.FC=101}(3)E∧E∧c>d102(jnz,b,,0/104){E.TC=102;E.FC=103}103(j,,,0/101)(4)E∧E∧’c>d{BP(E1.TC=102,NXQ=104);E∧’.FC=E1.FC=103}(5)E∧E∧’E104(j>,c,d,0){E.TC=104;E.FC=105}105(j,,,0/103)(6)E∧E1{E1.TC=E.TC=104;E1.FC=MERG(E∧’.FC=103,E.FC=105)=105}(7)E2{E2.TC=E1.TC=104;E2.FC=MERG(E∧.FC=101,E.FC=105)=105}8.改写布尔表达式语义子程序，使得关系式i(1)ropi(2)不是按通常的方法翻译成两个相继的四元式。(jrop,i(1),i(2),0)(j,,,0)而是翻译成如下一个四元式(jnrop,i(1),i(2),0)使得当i(1)ropi(2)为真的情况下不发生转移（即自动下滑），当i(1)ropi(2)为假时才发生转移，从而产生较高效的目标代码。按改写后布尔表达式语义子程序，将下列布尔表达式翻译成四元式序列。¬a∨(b<c∧¬(d>e))解：(1)Ei{E.TC=NULL;E.FC=NXQ;GEN(jez,ENTRY(i),,0);}(2)Ei(1)ropi(2){E.TC=NULL;E.FC=NXQ;GEN(jnrop,ENRTY(i(1)),ENTRY(i(2)),0);}(3)E(E(1)){E.TC=E(1).TC;E.FC=E(1).FC;}(4)E¬E(1){E.FC=NXQ;GEN(j,,,0);BACKPATCH(E(1).FC,NXQ);}(5)E∧E(1)∧{E∧.FC=E(1).FC;}(6)EE∧E(2){E.TC=E(2).TC;E.FC=MERGE(E∧.FC,E(2).FC);}(7)E∨E(1)∨{E∨.TC=NXQ;GEN(j,,,0);BACKPATCH(E(1).FC,NXQ);}(8)EE∨E(2){E.FC=E(2).FC;BACKPATCH(E∨.TC,NXQ);}四元式序列：100(jez,a,,102)101(j,,,103)102(j,,,106)103(jn<,b,c,q)104(jn>,d,e,106)105(j,,,103)T:106F:q9.写出下列条件赋值语句的四元式序列。z=if(a>c){x+y}else{x+y-0.5}解：根据语义子程序，其条件赋值语句四元式序列为：100(j>,a,c,102)101(j,,,105)102(+,x,y,T1)103(=,T1,,z)104(j,,,108)105(+,x,y,T2)106(-,T2,0.5,T3)107(=,T3,,z)10810.将下列条件（含while循环）语句翻译成四元式序列。if(x==y+1){x=x*y}else{while(x!=0){x=x-1;y=y+2;}}解：根据语义子程序，其条件赋值语句四元式序列为：100(+,y,1,T1)101(j=,x,T1,103)102(j,,,106)103(*,x,y,T2)104(=,T2,,x)105(j,,,113)106(jnz,x,0,108)107(j,,,113)108(-,x,1,T3)109(=,T3,,x)110(+,y,2,T4)111(=,T4,,y)112(j,,,113)11311.将下列while语句翻译成四元式序列。while((a<c)&&(b<d)){if(a==1){c=c+1;}else{while(a<=d){a=a+2;}}解：语法制导翻译过程:(1)W(a<c∧b<d){……}{W.QUAD=100}(2)WE1∧b<d{......}100(j<,a,c,102);{E1.TC=100,E1.FC=101}101(j,-,-,0);(3)WE∧b<d{......}{BACKPATCH(E1.TC=100,NXQ=102);E∧.FC=E1.FC=101}(4)WE∧E2{......}102(j<,b,d,104){E2.TC=102;E2.FC=103}103(j,-,-,101)(5)WE{......}{E.TC=E2.TC=102;E.FC=MERG(E∧.FC=101,E2.FC=103)=103}(6)Wdifa==1{......}{BACKPATCH(E.TC=102,NXQ=104);Wd.CHAIN=E.TC=103;Wd.QUAD=W.QUAD=100}(7)WdifE{c=c+1......}{E.TC=104;E.FC=105}104(j=,a,’1’,106)105(j,-,-,109)(8)WdCc=c+1else{......}{BACKPATCH(E.TC=104,NXQ=106);C.CHAIN=E.FC=105}(9)WdCS1else{......}106(+,C,’1’,T1){S1.CHAIN=0;107(=,T1,-,C)T1=NEWTEMP}(10)WdTPwhilea<=d{......}{q=108;108(j,-,-.100)BACKPATCH(C.CHAIN=105,NXQ=109);TP.CHAIN.=MFRG(S1.CHAN=0,q=108)}(11)WdTPW’a<=d{......}{W’.QUAD=NXQ=109}(12)WdTPW’E{a=a+2}{E.TC=109;109(j=,a,d,111)E.FC=110}110(j,-,-,100)(13)WdTPWd{a=a+2}{BACKPATCH(E.TC=109,NXQ=111);Wd.CHAIN=E.FC=110;Wd.QUAD=W.QUAD=109}(14)WdTPWd’S1{S.CHAIN=0;111(+,a,’2’,T2)T2=NEWTEMP}112(=,T2,-,a)(15)WdTPS2{BACKPATCH(S1.CHAIN,Wd’.QUAD=109)S2.CHAIN=Wd’.CHAIN=110}113(j,-,-,109)(16)WdS1{S.CHAIN=MERG(TP.CHAIN=108,S1.CHAIN=110)=110}(17)S{BACKPATCH(S1.CHAIN=110,Wd.QUAD=100);S.CHAIN=Wd.CHAIN=103}114(return,-,-,0)序列：100(j<,a,c,102);101(j,-,-,0)102(j<,b,d,104)103(j,-,-,101)104(j=,a,’1’,106)105(j,-,-,109)106(+,c,’1’,T1)107(=,T1,-,c)108(j,-,-.100)109(j=,a,d,111)110(j,-,-,100)111(+,a,’2’,T2)112(=,T2,-,a)113(j,-,-,109)114(return,-,-,0)S.CHAIN=10312.写出下列for循环语句的四元式序列。for(i=a+b*2;i<=c+d+10;i++){if(h>g)p=p+1;}解：(*,b,2,T1)(+,a,T1,T2)(=,T2,,i)(+,c,d,T3)(+,T3,10,T4)(=,T4,,T)(j,,,108)(+,i,1,i)(j>,i,T,114)(j>,h,g,111)(j,,,113)(+,p,1,T5)(=,T5,,p)(j,,,107)13.写出翻译下列语句的语义子程序：for(i=E1;i<=E2;i++,j--){S1}（其中E1和E2值都是整数或整型简单表达式-）解：①F∷=for(i=E1;i<=E2;i++,j--){F.PLACE=ENTRY(i);//*将i的入口地址保留，以供以后查表GEN(=,E1.PLACE,,F.PLACE);//*生成一个四元式,将初值送iT=NEWTEMP;//*产生一个中间变量，以后存储终值GEN(=,E2.PLACE,,T);//*生成一个四元式,将终值送中间变量q=NXQ;//*记下无条件转移四元式的编号,即gotoOVER位置GEN(j,,,q+2);//*生成一个四元式,无条件转移到OVER位置F.QUAD=q+1;//*记下AGAIN位置，即i＝i+1位置GEN(+,F.PLACE,1,F.PLACE);//*i＝i+1GEN(-,E2.PLACE,1,T);//*j=j-1F.CHAIN=NXQ;//*将NXQ的位置传递下去，以供以后回填GEN(j>,F.PLACE,T,0)}//*条件四元式,判断是否达到达终值②S=FS1{BACKPATCH(S1.CHAIN,F.QUAD);//*用i＝i+1位