编译原理第三版课后习题解答.pdf

《编译原理第三版课后习题解答.pdf》由会员分享，可在线阅读，更多相关《编译原理第三版课后习题解答.pdf（47页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第二章习题解答P36-6(1)L(G)是。9组成的数字串(2)最左推导：N n N D n NDD n NDDD o DDDD n QDDD=01QD=012 D n 0127N n N D n D D n 3 D n?AN n N D n NDD n DDD=5DD n 56D n 568最右推导：N n N D n N 7 n ND7 n N27 n ND27 n N127 n D127=0127N n ND n N 4=D 4 n 34N=ND n N8 n ND8=N68=D68=568P36-7G(S)O-1|3|5|7|9N-2|4|6|8|OO f 0|NS O A OA-A D

2、 NP36-8文法：E-T E +T E-TTT F T*F T/F最左推导:E E +T T+T F +T i +T i +T*F i+F*F i+i*F i+i*iE n Tn T*F=F*F n i*F n i*(E)n i*(；+T)n i*(T+T)n i*(F +T)ni*(i +T)ni*(i +F)ni*(i +i)最 右 推 导:E n E+T n E+T*E=E+T*i=E+尸*i=：+/*，=T +i*i=F+i*i=i +i*iE n Tn F*Tn F*F n F*(E)n F*(E+T)n F*(E+F)n F*(E+i)n E*(T+i)n F*(E+i)n F*

3、(i +i)ni*(i +i)去 权,./*T F iT F iF iii+i+ic 5c rjc|c iSeS=iSei=USei=iiiei5 C CC*,=LS=uSeS n uSei=metP36-10S T S TT f (S)|()P36-ULI:S f A CA aAb abC cC|L2:S A BA-aA sB bBc|beL3:S -A BA aAb B aBb L 4：S-A-0A11 Arjc I第三章习题参考答案P64-711011确定化：01X*1,2,3电也1,2,32,3(2,3,4)2,32,32,3,42,3,42,3,52,3,42,3,52,32,3,4

4、,Y2,3,4,Y2,3,5(2,3,4,)111最小化：0,1 2 3,4,5 ,0,1 2 3,4,5 0 =1,3,5 0,1,2 3 4,5 =1,2,4,6)0,1 2 3,4 ,5 ,6(0,1,2,3,4 0=1,3,5)(0,1,2,3 ,4 ,5 ,6 0,1 2 3 0 =1,3 0,1,2,3 =1,2,4 0,1 ,2,3 4 ,5 ,6 0，1 ()=1 0叫=1 2 2,3。=3 =4 0 ,1 ,2,3 ,4 ,5 ,6 1 1P64-8(1)(1 1 0)*0 1(2)(l|2|3|4|5|6|7|8|9 X 0|l|2|3|4|5|6|7|8|9)*(0|5)

5、|(0|5)(3)0*1(0|1 0*1)*1 1*0(0 1 1 0*1)*P64-12(a)a确定化:ab00,110,1091110事66给状态编号:ab012112203333aa最小化：0,1,2,30,1=1 0,1=22,3,=0,3 2,3=30,1,2,3(b)abaa已经确定化了，进行最小化最小化：0,1 ,2,3,4,5)0,1 =1 0,1 产 2,4 2,3,4,5 “=1,3,0,5)2,3,4,5 =2,3,4,5)2,4 “=1,0 2,4 .=3,5 3,5。=3,5 3,5 =2,4 0,1 ,2,4 ,3 5 5 )0,1 “=1 0,1 ,=2,4 2,

6、4 “=1,0 2,4 =3,5 3,5 =3,5 3,5 ,=2,4 0(2)：确定化:01X,1,Y)1,Y21,Y1,Y21,Y664 给状态编号:01012112213333最小化:0,1,2,3。1。=2,3=1,30,1,2,30,1,=22,3尸310第四章P81-1(1)按照T,S的顺序消除左递归G(S)S f a|A|(T)T T STV ST s递归子程序：procedure S;beginif sym=a or sym=A，then abvanceelse if sym=(then beginadvance;T;if sym=)then advance;else erro

7、r;endelse errorend;procedure T;beginS；rend;procedure T,beginif sym=,then beginadvance;S；rendend;其中：sym:是输入串指针I P所指的符号advance:是把I P调至下一个输入符号error:是出错诊察程序(2)FI RST(S)=a,(FI RST(T)=a?,()FI RST(r)=,FOLLOW(S)=),#FOLLOW(T)=)FOLLOW(r)=)预测分析表aA(I9#sS uS r人s-TT fS TT fS TTTSTVT T T f S T是LL(1)文法P81-2文法：E TEE

8、+E T t FTT-TF t PFF f *尸|P f (E)|a|b|A(1)FI RST(E)=(,a,b?)FI RST(E)=+,FI RST(T)=(,a,b?FI RST(T)=(,a,b,A,)FI RST(F)=(,a,bJFI RST(F)=*,FI RST(P)=(,a,bFFOLLOW(E)=#,)FOLLOW(E)=#,)FOLLOW(T)=+,),#FOLLOW。尸+,),#FOLLOW(F)=(,a,b,人,+,),#FOLLOW(F)=(,a,b,A,+,),#FOLLOW(P)=*,(,a,b,A,+,),#(2)考虑下列产生式：E+E eT J T F*F

9、P(E)abFI RST(+E)n FI RST()=+n =6FI RST(+E)A FOLLOW(E尸+A#,)二 6FI RST(T)AFI RST()=(,a,b,A n =6FI RST(T)A FOLLOW(T)=(,a,b,A 0+,),#=6FI RST(*F)AFI RST(尸*G =6FI RST(*F)n FOLLOW(F)=*n(,a,b,人,+,),#=(bFI RST(E)A FI RST(a)A FI RST(b)n FI RST(A)=4)所以，该 文 法 式LL文法.+*()abA#EETTE，ETTE ETTE，E r mEE J+EE f gE T TT

10、fF TT fF TTTFT T fF TTTT TTTT TTT TTT TTTFF PFFT PF FT PF F fP F FFF SFF T FFFPP aP f bP f人procedure E;beginif sym=(or sym=a or sym-b or sym=A，then begin T;E endelse errorendprocedure E;beginif sym=+then begin advance;E endelse if sym)and sym#then errorendprocedure T;beginif sym=(or sym=a or sym=b o

11、r sym=A，then begin F;T endelse errorendprocedure T;beginif sym=(or sym=a or sym=b or sym=A，then Telse if sym-*then errorendprocedure F;beginif sym=(or sym=a or sym=b or sym=A，then begin P;F endelse errorendprocedure F;beginif sym-*then begin advance;F endendprocedure P;beginif sym=a or sym=b or sym=

12、A，then advanceelse if sym=(thenbeginadvance;E;if sym-)then advanceelse errorendelse errorend;P81-3 是，满足三个条件。不是，对 于A不满足条件3。不是，A、B均不满足条件3。(4)是，满足三个条件。*|c 5 1 c /第五章P133-1E=E+T=E+T*F短语：E+T*F,T*F,直接短语:T*F句柄:T*FPl33-2文法：S f a l l TT,SS(1)最左推导：s n (T)n (T,S)n (S,S)n (a,S)n (a,(T)=(a,(T,S)n (a,(S,S)=(a,(a,

13、S)n (a,(a,a)S=(T,S)n (S,S)=(T),S)=(T,S),S)n (T,S,S),S)n (S,S,S),S)=(T),S,S),S)n(S),S,S),S)n(S,S),S,S),S)n(a,S),S,S),S)n(a,a),S,S),S)=(a,a)J,S),S)n(a,a),A,(r),S)n(a,a)J,(S),S)n(a,a),A,(a),S)=(aM)J,(a),a)最右推导：S n (T)n (T,S)=(T,)=(T,(T,S)=(T,(T,a)=(T,(S,a)n (T,(a,a)=(S,(a,a)=(a,(a,a)S=(T,S)=(T,a)=(S,a)

14、n (,a)=(T,S),a)n (T,(T),a)n (T,(S),a)=(7,(a),a)n (T,S,(a),a)=(T,3(a),a)=(S,3(a),a)n (T)J,(a),a)n (T,S),3(a),a)=(T,a),3(a),a)=(S,a),(a)M)=(a,a),人,),a)(2)(a),人,(a),a)(S,a)?,(a),a)(T,a)?,(a),a)(工SJ,(a),a)(O ir，(a),a)(S?,(a),a)(T J,(a),a)(整,(a),a)(T,(a),a)(T,(S),a)(T,(T),a)(L S),a)(D，a)(S,a)(LS)(T)S“移进-

15、归约”过程：步 骤 栈 输入串 动作0#(a),(a),a)#预备1#(a),晨a),a)#进21#(T,(S),a)#归2#(a,a),A,(a),a)#进3#(a，a),人,(a),a)#进4#(a,a)J,(a),a)#进5#(S,a1,(a),a)#归6#(T,a)J,(a),a)#归7#(T,a),人,(a),a)#进8#(T,a),A,(a),a)#进9#(T,S),A,(a),a)#归10#(T,(a),a)#归11#(T)J,(a),a)#进12#(S(a),a)#归13#(T,A,(a),a)#归14#(T,人,(a),a)#进15#(T,A,(a),a)#进16#(T,S,

16、(a),a)#归17#(T,(a),a)#归18#(T,(a),a)#进19#(T,(a),a)#进20#(T,(a),a)#进22#(T,(T),a)#归23#(T,(T),a)#进24#(T,S),a)#归25#(T),a)#归26#(T),a)#进27#(S,a)#归28#(T,a)#归29#(T,a)#进30#(T,a)#进31#(T,S)#归32#(T)#归33#(T)#进34#S#归Pl 33-3(1)nRSTVT(S)=a,A,(FI RSTVT(T)=a,A,()LASTVT(S)=a,)LASTVT(T)=,aJ,)Q)aA()aA(=G6是算符文法，并且是算符优先文法优先函

17、数aA()f44244g55523(4)栈 输入字符串 动作#(a,(a,a)#预备#A-S4.S f AS-5,S fb6.s fb,7.A f S4S.AS-A9.ASA-lO.A f 411.A a 确定化:SAab(0,2,5,7,1 0(1,2,5,7,8,10)2,3,5,7,1 0 1 1 1 2 5,7,8,10(2,5,7,8,1 0)2,3,5,7,9,10)1 1 6 2,3,5,7,1 0 2,4,5,7 8 1 2,3,5,7,1 0 1 1 6 0)2,5,7,8,1 0 (2,5,7,8,1 0 2,3,5,7,9,10 1 1 2 3 5,7,90)2,4,5,

18、7 8 10)(2,3,5,7,1 0 1 1 6 2 4 5,7,8,10)2,5,7,8,1 0)2,3,5,7,9,10)1 1 1 1 64)(i)6 4)4)4)6b a,A S S Ab-a A7：S f AS-A S AS f ASS f bA-SAA/aDFA构 造LR(O)项目集规范族也可以用GO函数来计算得到。所得到的项目集规范族与上图中的项目集一样：/0 S -S,S -AS，S-乃，A.-SA，A -Q GO(Io,a)=A a -=/(GO(IQ,b)=s/?-=/,GO(IQ,S)=S T S-，A-S-A,A-SA,A f a,S-AS,S /?!=/3GO(/0

19、，A)=S-A S,S-AS,S-b,A-SA,A-a =74GO(/3,a)=A a -=/,GO(73,b)=s -=/2GO(I S)A S-A 9 S -AS,S -b A -SA，A -a /5GO(八，A)=ASA-,S A-S ,S-AS,S+b,A f必，A Cl 二 GO(I4,a)=A a=1GO(Z4,b)=s b -=I2GO(/4 9 S)=S AS 9 A S,A 9 S ,AS，S h,A ,SA，A a =/7G0(/4 9 A)=S AS,S rAS 9 S，b,A，SA,A.a 二，4GO(八，a)=A.a =/GO(l5,b)=s b -=I2GO(/s

20、9 S)A S A,S ,AS,S，b,A.,SA.?A,a 二，5G O(八，A)A SA ,S A S,S A S，S-，b,A ,SA,A f a =/6GO(/6 9 u)A.b -=I2GO(16，S)S AS,9 A.5,A,S AS,S ,b,A.*SA,A.C l =，7GO(/6,A)=S A S,S ,AS，S *b,A SA.,A 14GO(/7,a)=A a -=IIGO(/7,b)=s-=I2GO(/7,S)A St A J S ,AS,S，b,A.SA,A.,a =/$GO(I 9 A)A SA,9 S A,S,S-AS,S-,h,A.*SA.,A f a =/6项

21、目集规范族为C=小z2,八，小 小 3 M(3)不是SLR文法状态3,6,7有移进归约冲突状态3：FOLLOW)=#不包含a,b状态6：FOLLOW(S)=#,a,b包含a,b,；移进归约冲突无法消解状态7：FOLLOW(A)=a,b包含a,b；移进归约冲突消解所以不是SLR文法。(4)构造例如LR(1)项目集规范族见下图：对于状态5,因为包含项目AfAS.a/b,所以遇到搜索符号a 或 b时，应 该 用 归 约。又因为状态5 包含项目alb,所以遇到搜索符号a 时，应该移进。因此存在“移进-归约”矛盾，所以这个文法不是LR(1)文法。bA1:S TS*#A f S A a/bA-SA a/b

22、A a/bS f AS a/bA5：A SA a/bS-A S a/bS f AS a/bS /?a/bA SA a/b8：S A-S a/bS T AS a/bS T-b a/bA f SA a/bM -6 Z a/bS /?a/bA-a a/b-ASSaSaA “a/baAAbAb,AA5-第六章/*第六章_ 有点又隹P164 5(1)E-E1+T if(El.type=int)and(T.type=int)then E.type:=intelse E.type:=realE-T E.type:=T.typeTrnum.num T.type:=realT-num T.type:=int(2

23、)P164-7SL1|L2 S.val-Ll.val+(L2.val/2L2Jeng,h)S-L S.val:=L.valL-L1B L.val:=2*Ll.val+B.val;L.length:=L 1 ,length+1L-B L.val:=B.c;L.length:=1B-0 B.c:=OB f 1B.c:=l第七章P217-1a*(-b+c)a+b*(c+d/e)-a+b*(-c+d)v i(C v i。)(A A B)v(iC v D)(A v B)A(C v 1 A E)abc+*abcde/+*+abcd+*+A CD v iVA 8AC OV vABVCZ)EA V Aif(x

24、+y)*z=0 then(a+b)c else a t b f cxy+z*0=ab+c t abc t t或 xy+z*0=Pl jez ab+c f P2 jump abc f fPIP2P217-3-(a+b)*(c+d)-(a+b+c)的三元式序列：(1)+,a,b(1),-(3)+,c,d(4)*,(2),(3)(5)+,a,b(6)+,(5),c-,(4),(6)间接三元式序列:三元式表：(1)+,a,b(2),(1),-(3)+,c,d(4)*,(2),(3)(5)+,(1),C(6)-,(4),(5)间接码表：(1)Q)(3)(1)(6)四元式序列:(1)+,a,b,1(2)r

25、.,T20)+,c,d,T3(4)*,T2,T3,T*(5)+,a,b,T5(6)+,T5,C,Tb(7)T4,T6,T7P218-4自下而上分析过程中把赋值句翻译成四元式的步骤:A:=B*(-C+D)步 骤 输 入 串 栈 PLACE 四元式(1)A:=B*(-C+D)(2):=B*(-C+D)i A(3)B*(-C+D)i:=A-(4)*(-C+D)i:=i A-B(5)*(-C+D)i:=E A-B(6)*(-C+D)i:=E A-B(7)(-C+D)i:=E*A-B-(8)-C+D)i:=E*(A-B-(9)C+D)i:=E*(-A-B(10)+D)i:=E*(-i A-BCTn:=T

26、2T3 这一步是多余的(11)+D)i:=E*(-E A-BC 4)(12)+D)(13)D)(1 4)(15)(16)(17)(18)(19)产生的四元式：(,C,-,J；)(+,T,D,q)(*,8,4,73)(：=,4，-,A)P218-5i:=E*(E A-B T i:=E*(E+A-B T-i:=E*(E+i A-B-Di:=E*(E+E A-B-4-D(+,4,D,q)i:=E(E A-B-i:=E*(E)A-B-T；-i:=E+E A-B-T,(*,B,7,r3)i：=E A-4(:=,q,-,A)(20)A/*设A：10*20,B、C、D：20,宽度为w=4则T l:=i*20

27、Tl:=Tl+jT2:=A 84T3:=4*T1T4:=i+jT5:=B-4T6:=4*T4T7:=T5T6T8:=i*20T8:=T8+jT9:=A-84T10:=4*T8Tll:=T9T10T12:=i+jT13:=D-4T14:=4*T12T15T13T14T16:=T11+T15T17-C-4T18:=4*T16T19T17T18T20:=T7+T19Tn:=T205 1 c IP218-6100.(jnz,A,0)101.(j,102)102.(jnz,B,104)103.(j,0)104.(jnz,C,103)105.(j,106)106.Qnz,D,104)假链链首107.(j,

28、-,-,100)真链链首假链：106,104,103)真链：107,100P218-7loo.(j,A,C,102)ioi.0,0)102.(jF do MS、F For/:=,to,I f i dM T S FdoMSt backpatch(S 1 .nextlist,nextquad);backpatch(F.truelist,M.quad);emit(F.place:=F.place+1);emit(j,F.place F.end,M.quad);S.nextlist:=F.falselist;)F f For/：=Et to E2 F.falselist:=makelist(nextq

29、uad);El.place,E2.place,0);emit(I.Place place);F.truelist:=makelist(nextquad);emit,jF.place:=I.place;F.end:=E2.place;)I t id p:=lookup(id.name);if p nil thenI.place:=pelse error)M-M.quad:=nextquad)c?c forid:-EltoE2 doI NI TI AL=NEWTEMP;emit(El.PLACE,I NI TI AL);FI NAL=NEWTEMP;emit(E2.PLACE,FI NAL);p:

30、=nextquad+2;emit(jI NI TI ALFI NAL p);F.nextlist:=makelist(nextquad);emit(1,-,-,一，);F.place:=lookup(id.name);if F.place nil thenemit(F.place:=,I NI TI AL)F.quad:=nextquad;F.final:=FI NAL;)S FS1(backpatch(S 1 .nextlist,nextquad)p:=nextquad+2;emit(，j:F.place F.final/p);S.nextlist:=merge(F.nextlist,mak

31、elist(nextquad);emit();emit(succ,F.place F.place);emit(j,一,一,F.quad);第九章P270-9传名即当过程调用时，其作用相当于把被调用段的过程体抄到调用出现处，但必须将其中出现的任一形式参数都代之以相应的实在参数。A:=2;B:=3;A:=A+1;A:=A+(A+B);p r i n t A;.A=9(2)传地址即当程序控制转入被调用段后，被调用段首先把实在参数抄进相应的形式参数的形式单元中，过程体对形参的任何引用或赋值都被处理成对形式单元的间接访问。当被调用段工作完毕返回时，形式单元(都是指示器)所指的实参单元就持有所希望的值。A

32、:=2;B:=3;T:=A+B把T,A,A的地址抄进已知单元J 1,J 2,J 3 x:=J l;y:=J 2;z:=J 3 把实参地址抄进形式单元，且J 2=J 3 Y f:=y T+lZT :=z T +x T 丫T ：对y的间接访问Z?：对z的间接访问 p r i n t AA=8(3)得结果每个形参均对应两个单元,第一个存放实参地址,第二个存放实参值,在过程体中对形参的任何引用或赋值都看成是对它的第二个单元的直接访问，但在过程工作完毕返回前必须把第二个单元的内容放到第一个单元所指的那个实参单元中 A:=2;B:=3;T:=A+B把T,A,A的地址抄进已知单元J1,J2,J3xl:=Jl

33、;x2:=T;y l:=J2;y2:=A;zl:=J3;z2:=A;将实参的地址和值分别放进两个形式单元中y2:=y2+l;z2:=z2+x2;对形参第二个单元的直接访问x lf：=x2;ylf:=y2;zlf:=z2/返回前把第二个单元的内容存放到第一个单元所指的实参地址中print AA=7(4)传值即被调用段开始工作时，首先把实参的值写进相应的形参单元中，然后就好像使用局部变量一样使用这些形式单元A:=2;B:=3;x:=A+By:=Az:=Ay:=y+lz:=z+xprint AA=2过程调用不改变A 的值第十章P306-1P306-2BiB2B4read A,BF:=lC:=A*ABiD:=B*Bif C100 goto L2L2:F:=F-1goto L,基本块为用、B?、B r a、B5P307-4B2有回路，所以B2是循环，B2既是入口节点，又是出口节点(1)代码外提：不存在不变运算，故无代码外提(2)强度削弱：A:=K*I B:=J*I *+(3)删除基本归纳变量：K100可以用A100*K或 B100*J代替P307-5B:=J+1B2,B3是循环，B2是入口节点，也是出口节点(1)代码外提：B:=J+1(2)删除归纳变量