编译原理课后答案

第二章P36-6(1)L(G1)是0~9组成的数字串(2)最左推导:NNDNDDNDDDDDDD0DDD01DD012D0127NNDDD3D34NNDNDDDDD5DD56D568最右推导:NNDN7ND7N27ND27N127D1270127NNDN4D434NNDN8ND8N68D68568P36-7G(S)1|3|5|7|9N2|4|6|8|OD0|NSO|AOAAD|NP36-8文法：E T|E T|E TF|T*F|T/FF(E)|i最左推导:EETTTFTiTiT*FiF*Fii*Fii*iETT*FF*Fi*Fi*(E)i*(ET)i*(TT)i*(FT)i*(iT)i*(iF)i*(ii)最右推导:EETET*FET*iEF*iEi*iTi*iFi*iii*iETF*TF*FF*(E)F*(ET)F*(EF)F*(Ei)F*(Ti)F*(Fi)F*(ii)i*(ii)语法树：/********************************EEEE+TE+TE-TE+TFTT*FE-TFTFiFFiTFiFiiiFiiii+i+ii-i-ii+i*i*****************/P36-9句子iiiei 有两个语法树：S iSeS iSei iiSei iiieiS iS iiSeS iiSei iiieiP36-10/**************TS|TT(S)|()***************/P36-11/***************L1:SACAaAb|abCcC|L2:SABAaA|BbBc|bcL3:ABAaAb|BaBb|L4:A|BA0A1|B1B0|A***************/第三章习题参考答案P64–7(1)1(01|)*101X Y01101X12345Y1确定化：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,}01023000110101564011 1最小化：{0,1,2,3,4,5},{6}{0,1,2,3,4,5}0{1,3,5}{0,1,2,3,4,5}1{12,,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{12,,4}{0,1},{2,3}{4},{5},{6}{0,1}0{1}{0,1}1{1,2}{2,3}0{3}{2,3}1{4}{0},{1},{2,3},{4},{5},{6}010 20 0 1 0011345011 1P64–8(1)(1|0)*01(2)(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*(0|5)|(0|5)(3)0*1(0|10*1)*|1*0(0|10*1)*P64–12(a)aa,b0 1a确定化：ab{0}{0,1}{1}{0,1}{0,1}{1}{1}{0}φφ φ φ给状态编号：ab012112203333aa01abbbb23a最小化：{0,1},{2,3}{0,1}a{1}{0,1}b{2}{2,3}a{0,3}{2,3}b{3}{0,1},{2},{3}aabb012ab(b)bba023abaa bba514aa已经确定化了,进行最小化最小化：{{0,1},{2,3,4,5}}{0,1}a{1}{0,1}b{2,4}{2,3,4,5}a{1,3,0,5}{2,3,4,5}b{2,3,4,5}{2,4}a{1,0}{2,4}b{3,5}{3,5}a{3,5}{3,5}b{2,4}{{0,1},{2,4},{3,5}}{0,1}a{1}{0,1}b{2,4}{2,4}a{1,0}{2,4}b{3,5}{3,5}a{3,5}{3,5}b{2,4}b b a0 1 2a baP64–1401010(2):X(|)*010Y201X 1 Y0确定化：0

1{X,1,Y}

{1,Y}

{2}{1,Y}{1,Y}{2}{2}{1,Y}φφφφ给状态编号：01012112213333000110111230最小化：{0,1},{2,3}{0,1}0{1}{0,1}1{2}{2,3}0{1,3}{2,3}1{3}{0,1},{2},{3}011101300第四章P81–1按照T,S的顺序消除左递归G(S)a|^|(T)TSTT,ST|递归子程序：procedureS;beginifsym='a'orsym='^'thenabvanceelseifsym='('thenbeginadvance;T;ifsym=')'thenadvance;elseerror;endelseerrorend;procedureT;beginS;Tend;procedure T;beginifsym=','thenbeginadvance;S;Tendend;其中:sym:是输入串指针 IP所指的符号advance:是把IP调至下一个输入符号error: 是出错诊察程序(2)FIRST(S)={a,^,(}FIRST(T)={a,^,(}FIRST(T)={,, }FOLLOW(S)={),,,#}FOLLOW(T)={)}FOLLOW(T)={)}预测分析表a ^ ( ) , #S S a S ^ S (T)T T ST T ST T STT T T ,ST是LL(1)文法P81–2文法：E TEE E|T FTT|FPFF *F|P (E)|a|b|^(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)考虑下列产生式 :E

E|T T|F *F|P (E)|^|a|bFIRST(+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)+

*

(

)

a

b

^

#E

E TE'

E TE'

E

TE'E

TE'E'

E

E

E

ET

T FT

T FT

T

FT

T

FTT'

T

T

T T

T

T T

T T

T TFF'P

F PF F PF F PF F PFF F *F F F F F F FP (E) P a P b 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='('thenbeginadvance;E;ifsym=')'thenadvanceelseerrorendelseerrorend;P81–3/***************是，满足三个条件。不是，对于A不满足条件3。不是，A、B均不满足条件3。是，满足三个条件。***************/第五章P133–1E E T E T*F短语:E+T*F,T*F,直接短语:T*F句柄:T*FP133–2文法：a|^|(T)TT,S|S(1)最左推导

:S (T) (T,S)S (T,S) (S,S)(((T,S),S,S)),S)(((a,a),^,S),S)

(S,S) (a,S) (a,(T)) (a,(T,S))((T),S) ((T,S),S) ((T,S,S),S)(((S,S),S,S),S) (((a,S),S,S),S)(((a,a),^,(T)),S) (((a,a),^,(S)),

S)

(a,(S,S)) (a,(a,S)) (a,(a,a))((S,S,S),S) (((T),S,S),S)(((a,a),S,S),S)(((a,a),^,(a)),S)(((a,a),^,(a)),a)最右推导

:SS

(T) (T,S) (T,(T)) (T,(T,S)) (T,(T,a)) (T,(S,a)) (T,(a,a))(S,(a,a)) (a,(a,a))(T,S) (T,a) (S,a) ((T),a) ((T,S),a) ((T,(T)),a) ((T,(S)),a)((T,(a)),a) ((T,S,(a)),a) ((T,^,(a)),a) ((S,^,(a)),a) (((T),^,(a)),a)(((T,S),^,(a)),a) (((T,a),^,(a)),a) (((S,a),^,(a)),a) (((a,a),^,(a)),a)(2)(((a,a),^,(a)),a)(((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)#归26#((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>>^>>(<<<=<)>>,<<<>>G6是算符文法，并且是算符优先文法优先函数a^(),f44244g55523fffffa^(),ggggga^(),4）栈输入字符串动作#（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））#归#（t,（t））#归#（t,（t））#进#（t,s）#归#（t）#归#（t）#进#s#归successP134–5(1)0.SS1.SS2.SAS3.SAS4.SAS5.Sb6.Sb7.ASA8.ASA9.ASA10.Aa11.Aa(2)1S AS789a01011AS234d5 6确定化：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}{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:SS5:ASA6:ASASASASSASAabSASSASbASAASASbAaAaASASASAaSbSaASbSAbaA0:SS4:SAS7:SASSAASSSASASASbSbSASASAbASASbAaAaASAAaaabba1:Aa2:SbDFA构造LR(0)项目集规范族也可以用GO函数来计算得到。所得到的项目集规范族与上图中的项目集一样:I0={S S，SGO(I0，a)={AGO(I0，b)={SGO(I0，S)={S

AS，S b，A SA，A a}}=I1}=I2S，A SA，A SA，A a，S AS，S b}=I3GO(I0，A)={SAS，SAS，Sb，ASA，Aa}=I4GO(I3，a)={Aa}=I1GO(I3，b)={Sb}=I2GO(I3，S)={ASA，SAS，Sb，ASA，Aa}=I5GO(I3，A)={ASA，SAS，SAS，Sb，ASA，Aa}=I6GO(I4，a)={Aa}=I1GO(I4，b)={Sb}=I2GO(I4，S)={SAS，ASA，SAS，Sb，ASA，Aa}=I7GO(I4，A)={SAS，SAS，Sb，ASA，Aa}=I4GO(I5，a)={Aa}=I1GO(I5，b)={Sb}=I2GO(I5，S)={ASA，SAS，Sb，ASA，Aa}=I5GO(I5，A)={ASA，SAS，SAS，Sb，ASA，Aa}=I6GO(I6，a)={Aa}=I1GO(I6，b)={Sb}=I2a}=I7GO(I6，S)={SAS，ASA，SAS，Sb，ASA，AGO(I6，A)={SAS，SAS，Sb，ASA，Aa}=I4GO(I7，a)={Aa}=I1GO(I7，b)={Sb}=I2GO(I7，S)={ASA，SAS，Sb，ASA，Aa}=I5GO(I7，A)={ASA，SAS，SAS，Sb，ASA，Aa}=I6项目集规范族为 C={I1，I2，I3，I4，I5，I6，I7}不是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 AS a/b]，所以遇到搜索符号 a或b时，应该用A AS归约。又因为状态 5包含项目[A a a/b]，所以遇到搜索符号 a时，应该移进。因此存在“移进-归约”矛盾，所以这个文法不是 LR(1)文法。bbb1：5：8：S S #A ASAa/bAASAa/bA a a/bSSAS a/bS b a/bSS a

