编译原理-第三版-课后答案.pdf

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

1、编译 原理 课后题答案第二章P36-6(1)G。是。9组成的数字串(2)最左推导：N n N D n NDD n NDDD=DDDD n ODDD n 01 n 012。n 0127N=ND=DD=3D n34N n N D n NDD=DDDn 5DD=56D=568最右推导：N n ND=N ND7=N27 n ND21 n N127 n DI27 n 0127N n NO n N 4 n o 4 n 34N n ND n N 8 n ND8=N68 n 068 n 568P36-7G(S)(7-113151719N f 214161810。-0INS fO IA。A A D NP36-8

2、文法：E-T 1E +T1E TFIT*FIT/FF (E)li最左推导：E=E+T T+T F+T=i+T i +T*F=i+F*F=i+i*F i+i*iE n T n T*F n F*F n i*F n i*(E)n i*(E +T)ni*(T +T)n i*(F +T)n i*(i+T)n i*(i+F)n i*(i+i)最右推导：实用文档.七二石+7=E+7*/=七+7*，=+/*，=；+浮，=7+浮，=歹+浮，=+浮EnT nF*7 nF*FnF*（E）n/*（：+T）nF*（：+/0 n F*（：+i）0尸*（7+）=/*（/+，）=/*（，+）=涔（，+）语法树：/*、F iF

3、 iii+i+iP36-9句子iiiei有两个语法树：S=iSeS n iSei n USei n iiieiS=iS=USeS=USei=iiieiP36-10S TSTT f 1（）P36-11Ll:S t ACA T aAb I abC-c C I L2:实用文档.ABA-Q A I eB bBc I beL3:ABA f aAh 18B ciBb I 8L4:S A BA t 0411 s8 180 I A第三章习题参考答案P6 4-7(1)Q _iWioiQ0G 公 J .G 1c3制,P，0 u确定化：01 X0 1,2,3)4)6 1,2,3)3 2,3,4)2,3(2,3)3.

4、4)3,4)2,3,5)(2,3.4)(2,3,5 3(2,3,4,Y)2,3,4,Y 2,3,5)(2,3,4,最小化：(0,1,2,3,4,5,60,123,4,5=1,3,5 0,12,3,4,5=1,2,4,6)0,1,2,3,4,8 ,6 0,1,2,3,4=1,3,5)(0,1,2,3,H,5,6(0,1,2,3=1,3 0,1,2,3=1,2,4)0,1,2遭 4,5,6 10,1=1 0,1=1,22,3=3 2,3|=40,?,2,3,4,5|,6P6 4-8(1)(110)-01(2)(1 I2 I3 I4 I5 I6 I7 I8 1 9)(0111 2 13 14 15

5、I 6 17 18 19)*(0 15)I(0 15)(3)0*1(0110*1)*11*0(0110*1)*P6 4-12(a)实用文档.确定化:ab001 11o,1(o,1)110巾66小给状态编号:ab012112203333最小化：0,1,2,3 0,1 =1 0,1 =2 2,3“=0,3 20 =3 0,1,，2,3 b(b)ab已经确定化了，进行最小化最小化：0,1,2,3,4,510,1=1 0,1=2,4ab2,3,4,5=1,3,0,5 2,3,4,5=2,3,4,5ab2,4=1,0 2,4=3,5ab3,5=3,5 3,5=2,4ab0,1,2,4,355)0,1=1

6、 0,1=2,4ab2,4=1,0 2,4=3,5ab3,5=3,5 3,5=2,4ah(2):实用文档.0确定化:01X,1.Y1.Y)21.Y)1,Y)221.Y)4)64 6给状态编号:01012112213333 0,1,2,3)0,1 =1 0,1 =201 2,3 =1,3 2,3 =30 I 0,1,2,3P81-1(1)按照T,S的顺序消除左递归G S fa lA!(T)T T STT，f S T 递归子程序：实用文档.pr oc ed u r e S;b eginif s y m=a or s y m=，”t hen a b va n c eels e if s y m=(t

7、 hen b egina d va n c e;?;if s y iTF)t hen a d va n c e;els e er r or;en dels e er r oren d;pr oc ed u r e T;b egins；ren d;pr oc ed u r e T ;b eginif s y m=,t hen b egina d va n c e;s；ren den d;其中：s y m:是输入串指针I P所指的符号a d va n c e:是 把I P调至下一个输入符号er r or:是出错诊察程序(2)F I R ST(S)=a/，(F I R ST(T)=a/，(F I R

8、 ST(T)=,F O LLO W(S)=),#F O LLO W(T)=)F O LLO W(F)=)预测分析表是LL(1)文法a()#SS-,C L5 (7)TTTSPT s rTTSTTr-T J,SP81-2文法:实用文档.E TEE-+ET t FTr-r iF T PFF J *尸|Pf(E)lalb|A(1)F I R ST(E)=(,a,b,F I R ST(E,)=+,e F I R ST(T)=(,a,b,*F I R ST(T)=(,a,b/,e)F I R ST(F)=(,a,b,*F I R S T )=*,e F I R ST(P)=(,a,b,F O LLO W(

9、E)=#,)F O L L O W )=#,)F O LLO W(T)=+,),#F O LLO W(V)=+,),#F O LLO W(F)=(,a,b j,+,),#F O LLO W。)=(,a,b,+,),#F O LLO W(P)=*,(,a,b j,+,),#(2)考虑以下产生式：E T+E后r-risF f *尸 lP-()四。历F I R ST(+E)A F I R ST(e)=+C e =3F I R ST(+E)A F O LLO W(E )=+C#,)=6F I R ST(T)A F I R ST(e)=(,a,b,*n e =4F I R ST(T)A F O LLO

10、W(T)=(,a,b/C +,),#=F I R ST(*F)D F O LLO W(F )=*C (,a,b/，+,),#=F I R ST(E)A F I R ST(a)n F I R ST(b)C F I R ST)=所以，该文法式LL(1)文法.(3)实用文档.+*()abEETTEETTE，ETTE，ETTEE E+EEf-E T 8TTT FTTT FT T r FT T FT实用文档.(4)Tr-T-Tr-r r T Tr-r r-FFT PFF fP F F fP F FT PFF *尸 尸 F广 尸 F f F f pPf (E)P i aP T bPipr oc ed u

11、r e E;b eginif sym-(or s y m=，a or s y m=b or s y m=t hen b egin T;E en dels e er r oren dpr oc ed u r e E;b eginif s y m=，+，t hen b egin a d va n c e;E en dels e if s y m，)J a n d s y m#t hen er r oren dpr oc ed u r e T;b eginif s y m=，(or s y m=，a or s y m=b or s y m=，t hen b egin F;T，en dels e er

12、 r oren dpr oc ed u r e T，;b eginif s y m=(or s y m=a or s y m=b or s y m=t hen Tels e if s y m=t hen er r oren dpr oc ed u r e F;b eginif s y m=(or s y m=，a or s y m=b or s y m=,t hen b egin P;F en dels e er r oren dpr oc ed u r e F;b eginif s y m=，*，t hen b egin a d va n c e;F en den dpr oc ed u r

13、 e P;实用文档.b eginif s y m=，a or s y m=b or s y n p t hen a d va n c eels e if s y m=，(t henb egina d va n c e;E;if s y m=)t hen a d va n c eels e er r oren dels e er r oren d;P8 1-3(i)是，满足三个条件。(2)不是，对于A不满足条件3。(3)不是，A、B 均不满足条件3。(4)是，满足三个条件。第五章P133-1E=E +TnE+T*F短语：E+T*F,T*F,直接短语：T*F句柄：T*FP133-2文法：S T 1

14、(T)T T,S S(1)最左推导：S n(T)n (T,S)=(S,S)n (a,S)=(,(D)=(,(T,S)n (a,(S,S)n (a,(,S)n (,(,)S=(T,S)=(S,S)=(T),S)=(T,S),S)n (T,S,S),S)=(S,5,S),S)=(T),S,S),S)n(T,S),S,S),S)n(S,S),S,S),S)n(a,S),S,S),S)n(a,a),S,S),S)=(a,a),A,S),S)n(a,a)6 ,(7),S)n (a,(S),S)=(a,a/,(a),S)=(a,a),A,(a),a)最右推导：实用文档.S n (T)n (T,S)n (T

15、,(T)=(T,(T,S)n (T,(T,a)n (T,(S,a)n (T,(a,a)=(S,(,)=(a,(a,a)S n (T,S)=(T,a)=(S,a)n (T),a)n (T,S),a)=(T,(T),a)n (T,(S),a)n (T,(),)n (T,S,(a),)n (TJ,(),)n (人,(),)n (7V,(),)=(T,S ,(a),a)n(r,a),A,(a),a)n(S,a ,(a),a)n(a,a),(),)(2)(a,a)J,(a),a)(a)J,(a),a)(T.a)/,(a),a)()，(a),a)(，(a),a)(0(a),a)(T，(a),a)(T.S.

16、(a),a)(T,(a),a)(T,(S),a)(T,(I),a)(八)，a),a)a)(11)(T)“移进-归约”过程：步骤 栈输入串 动作0#(a,a),(a),a)#预备1#(a,a),(a),a)#进2#(a,a),(a),a)#进3#(a,a),(a),a)#进4#(a,a),(a),a)#进5t t(S,a),(a),a)#归6#(T,a),(a),a)#归7#(T,a),(a),a)#进8#(T,a)/,(a),a)#进9#(T,S)/,(a),a)#归10#(T)/,(a),a)#归11ft(T)/,(a),a)#进12#(S,(a),a)#归13#(T,(a),a)#归14#

17、(T,(a),a)#进15#(T,(a),a)#进16#(T,S,(a),a)#归17#(T,(a),a)#归实用文档.18#(T,(a),a)#进19#(T,(a),a)#进20#(T,(a),a)#进21#(T,(S),a)#归22#(T,(T),a)#归23#(T,(T),a)#进24#(T,S),a)#归25#(T),a)#归26#(T),a)#进27#(S,a)#归28t t(T,a)#归29#(T,a)#进30#(T,a)#进31#(T,S)#归32#(T)#归33t t(T)#进34#S#归P133-3(i)F I R STVT(S)=a,(F I R STVT(T)=,a/，(

18、LA STVT(S)=a,*,)LA STVT(T)=,)a)(2)a()a(=GA是算符文法，并且是算符优先文法0优先函数a*()f44244g55523实用文档.gag(g)g栈输入字符串动作#(a,(a,a)#预备#(a,(a,a)#进#(a,(a,a)#进#(t,(a,a)#归#(t,(a,a)#进#(t,(a,a)#进#(t,(a,a)#进#(t,(t,a)#归#(t,(t,a)#进#(t,(t,a)#进#(t,(t,s)it归#(t,(t)#归#(t,(t)#进#(t,s)t t归#(t)#归i t (t )#进#s#归s u c c es sP134-5(1)0.S-S 1.S-

19、S-2.Sf AS 3.Sf A S4.S AS-5.S 8 6.s t b-7.A SA8.A-5-A 9.A-SA-10.Aa 11.A-a-确定化:SAab(0,2,5,7,10)1,2,5,7,8,10)2,3,5,7,10)11 6 1,2,5,7,8,10)2,5,7,8,10)2,3,5,7,9,10)11 6(2,3,5,7,10)4,5,7,8,10)2,3,5,7,10 11 6(2,5,7,8,10)2,5,7,8,10)2,3,5,7,9,10)11 6 2,3,5,7,9,10(2,4,5,7,8,10)2,3,5,7,10 11 6 2,4,5,7,8,10)2,5

20、,7,8,10 2,3,5,7,9,10)11 6 11向6 6 666实用文档.D F A构 造LR(O)工程集标准族也可以用GO函数来计算得到。所得到的工程集标准族与上图中的工程集一样:I=S-S ,S f A S,S,A S A ,A -a G O (),a)=G 0(/,b)=G 0(/,S)=G O(1,A)=*0G0(4，a)=G 0(/,b)=G0(4，S)=G 0(/,A)=G 0(/.,a)=G 0(/4，b)=G 0(/,S)=G 0(/,A)=4G0(，a)=G 0(1,b)=G 0(/,S)=G 0(/.A)=G 0(75,a)=6G 0(7,b)=6G O(/,S)=

21、G 0(/6,A)=G0(/，a)=G 0(4 ,b)=G 0(/；,S)=G 0(，A)=7A f a =/iS,f b 二I,Sf S-f ABS.A,A Af aS A S,S ,AS,S-，b,A ,SA,A a-IiS f b 二LA f S.A,5.二 AS,S b ,4-SA,A SA,S-A,S,S AS,S-，b,A f a -IiS f b.S AS,A S,A,S ,AS,S *h,S A,S f S,AS,S-,A ,SA,A f a 二/S t b 二 LA S A，ST AS,S -b,A -SA,A-SA,S-A,S,S-,AS,S-,b,A a-IiST b-=

22、I2S AS,A S,A,S AS,S-，b,S A,S,S-,AS,S-，b,A ,SA,4 f a =/S-b-=f2A-S.A,S AS,S T b,A SA,A SA,S A-S,S -AS,S-b,S A S,S b 二 Ir3A a =/A-a =I5*A-SA,A a =I6A-SA.,A-,C i IA f a 二，4A-a =IA-SAA f a =/6A-SA,A-a =/A a =I44 f 二/A SA f5 A -a =I6工程集标准族为c叫，1号/4,g(3)不是S L R文法状态3,6,7有移进归约冲突状态 3 F O L L O W (ST)=#不包含 a,b状

23、态6：F O L L O W (S)=#,a,b 包含a,b,；移进归约冲突无法消解状 态7：F O L L O W (A)=a,b 包含a,b；移进归约冲突消解所以不是S L R文法。(4)构造例如L R(1)工程集标准族见以下图：对 于 状 态5,因为包含工程 A fA S-a l b、,所以遇到搜索符号a或b时，应该用A-A S 归约。又因为状态5包含工程 A 一 驾 a l b ,所以遇到搜索符号a时，应该移进。因此存在“移进-归约矛盾，所以这个文法不是L R(1)文法。实用文档.SA实用文档.第六章/*第六章会有点难P 16 4 -5(1)E E l+T if (E l.type=i

24、nt)and (T.type=int)th en E.type:=intelse E.type:=realE f T E.type:=T.type)T-num.num T.type:=realT f num T.type:=int)(2)P 16 4 -7S f L l.l e n g t h )S f L S.val:=L.valL-L 1B L.val:=2*L 1.val+B.val;L.leng th:=L L leng th+1)L-B L.val:=B.c;L.leng th :=1B-0 B.c:=0 B-1 B.c:=l第七章P 2 17 -1(AAB)V(CV)a*(-b+c

25、)ab c+*a+b*(c+d/e)ab c d e/+*+-a+b*(-c+d)a b c d+*+-iA v )(C v-iD)A-CD-1 v-1 vA B A C v v(A v B)A(C V DAE)A B v C D E A v Aif (x+y)*z=0 th en(a+b)f c else a t b t c xy+z*0=ab+c t ab c f f 或 xy+z*0=P l jez ab+c t P 2 jump ab c t tP l P 2实用文档.P 2 17 -3-(a+b)*(c+d)-(a+b+c)的三元式序列：(1)+,a,b(2)(1),-(3)+,c,

26、d(4)*,(2),(3)(5)+,a,b(6)+,(5),c(4),(6)间接三元式序列：三元式表：+,a,b(1),-+,c,d(4)*,(2),+,，C(6)(4),间接码表：(1)(2)(3)(4)(1)(5)(6)四元式序列：)/+,a,b,T77/)/17)/1234567z(z(xz(z(xz(xz(xz(x，5 U，3*,&勺 r+,a,b,T+,T c VP 2 18 -4自下而上分析过程中把赋值句翻译成四元式的步骤:A:=B*(-C+D)实用文档.步骤输入串栈P L A C E四元式(1)A:=B*(-C+D)(2):=B*(-C+D)iA(3)B*(-C+D)i:=A-(

27、4)*(-C+D)i:=iA-B*(-C+D)i:=EA-B(6)*(-C+D)i:=EA-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*(-iA-B C(11)+D)i=E*(-EA-B CT )(12)+D)i=E*(EA-B-T1(13)D)i=E*(E+A-B i -(14)i=E*(E+iA-B i-D(15)i=E*(E+EA-B i-D(+,T ,D,T )(16)i=E(EA-B i1 2(17)i=E*(E)A-B T2-(18)i=E+EA-B-T 2(*,B,T,T)(19)i=EA E 2A-

28、T(：=,T3(2 0)A3产生的四元式：(,C,-,T)(+,T ,D)(*,B.T(:=,T?3P 2 18-5设 A ：10*2 0,B、C、D：2 0,宽度为 w=4 那么T l:=i*2 0T l:=T l+jT 2:=A-8 4T 3:=4*T 1T n:二T 2 T 3 这一步是多余的T 4:=i+jT 5:二B-4T 6:=4*T 4T 7:=T 5 T 6 T 8:=i*2 0T 8:=T 8+jT 9:=A-8 4T 10:=4*T 8T ll:=T 9 T 10 T 12:=i+jT 13:=D-4T 14:=4*T 12T 15:=T 13 T 14 T 16:=T 1

29、1+T 15T 17:=C-4T 18:=4*T 16实用文档.T 19:=T 17 T 18 T 2 0:=T 7+T 19T n:=T 2 0P 2 18 -610 0.(jnz,A,0)10 1.(j,10 2)10 2.(jnz,B,10 4)10 3.(j,0)10 4.(jnz,C,10 3)10 5.(j,10 6)10 6.(jnz,D,10 4)10 7.(j,10 0)一假链链首一真链链首假链：10 6,10 4,10 3)真链：(10 7,10 0 P 2 18 -710 0.(j,A,C,10 2)10 1.(j,0)10 2.(j For I:=E to E12I i

30、dM f S F do MSb ac kpatc h(S l.nextlist,nextquad);b ac kpatc h(F.truelist,M.quad);emit(F.plac e 二F.plac e+1);emit(jK,F.plac e F.end M.quad);S.nextlist:=F.f alselist;)F For I：=E to E F.f alselist:=makelist(nextquad);1 2emit(j,E l.plac e E 2.plac e,0);emit(I.P lac e=E l.plac e);F.truelist:=makelist(ne

31、xtquad);emit(j,;F.plac e:=I.plac e;F.end :=E 2.plac e;I f id p:=lookup(id.name);if p nil th enI.plac e:=pelse error)M M.quad :=nextquad 方法2：S-*f or id:=E l to E 2 d o S IS f F S IF f f or id:=E l to E 2 d oF forid:=EtoE2 d o(I N I T I A L=N E W T E M P;emit(I N I T I A L);F I N A L=N E W T E M P;emi

32、t(-J F I N A L);p:=nextquad+2;emit(j,I N I T I A L F I N A L ,p);F.next1ist:=makelist(nextquad);emit(j,一,);实用文档.F.plac e:=lookup(id.name);nil th enemit(F.plac e=I N I T I A L)F.quad:=nextquad;F.f inal-F I N A L;)S FS(b ac kpatc h(S l.nextlist,nextquad)p:=nextquad+2;emit(j,F.f inal ,p);S.nextlist:=me

33、rg e(F.next list,makelist(nextquad);emit(j,)；emit(suc c,F.plac e 一，F.plac e);emit(，j,F.quad);)第九章P 2 7 0 -9 传 名即当过程调用时，其作用相当于把被调用段的过程体抄到调用出现处，但必须将其中出现的任一形式参数都代之以相应的实在参数。A:=2;B:=3;A:=A+1;A:=A+(A+B);print A;A=9(2)传地址即当程序控制转入被调用段后，被调用段首先把实在参数抄进相应的形式参数的形式单元中，过程体对形参的任何引用或赋值都被处理成对形式单元的间接访问。当被调用段工作完毕返回时，形式

34、单元(都是指示器)所指的实参单元就持有所希望的值。A:=2;B:=3;T:=A+B 把 T,A,A 的地址抄进单元J 1,J 2,J 3x:=J l;y:=J 2;z:=J 3Y t :=y t +1Z t :=z t +x t把实参地址抄进形式单元，且 J 2=J 3/Y t ：对 y的间接访问Z t ：对 z的间接访问p r i n t AA=8(3)得结果每个形参均对应两个单元，第一个存放实参地址，第二个存放实参值，在过程体中对形参的任何引用或赋值都看成是对它的第二个单元的直接访问，但在过程工作完毕返回前必须把第实用文档.二个单元的内容放到第一个单元所指的那个实参单元中实用文档.A:=2

35、;B:=3;T:=A+B 把 T,A,A 的地址抄进单元J I,J 2,J 3xl:=J 1;x2:=T;y l:=J 2;y 2:=A;z l:=J 3;z 2:=A;将实参的地址和值分别放进两个形式单元中y 2:=y 2+l;z 2:=z 2+x2;对形参第二个单元的直接访问xl t ：=x2;y l t :=y 2;z l t :=z 2 返回前把第二个单元的内容存放到第一个单元所指的实参地址中p r i n t AA=7(4)传值即被调用段开始工作时，首先把实参的值写进相应的形参单元中，然后就好似使用局部变量一样使用这些形式单元A:=2;B:=3;x:=A+By:=Az:=Ay:=y+

36、1z:=z+xp r i n t AA=2过程调用不改变A 的值第十章P 306-1实用文档.r e a d CA:=0B：=lL i ：A：=A-Bi f B C g o t o L zBiB2B3B4P 306-2r e a d A,BF:=lC:=A*A BD:=B*Bi f C 1 00 g o t o L】实用文档.5halt B4L：2F:=F-1goto L B根本块为外B2、B、B、B3 4 5P307-4B2有回路，所以 B2 是循环，B2既是入口节点，又是出口节点(1)代码外提：不存在不变运算，故无代码外提(2)强度削弱：A:=K*I B:=J*I *-+(3)删除根本归纳变量：1 1 00可以用A 1 00*K 或 B 1 00*J 代替实用文档.P 307-5实用文档.B2,B3 是循环，B2是入口节点，也是出口节点(1)代码外提：B:=J+1(2)删除归纳变量(3)本文档局部内容来源于网络，如有内容侵权请告知删除，感谢您的配合!(4)(5)实用文档.