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

1、精品第二章P36-6(1)L ( G1) 是 09组成的数字串(2)最左推导 :NNDNDDNDDDDDDD0DDD01DD012D 0127NNDDD3D34NNDNDDDDD5DD56 D568最右推导 :NNDN 7ND 7N 27ND 27N 127D1270127NNDN 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最左推导 :EETTTFTiTiT * FiF * Fii * Fii * iETT *

2、FF * Fi * Fi *( E )i *( ET )i *( TT )i *( FT )i *( iT )i *( iF )i *( ii )感谢下载载精品最右推导 :EE TE T*FE T * iE F * iE i * i T i * iF i * ii i * iET F*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-i-ii+i*i*/P36-9句子 iii

3、ei 有两个语法树：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*/第三章习题参考答案P64 7(1)1(01|) * 101XY0X12345Y感谢下载载精品11011确定化：01X1,2,31,2,32,32,3,42,32,32,3,42,3,42,3,52,3,42,3,52,32,3,4,Y2,3,4,

4、Y2,3,52,3,4,0012030011014051601感谢下载载精品11最小化： 0,1,2,3,4,5, 6 0,1,2,3,4,5 01,3,50,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,1,2,3112,4 0,1,2,3 4, 5,6 0,1 010,1 11,2 2,3 0 3 2,3 14 0, 1, 2,3, 4, 5, 6001200101304150111P64 8(1)(1 | 0)* 01(2)(1|2|3|4|5|6|7|8|9)(0|1

5、|2|3|4|5|6|7|8|9)*(0|5) |(0|5)(3)感谢下载载精品0*1(0 | 10*1) * |1* 0(0 |10* 1) *P64 12(a)aa,b01a确定化：ab00,110,10,1110给状态编号：ab012112203333感谢下载载aa0ab2最小化： 0,1, 2,3 0,1 a10,1 b 2 2,3 a 0,3 2,3 b 3 0,1, 2, 3ab0a精品1bb3baab12b感谢下载载精品(b)b2b3a0abaab1b45aaa已经确定化了 ,进行最小化最小化： 0,1, 2, 3,4, 5 0,1 a1 0,1 b 2,4 2, 3,4,5 a

6、 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,4bba012ab感谢下载载精品aP64 14(1)01010(2):X(010 *Y| )201X1Y0感谢下载载精品确定化：01X,1,Y1,Y21,Y1,Y221,Y给状态编号：01012112213333001010112310最小化：感谢下载载精品 0,1, 2, 3 0,1 01 0,1 1 2 2,3

7、 01,3 2,31 3 0,1, 2, 3011101300第四章P81 1(1) 按照 T,S 的顺序消除左递归G (S)Sa | | (T )TSTT,ST |递归子程序：procedure S;beginif sym=a or sym=then abvanceelse if sym=(then beginadvance;T;if sym=) then advance;感谢下载载精品else error;endelseerrorend;procedure T;beginS;Tend;procedureT ;beginif sym=,then beginadvance;S;Tendend;

8、其中 :sym: 是输入串指针IP 所指的符号advance: 是把 IP 调至下一个输入符号error: 是出错诊察程序(2)FIRST(S)=a,(感谢下载载精品FIRST(T)=a,(FIRST( T )=,FOLLOW(S)=),#FOLLOW(T)=)FOLLOW( T )=)预测分析表a(),#SaSS(T)STSTTSTTSTTTTT,ST是 LL(1) 文法P81 2文法：ETEEE |TFTT T |FPFF* F |P( E) | a | b |(1)FIRST(E)=(,a,b,FIRST(E)=+, FIRST(T)=(,a,b,FIRST(T)=(,a,b,感谢下载载

9、精品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( )=+ = FIRST(+E) FOLLOW(E)=+#,)= FIRST(T) FIRST( )=(,a,b,= FIRST(T) FOLLOW(T)=(,a,b,+,

10、),#=FIRST(*F) FIRST( )=* = FIRST(*F) FOLLOW(F)=*(,a,b,+,),#=FIRST(E) FIRST(a)FIRST(b)FIRST()=所以 ,该文法式LL(1) 文法 .感谢下载载精品(3)+*()ab#EETE ETE ETE ETE EEEEETTFTTFTTFTTFTTTT TTT TT TT TTFFPFFPFFPFFPFFF*FFFFFFFFPP( E )PaPbP(4)procedure E;beginif sym=( or sym=a or sym=b or sym=then begin T; E endelse erroren

11、dprocedure E;beginif sym=+then begin advance; E endelse if sym) and sym# then errorend感谢下载载精品procedure 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;beginif sym=( or sym=a or sy