ASAa/bSASa/bASASa/bSASa/bSASa/bSba/bSba/bASAa/bASAa/bAaa/baAaa/baS3：0： a a A3： aSS#AaAa/bSAS#/a/b6：Sb#/a/bSASAa/bASAba/b4：ASAa/bAaa/bSb#/a/bAaa/bSSASa/bSba/bAbaaSbb2：7：

9：SASa/bASAa/bASAa/bAaa/bSASa/bSba/bSAS#/a/bSAS#/a/bSb#/a/bbSASAa/bAaa/b

SAS#/a/bASAa/bASAa/b10：Aaa/bSba/bSASa/bSba/bAA5：第六章/******************** 第六章会有点难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/2L2.length)}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+*+A (C D) A CD(A B) ( C D) AB C@D(A B) (C D E) AB CD@Eif(x+y)*z=0then(a+b) ↑celsea ↑b↑c xy+z*0=ab+c↑abc↑↑￥或xy+z*0=P1jezab+c ↑P2jumpabc ↑↑P1 P2P217–3-(a+b)*(c+d)-(a+b+c) 的三元式序列:+,a,b@,(1),-+,c,d*,(2),(3)+,a,b+,(5),c-,(4),(6)间接三元式序列 :三元式表：+,a,b@,(1),-+,c,d*,(2),(3)+,(1),c-,(4),(5)间接码表：(1)(2)(3)(4)(1)(5)(6)四元式序列:(1)+,a,b,T1@,T1,-,T2(3)+,c,d,T3*,T2,T3,T4(5)+,a,b,T5+,T5,c,T6-,T4,T6,T7P218–4自下而上分析过程中把赋值句翻译成四元式的步骤步骤 输入串 栈 PLACE

