编译原理第三版课后习题解答.

1、第二章习题解答P36-6 L(Gi)是组成的数字串最左推导：NNDNDDNDDDDDDD0DDD01DD012D0127NNDDD3D 34NNDNDDDDD5DD56D568最右推导:NNDN7ND 7N27ND 27N127D1270127NNDN4D4 34NNDN8ND 8N68D68568P36-7G(S)O 1|3|5|7|9N 2|4|6|8|0D 0|NS 0|A0A AD |NP36-8文法：ET E T|E TTF T* F|T/ FF (E)|i最左推导:E E T TT FT iTi T* Fi F* F ii* Fi i*iE TT* FF * Fi * Fi*(E)

2、 i*( ET)i*( TT) i*( F T)i*( iT) i*(i F)i *( i i)最右推导E ET ET* FE T*iEF*i Ei*iT i *i F i*i i i*E TF*TF * FF*( E)F*( E T)F*( EF)F*( E i)F*( Ti)F*( F i)F*( ii)i*(i i)/*EETii+i+ii-i-iii+i*i*/P36-9句子iiiei有两个语法树：S iSeS iSei iiSei iiieiS iS iiSeS iiSei iiieiP36-10/*S TS |TT (S)|()*/P36-11/*L1:S ACA aAb | ab

3、 C cC |L2:S ABA aA|B bBc|bcL3:S ABA aAb|B aBb|L4:S A| BA 0A1|B 1B0| A*/第三章习题参考答案P64 - 701(01)*1017n确定化:01X01,2,30001,2,32,32,3,42,32,32,3,42,3,42,3,52,3,42,3,52,32,3,4,Y2,3,4,Y2,3,52,3,4,最小化:0,1,2,3,4,5,60,123,4,5。1,3,50,1,2,3,4,511,2,40,1,2,3,4, 5,60,1,2,34。1,3,50,1,23,4, 5,60,1,23。1,30,1,2,3 11,2,

