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

1、目录P36-6 2P36-7 2P36-8 2P36-9 3P36-10 3P36-11 3P64 - 74P64 - 85P64 - 125P64 - 147P81 - 18P81 - 29P81 - 312P133- 112P133-212P133 - 314P134 - 515P164 - 519P164 - 719P217 - 119P217 - 320P218 - 420P218 - 521P218 - 622P218 - 722P219 - 1222P270 924P36-6(1)L(G)是o9组成的数字串(2) 最左推导 :NNDNDDNDDD DDDD0DDD01DD012D

2、0127NNDDD3D 34NNDNDDDDD 5DD56D568最右推导 :NNDN7ND7 N27ND27N127D1270127NNDN4D4 34NNDN8ND8 N68D68568P36-7G(S)O 1|3|5|7|9N 2|4|6|8|OD 0|NS O|AOA AD|NP36-8文法：E T|E T|E TTF|T*F|T/ FF(E)|i最左推导 :EET T T FTiTi T* Fi F* F ii* F i i *iETT*FF*Fi*Fi *(E) i*( ET)i*( TT) i*( F T)i*( iT) i*( i F)i*( i i)最右推导EETET*FET

3、*iEF*i Ei*iT i *i F i*i i i*ETF*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 C cC |L2:S ABA aA|B bBc|bcL3:S ABA aAb|B aBb|L4:S A| BA 0A1|B 1

4、B0| A*I第三章习题参考答案P64 - 701(01)*101700231011501101确定化: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,4©0,1,2,3,4, 5,60,123,4。1,3,50,1,23,4, 5,60,1,23° 1,30,1231,2,40,1,2,04, $,60,1 0 1 0,1 1 1,22,30 B 门匡40,1

5、,2,3, 4, 5, 601 1P64 - 8(1)(1|0)*01(1|2|3|4|5|6|7|8|9)(0 2|3|4|5|6|7|8|9)*(0|5)|(0|5) 0*1(0|10*1)* |1*0(0|10*1)P64 - 12a确定化:ab00,110,10,11100000给状态编号:ab012112203333a最小化：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,5a 1,3,0,52,3,4,5b 2,3,4,52,4a 1,02,4

6、b 3,53,5a 3,53,5b 2,4 0,1, 2,4, 3,50,1a 10,1b 2,42,4a 1,03,5a 3,52,4b 3,53,5b 2,4bba:0确定化:01X,1,Y1,Y21，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

7、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

8、(S)=),#FOLLOW(T)=)FOLLOWT )=)预测分析表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

9、(T)=+,),#FOLLOW(T')=+,),#FOLLOW(F)=(,a,b,A,+,),#FOLLOW(F')=(,a,b,A,+,),#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 +,),#=

10、$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)= $ 所以,该文法式LL(1)文法.+*()abA#EE TE'E TE'E TE'E TE'E'EEEETT FTT FTT FTT FTT'TT TTT TT TTTTFFPFFPFFPFF PFF'FF *FFFFFFF :PP(E)PaPbP Aproc

11、edure 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 endprocedure T;beginif sym='('

12、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=

13、'b' or sym='人' the n beg in P; F' end else errorendprocedure F'beginif sym='*'the n beg in adva nee; F' endendprocedure P;beginif sym='a' or sym='b' or sym='A'the n adva neeelse if sym='(' the nbeginadvanee; E;if sym=')' the

14、 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,(S,S)(a,(a,S)(a,(a,a)(S,S,S),S)(T),S,S),S)(a,a),S,S),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,

15、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),A ,(a), 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,(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)

16、, 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)(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)

17、,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),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)

18、#进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)输入字符串动作(4) 栈#(#(a #(tFIRSTVT(S)=a,( FIRSTVT(T)=,a】,( LASTVT(S)=a,) LASTVT(T)=,a】,) aA()5a>>A>>(<<<=<)>>5<&l

19、t;<>>G6是算符文法，并且是算符优先文法(3)优先函数aA()5f44244g55523预备(a,(a,a) ) #a, (a,a)#进,(a,a)#进,(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.SA S4.SAS 5.Sb

20、6. 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,1011611000060000SAAsAssbAAA7sAsSAAsbSAaAsSASAaSass

21、sSAAsbi aAsbSAa1DFA工程集样：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)工程集标准族也可以用GO函数来计算得到。所得到的工程集标准族与上图中的AS, Sb= 13GOI 0 ， A=SA S，SAS，Sb， ASA，Aa = I 4GOI 3 ， a=Aa=I1GOI 3 ， b=Sb=I2GOI 3 ， S=AS A ，SAS，Sb， ASA，Aa= I 5GOI 3 ， A=ASA ，SA S，SAS， Sb，ASA， A

