编译原理第三版课后习题

目录P36-6.......................................................................................................错误!不决义书签。P36-7.......................................................................................................错误!不决义书签。P36-8.......................................................................................................错误!不决义书签。P36-9.......................................................................................................错误!不决义书签。P36-10.....................................................................................................错误!不决义书签。P36-11.....................................................................................................错误!不决义书签。P64–7......................................................................................................错误!不决义书签。P64–8......................................................................................................错误!不决义书签。P64–12....................................................................................................错误!不决义书签。P64–14....................................................................................................错误!不决义书签。P81–1......................................................................................................错误!不决义书签。P81–2......................................................................................................错误!不决义书签。P81–3......................................................................................................错误!不决义书签。P133–1....................................................................................................错误!不决义书签。P133–2....................................................................................................错误!不决义书签。P133–3....................................................................................................错误!不决义书签。P134–5....................................................................................................错误!不决义书签。P164–5....................................................................................................错误!不决义书签。P164–7....................................................................................................错误!不决义书签。P217–1....................................................................................................错误!不决义书签。P217–3....................................................................................................错误!不决义书签。P218–4....................................................................................................错误!不决义书签。P218–5....................................................................................................错误!不决义书签。P218–6....................................................................................................错误!不决义书签。P218–7....................................................................................................错误!不决义书签。P219–12..................................................................................................错误!不决义书签。P270–9....................................................................................................错误!不决义书签。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文法：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)语法树：/********************************EEEE+TE+TE-TE+TFTT*FE-TFTFiFFiTFiFiiiFiiii+i+ii-i-ii+i*i*****************/P36-9句子iiiei有两个语法树：SiSeSiSeiiiSeiiiieiSiSiiSeSiiSeiiiieiP36-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|)*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,}001032001101051460111最小化：{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}010200101041350111P64–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确立化：ab{0}{0,1}{1}{0,1}{0,1}{1}{1}{0}φφ给状态编号：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

φφab121203331bb3aab12bba23ba

ab1

ba45a已经确立化了,进行最小化最小化：{{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–14(1)01010(2):X(010*Y|)201X1Y0确立化：{X,1,Y}

0{1,Y}

1{2}{1,Y}{1,Y}{2}{1,Y}φφ给状态编号：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依据T,S的次序除去左递归G(S)a|^|(T)TSTT,ST|递归子程序：procedureS;beginifsym='a'orsym='^'thenabvanceelseifsym='('

{2}φφ122330130130thenbeginadvance;T;ifsym=')'thenadvance;elseerror;endelseerrorend;procedureT;beginS;Tend;procedureT;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^(),#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)+*()ab^#EETE'ETE'ETE'ETE'E'EEEETTFTTFTTFTTFTT'TTTTTTTTTTTFF'P

FPFFPFFPFFPFFF*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是算符文法，而且是算符优先文法(3)优先函数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)17S8AS910a1102A3S4d56确立化：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:ASASASASASaASASbSASSbASAASASbAaAaASASASAaSbSaASbSAbaA0:SS4:SAS7:SASSASSASSASASbAbSASSASAASAbSbAaAaASAAaaabba1:Aa2:SbDFA结构LR(0)项目集规范族也能够用GO函数来计算获得。所获得的项目集规范族与上图中的项目集同样: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，GO(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，GO(I6，a)={Aa}=I1GO(I6，b)={Sb}=I2GO(I6，S)={SAS，ASA，SAS，Sb，ASA，GO(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，项目集规范族为C={I1，I2，I3，I4，I5，I6，I7}

a}=I7Aa}=I6Aa}=I7Aa}=I6(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，由于包括项目[AASa/b]，所以碰到搜寻符号a或b时，应当用AAS归约。又由于状态5包括项目[Aaa/b]，所以碰到搜寻符号a时，应当移进。所以存在“移进-归约”矛盾，所以这个文法不是LR(1)文法。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/bSba/bbSba/baaSbb7：SAS#/a/bSAS#/a/bSb#/a/bSASAa/bAaa/bA

SAS#/a/bASAa/bASAa/bAaa/bSASa/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--T1(13)D)1i:=E*(E+A-B--T-(14))1i:=E*(E+iA-B--T-D1(+,T,D,T)(15))i:=E*(E+EA-B--T-D(16))i:=E(E112A-B--T(17)i:=E*(E)2A-B--T-2(*,B,T,T)(18)i:=E+EA-B-T(19)i:=EA-T223(:=,T,-,A)3(20)3A产生的四元式：(@,C,-,T)1(+,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,-,-,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,－,－,－’)