编译原理课后习题答案(陈火旺+第三版)精选.

1、第二章word.P36-6(1)L(Gi)是o9组成的数字串(2) 最左推导 :NNDNDDNDDD DDDD0DDD01DD012D 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*

2、Fi *(E)i *( ET)i*( TT) i*( F T)i*( iT) i*( i F)i*( i i)最右推导EETET*FET*iEF*iEi*iT i*i F i *i i i*ETF*TF*FF*( E)F*( ET)F *( EF)F *( E i)F *( Ti)F*( F i)F *( ii)i*( ii)语法树：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

3、| ab C cC |L2:S ABA aA|B bBc|bcL3:S ABA aAb|B aBb|L4:S A| BA 0A1|B 1B0| 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,最小化：012,3,4,5,6012,3,4,5。1,3,50,1,2,3,4,511,2,4®012,3,4, 5,60,1,2,34。1,3,50,1,23,4, 5,60,1,

4、23°1,30,1,2,$1,2,40,1,2,04, $,60,1 0 1 0,1 1 1,22,30 B 2,311 40,1,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已经确定化了，进行最小化最小化:

5、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,4b 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 |递归子

6、程序：procedure S;beginif sym='a' or sym='人'the n abva neeelse 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:

7、是把IP调至下一个输入符号 error:是出错诊察程序FIRST(S)=a,(FIRST(T)=af,(FIRST(T )=,FOLLOW(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(

8、F')=*,£ FIRST(P)=(,a,bfFOLLOW(E)=#,)FOLLOW(E')=#,)FOLLOW(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( &

9、#163; )=(,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)= $ 所以,该文法式LL(1)文法.+*()abA#EE TE'E TE'E TE'E TE'E'EEEETT FTT FTT FTT FT

10、T'TT TTT TT TTTTFFPFFPFFPFF PFF'FF *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&

11、lt;>'#' then error endprocedure 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 e

12、rrorendprocedure 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 nee; F' endendprocedure P;beginif sym='a' or sym='b' or sym='A'the n adva n

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

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

15、(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)(T,( T),a)(TS),a)(IL，a)(S，a)(TS)(T)_

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

17、6#(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】,) aA()5a>

18、;>A>>(<<<=<)>>5<<<>>G6是算符文法，并且是算符优先文法(3) 优先函数aA()5f44244g55523(4) 栈#(#(a #(t输入字符串动作(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

19、,s)#归# (t)#归# (t)#进# s#归successP134-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,10

20、2,5,7,8,102,3,5,7,9,1011611000060000SAAsAssbAAA7sAsSAAsbSAaAsSASAaSasssSAAsbi 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)项目集规范族也可以用GO（I 0 ， A）=SA S，SAS，Sb， ASA，Aa = I 4GO（I 3 ， a）=Aa=I1GO（I 3 ， b

21、）=Sb=I2GO（I 3 ， S）=AS A ，SAS，Sb， ASA，Aa= I 5GO（I 3 ， A）=ASA ，SA S，SAS， Sb，ASA， Aa= I 6GO（I 4 ， a）=Aa=I1GO（I 4 ， b）=Sb=I2GO（I 4 ， S）=SAS ，AS A ，SAS， Sb，ASA ， Aa = I 7GO（I 4 ， A）=SA S，SAS，Sb， ASA，Aa = I 4GO（I 5 ， a）=Aa=I1GO（I 5 ， b）=Sb=I2GO（I 5 ， S）=AS A ，SAS，Sb， ASA，Aa= I 5GO（I 5， A）=ASA ，SA S，SAS， S

22、b，ASA， Aa= I 6GO（I 6 ， a）=Aa=I1GO（I 6 ， b）=Sb=I2GO（I 6 ， S）=SAS ，AS A ，SAS， Sb，ASA， Aa= I 7GO（I 6， A）=SA S，SAS，Sb， ASA，Aa= I 4GO（I 7， a）=Aa=I1GO（I 7， b）=Sb=I2GO（I 7， S）=AS A ，SAS，Sb， ASA，Aa = I 5GO（I 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 有移进归约冲突状态

23、 3：FOL LOW('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) 文法。S/*第六章会有点难第六章P164 5(1)E E1 + T if (El.type = in

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

25、*(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¥或 xy+z*0= 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) +, (

26、5), c(7) -, (4), (6) 间接三元式序列 :(1) +, a, b(2) , (1), -(3) +, c, d(4) *, (2), (3)(5) +, (1), c(6) -, (4), (5) 间接码表：(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四

27、元式(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)-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

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

29、:=A -84T10:=4*T8T11:=T9T10T12:= i + jT13:=D -4T14:=4*T12T15:= T13T14T16:=T11+T15T17:=C-4T18:=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. (jnz, D, -, 104) -107. (j, -, -, 10

30、0) - 假链： 106,104 ， 103 真链： 107,100P218-7100.(j<, A, C, 102)101.(j, -, -, 0)102.(j<, B, D, 104)103.(j, -, -, 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)11

31、3.(j, -, -, 109)114.(j, -, - 100)P219- 12/*(1)MAXINT - 5MAXINT - 4MAXINT - 3MAXINT - 2MAXINT - 1MAXINT(2)翻译模式方法1：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.pla

32、ce , ' F.end, ' M.quad);S.n extlist := F.falselist;F For I : E! to E2F.falselist:= makelist(nextquad);emit( ' 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 :=

33、E2.place;I idp:=lookup(id. name);if p <> nil the nI.place := pelse errorMM.quad := nextquad*/方法2:St for id:=E1 to E2 do S1St F S1Ft for id:=E1 to E2 doF forid : E1toE2do,'INITIAL);,'FINAL);'FINAL 'p);INITIAL=NEWTEMP; emit( ' :=， E1.PLACE , FINAL=NEWTEMP;emit( ' :=， E2.P

34、LACE , p:= n extquad+2;emit( 'j , ' INITIALF.n extlist:=makelist (n extquad);emit( j,');F.place:=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)传名即当过程调用时，其作用相当于把被调用段的过程体抄到调用出现处，但必须将其中出现的任一形式参数都代之以相应的实在参数