22、a= I 6GOI 4 ， a=Aa=I1GOI 4 ， b=Sb=I2GOI 4 ， S=SAS ，AS A ，SAS， Sb，ASA ， Aa = I 7GOI 4 ， A=SA S，SAS，Sb， ASA，Aa = I 4GOI 5 ， a=Aa=I1GOI 5 ， b=Sb=I2GOI 5 ， S=AS A ，SAS，Sb， ASA，Aa= I 5GOI 5， A=ASA ，SA S，SAS， Sb，ASA， Aa= I 6GOI 6 ， a=Aa=I1GOI 6 ， b=Sb=I2GOI 6 ， S=SAS ，AS A ，SAS， Sb，ASA， Aa= I 7GOI 6， A=SA

23、 S，SAS，Sb， ASA，Aa= I 4GOI 7， a=Aa=I1GOI 7， b=Sb=I2GOI 7， S=AS A ，SAS，Sb， ASA，Aa = I 5GOI 7， A=ASA ，SA S，SAS， Sb，ASA ， Aa = I 6工程集标准族为C= I1 ， I2，I3 ， I 4，I5，I 6， I7不是SLR文法状态 3，6，7 有移进归约冲突状态 3：FOL LOW('S )=# 不包含 a,b状态 6： FOLLOW(S)=#,a,b 包含 a,b, ；移进归约冲突无法消解状态7： FOLLOW(A)=a,b包含a,b ;移进归约冲突消解所以不是SLR文法

24、。(4) 构造例如 LR(1) 工程集标准族见以下列图：对于状态5，因为包含工程A AS a/b，所以遇到搜索符号a或b时，应该用A AS 归约。又因为状态 5包含工程A a a/b，所以遇到搜索符号 a时，应该移进。因此 存在“移进-归约矛盾，所以这个文法不是LR(1)文法。S/*第六章会有点难第六章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 :=

25、 intP164-7SL1|L2S.val:=L1.val+(L2.val/2L2.length »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 els

26、e <af b f c xy+z*0= ab+c f abc¥或 xy+z*O= P1 jez ab+cf P2 jump abc ffP1 P2P217- 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) 间接码表：(

27、1)(2)(3)(4)(1)(5)(6)四元式序列 :(1) +, a, b,T1(2) , T1, -,T2(3) +, c, d,T3(4) *, T2, T3 , T4(5) +, a, b,T5(6) +, T5, c,T6(7) -, T4, T6 , T7P218-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-B(6)*(-C+D) i:=E(7)(-C+D)i:=E*(8)-

28、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+i(15)i:=E*(E+E(16)i:=E(E(17)i:=E*(E)(18)i:=E+E(19)i:=E产生的四元式：(,C,-,(+, T ,D,1(*,B, T2 (:=, T ,3T)1T12) ,T)3 ,A)A-BA-B-A-B-A-B-A-B-CA-B-C(,C,-, T )1A-B- T1A-B- T -1A-B- T -DA-B-T -D1(+, T1,D,T)2A-B-T2A-B-T-2A

29、-B- T(*,B,T,T)223A-T(:=,T ,-,A)33(20) AP218- 5/*宽度为w = 4那么设 A ： 10*20 ，B、C、D：20， T1:= i * 20T1:=T1+jT2:=A -84T3:=4*T1Tn:=T2T3/这一步是多余的T4:= i + jT5:=B-4T6:=4*T4T7:=T5T6T8:= i * 20T8:=T8+jT9:=A -84T10:=4*T8T11:=T9T10T12:= i + jT13:=D -4T14:=4*T12T15:= T13T14T16:=T11+T15T17:=C-4T18:=4*T16T19:=T17T18T20:

30、=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,100P218-7100.(j<, A, C, 102)101.(j, -, -, 0)102.(j<, B, D, 104)103.(j, -, -,

31、 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 - 1MAXINT(2)翻译模式方法1：

32、for E1 :=:E2 to E3 do SSF do MS!F For I : E1 to E2I idMS F do MS!backpatch(S1.nextlist,nextquad);backpatch(F.truelist,M.quad);emit(F.place := ' F.place +' 1);emit( j , ' F.place , ' F.end , ' M.quad);S.n extlist := F.falselist;F For I : E! to E2 F.falselist:= makelist(nextquad);e

33、mit( ' 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 := pelse errorMM.quad := nextquad*/方法2:St for i

34、d:=E1 to E2 do S1St F S1Ft for id:=E1 to E2 doF forid : EltoE 2do,'INITIAL);,'FINAL);'FINAL 'p);INITIAL=NEWTEMP; emit( ' :=， E1.PLACE , FINAL=NEWTEMP;emit( ' :=， E2.PLACE , p:= n extquad+2;emit( 'j , ' INITIALF.n extlist:=makelist (n extquad);emit( j,');F.place:=l

35、ookup(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)传名即当过程调用时，