12、m=b or sym=then begin P; F endelse errorendprocedure F;beginif sym=*then begin advance; F end感谢下载载精品endprocedure P;beginif sym=a or sym=b or sym=then advanceelse if sym=( thenbeginadvance; E;if sym=) then advanceelse errorendelse errorend;P81 3/*(1) 是，满足三个条件。(2) 不是，对于 A 不满足条件 3 。(3) 不是， A 、 B 均不满足条件

13、 3。(4) 是，满足三个条件。*/第五章感谢下载载精品P133 1EETET*F短语 :E+T*F, T*F,直接短语 : T*F句柄 : T*FP133 2文法：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 ,( 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 ,

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

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

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

17、进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,)(2)a(),a(=,G6 是算符文法，并且是算符优先文法(3) 优先函数a(),感谢下载载精品f44244g55523f af

18、 f(f )f ,gagg(g)g,（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#归successP134 5(1)0.SS1.SS2.SAS3.SA S4. SAS5. Sb6. Sb7

19、. ASA8. AS A 9. A SA 10. A a11. Aa(2)17S8A9S010a112A3S4感谢下载载精品d56确定化：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,101162,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

20、: AS A6: ASASASSA SAS ASbSASASAASASbAaSAaAASAaSASAaSb感谢下载载精品bSaAS bSAbaA0: SS4: SA S7: SASSASSASAS ASbSbSASASAASASbAaAAaSASAAabaabba1: Aa2: SbDFA构造 LR(0) 项目集规范族也可以用GO 函数来计算得到。所得到的项目集规范族与上图中的感谢下载载精品项目集一样 :I0= SS， SAS， Sb ， ASA， A a GO( I 0 ， a)=Aa= I1GO( I 0 ， b)=Sb= I2GO( I 0 ，S)=SS ， AS A，ASA， Aa ，

21、 SAS， Sb = I 3GO( I 0 ， A)=SA S，SAS， Sb ， ASA， Aa = I 4GO( I 3 ， a)=Aa= I1GO( I 3 ， b)=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 =

22、 I 4GO( I 5 ， a)=Aa= I1GO( I 5 ， b)=Sb= I2GO( I 5 ， S)=AS A，SAS， Sb ， ASA， Aa = I 5a = I 6GO( I 5 ， A)=ASA ，SA S，SAS， Sb ， ASA， AGO( 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= I2S bASA A

23、a = I 5GO( I 7 ， S)=A S A，SAS，GO( I 7 ， A)=ASA ，SA S，SAS， Sb ， ASA， Aa = I 6项目集规范族为C= I1， I 2， I 3， I4， I5， I6，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

24、，因为包含项目 AASa / b ，所以遇到搜索符号a 或 b 时，应该用 AAS归约。又因为状态 5 包含项目 Aaa / b ，所以遇到搜索符号a 时，应该移进。因此存在“移进 - 归约”矛盾，所以这个文法不是LR(1) 文法。感谢下载载精品bbb1：5：8：SS#ASAa/bSA Sa/bAS Aa/bSA Sa/bSASa/bASAa/bSASa/bSba/bAaa/bSba/bASAa/bASASa/bASAa/bAaa/bSba/bAaa/bAASaaS3：SaS0：3：SS#SAS#/a/bSb#/a/bA SA a/b A a a/bAaa/bAaaaA6：9：SASa/bAS

25、 Aa/bASAa/bAS Aa/bAaa/bSASAa/bAaa/b4：SASa/bSb# / a/bSASa/bSba/b感谢下载载Sba/b精品bSAbaaSbb2：7：SA S#/a/bSAS# / a/bSAS#/a/bAS Aa/bSb#/a/bASAa/bASAa/bAaa/bAaa/bSASa/bSba/b10：Sba/bSbAA5：感谢下载载精品第六章/*第六章会有点难P164 5(1)EE1 T if (E1.type = int) and (T.type = int )then E.type := intelse E.type := realETE.type := T.t

26、ypeTnum.num T.type := realTnumT.type := int(2)P164 7SL1|L2S.val:=L1.val+(L2.val/2L2 .length )SLS.val:=L.valLL1BL.val:=2*L1.val + B.val;L.length:=L1.length+1LBL.val:=B.c;L.length :=1B0B.c:=0B1B.c:=1*/感谢下载载精品第七章P217 1a*(-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 =0then(a+b) celsea b cxy+z*0= ab+cabc ￥或 xy+z*0= P1 jez ab+c P2 jump abcP1P2P217 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