编译原理课后答案(陈火旺)

1、课后答案网第二章P36-6(1)L ( G1) 是 09 组成的数字串(2)最左推导 :NNDNDDNDDDDDDD0 DDD01DD012 D 0127NNDDD3D34NNDNDDDDD5DD56D568最右推导 :NNDN 7ND 7N 27ND 27N 127D 1270127NNDN 4D 434NNDN 8ND 8N 68D 68568P36-7G(S)O 1|3|5|7|9N 2|4|6|8|O D 0|NS O|AO A AD|NP36-8文法：ET|ET|ETT F|T*F|T/F F ( E)|i最左推导 :EE TT TF T i Ti T * Fi F * Fi i *

2、 F i i * iETT * FF * Fi * Fi *( E ) i *( E T )i *( T T )i *( F T )i *( iT )i *( iF )i *( ii )最右推导 :EE TE T*FE T * iE F * iE i * iT i * iF i * i i i * iETF * TF * FF*( E)F*( E T)F*( E F)F *( E i )F *( T i )F *( F i )F *( i i )i *( i i )语法树： /*课后答案网课后答案网EEEE+TE+TE-TE+TFTT*FE-TFTFiFFiTFiFiiiFiiii+i+ii-

3、i-ii+i*i*/P36-9句子 iiiei有两个语法树：SiSeSiSeiiiSeiiiieiSiSiiSeSiiSeiiiieiP36-10/*S TS |TT(S) |()*/P36-11/*L1:SACAaAb | abCcC |L2:SABAaA |BbBc | bcL3:课后答案网课后答案网S ABA aAb | B aBb |L4:S A | B A 0A1| B 1B0| A*/第三章习题参考答案P647(1)1(01|) * 101XY01101X12345Y1确定化：01X1,2,31,2,32,32,3,42,32,32,3,42,3,42,3,52,3,42,3,52

4、,32,3,4,Y2,3,4,Y2,3,52,3,4,010230001101015640111最小化：课后答案网课后答案网 0,1,2,3,4,5, 6 0,1,2,3,4,5 01,3,50,1,2,3,4,5 112,4,6 0,1,2,3,4, 5, 6 0,1,2,3,4 01,3,5 0,1,2,3, 4, 5, 6 0,1,2,3 01,30,1,2,3 112,4 0,1,2,3 4,5,6 0,1 010,111,2 2,3 0 3 2,314 0, 1, 2,3, 4, 5, 6010200100113450111P648(1)(1 | 0)* 01(2)(1|2|3|4|

5、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) *P6412(a)aa,b01a确定化：ab00,110,10,1110课后答案网课后答案网给状态编号：ab012112203333aa01abbbb23a最小化： 0,1,2,3 0,1 a10,1 b 2 2,3 a 0,3 2,3 b3 0,1,2,3aabb012ab(b)bba023abaabb1a5a4a已经确定化了, 进行最小化课后答案网课后答案网最小化： 0,1, 2, 3,4, 5 0,1 a1 0,1 b 2,4 2,

6、 3,4,5 a 1, 3, 0, 5 2,3,4,5 b 2, 3,4,5 2, 4 a1,0 2,4 b 3,5 3, 5 a 3,5 3,5 b 2,4 0,1,2, 4,3, 5 0,1 a1 0,1 b 2,4 2, 4 a1,0 2,4 b 3,5 3, 5 a 3,5 3,5 b 2,4bba012abaP6414(1) 01010(2):X(| )*010Y201X1Y0确定化：01X,1,Y1,Y2课后答案网课后答案网1,Y1,Y221,Y给状态编号：01012112213333000110111230最小化： 0,1, 2, 3 0,1 01 0,1 1 2 2,3 01,

7、3 2,31 3 0,1, 2, 3011101300第四章P811(1) 按照 T,S 的顺序消除左递归G (S)S a | | (T )T STT ,ST|递归子程序：procedure S;beginif sym='a' or sym=''then abvanceelse if sym='('课后答案网课后答案网then beginadvance;T;if sym=')' then advance;else error;endelse errorend;procedure T;beginS; Tend;procedureT

