编译基础学习知识原理第三版课后习题集解答

1、第二章习题解答P36-6(1)L(G)是 09组成的数字串(2)0127最左推导 :NNDDD3D34NNDNDDDDD 5DD56D 568最右推导 :NNDN7ND7N27ND27 N127D127 0127NNDN4D434NNDN8ND8N68D68 568NNDNDDNDDD01DD012DDDDD 0DDDP36-7G(S)1|3|5|7|92|4|6|8|O0|NO|AOAD|NP36-8文法：T|E T|E F|T*F|T/ F (E)|i最左推导 :EETiTiT* F iF*Fi*Fi i *iETi*( iT* F F*F T) i*( i F)i*F i *( ii*(

2、 E) i)i*( E T) i*( TT)i *( F T)最右推导：E E T E T* FE T*iE F*i E i*iT i *i F i*i i i*iE T F*T F * FF*(T i)F*( Fi)F*( E)F*( ii)F*( E T) F*( E)i *( i i )F) F*( E i)语法树./*ETE +EE+ TE+Ti+i+ii-i-ii+i*i*/P36-9句子iiiei有两个语法树:巳P36-10/*TS |T*/P36-11/*L1:ACaAb | ab cC |L2:ABaA| bBc|bcL3:ABaAb|aBb|L4:A| B0A1|1B0| A

3、*/第二章习题参考答案P64 -(1)1(01)*10111确定化: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,Y2,3,52,3,4,最小化:0,1,2,3,4,5,60,123,4耳0 1,3待0,1,2,3,4,f11,2,4©0,1,2,3,4, 0,60,1,2,34 01,3,50,1,23，4, $,60,1,23。1,30,1,2,3 11,2,40,1,234, 5UQ0,1 0 1 0,1 1 1,22,30 3 2,3 40,1,2,3, 4, 5, 6八1P64 -8(

4、1)(1|0)*01(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9) (0|5)|(0|5)0*1(0|10*1)* |1*0(0|10*1)*P64 -12a,b0a确定化:ab00,110,10,1110给状态编号:ab012112203333最小化:>0a©bA©bVa0,1， 2,3 0,1 a 1 2,3a0,1, 2, 30爲b23abbA©Vab(b)a已经确定化了，进行最小化最小化:0,1,2,3,4,50，1a10,1 b2,42,3,4,5a 1,3,0,52,3,4,52,4a1,02,4b3,53,5a

5、3,53,5b2,40,1, 2,4, 3,50,1a10,1 b2,42,4a1,02,4b3,53,5a3,53,5b2,42,345babaP64 -4(1)A310:(0|10)* ©确定化:01X,1,Y1，Y21，Y1，Y221，Y给状态编号:0101211221333301最小化:0,1,2,3O,1o 1 2,3o 1,30,1,2,30,11 22,31310第四章P81 -(1) 按照T,S的顺序消除左递归(S)aF |仃)ST，ST |递归子程序:P rocedure S;beginif sym='a' or sym=''then

6、 abva nee else if sym='('then begi nadvance;T;if sym=')' the n adva nee;else error;end(2)elseerrorend;procedure T;beginend;procedure T ;beginif sym=','then beginadvance;endend;其中sym: 是输入串指针 IP 所指的符号advance: 是把 IP 调至下一个输入符号error: 是出错诊察程序FIRST(S)=a,A,(FIRST(T)=a,A,(FIRST(T )=,

7、FOLLOW(S)=),#FOLLOW(T)=)FOLLOW( T )=)预测分析表aA()J#SS aS AS (T)TT STT STT STTTT ,ST是LL(1)文法P81文法:TEE |FTT |PF*F |(E)|a|bF(1)FIRST(E)=(,a,b,AFIRST(E')=+, 4FIRST(T)=(,a,b,AFIRST(T')=(,a,b,A,4FIRST(F)=(,a,b,AFIRST(F')=*,耳FIRST( P)=(,a,b,AFOLLOW(E)=#,)FOLLOW(E')=#,)FOLLOW(T)=+,),#FOLLOW(T&#

8、39;)=+,),#FOLLOW(F)=(,a,b,A,+,),#FOLLOW(F')=(,a,b,A,+,),#FOLLOW( P)=*,(,a,b,A,+,),# (2)考虑下列产生式 :E|T|*F |(E)F|a|bFIRST(+E) nFIRST(护+ Q沪 ©FIRST(+E) QFOLLOW(E')=+ n#,)= ©FIRST(T) nFIRST(沪(abf n沪 ©FIRST(T) nFOLLOW(T')=(,a,b,A+,),#= ©FIRST(*F') nFIRST( 9=* n 4= ©F