:A:=B*(-C+D)四元式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-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---C(@,C,-,T)(12)+D)i:=E*(EA-B--T1(13)D)i:=E*(E+1A-B--T-(14))i:=E*(E+i1A-B--T-D(15))i:=E*(E+E1(+,T,D,T)A-B--T-D(16))i:=E(E112A-B--T(17)i:=E*(E)2A-B--T-(18)i:=E+E2(*,B,T,T)A-B-T(19)i:=E2(:=,23A-TT,-,A)33(20)A产生的四元式：(@,C,-, T)1(+,T,D,T)1 2(*,B, T,T)2 3(:=, T,-,A)3P218–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–4T18:=4*T16T19:=T17[T18]T20:=T7+T19Tn:=T20******************/P218–6(jnz,A,-,0)(j,-,-,102)(jnz,B,-,104)(j,-,-,0)(jnz,C,-,103)(j,-,-,106)106. (jnz,D,-,104)--107. (j,-,-,100) --假链：{106,104，103}真链：{107,100}

假链链首真链链首P218–7(j<,A,C,102)(j,-,-,0)(j<,B,D,104)(j,-,-,101)(j=,A,‘1’,106)(j,-,-,109)(+,C,‘1’,T1)(:=,T1,-,C)(j,-,-,100)(j≤,A,D,111)(j,-,-,100)(+,A,‘2’,T2)(:=,T2,-,A)(j,-,-,109)(j,-,-100)P219–12/********************(1)MAXINT–5MAXINT–4MAXINT–3MAXINT–2MAXINT–1MAXINT翻译模式方法1：forE1:=E2toE3doSSFdoMS1FForI:E1toE2IidMSFdoMS1{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;}FForI:E1toE2{F.falselist:=makelist(nextquad);emit(‘j>,’E1.place‘,’E2.place‘,0’);emit(I.Place‘:=’E1.place);idM

F.truelist:=makelist(nextquad);emit(‘j,-,-,- ’);F.place:=I.place;F.end:=E2.place;}{p:=lookup();ifp<>nilthenI.place:=pelseerror}{M.quad:=nextquad}****************/方法2：S→forid:=E1toE2doS1S→FS1F→forid:=E1toE2doF forid: E1toE2do{INITIAL=NEWTEMP;emit(‘:=，’E1.PLACE’，-，’INITIAL);FINAL=NEWTEMP;emit(‘:=，’E2.PLACE’，-，’FINAL);p:=nextquad+2;emit(‘j ,’INITIAL ‘,’FINAL ’,’p);F.nextlist:=makelist(nextquad);emit(‘j,－,－,－’);F.place:=lookup();ifF.place

nilthenemit(F.place

‘:=’

INITI

AL)F.quad:=nextquad;F.final:=FINAL;}S FS1{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.placeemit(‘j,－,－,’F.quad);

’，

-

，’

F.place);}第九章P270–9传名即当过程调用时，其作用相当于把被调用段的过程体抄到调用出现处，但必须将其中出现的任一形式参数都代之以相应的实在参数。A:=2;B:=3;A:=A+1;A:=A+(A+B);printA;A=9传地址即当程序控制转入被调用段后，被调用段首先把实在参数抄进相应的形