编译原理课后答案(陈火旺).doc 27页

'课后答案http://www.khdaw.com第二章P36-6(1)是0~9组成的数字串(2)最左推导:最右推导:P36-7G(S)P36-8文法：最左推导:最右推导:语法树：/********************************27 课后答案http://www.khdaw.com*****************/P36-9句子iiiei有两个语法树：P36-10/*****************************/P36-11/***************L1:L2:L3:27 课后答案http://www.khdaw.comL4:***************/第三章习题参考答案P64–7(1)XYX1234Y5011011确定化：01{X}φ{1,2,3}φφφ{1,2,3}{2,3}{2,3,4}{2,3}{2,3}{2,3,4}{2,3,4}{2,3,5}{2,3,4}{2,3,5}{2,3}{2,3,4,Y}{2,3,4,Y}{2,3,5}{2,3,4,}032010100110654010111最小化：27 课后答案http://www.khdaw.com002110010543010111P64–8(1)(2)(3)P64–12(a)a10a,ba确定化：ab{0}{0,1}{1}{0,1}{0,1}{1}{1}{0}φ27 课后答案http://www.khdaw.comφφφ给状态编号：ab012112203333a10aabbb32ba最小化：aa210bbab(b)032bbaabaab541baaa已经确定化了,进行最小化27 课后答案http://www.khdaw.com最小化：021bbaabaP64–14(1)01010(2):YX201Y1X0确定化：01{X,1,Y}{1,Y}{2}27 课后答案http://www.khdaw.com{1,Y}{1,Y}{2}{2}{1,Y}φφφφ给状态编号：01012112213333010010321110最小化：031011100第四章P81–1(1)按照T,S的顺序消除左递归递归子程序：procedureS;beginifsym="a"orsym="^"thenabvanceelseifsym="("27 课后答案http://www.khdaw.comthenbeginadvance;T;ifsym=")"thenadvance;elseerror;endelseerrorend;procedureT;beginS;end;procedure;beginifsym=","thenbeginadvance;S;endend;其中:sym:是输入串指针IP所指的符号advance:是把IP调至下一个输入符号error:是出错诊察程序(2)FIRST(S)={a,^,(}FIRST(T)={a,^,(}FIRST()={,,}FOLLOW(S)={),,,#}FOLLOW(T)={)}FOLLOW()={)}预测分析表a^(),#ST是LL(1)文法P81–2文法：27 课后答案http://www.khdaw.com(1)FIRST(E)={(,a,b,^}FIRST(E")={+,ε}FIRST(T)={(,a,b,^}FIRST(T")={(,a,b,^,ε}FIRST(F)={(,a,b,^}FIRST(F")={*,ε}FIRST(P)={(,a,b,^}FOLLOW(E)={#,)}FOLLOW(E")={#,)}FOLLOW(T)={+,),#}FOLLOW(T")={+,),#}FOLLOW(F)={(,a,b,^,+,),#}FOLLOW(F")={(,a,b,^,+,),#}FOLLOW(P)={*,(,a,b,^,+,),#}(2)考虑下列产生式:FIRST(+E)∩FIRST(ε)={+}∩{ε}=φFIRST(+E)∩FOLLOW(E")={+}∩{#,)}=φFIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φFIRST(T)∩FOLLOW(T")={(,a,b,^}∩{+,),#}=φFIRST(*F")∩FIRST(ε)={*}∩{ε}=φFIRST(*F")∩FOLLOW(F")={*}∩{(,a,b,^,+,),#}=φFIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(^)=φ所以,该文法式LL(1)文法.(3)+*()ab^#EE"TT"27 课后答案http://www.khdaw.comFF"P(4)procedureE;beginifsym="("orsym="a"orsym="b"orsym="^"thenbeginT;E"endelseerrorendprocedureE";beginifsym="+"thenbeginadvance;Eendelseifsym<>")"andsym<>"#"thenerrorendprocedureT;beginifsym="("orsym="a"orsym="b"orsym="^"thenbeginF;T"endelseerrorendprocedureT";beginifsym="("orsym="a"orsym="b"orsym="^"thenTelseifsym="*"thenerrorendprocedureF;beginifsym="("orsym="a"orsym="b"orsym="^"thenbeginP;F"endelseerrorendprocedureF";beginifsym="*"thenbeginadvance;F"endendprocedureP;beginifsym="a"orsym="b"orsym="^"thenadvanceelseifsym="("then27 课后答案http://www.khdaw.combeginadvance;E;ifsym=")"thenadvanceelseerrorendelseerrorend;P81–3/***************(1)是，满足三个条件。(2)不是，对于A不满足条件3。(3)不是，A、B均不满足条件3。(4)是，满足三个条件。***************/第五章P133–1短语:E+T*F,T*F,直接短语:T*F句柄:T*FP133–2文法：(1)最左推导:最右推导:(2)(((a,a),^,(a)),a)27 课后答案http://www.khdaw.com(((S,a),^,(a)),a)(((T,a),^,(a)),a)(((T,S),^,(a)),a)(((T),^,(a)),a)((S,^,(a)),a)((T,^,(a)),a)((T,S,(a)),a)((T,(a)),a)((T,(S)),a)((T,(T)),a)((T,S),a)((T),a)(S,a)(T,S)(T)S“移进-归约”过程：步骤栈输入串动作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)#进5#(((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)#归11#(((T),^,(a)),a)#进12#((S,^,(a)),a)#归13#((T,^,(a)),a)#归14#((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)#归27 课后答案http://www.khdaw.com26#((T),a)#进27#(S,a)#归28#(T,a)#归29#(T,a)#进30#(T,a)#进31#(T,S)#归32#(T)#归33#(T)#进34#S#归P133–3(1)FIRSTVT(S)={a,^,(}FIRSTVT(T)={,,a,^,(}LASTVT(S)={a,^,)}LASTVT(T)={,,a,^,)}(2)a^(),a>>^>>(<<<=<)>>,<<<>>是算符文法，并且是算符优先文法(3)优先函数a^(),f44244g55523（4）栈输入字符串动作#（a,(a,a)）#预备#(a,(a,a))#进#(a,(a,a))#进#(t,(a,a))#归27 课后答案http://www.khdaw.com#（t,(a,a)）#进#（t,（a,a））#进#（t,（a,a））#进#（t,（t,a））#归#（t,（t,a））#进#（t,（t,a））#进#（t,（t,s））#归#（t,（t））#归#（t,（t））#进#（t,s）#归#（t）#归#（t）#进#s#归successP134–5(1)0.1.2.3.4.5.6.7.8.9.10.11.(2)1987SAS11100a432ASd56确定化：SAab{0,2,5,7,10}{1,2,5,7,8,10}{2,3,5,7,10}{11}{6}{2,5,7,8,10}{11}{6}27 课后答案http://www.khdaw.com{1,2,5,7,8,10}{2,3,5,7,9,10}{2,3,5,7,10}{2,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,7,8,10}{2,3,5,7,9,10}{11}{6}{11}φφφφ{6}φφφφAS3:5:6:SAabSaASbSAbaA4:0:7:ASbaabba2:1:DFA构造LR(0)项目集规范族也可以用GO函数来计算得到。所得到的项目集规范族与上图中的项目集一样:={，，，，}GO(，a)={}=GO(，b)={}=GO(，S)={，，，，，}=27 课后答案http://www.khdaw.comGO(，A)={，，，，}=GO(，a)={}=GO(，b)={}=GO(，S)={，，，，}=GO(，A)={，，，，，}=GO(，a)={}=GO(，b)={}=GO(，S)={，，，，，}=GO(，A)={，，，，}=GO(，a)={}=GO(，b)={}=GO(，S)={，，，，}=GO(，A)={，，，，，}=GO(，a)={}=GO(，b)={}=GO(，S)={，，，，，}=GO(，A)={，，，，}=GO(，a)={}=GO(，b)={}=GO(，S)={，，，，}=GO(，A)={，，，，，}=项目集规范族为C={，，，，，，}(3)不是SLR文法状态3，6，7有移进归约冲突状态3：FOLLOW(S’)={#}不包含a,b状态6：FOLLOW(S)={#,a,b}包含a,b,；移进归约冲突无法消解状态7：FOLLOW(A)={a,b}包含a,b；移进归约冲突消解所以不是SLR文法。(4)构造例如LR(1)项目集规范族见下图：对于状态5，因为包含项目[]，所以遇到搜索符号a或b时，应该用归约。又因为状态5包含项目[]，所以遇到搜索符号a时，应该移进。因此存在“移进-归约”矛盾，所以这个文法不是LR(1)文法。27 课后答案http://www.khdaw.combbb8：1：5：AAASaaS3：SaS3：0：aaAaA6：9：4：SbSAbaaSbb7：2：10：SbAA5：27 课后答案http://www.khdaw.com第六章/********************第六章会有点难P164–5(1)EE1＋T{if(E1.type=int)and(T.type=int)thenE.type:=intelseE.type:=real}ET{E.type:=T.type}Tnum.num{T.type:=real}Tnum{T.type:=int}(2)P164–7SL1|L2{S.val:=L1.val+(L2.val/2)}SL{S.val:=L.val}LL1B{L.val:=2*L1.val+B.val;L.length:=L1.length+1}LB{L.val:=B.c;L.length:=1}B0{B.c:=0}B1{B.c:=1}***********************/第七章P217–1a*(-b+c)ab@c+*a+b*(c+d/e)abcde/+*+-a+b*(-c+d)a@bc@d+*+if(x+y)*z=0then(a+b)↑celsea↑b↑cxy+z*0=ab+c↑abc↑↑￥或xy+z*0=P1jezab+c↑P2jumpabc↑↑P1P227 课后答案http://www.khdaw.comP217–3-(a+b)*(c+d)-(a+b+c)的三元式序列:(1)+,a,b(2)@,(1),-(3)+,c,d(4)*,(2),(3)(5)+,a,b(6)+,(5),c(7)-,(4),(6)间接三元式序列:三元式表：(1)+,a,b(2)@,(1),-(3)+,c,d(4)*,(2),(3)(5)+,(1),c(6)-,(4),(5)间接码表：(1)(2)(3)(4)(1)(5)(6)四元式序列:(1)+,a,b,(2)@,,-,(3)+,c,d,(4)*,,,(5)+,a,b,(6)+,,c,(7)-,,,P218–4自下而上分析过程中把赋值句翻译成四元式的步骤:A:=B*(-C+D)步骤输入串栈PLACE四元式(1)A:=B*(-C+D)(2):=B*(-C+D)iA(3)B*(-C+D)i:=A-(4)*(-C+D)i:=iA-B(5)*(-C+D)i:=EA-B27 课后答案http://www.khdaw.com(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---C(@,C,-,)(12)+D)i:=E*(EA-B--(13)D)i:=E*(E+A-B---(14))i:=E*(E+iA-B---D(15))i:=E*(E+EA-B---D(+,,D,)(16))i:=E(EA-B--(17)i:=E*(E)A-B---(18)i:=E+EA-B-(*,B,,)(19)i:=EA-(:=,,-,A)(20)A产生的四元式：(@,C,-,)(+,,D,)(*,B,,)(:=,,-,A)P218–5/****************设A：10*20，B、C、D：20，宽度为w＝4则T1:=i*20T1:=T1+jT2:=A–84T3:=4*T1Tn:=T2[T3]//这一步是多余的T4:=i+jT5:=B–4T6:=4*T4T7:=T5[T6]T8:=i*20T8:=T8+jT9:=A–84T10:=4*T8T11:=T9[T10]T12:=i+jT13:=D–4T14:=4*T12T15:=T13[T14]T16:=T11+T15T17:=C–427 课后答案http://www.khdaw.comT18:=4*T16T19:=T17[T18]T20:=T7+T19Tn:=T20******************/P218–6100.(jnz,A,-,0)101.(j,-,-,102)102.(jnz,B,-,104)103.(j,-,-,0)104.(jnz,C,-,103)105.(j,-,-,106)106.(jnz,D,-,104)--假链链首107.(j,-,-,100)--真链链首假链：{106,104，103}真链：{107,100}P218–7100.(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.(j,-,-100)P219–12/********************(1)MAXINT–5MAXINT–4MAXINT–3MAXINT–2MAXINT–1MAXINT27 课后答案http://www.khdaw.com(2)翻译模式方法1：forE1:=E2toE3doS{backpatch(S1.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.falselist:=makelist(nextquad);emit(‘j>,’E1.place‘,’E2.place‘,0’);emit(I.Place‘:=’E1.place);F.truelist:=makelist(nextquad);emit(‘j,-,-,-’);F.place:=I.place;F.end:=E2.place;}{p:=lookup(id.name);ifp<>nilthenI.place:=pelseerror}{M.quad:=nextquad}****************/方法2：S→forid:=E1toE2doS1S→FS1F→forid:=E1toE2dodo{INITIAL=NEWTEMP;emit(‘:=，’E1.PLACE’，-，’INITIAL);FINAL=NEWTEMP;emit(‘:=，’E2.PLACE’，-，’FINAL);p:=nextquad+2;emit(‘j£,’INITIAL‘,’FINAL’,’p);F.nextlist:=makelist(nextquad);27 课后答案http://www.khdaw.comemit(‘j,－,－,－’); F.place:=lookup(id.name);ifF.place¹nilthenemit(F.place‘:=’INITIAL) F.quad:=nextquad;F.final:=FINAL;}{backpatch(S1.nextlist,nextquad)p:=nextquad+2;emit(‘j¹,’F.place‘,’F.final’,’p);S.nextlist:=merge(F.nextlist,makelist(nextquad));emit(‘j,－,－,－’); emit(‘succ，’F.place’，-，’F.place);emit(‘j,－,－,’F.quad); }第九章P270–9(1)传名即当过程调用时，其作用相当于把被调用段的过程体抄到调用出现处，但必须将其中出现的任一形式参数都代之以相应的实在参数。A:=2;B:=3;A:=A+1;A:=A+(A+B);printA;∴A=9(2)传地址即当程序控制转入被调用段后，被调用段首先把实在参数抄进相应的形式参数的形式单元中，过程体对形参的任何引用或赋值都被处理成对形式单元的间接访问。当被调用段工作完毕返回时，形式单元（都是指示器）所指的实参单元就持有所希望的值。①A:=2;B:=3;T:=A+B②把T,A,A的地址抄进已知单元J1,J2,J3③x:＝J1;y:=J2;z:=J3//把实参地址抄进形式单元，且J2=J3④Y↑:=y↑+1Z↑:=z↑+x↑//Y↑：对y的间接访问Z↑：对z的间接访问⑤printAA=8(3)得结果27 课后答案http://www.khdaw.com每个形参均对应两个单元，第一个存放实参地址，第二个存放实参值，在过程体中对形参的任何引用或赋值都看成是对它的第二个单元的直接访问，但在过程工作完毕返回前必须把第二个单元的内容放到第一个单元所指的那个实参单元中①A:=2;B:=3;T:=A+B②把T,A,A的地址抄进已知单元J1,J2,J3③x1:=J1;x2:=T;y1:=J2;y2:=A;z1:=J3;z2:=A;//将实参的地址和值分别放进两个形式单元中④y2:=y2+1;z2:=z2+x2;//对形参第二个单元的直接访问⑤x1↑：＝x2;y1↑:=y2;z1↑:=z2//返回前把第二个单元的内容存放到第一个单元所指的实参地址中⑥printAA=7(4)传值即被调用段开始工作时，首先把实参的值写进相应的形参单元中，然后就好像使用局部变量一样使用这些形式单元A:=2;B:=3;x:=A+By:=Az:=Ay:=y+1z:=z+xprintAA=2过程调用不改变A的值第十章P306-127 课后答案http://www.khdaw.comP306-2readA,BB1F:=1C:=A*AD:=B*BB3B2ifC100goto27 课后答案http://www.khdaw.com---------------------------halt---------------------------:F:=F-1goto---------------------------基本块为、、、、P307-4I:=1readJ,KA:=K*IB:=J*IT:=K*100L:C:=A*BwriteCA:=A+KB:=B+JifA