8、;beginif sym=','then beginadvance;S; Tendend;其中 :sym: 是输入串指针IP 所指的符号advance: 是把 IP 调至下一个输入符号error:是出错诊察程序(2)FIRST(S)=a,(FIRST(T)=a,(FIRST( T )=,FOLLOW(S)=),#FOLLOW(T)=)FOLLOW(T )=)预测分析表a(),#SSaSS(T)TTSTTSTTSTTTT,ST是 LL(1) 文法P812文法：课后答案网课后答案网ETEEE |TFTT T |FPFF* F |P( E) | a | b |(1)FIRST(E)=

9、(,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( )=+ = FI

10、RST(+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'TTTTTTT

11、TTTT课后答案网课后答案网FF'PFPFFPFFPFFPFFF*FFFFFFFP( E )PaPbP(4)procedure E;beginif sym='(' or sym='a' or sym='b' or sym=''then begin T; E' endelse errorendprocedure E'beginif sym='+'then begin advance; E endelse if sym<>')' and sym<>'

12、;#' then errorendprocedure T;beginif sym='(' or sym='a' or sym='b' or sym=''then begin F; T' endelse errorendprocedure T'beginif sym='(' or sym='a' or sym='b' or sym=''then Telse if sym='*' then errorendprocedure F;b

13、eginif sym='(' or sym='a' or sym='b' or sym=''then begin P; F' endelse errorendprocedure F'beginif sym='*'then begin advance; F' endendprocedure P;beginif sym='a' or sym='b' or sym=''then advanceelse if sym='(' then课

14、后答案网课后答案网beginadvance; E;if sym=')' then advanceelse errorendelse errorend;P813/*(1) 是，满足三个条件。(2) 不是，对于 A 不满足条件 3。(3) 不是， A 、 B 均不满足条件 3。(4) 是，满足三个条件。*/第五章P1331EETET*F短语 : E+T*F, T*F,直接短语 : T*F句柄 : T*FP1332文法：S a|( T ) T T, S|S(1)最左推导 :S(T )(T , S)(S, S)(a, S)( a,( T )(a,( T , S)(a ,( S,S)(a

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

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

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

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

19、#(T)#进34#S#归P1333(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) ） #进#（

20、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#归successP1345(1)0.SS1. SS2. SAS 3.SA S4.SAS 5.Sb6. Sb7.ASA8.AS A9.ASA10.Aa11. Aa(2)1SAS789a01011AS234d56确定化：SAab0,2,5,7,101,2,5,7,8,102,3,5,7,101161,2,5,7,8,102,5

21、,7,8,102,3,5,7,9,10116课后答案网课后答案网2,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,10116116AS3: SS5:A SA6: ASASASASSA SAabSASS ASbASAASASbAaAaASASASAaSbSaAS bS AbaA0: SS4: SA S7: SASSAASSSASAS ASbSbSASASAbASASbAa

22、AaASAAaaabb a1: Aa2: SbDFA构造 LR(0) 项目集规范族也可以用 GO函数来计算得到。所得到的项目集规范族与上图中的项目集一样 :I0= SS， SGO(I 0， a)=AGO(I 0， b)=SGO(I 0， S)=SAS， Sb ， ASA， Aa a = I1b = I2S ， AS A ， ASA， Aa ， SAS ， Sb = I 3课后答案网课后答案网GO(I 0 ， A)= GO(I 3 ， a)= GO(I 3 ， b)= GO(I 3 ， S)= GO(I 3 ， A)= GO(I 4 ， a)= GO(I 4 ， b)= GO(I 4 ， S)=

23、 GO(I 4 ， A)= GO(I 5 ， a)= GO(I 5 ， b)= GO(I 5 ， S)= GO(I 5 ， A)= GO(I 6 ， a)= GO(I 6 ， b)= GO(I 6 ， S)= GO(I 6 ， A)= GO(I 7 ， a)= GO(I 7 ， b)= GO(I 7 ， S)= GO(I 7 ， A)=项目集规范族为S AS，SAS， Sb， ASA ， A a = I 4Aa= I1Sb= I2A SA，SAS， Sb ， ASA， Aa = I 5A SA，SA S，SAS， Sb， ASA， A a = I 6Aa= I1Sb= I2S AS，AS A，

24、SAS， Sb ， ASA ， A a = I 7S AS，SAS， Sb， ASA ， A a = I 4Aa= I1Sb= I2A SA，SAS， Sb ， ASA， Aa = I 5A SA，SA S，SAS， Sb， ASA， A a = I 6Aa=I 1Sb=I 2SA， A a = I 7S AS，AS A，SAS， Sb， AS AS，SAS， Sb ， ASA， A a = I 4Aa= I1Sb= I2A SA，SAS， Sb ， ASA， A a = I 5A SA，SA S，SAS， Sb， ASA ， A a = I 6C=I1，I2， I3，I4， I5， I6，

25、I7(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，因为包含项目 A AS a / b ，所以遇到搜索符号 a 或 b 时，应该用 A AS 归约。又因为状态 5 包含项目 A a a / b ，所以遇到搜索符号 a 时，应该移进。因此存在“移进 - 归约”矛盾，所以这个文法不是LR(1) 文法。课后答案

26、网课后答案网bbb1：5：8：SS#AA S A a/b A A SA a/bAaa/bS S ASa/bSba/bSSaASAa/bSA Sa/bASA Sa/bSASa/bSASa/bSba/bSba/bASAa/bASAa/bAaa/baAaa/baS3：0：aaA3：aSS#AaAa/bSAS#/a/b6：Sb#/a/bSAS Aa/bASAb a/b4：ASAa/bAaa/bSb# / a/bAaa/bSSASa/bSba/bAbaaSbb2：7：9：SASa/bAS Aa/bASAa/bAaa/bSASa/bSba/bSA S#/a/bSAS#/a/bSb#/a/bbSASAa/b

27、Aaa/bSAS# / a/bAS Aa/bASAa/b10：Aaa/bS b a/bSASa/bSba/bAA5：课后答案网课后答案网第六章/*第六章会有点难P1645(1)EE1 T if (E1.type = int) and (T.type = int )then E.type := intelse E.type := realETE.type := T.typeT num.num T.type := realTnumT.type := int(2)P1647SL1|L2S.val:=L1.val+(L2.val/2L 2.length )SLS.val:=L.valLL1BL.val

28、:=2*L1.val + B.val;L.length:=L1.length+1LBL.val:=B.c;L.length :=1B0B.c:=0B1B.c:=1*/第七章P2171a*(-b+c)abc+*a+b*(c+d/e)abcde/+*+-a+b*(-c+d)abcd+*+A(CD)ACD(AB)(CD)ABCD(AB)(CDE)ABCDEif (x+y)*z =0 then (a+b) c else ab cxy+z*0= ab+c abc ￥或 xy+z*0= P1 jez ab+c P2 jump abcP1P2课后答案网课后答案网P2173-(a+b)*(c+d)-(a+b+

29、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)间接码表：(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)

30、+, T5 , c, T6(7) -, T4, T6 , T7P2184自下而上分析过程中把赋值句翻译成四元式的步骤: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:=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

31、)i:=E*(EA-B- T1(13)D)i:=E*(E+1A-B- T -(14)i:=E*(E+i1A-B- T -D(15)i:=E*(E+E1(+, T ,D,T )A-B- T -D(16)i:=E(E112A-B- T(17)i:=E*(E)2A-B- T -(18)i:=E+E2(*,B,T ,T )A-B- T(19)i:=E2(:=,23A- TT ,-,A)33(20) A产生的四元式：(,C,-,T )1(+,T,D,T)12(*,B,T ,T )23(:=,T ,-,A)3P2185/*设 A ： 10*20 ， B、 C、 D： 20，宽度为 w 4 则T1:= i

32、* 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 4课后答案网课后答案网T18:=4*T16T19:=T17T18T20:=T7+T19Tn:=T20*/P2186100. ( jnz, A, -, 0)101. (j, -, -, 102)102. (jnz, B, -, 104)

33、103. (j, -, -, 0)104. (jnz, C, -, 103)105. (j, -, -, 106)106.(jnz, D, -, 104) -假链链首107.(j, -, -, 100)-真链链首假链： 106,104 ， 103真链： 107,100P2187100. ( 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)10

34、8. (j, -, -, 100)109. (j , A, D, 111)110. (j, -, -, 100)111. (+, A, 2, T2)112. (:=, T2, -, A)113. (j, -, -, 109)114. (j, -, - 100)P21912/*(1)MAXINT 5MAXINT 4MAXINT 3MAXINT 2MAXINT 1MAXINT课后答案网课后答案网(2) 翻译模式方法 1：for E1 := E2 to E3 do SSF do MS1FFor I :E1 to E2IidMSF do MS1backpatch(S1.nextlist,nextqua

35、d);backpatch(F.truelist,M.quad);emit(F.place := F.place + 1);emit( j, F.place , F.end , M.quad);S.nextlist := F.falselist;FFor I :E1 to E2F.falselist:= makelist(nextquad);emit( j>, E1.place , E2.place ,0 );emit(I.Place := E1.place);I idMF.truelist := makelist(nextquad);emit( j,-,-,- );F.place := I.place;F.end := E2.place;p:=looku