編譯原理課后題答案第二章P36-6(1)L(G1)是0~9構成的數(shù)字串(2)最左推導:NNDNDDNDDDDDDD0DDD01DD012D0127NNDDD3D34NNDNDDDDD5DD56D568最右推導:NNDN7ND7N27ND27N127D1270127NNDN4D434NNDN8ND8N68D68568P36-7G(S)1|3|5|7|9N2|4|6|8|OD0|NSO|AOAAD|NP36-8文法：ET|ET|ETF|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)語法樹：/********************************EE+TE+TFTFiFiii+i+i*****************/P36-9句子iiiei有兩個語法樹：SiSeSiSeiiiSeiiiieiSiSiiSeSiiSeiiiiei

EEE+TE-TTT*FE-TFFFiTFiiiFiii-i-ii+i*iP36-10/**************TS|TT(S)|()***************/P36-11/***************L1:SACAaAb|abCcC|L2:SABAaA|BbBc|bcL3:ABAaAb|BaBb|L4:SA|B0A1|B1B0|A***************/第三章習題參照答案P64–7(1)1(01|)*101XY01101X12345Y1確立化：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,}012030001101014560111最小化：{0,1,2,3,4,5},{6}{0,1,2,3,4,5}0{1,3,5}{0,1,2,3,4,5}1{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{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}001200101304150111P64–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,b01a確立化：{0}{0,1}{1}φ給狀態(tài)編號：0123aa0ab2最小化：{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}ab0a(b)b0aa

ab{0,1}{1}{0,1}{1}{0}φφφab121203331bb3aab12bba23bab1b4aa5a已經確立化了,進行最小化最小化：{{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}bba012abaP64–14(1)01010(2):X(010|)*Y201X1Y0確立化：0{X,1,Y}{1,Y}{1,Y}{1,Y}{2}{1,Y}φφ給狀態(tài)編號：00111213300110121最小化：{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}011001第四章P81–1依據(jù)T,S的次序除去左遞歸G(S)Sa|^|(T)TSTT,ST|

1{2}{2}φφ122330130130遞歸子程序：procedureS;beginifsym='a'orsym='^'thenabvanceelseifsym='('thenbeginadvance;T;ifsym=')'thenadvance;elseerror;endelseerrorend;procedureT;beginS;Tend;procedureT;beginifsym=','thenbeginadvance;S;Tendend;此中:sym:是輸入串指針I(yè)P所指的符號advance:是把IP調至下一個輸入符號error:是犯錯診察程序(2)FIRST(S)={a,^,(}FIRST(T)={a,^,(}FIRST(T)={,,}FOLLOW(S)={),,,#}FOLLOW(T)={)}FOLLOW(T)={)}展望剖析表a^(),#SSaS^S(T)TTSTTSTTSTTTT,ST是LL(1)文法P81–2文法：ETEEE|TFTT|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)考慮以下產生式:EE|TT|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

ETE'

ETE'E

TE'E

TE'E'

E

E

E

ET

TFT

TFT

T

FT

T

FTT'FF'P

TTTTTTTTTTTFPFFPFFPFFPFFF*FFFFFFFP(E)PaPbP^(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–1EETET*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是算符文法，而且是算符優(yōu)先文法(3)優(yōu)先函數(shù)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)17S8A9S10a0112A3S4d56確立化：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:ASASASASASaASASbSASSASAASASbbaAaASAASASAaSbSaASbSAbaA0:SS4:SAS7:SASSASSASSASASbAbSASSASAASAbSbAaAaASAAaaabba1:Aa2:SbDFA結構LR(0)項目集規(guī)范族也能夠用GO函數(shù)來計算獲得。所獲得的項目集規(guī)范族與上圖中的項目集同樣:I0={SS，SAS，Sb，ASA，Aa}GO(I0，a)={Aa}=I1GO(I0，b)={Sb}=I2GO(I0，S)={SS，ASA，ASA，Aa，SAS，Sb}=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}=I5a}=I6GO(I5，A)={ASA，SAS，SAS，Sb，ASA，AGO(I6，a)={Aa}=I1GO(I6，b)={Sb}=I2AS，Sb，Aa}=I7GO(I6，S)={SAS，ASA，SSA，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項目集規(guī)范族為C={I1，I2，I3，I4，I5，I6，I7}(3)不是SLR文法狀態(tài)3，6，7有移進歸約矛盾狀態(tài)3：FOLLOW(S’)={#}不包括a,b狀態(tài)6：FOLLOW(S)={#,a,b}包括a,b,；移進歸約矛盾沒法消解狀態(tài)7：FOLLOW(A)={a,b}包括a,b；移進歸約矛盾消解所以不是SLR文法。(4)結構比如

LR(1)項目集規(guī)范族見以下圖：關于狀態(tài)5，由于包括項目[AASa/b]，所以碰到搜尋符號a或歸約。又由于狀態(tài)5包括項目[Aaa/b]，所以碰到搜尋符號存在“移進-歸約”矛盾，所以這個文法不是LR(1)文法。

b時，應當用AASa時，應當移進。所以bbb1：5：8：SS#AASAa/bASAa/bAAaa/bSASa/bSSba/bSSa0：a3：

ASAa/bSASa/bSASa/bSASa/bSASa/bASba/bSba/bASAa/bASAa/bAaa/bAaa/baaS3：aAaSS#SAS#/a/bSb#/a/bASAa/bAaa/bA2：

Aaa/bA6：9：SASa/bASAa/bSSAa/bb4：ASAa/bAASAa/bSb#/a/bAaa/bAaa/bSASa/bSSASa/bbSba/bSba/baaSbb7：SAS#/a/bSAS#/a/bSb#/a/bSASAa/bAaa/bA

SAS#/a/bASAa/bASAa/bAaa/bASa/bSba/b

b10：Sba/bA5：第六章/********************第六章會有點難P164–5(1)EE1＋T{if=int)and=int)then:=intelse:=real}ET{:=}{:=real}Tnum{:=int}(2)P164–7SL1|L2{:=+2L2.length)}SL{:=}LL1B{:=2*+;:=+1}LB{:=;:=1}B0{:=0}B1{:=1}***********************/第七章P217–1a*(-b+c)ab@c+*a+b*(c+d/e)abcde/+*+-a+b*(-c+d)a@bc@d+*+A(CD)ACD(AB)(CD)ABC@D(AB)(CDE)ABCD@Eif(x+y)*z=0then(a+b)↑celsea↑b↑cxy+z*0=ab+c↑abc↑↑￥或xy+z*0=P1jezab+c↑P2jumpabc↑↑P1P2P217–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)四元式序列:+,a,b,T1@,T1,-,T2+,c,d,T3*,T2,T3,T4+,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--T1i:=E*(E+A-B--T1(13)D)-1(14))i:=E*(E+iA-B--T-D(15))1(+,T,D,T)i:=E*(E+EA-B--T-D112(16))i:=E(EA-B--T(17)i:=E*(E)A-B--T2-(18)i:=E+E2(*,B,T,T)A-B-TA-T2(:=,T23(19)i:=E,-,A)3(20)3A產生的四元式：(@,C,-,T1)(+,T1,D,T2)(*,B,T2,T3)(:=,T3,-,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–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)(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(2)翻譯模式方法1：forE1:=E2toE3doSSFdoMS1FForI:E1toE2idMSFdoMS1{backpatch,nextquad);backpatch,;emit‘:=’‘+’1);emit(‘j,’‘,’‘,’;:=;}FForI:E1toE2{:=makelist(nextquad);emit(‘j>,’‘,’‘,0’);emit‘:=’;idM

:=makelist(nextquad);emit(‘j,-,-,-’);:=;:=;}{p:=lookup;ifp<>nilthen:=pelseerror}{:=nextquad}****************/方法2：S→forid:=E1toE2doS1S→FS1F→forid:=E1toE2doFforid:E1toE2do{INITIAL=NEWTEMP;emit(‘:=，’’，-，’INITIAL);FINAL=NEWTEMP;emit(‘:=，’’，-，’FINAL);p:=nextquad+2;emit(‘j,’INITIAL‘,’FINAL’,’p);:=makelist(nextquad);emit(‘j,－,－,－’);:=lookup;ifnilthenemit‘:=’INITIAL):=nextquad;:=FINAL;}SFS1{backpatch,nextquad)p:=nextquad+2;emit(‘j,’‘,’’,’p);:=merge,makelist(nextquad));emit(‘j,－,－,－’);emit(‘succ，’’，-，’;emit(‘j,－,－,’;}第九章P270–9傳名即當過程調用時，其作用相當于把被調用段的過程體抄到調用出現(xiàn)處，但一定將此中出現(xiàn)的任一形式參數(shù)都代之以相應的實在參數(shù)。A:=2;B:=3;A:=A+1;A:=A+(A+B);printA;A=9傳地點即當程序控制轉入被調用段后，被調用段第一把實在參數(shù)抄進相應的形式參數(shù)的形式單元中，過程體對形參的任何引用或賦值都被辦理成對形式單元的間接接見。當被調用段工作完畢返回時，形式單元（都是指示器）所指的實參單元就擁有所希望的值。①A:=2;B:=3;T:=A+B②把T,A,A的地點抄進已知單元J1,J2,J3③x:＝J1;y:=J2;z: