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

《编译原理课后标准标准答案(陈火旺)》由会员分享，可在线阅读，更多相关《编译原理课后标准标准答案(陈火旺)（35页珍藏版）》请在装配图网上搜索。

1、个人收集整理仅供参考学习第二章P36-6(1)L (G1 ) 是 09 组成地数字串(2)最左推导 :NNDNDDNDDDDDDD0DDD01DD012D 0127NNDDD3D34NNDNDDDDD5DD56D568最右推导 :NNDN 7ND 7N 27ND 27N 127D1270127NNDN 4D434NNDN 8ND 8N 68D 68568P36-7G(S)O 1|3|5|7|9 N 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 * F

2、i i * 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 )语法树： /*1/28个人收集整理仅供参考学习EEEE+TE+TE-TE+TFTT*FE-TFTFiFFiTFiFiiiF

3、iiii+i+ii-i-ii+i*i*/P36-9句子 iiiei有两个语法树：SiSeSiSeiiiSeiiiieiSiSiiSeSiiSeiiiieiP36-10/*S TS |TT(S)|()*/P36-11/*L1:SACAaAb | abCcC |L2:SABAaA |BbBc | bcL3:2/28个人收集整理仅供参考学习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

4、,52,3,42,3,52,32,3,4,Y2,3,4,Y2,3,52,3,4,010230001101015b5E2RGbCAP4601113/28个人收集整理仅供参考学习最小化： 0,1,2,3,45, 6 0,1,2,3,45, 01,35, 0,1,2,3,4,5 11,2,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,12,3 112,4 0,1,2,3 4, 5,6 0,1 0101,112, 2,3 0 3 2,3 1 4 0, 1, 2,3, 4, 5, 60102001001p1Eanq

5、FDPw13450111P648(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)*P6412(a)aa,b01a确定化：ab00,110,10,114/28个人收集整理仅供参考学习10给状态编号：ab012112203333aa01abbbb23a最小化： 0,1,2,3 0,1 a10,1 b 2 2,3 a 0,3 2,3 b 3 0,1,2,3aabb120ab(b)bbaDXDiTa9E3d023abaabba514aaRTC

6、rpUDGiT5/28个人收集整理仅供参考学习已经确定化了 ,进行最小化最小化： 0,1, 2, 3, 4,5 0,1 a1 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 a1,02,4 b 3,5 3, 5 a 3,5 3,5 b2,4 0,1,2, 4,3,5 0,1 a1 0,1 b 2,4 2, 4 a1,02,4 b 3,5 3, 5 a 3,5 3,5 b2,4bba5PCzVD7HxA012abaP6414(1) 01010(2):(010|)*XY201X1Y0确定化：016/28个人收集整理仅供参考学习X,1,

7、Y1,Y21,Y1,Y221,Y给状态编号：01012112213333001010111230最小化：jLBHrnAILg 0,1,2,3 0,1 01 0,1 1 2 2,3 01,3 2,3 1 3 0,1,2, 30111xHAQX74J0X01300第四章P811(1) 按照 T,S 地顺序消除左递归G (S)S a | | (T )T STT ,ST|递归子程序：procedure S;beginif sym=a or sym=then abvance7/28个人收集整理仅供参考学习else if sym=(then beginadvance;T;if sym=) then adv

8、ance;else error;endelse errorend;procedure T;beginS; Tend;procedureT ;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文法：

9、8/28个人收集整理仅供参考学习ETEEE |TFTT T |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*

10、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#EETEETE ETE ETEEEEEETTFTTFTTFTTFTTTTTTTTTTTTT9/28个人收集整理仅

11、供参考学习FFPFPFFPFFPFFPFFF*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# then errorendprocedure T;beginif sym=( or sym=a or sym=b or sym=then begin F; T endelse errorendproce

12、dure T;beginif sym=( or sym=a or sym=b or sym=then Telse if sym=* then errorendprocedure F;beginif 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=( then10/28个人收集整理仅供

13、参考学习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 ,( a ,S)(a,(

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

15、,( 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)11/28个人收集整理仅供参考学习(S,a),(a),a)(T,a),(a),a)( T,S ),

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

17、(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)#归12/28个人收集整理仅供参考学习26#(T),a)#进27#(S,a)#归28#(T,a)#归29#(T,a)#进30#(T,a)#进31#(T,S)#归32#(T

18、)#归33#(T)#进34#S#归P1333(1)FIRSTVT(S)=a,(FIRSTVT(T)=,a,(LASTVT(S)=a,)LASTVT(T)=,a,)(2)a(),a(=,G6 是算符文法，并且是算符优先文法(3) 优先函数a(),f44244g55523f a f f ( f ) f ,ga g g( g) g ,（ 4）栈输入字符串动作#（ a,(a,a) ） #预备#(a, (a,a)#进#(a, (a,a)#进#(t, (a,a)#归13/28个人收集整理仅供参考学习#（ t,(a,a) ） #进#（ t,（a,a ） #进#（ t, （ a,a ） #进#（ t, （ t

19、,a ） #归#（ t,（ t,a） #进#（ t,（ t,a） #进#（ t,（ t,s） #归#（ t, （ t） #归#（ t,（ t ） #进#（ t,s）#归#（ t） #归#（ t）#进# s#归successP1345(1)0.SS1. SS2.SAS3. SA S4.SAS 5.Sb 6.Sb7. ASA8.AS A9.ASA10.Aa11. Aa(2)1SAS789a01011AS234dLDAYtRyKfE56确定化：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,1011614/

20、28个人收集整理仅供参考学习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 SAAabSASSSASAASASbbaAaASAASASAaSbSaAS bSAZzz6ZB2LtkbaA0: SS4: SA S7: SASSAASSSASASASSbSASbASAASASbbaAaASAAAaaabb

21、 a1: Aa2: SbDFA构造 LR(0) 项目集规范族也可以用 GO函数来计算得到 . 所得到地项目集规范族与上图中地项目集一样 :I0= SS， SAS， Sb ， ASA ， Aa GO(I 0 ， a)=Aa=I 1GO(I 0 ， b)=Sb= I215/28个人收集整理仅供参考学习GO(I 0 ， S)=SS ， AS A，ASA， Aa ， SAS，Sb = I 3GO(I 0 ， A)=SA S，SAS， Sb ， ASA， Aa = I 4GO(I3， a)=Aa= I1GO(I3， b)=Sb= I2GO(I3， S)=AS A，SAS， Sb ， ASA， Aa =

22、I 5GO(I3， A)=ASA ，SA S，SAS， Sb， ASA， Aa = I 6GO(I 4 ， a)=Aa= I1GO(I 4 ， b)=Sb=I 2GO(I 4 ， S)=SAS，AS A，SAS， Sb ， ASA， Aa = I 7GO(I 4 ， A)=SA S，SAS， Sb ， ASA， Aa = I 4GO(I5， a)=Aa= I1GO(I5， b)=Sb=I 2GO(I5， S)=AS A，SAS， Sb ， ASA， Aa = I 5a = I 6GO(I5， A)=ASA ，SA S，SAS， Sb， ASA， AGO(I6 ， a)=Aa=I 1GO(I6

23、， b)=Sb=I 2a = I 7GO(I6 ， S)=SAS，AS A，SAS， Sb， ASA， AGO(I6 ， 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， I4， I5， I6， I7(3) 不是 SLR文法状态 3， 6， 7 有移进归约冲突状态 3：FOLLOW(S)=# 不包含a,b状态 6：

24、 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) 文法 . dvzfvkwMI1bbb1：5：8：SS#ASAa/bSA Sa/bAAS Aa/bSA Sa/bSASa/bAA SAa/b AS

25、ASa/bSba/bAaa/bSba/bASAa/bSASa/bASAa/bAaa/bSba/bAaa/b16/28SSSa0：aarqyn14ZNXISS#SAS #/a/bSb#/a/bASA a/bAa b a/bAba2：SA SSASSbSASAAaA个人收集整理仅供参考学习aaS3：3：Aaa/bA6：SAS Aa/b4：ASAa/bSb# / a/bAaa/bSSASa/bSba/baSbb7：#/a/bSAS# / a/b#/a/bAS Aa/b#/a/bbASAa/ba/bAaa/ba/bSASa/bASba/b5：aA9：SASa/bEmxvxOtOcoAS Aa/bASA

26、a/bAaa/bSASa/bSba/b10：Sba/b第六章/*第六章会有点难P1645(1)E E1 T if (E1.type = int) and (T.type = int ) then E.type := intelse E.type := realETE.type := T.typeTnum.num T.type := realTnumT.type := int17/28个人收集整理仅供参考学习(2)P1647SL1|L2S.val:=L1.val+(L2.val/2L 2.length )SLS.val:=L.valLL1BL.val:=2*L1.val + B.val;L.le

27、ngth:=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+*+SixE2yXPq5A(CD)ACD(AB)(CD)ABCD(AB)(CDE) ABCDEif (x+y)*z =0 then (a+b) c else ab cxy+z*0=ab+cabc￥ 6ewMyirQFL或 xy+z*0= P1 jez ab+c P2 jump abcP1P2P2173-(a+b)*(c+d)-(a+b+c)地三元式序列 :(1)

28、+, a, b(2) , (1), -(3) +, c, d(4) *, (2), (3)(5) +, a, b(6) +, (5), c(7) -, (4), (6)18/28个人收集整理仅供参考学习间接三元式序列:三元式表：(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(

29、6) +, 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)i:=E*(

30、EA-B- T1(13)D)i:=E*(E+1A-B- T-1(14)i:=E*(E+iA-B- T-D(15)i:=E*(E+E1T -D (+,T ,D,T )A-B-(16)i:=E(EA-B-112T219/28个人收集整理仅供参考学习(17)i:=E*(E)A-B- T -(18)i:=E+E2(*,B,T ,T )A-B- T223(19)i:=EA- T(:=,T ,-,A)33(20) A产生地四元式：(,C,-,T1 )(+, T,D,T)12(*,B,T2 , T3 )(:=,T ,-,A)3P2185/*设 A ： 10*20 ， B、 C、 D： 20，宽度为 w 4

31、则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:=T7+T19Tn:=T20*/P2186100. ( jnz, A, -, 0)101. (j, -, -, 102)102. (jnz, B, -, 104)10

32、3. (j, -, -, 0)20/28个人收集整理仅供参考学习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, E1.place , E2.place ,0 );emit(I.Place := E1.place);I idMF.truelist := makelist(nextquad);emit( j,-,-

33、,- );F.place := I.place;F.end := E2.place;p:=lookup(id.name);if p nil thenI.place := pelse errorM.quad := nextquad*/方法 2：S for id:=E1 to E2 do S1S FS1F for id:=E1 to E2 doFforid :E1toE 2 doINITIAL=NEWTEMP;emit( := ， E1.PLACE， - ， INITIAL);FINAL=NEWTEMP;emit( := ， E2.PLACE， - ， FINAL);p:= nextquad+2;emit( j, INITIAL , FINAL , p);F.nextlist:=makelist(nextquad);emit( j, , , );F.pla