9、IRST(*F') nFOLLOW(F')=*n(,a,b,+,),#=©FIRST(E) nFIRST(a) nFIRST(b) nFIRST()= ©所以，该文法式LL(1)文法.+*()abA#EE TE'E TE'E TE'E TE'E'EEEETT FTT FTT FTT FTT'TT TTT TT TTTTFF PFF PFF PFF PFF'FF *FFFFFFFPP (E)P aP bP AP rocedure E;beginif sym='(' or sym='

10、a' or sym='b' or sym=''then begi n T; E' end else errorend p rocedure E'beginif sym-+'then begi n adva nee; E end else if sym<>')' and sym<>'#' the n errorendprocedure T;beginif sym='(' or sym='a' or sym='b' or sym=&

11、#39;'then begin F; T' end else errorend procedure T'beginif sym='(' or sym='a' or sym='b' or sym=''then T else if sym='*' then errorend procedure F;beginif sym='(' or sym='a' or sym='b' or sym=''then begin P; F'

12、end else errorend procedure F'beginif sym='*'then begin advance; F' endendprocedure 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 不满足条

13、件 3 。(3)不是， A 、 B 均不满足条件 3。(4)是，满足三个条件。*/第五章P133 -T* F短语：E+T*F, T*F,直接短语：T*F句柄:T*FP133 文法:(1)最左推导:S (T)(T,S)S (T,S)(S,S)(T,S),S,S),S) (a,a),A ,S),S) (a,a),A ,(a), a)(S,S)(a,S)(a,(T)(a,(T,S)(T),S)(T,S),S)(T,S,S),S)(S,S),S,S),S)(a,S),S,S),S)(a,a),A ,(T),S)(a,a),A ,(S),S)(a,(S,S)(a,(a,S)(a,(a,a)(S,S,S)

14、,S)(T),S,S),S)(a,a),S,S),S)(a,a),A ,(a),S)最右推导:(T,(T)(T,(T,S)(T,(T,a)S (T)(T,S)(S,(a,a)(a,(a,a)S (T,S)(T,a)(S,a)(T),a)(T,S),a)(T,(S,a)(T,(a,a)(T,(T), a)(T,(S), a) (T),A ,(a),a)(T,(a), a) (T,S,(a), a) (T - ,(a), a) (S" ,(a), a)(T,S),A ,(a), a) (T,a),A ,(a),a)( S,a),- ,(a), a) (a,a),- ,(a),a)(a，a

15、),A,(a),a)(S,a),A,(a),a)(T,ar,(a),a)(LS),A,(a),a)(IV,(a),a)(S，A,(a),a)(T,(a),a) (T,(S),a) (T,(T),a) (TS),a) (T) ,a) (S,a) (T,S)(T)“移进-归约”过程:步骤栈输入串动作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

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

17、#(T,a)#31#(T,S)#32#(T)#33#(T)34#SP133 -3(1)FIRSTVT(S)=a,A,(FIRSTVT(T)=,a,A,(LASTVT(S)=a,A,)LASTVT(T)=,a,A,)aA()Ja>>A>>(<<<=<)>>J<<<>>g6是算符文法，并且是算符优先文法(3)优先函数aA()Jf44244g55523#(#(a#(t(t,(t,(t,(a(t,(t(t,(t,(t,(t,a(t,(t,s(t,(tgagAg(g)输入字符串(a,(a,a) #a, (a,a)#

18、,(a,a)#,(a,a)#(a,a) #a,a) #,a) #,a) #a) #)动作预备#(t, (t)#进#)#归#(t)#归#(t)#进# s#successP134-5(1)o.SS1.SS2.SAS3.SA S4. SAS 5.Sb6. Sb7. ASA8. AS A 9.ASA10.A a11.A a归确定化: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,