4、40,1,2,04, $,60,1 0 1 0,1 1 1,22,30 B 门匡40,1,2,3, 4, 5, 60P64 8(1|0)*01 (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*(0|5)|(0|5)0 1(0|10 1) |1 0(0 |10 1)P64 - 12ab00,110,10,11100000给状态编号:ab012112203333最小化：0,1, 2,30,1 a 1 0,1b 2 2,3a 0,32,3b 30,1, 2, 3已经确定化了，进行最小化最小化:0,1, 2,3,4,50,1a 10,1b 2,42,3,4,5爲1,3

5、,0,52,3,4,5b 2,3,4,52,4a 1,02,4b 3,53,5a 3,53,5b 2,40,1, 2,4, 3,50,1a2,4a3,5a11,03,50,叽2,42,4b3,5b3,52,4:001X,1,Y1,Y2确定化:1，Y1，Y221，Y0000给状态编号:01012112213333最小化：0,1，2,30,10 1 0,11 22,3o 1,32,3i 30,1,2,3P81 - 1(1) 按照T,S的顺序消除左递归G(S)S aF|(T)T STT ,ST |递归子程序：procedure S;beginif sym=a or sym=人the n abva n

6、eeelse if sym=(the n begi nadvance;T;if sym=) the n adva nee; else error;endelse erroren d;procedure T;beginS;Ten d;procedure T ;beginif sym=,the n begi nadvanee;S;Tenden d;其中：sym:是输入串指针IP所指的符号advanee:是把IP调至下一个输入符号 error:是出错诊察程序FIRST(S)=a,(FIRST(T)=af,(FIRST(T )=,FOLLOW(S)=),#FOLLOW(T)=)FOLLOWT )=)预

7、测分析表aA()J#SS aS AS (T)Tr T STr T STT STTTT ,ST是LL(1)文法P81 - 2文法:E TEEE|TFTTT |FPFF*F|P (E)|a|b$(1)FIRST(E)=(,a,bfFIRST(E)=+, FIRST(T)=(,a,bFIRST(T)=(,a,b,A, FIRST(F)=(,a,b,AFIRST(F)=*, FIRST(P)=(,a,bfFOLLOW(E)=#,)FOLLOW(E)=#,)FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=(,a,b,A,+,),#FOLLOW(F)=(,a,b,A,+,)

8、,#FOLLOW(P)=*,(,a,bf,+,),#考虑下列产生式：E E|TT|F*F |P(E)|A|a|bFIRST(+E) A FIRST( )=+ n = $FIRST(+E) A FOLLOW(E)=+ A #,)=$FIRST(T) A FIRST( )=(,a,b,AA = $FIRST(T) A FOLLOW(T)=(,a,b,A A +,),#=$FIRST(*F) A FIRST( )=* A = $FIRST(*F) A FOLLOW(F)=* A (,a,b,A,+,),#=$FIRST(E) A FIRST(a) A FIRST(b) A FIRST(A)= $ 所

9、以,该文法式LL(1)文法.+*()abA#EE TEE TEE TEE TEEEEEETT FTT FTT FTT FTTTT TTT TT TTTTFFPFFPFFPFF PFFFF *FFFFFFF :PP(E)PaPbP Aprocedure E;beginif sym=( or sym=a or sym=b or sym=人 the n beg in T; E end else errorendprocedure E：beginif sym=+the n beg in adva nee; E endelse if sym) and sym# then error endprocedu

10、re T;beginif sym=( or sym=a or sym=b or sym=人 the n beg in F; T end else errorendprocedure T;beginif sym=( or sym=a or sym=b or sym=人 the n Telse if sym=* then errorendprocedure F;beginif sym=( or sym=a or sym=b or sym=人 the n beg in P; F end else errorendprocedure F;beginif sym=*the n beg in adva n

11、ee; F endendprocedure P;beginif sym=a or sym=b or sym=Athe n adva neeelse if sym=( the nbeginadvanee; E;if sym=) the n adva nee else error end else erroren d;P81 3/*(1) 是，满足三个条件。(2) 不是，对于A不满足条件3。(3) 不是，A、B均不满足条件3。(4) 是，满足三个条件。*/第五章P133- 1E E T E T* F短语：E+T*F, T*F,直接短语：T*F 句柄:T*FP133-2文法:(1)最左推导:(a,(

12、S,S)(a,(a, S)(a,(a,a)(S,S,S),S)(T),S,S),S)(a,a),S,S),S)(a,a)T ,(a),S)S (T)(T,S)(S,S)(a,S)(a,(T)(a,(T,S)S (T,S)(S,S)(T),S)(T,S),S)(T,S,S),S)(T,S),S, S), S) ( S,S), S,S), S) (a,S),S,S),S)(a,a)T ,S),S)(a,a)T,(T), S) (a,a),A ,( S), S)(a,a)T ,(a), a)最右推导:S(T)(T,S)(T,(T)(T,(T,S)(T,(T,a)(T,(S,a)(T,(a,a)(S,

13、(a,a)(a,(a,a)S(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)(a,a),A,(a),a)(S0,(a),a)(T, a),A,(a),a) (LSV，(a),a)(TL，A，(a),a)(S，A，(a)，a) (T,A,(a),a)(TS，(a),a)(T,( a),a)(T,( S),a

14、)(T,( T),a)(TS),a)(IL，a)(S，a)(TS)(T)_S“移进-归约”过程:步骤栈输入串动作0#(a,a),A,(a),a)#预备1#(a,a),A,(a),a)#进2#(a,a),A,(a),a)#进3#(a,a),A, (a),a)#进4#(a,a),A,(a),a)#进5#(S,a),A,(a),a)#归6#(T,a),A,(a),a)#归7#(T，a),A,(a),a)#进8#(T，a),A,(a),a)#进9#(T，S),A,(a),a)#归10#(T),A,(a),a)#归11#(T),A,(a),a)#进12#(S,A,(a),a)#归13#(T,A,(a),

15、a)#归14#(T，A,(a),a)#进15#(T，a,(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】,( LA

16、STVT(S)=a,) LASTVT(T)=,a】,) aA()5aA(=5G6是算符文法，并且是算符优先文法(3)优先函数aA()5f44244g55523(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#归su

17、ccessP134-5(1)0.SS1.SS2. SAS3.SA S4.SAS 5.Sb6. Sb7.ASA8.AS A9.ASA10.A a11.Aa确定化:SAab0,2,5,7,101,2,5,7,8,102,3,5,7,101161,2,5,7,8,102,5,7,8,102,3,5,7,9,10112,3,5,7,102,4,5,7,8,102,3,5,7,101162,5,7,8,102,5,7,8,102,3,5,7,9,101162,3,5,7,9,102,4,5,7,8,102,3,5,7,101162,4,5,7,8,102,5,7,8,102,3,5,7,9,101161

18、1000060000SAAsAssbAAA7sAsSAAsbSAaAsSASAaSasssSAAsbi aAsbSAa1DFAGO函数来计算得到。所得到的项目集规范族与上图中的AS, Sb= 13项目集样：10 = ss，sAS， S b， ASA，A aGO(I o，a)= Aa = IiGO(I o，b)= Sb = 12GO(I o，S)= SS，A S A，ASA，A a，S构造LR(O)项目集规范族也可以用G0（| 0，A）=SA S，SAS，Sb，ASA，Aa = 14GO（13，a）=Aa=I1G0（| 3，b）=Sb=I 2GO（13，S）=AS A，SAS，Sb，ASA，Aa

19、= I5G0（| 3，A）=ASA，SA S，SAS，Sb，ASA，Aa = I 6G0（| 4，a）=Aa=I1G0（| 4，b）=Sb=I 2G0（| 4，S）=SAS，AS A，SAS，Sb，ASA，Aa = I7G0（I 4，A）=SA S，SAS，Sb，ASA，Aa = 14G0（15，a）=Aa=I1G0（15，b）=Sb=I 2G0（I 5，S）=AS A，SAS，Sb，ASA，Aa = 15G0（l5，A）=ASA，SA S，SAS，Sb，ASA，Aa = I 6G0（16，a）=Aa=I1G0（16，b）=Sb=I 2G0（I 6，S）=SAS，AS A，SAS，Sb，ASA

20、，Aa = 17GOg，A）=SA S，SAS，Sb，ASA，Aa = 14G0（17，a）=Aa=I1G0（17，b）=Sb=I 2G0（I 7，S）=AS A，SAS，Sb，ASA，Aa = 15G0（l7，A）=ASA，SA S，SAS，Sb，ASA，Aa = I 6项目集规范族为C= 11， I2， II 3， I 4，I5，I 6， I 7不是SLR文法状态3, 6, 7有移进归约冲突状态 3: FOLLOW)=#不包含 a,b状态6: FOLLOW(S)=#,a,b包含a,b,;移进归约冲突无法消解状态7： FOLLOW(A)=a,b包含a,b ;移进归约冲突消解所以不是SLR文法

21、。(4)构造例如LR(1)项目集规范族见下图：对于状态5，因为包含项目A AS a/b，所以遇到搜索符号a或b时，应该用A AS 归约。又因为状态 5包含项目A a a/b，所以遇到搜索符号 a时，应该移进。因此 存在“移进-归约”矛盾，所以这个文法不是LR(1)文法。5:ASAa/bSA Sa/bSASa/bSba/bASAa/bAaa/b8:SA Sa/bSASa/bSba/bASAa/bAaa/b0：aSS#SAS#/a/bSb#/a/bASAba/bAaa/b4:S b #/a/b6:AS Aa/bASAa/bAaa/bSASa/bSba/b -9:SASa/bAS Aa/bASAa/

22、bAaa/bSASa/bSba/b2:7:SA S#/a/bSAS#/a/bSAS#/a/bAS Aa/bS#/a/bbASAa/bASAa/bAaa/bAaa/bSASa/bSba/bA/*第六章会有点难第六章P164 5(1)E E1 + T if (El.type = in t) a nd (type = int ) then E.type := int else E.type := realETE.type:=T.typeTnum.num T.type := realTnum T.type := intP164-7SL1|L2S.val:=L1.val+(L2.val/2L2.leng

23、th SLS.val:=L.valLL1BL.val:=2*L1.val + B.val;L.le ngth:=L1.le ngth+1LBL.val:=B.c;L.le ngth :=1B0B.c:=0B1B.c:=1*/第七章P217- 1a*(-b+c) a+b*(c+d/e) -a+b*(-c+d)abc+* abcde/+*+ abcd+*+A(C D)ACD(AB) ( C D)ABCD(AB) (CD E)ABCDEif (x+y)*z =0 then (a+b)f c else af b f c xy+z*0= ab+c f abc ff 或 xy+z*O= P1 jez ab

24、+cf P2 jump abc ffP1 P2P217- 3-(a+b)*(c+d)-(a+b+c) 的 三元式序列：(1) +, a, b , (1),- +, c, d(4) *, (2), (3) +, a, b(6) +, (5), c(7) -, (4), (6)间接三元式序列：(1) +, a, b , (1),- +, c, d(4) *, (2), (3)(5) +, (1), c(6) -, (4), (5)间接码表：(1)(1)四元式序列：(1) +, a, b,T1 , T1, -,T2 +, c, d,T3*, T2, T3, T4 +, a, b,T5 +, T5,

25、c,T6-,T4, T6, T7P218-4自下而上分析过程中把赋值句翻译成四兀式的步骤:A:=B*(-C+D)步骤输入串栈PLACE四兀式(1)A:=B*(-C+D):=B*(-C+D)iAB*(-C+D)i:=A-*(-C+D)i:=iA-B*(-C+D)i:=EA-B*(-C+D)i:=E(-C+D)i:=E*(8)-C+D)i:=E*(9)C+D)i:=E*(-(10)+D)i:=E*(-i(11)+D)i:=E*(-E(12)+D)i:=E*(E(13)D)i:=E*(E+(14)i:=E*(E+iA-BA-B-A-B-A-B-A-BCA-BC(15)(16)(17)(18)(19)

26、=E*(E+E =E(E =E*(E) =E+ET1T -1T -D1T -D1T2T -2A-B-A-B-A-B-A-B-A-B-A-B-=EA-B- T2A-T3(20) A(,C,-, T1)(+, T1 ,D,T2)(*,B, T ,2(:=,T ,-,A)3T3)产生的四元式：(,C,-, T )1 (+, T1,D, T2) (*,B, T , T ) 23(:=，T3,-,A)P218-5/*设 A : 10*20 , B、C、 D: 20,宽度为w = 4T1:= i * 20T1:=T1+jT2:=A -84T3:=4*T1Tn:=T2T3这T4:= i + jT5:=B 步

27、是多余的T6:=4*T4T7:=T5T6T8:= i * 20T8:=T8+jT9:=A -84T10:=4*T8T11:=T9T10T12:= i + jT13:=D -T14:=4*T12T15:= T13T14T16:=T11+T15T17:=C T18:=4*T16T19:=T17T18T20:=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.

28、 (jnz, D, -, 104)-107. (j, -, -, 100)- 假链：106,104 , 103 真链：107,100P218-7100.(j, A, C, 102)101.(j, -, -, 0)102.(j, El.place , E2.place ,0 ); emit(I.Place := El.place);F.truelist := makelist (n extquad); emit( j,-,-,-);F.place := I.place;F.e nd := E2.place;I idp:=lookup(id. name);if p nil the nI.place

29、 := pelse errorMM.quad := nextquad*/方法2:St for id:=E1 to E2 do S1St F S1Ft for id:=E1 to E2 doF forid : EltoE 2doINITIAL=NEWTEMP;emit( :=， E1.PLACE，-， INITIAL); FINAL=NEWTEMP;emit( :=， E2.PLACE，-， FINAL); p:= n extquad+2;p);emit( j , INITIAL , FINAL F.n extlist:=makelist (n extquad);emit( j,);F.plac

30、e:=lookup(id. name);if F.placenil the nemit(F.place := INITIAL)F.quad:=n extquad;F.fi nal:=FINAL;S FS1backpatch(S1. nextlist, n extquad)p:=n extquad+2;emit( j , F.place , F.final , p );S.n extlist := merge(F. nextlist, makelist (n extquad); 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); print A; A=9传地址即当程序控制转入被调用段后，被调用段首先把实在参数抄进相应的形式参数的形式单元中，