19、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,10116116S3:SSAS AASAAaSAS-bA5: AS A6: ASASASSA SSbSASASASbAaAASAAaabaDFA构造LR(O)项目集规范族也可以用 GO函数来计算得到。所得到的项目集规范族与上图中的项目集一样 :I0 = S GO( GO( GO( GO( GO( GO( GO( GO( GO( GO( GO( GO( GO( GO( GO( GO( GO( GO( GO( GO( GO( GO( GO( G

20、O(I0，I0，I0，I0，I3，I3，I3，I3，I4，I4，I4，I4，I5，I5，I5，I5，I6，I6 ，b)=I 6 ， S)=I 6 ， A)= I7 ，a)=I 7 ， b)=I 7 ， S)=I 7 ， A)=，a)= ，b)= ，S)= ，A)= ，a)= ，b)= ，S)= ，A)= ， a)= ，b)= ，S)= ，A)= ， a)= ，b)= ，S)= ，A)= ，a)=S，SASSSA S A A ASSSAS A A A SSS A S A AAS，abS，A S ，abS A ，SA ，abAS ，A S ，abS A ，SA ，abAS ，A S， S=SSab

21、S A ，SA ，项目集规范族为S = = AS = =S=AS=S=AC= I1， I2 ，(3)不是 SLR 文法状态3，6，7 有移进归约冲突状态3：状态6：状态7：所以不是SA， AaI1I2S A ， AAS，SI1I2AS，S A S ， I1 I2S A ，AS，I1I2AS，SA S ，I1I2S A ，AS，I1I2 AS，S A S ，I3 ， I 4 ，I5，FOLLOW(S ' )=# 不包含 a,bFOLLOW(S)=#,a,b 包含 a,b, ；SA， b ， Ab ， AAS，Aa， SSA， AAS， b ， Ab ， AAS，AS， b ， Ab ，

22、AAS，SI6， I 7SA， Ab，b，SA，SA，b，b，SA，SA，b，移进归约冲突无法消解FOLLOW(A)=a,b 包含 a,b ；移进归约冲突消解SLR 文法。(4) 构造例如 LR(1) 项目集规范族见下图：AS，S a = I 4a = ISA，SA， a =a = ISA，SA， a =b= I 3AI4AI4a = I 5 SA ， Aa =a =a =a=a =I6I7I6I7I6对于状态5，因为包含项目A AS a/b，所以遇到搜索符号a或b时，应该用A AS归约。又因为状态 5包含项目A a a/b，所以遇到搜索符号 a时，应该移进。因此存在“移进 -归约”矛盾，所以

23、这个文法不是 LR(1) 文法。b1:SS#AS Aa/bASAa/bAaa/bSASa/bSba/bb5:ASAa/bSA Sa/bSASa/bSba/bASAa/bAaa/b8:SA Sa/bSASa/bSba/bASAa/bAaa/bbAAS3：SaAaa3:A a a/b0：SS#SAS#/a/bSb#/a/bASAa/bAaa/bSa4：S b #/a/b6:AS Aa/bASAa/bAaa/bSASa/bSba/b9:SASa/bAS Aa/bASAa/bAaa/bSASa/bSba/b5:SaaS2:7：SA S#/a/bSAS#/a/bSAS#/a/bAS Aa/bSb#/a/

24、bASAa/bASAa/bAaa/bAaa/bSASa/bSba/bS10:a/b第六章/* 第六章会有点难P164 -5(1)E1T if (E1.type = int) and (T.type = int )then E.type := int else E.type := real E.type := T.typenum.num T.type := realnumT.type := int(2)P164 -7L1|L2S.val:=L1.val+(L2.val/2 L2.length )L1BS.val:=L.valL.val:=2*L1.val + B.val;L.length:=L1

25、.length+1L.val:=B.c;L.length :=1B.c:=0B.c:=1*/第七章P217 -a*(-b+c)abc+*a+b*(c+d/e)abcde/+*+-a+b*(-c+d)abcd+*+A (C D)A CD(A B) ( CD)ABCD(A B) (CE)ABCDEif (x+y)*z =0the n(a+b)Icelsea tb fc xy+z*0= ab+cfabc ttY或 xy+z*0= P1 jez ab+ct P2 jump abc ttP1 P2P217 -3-(a+b)*(c+d)-(a+b+c) 的三元式序列：(1)+, a, b+, c, d*,

26、 (2), (3)+, a, b, (1),-(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)+, T5 , c, T6(7)-, T4, T6, T7P218 -4自下而上分析过程中把赋值句翻译成四元式的

27、步骤:A:=B*(-C+D)步骤输入串PLACE四元式(1)A:=B*(-C+D)(2):=B*(-C+D)(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*(-E A-B-C(,C,-,(12) +D)i:=E*(EA-B- T1 - T -1(13) D)i:=E*(E+ A-B-(14) )i:=E*(E+iA-B- T -D1 A-

28、B- T -D (+1A-B- T2 -T-(15)i:=E*(E+E(16)i:=E(E(17)i:=E*(E) A-B-2(18)i:=E+EA-B- T (*,2(19)i:=ET1), T1,D,T2 )A- T3(20)B, T ,T )23 (:=, T ,-,A)3A产生的四元式：(,C,-, T1) (+, T1,D, T2 )(*,B, 1T ,T2)23(:=, T3,-,A)P218 -5/*设 A : 10*20 , B、C、D: 20,宽度为 w = 4 则T1:= i * 20T1:=T1+jT2:=A -84T3:=4*T1Tn:=T2T3/ 这一步是多余的T4:

29、= 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 */P218 -6100. (jnz, A, -, 0)101.( j, -, -, 102)102.( jnz, B, -, 104)103.( j, -, -, 0)104.( jnz, C, -, 103)105.( j, -, -

30、, 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, -, -, 101)104.( j=, A, 1', 106)105.( j, -, -, 109)106.(+, C, 1', T1)107.(:=, T1, -, C)108.( j, -, -, 100)109.(j w. A, D, 111)110

31、.( j, -, -, 100)111.(+, A, 2', T2)112.(:=, T2, -, A)113.( j, -, -, 109)114.( j, -, - 100)P219 -12/* (1)MAXINTMAXINTMAXINTMAXINTMAXINTMAXINT(2) 翻译模式方法 1 ：for E1 := E2 to E3 do SF doMS1For I : E1to E2idF do MS1backpatch(S1.nextlist,nextquad);backpatch(F.truelist,M.quad);emit(F.place := ' F.pla

32、ce + '1);emit( j ,' F.placeF.end ,' M.quad);S.nextlist := F.falselist;For I :E1to E2 F.falselist:= makelist(nextquad);emit( j>, 'E1.place ,'E2.place ,0');emit(I.Place := ' E1.place);F.truelist := makelist(nextquad);emit( j,-,-,- ' );F.place := I.place;F.end := E2.p

33、lace;idp:=lookup();if p <> nil thenI.place := pelse error M.quad := nextquad*/方法2 :Stfor id:=E1 to E2 do S1StF S1Ftfor id:=E1 to E2 doF forid : E1toE2doINITIAL=NEWTE MP;emit( :=， E1.PLACEINITIAL);FINAL=NEWTE MP;emit( :=， E2.PLACE ',FINAL);p:= n extquad+2;emit(INITIALFINALp);F.n extl

34、ist:=makelist (n extquad);emit( j,，一');F.p lace:=look up (id .n ame);if F.place nil the nemit(F. placeINITIAL)F.quad:=n extquad;F.fi nal:=FINAL;S FS1back patch(S1. nextlist, n extquad)p:=n extquad+2;emit(F.p laceF.fi nalP )；S.n extlist := merge( F.n extlist, makelist (n extquad);emit( j,，一');emit( succ,F.place ',F. place);emit( 'j,F.quad);第九章P270 £(1)传名但必须将其中出现的即当过程调用时，其作用相当于把被调用段的过程体抄到调用出现处, 任一形式参数都代之以相应的实在参数。A:=2;B:=3;A:=A+1;A:=A+(A+B);print A;A=9 (2