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

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

1、编译原理课后答案（陈火旺）课后答案网 第二章P36-6L(G)是09组成的数字串最左推导：N = ND 二 NDD 二 NDDD = DDDD = 0DDD = 01DD= 012D= 0127N = ND = DD = 3D= 34N = ND 二 NDD 二 DDD 二 5DD 二 56D二 568 最右推导：N= ND = N7= ND7= N27= ND 27= N127= D127= 0127N = ND 二 N4二 D4二 34N = ND = N8= ND 8= N68= D68= 568P36-7G(S)O 1|3|5|7|9N 2|4|6|8|OD 0|NS O|AOA AD

2、|NP36-8文法：E T T E +T|E TT t F T* F|T/ FF (E)|i最左推导：E = E T= T T= F T= i T= i T * F = i F * F 二 i i * F = i i*iE = T= T* F = F * F = i* F = i *( E)= i *( E T)= i*( T T)二 i *( F T)二 i*( i T)二 i*(i F)= i*( i i)最右推导：E=E + T=E + T*FnE + T*i=E + F*inE + i*i=T + i*i=F + i*ini + i*i = r=F*r=F*F=F*(E)=F*(E +

3、 r)=F*(E + F)=F*(E + z) =*(7+0=*( + /)=*(/+0 =/*(/ + /)A口 彳Z、: / 666TT6个6t66666666小6666666个6666个TTTFTTETFi+i+i 1-1-1i + i*iP36-9句子iiiei有两个语法树:S = iSeS = iSei = iiSei = iiieiS n IS n USeS n iiSci = iiieiP36-10/2石|厂r-(s)|(), 、“ /P36-11/*L1:S ACA； aAb |abC cC | ；L2:S ABAr aA| ；B bBc|bcL3:S ABA： aAb | ；

4、B aBb| ；L4:S A| BA 0A1| ；B 1B0| A*/第三章习题参考答案P64 - 7(1)(0|1) 101课后答案网 11 0 1确定化:01X1,2,301,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,V ”最小化:0,1,2,3,4,5,60,123,4,5。=1,3待0,123,4,5 =1,2,40,1,2,3,4, 5,60,123,4。二1,3,50,1,23,4, 5,60,1,23 1,30,1,2,$ =1,2,40,1,2,职4, $,60,1 0 aF|

5、仃)T STT ,ST | ；递归子程序：procedure S;begi nif sym=a or sym=Athe n abva neeelse if sym=(the n begi nadvance;T;if sym=) the n adva nee;else error;endelse errorend;procedure T;begi nS；end;procedure t ;begi nif sym=,the n begi nadvanee;S;tendend;其中：sym:是输入串指针IP所指的符号 advanee:是把IP调至下一个输入符号 error:是出错诊察程序FIRST(

6、S)=af,( FIRST(T)=a,*( FIRST(t)=,FOLLOW(S)=),# FOLLOW(T)=) FOLLOW()=)预测分析表aA()#SSt aSt aSt (T)TTt STTt STTt STT J名T J ,ST是LL(1)文法P81 - 2文法：E TEE | ；T FTT T pF PFF； *F | ；P (E)| a |b |A(1)FIRST(E)=(,a,b,AFIRST(E)=+, FIRST(T)=(,a,b,AFIRST(T)=(,a,b,* FIRST(F)=(,a,b,AFIRST(F)=*, FIRST(P)=(,a,bfF0LL0W(E)=

7、#,)F0LL0W(E)=#,)F0LL0W(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=(,a,b,A,+,),#FOLLOW(F)=(,a,b,A,+,),# FOLLOW(P)=*,(,a,bf,+,),#考虑下列产生式：E ，E| ；T TpF *F |P (E)|A|a|bFIRST(+E) A FIRST( )=+ n = 0FIRST(+E) A FOLLOW(E)=+A #,)=0FIRST(T) A FIRST( )=(,a,b,A n = 0FIRST(T) A F0LL0W(T)=(,a,b,A n +,),#= 0FIRST(*F) A FIRST

8、( )=* n = 0FIRST(*F) A F0LL0W(F)=* AA FIRST(b)(,a,b,*+,),#=0FIRST(E) A FIRST(a)FIRST(A)= 0所以,该文法式LL(1)文法.+*()abA#EEt TEEt TEEt TEEt TE EEEE T名E J名TTt FT*Tt FTt FTt FTTTJ名TJ TTJ名t TTt TTt TTJ名FFt PFFt PFFt PFFt PLFF J eF J eF J名F J eF J名F J呂F J名PPt (E)Pt aPt bPt aprocedure E;begi nif sym=( or sym=a o

9、r sym=b or sym=Athe n begi n T; E endelse error课后答案网 endprocedure E;beginif sym=+then begin advance; E endelse if sym) and sym# then error end procedure T;beginif sym=(or sym=aor sym=borsym=Athen begin F; T end else errorendprocedure T; begin sym=Aif sym=(or sym=a or sym=borthen T else if sym=* then

10、 errorend procedure F;beginorif sym=( or sym=a or sym=b sym=Athen begin P; F endelse errorend procedure F; beginif sym=*then begin advance; F end end procedure P; beginif sym=a or sym=b or sym=A then advance else if sym=( then beginadvance; E;if sym=) then advance else errorelse errorend;P81 - 3/*(1

11、) 是，满足三个条件。(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文法：S a|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,

12、 S), S,S), S)二(a, S), S,S), S) = (a,a), S,S), S)= (a,a),A ,S),S)二(a,a),A ,(T), S)二(a,a),A ,(S), S)= (a,a),A ,(a), S)=(a,a)f ,(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)= ( ,(a

13、), a)= (S“ ,(a), a)= (T)“ ,(a),a) =(T,S)“ ,(a), a)= (T,a),(a),a)二(S,a)“ ,(a), a)= (a,a)“ ,(a), a)(ae)A(a),a)(Sg),“,(a),a)(T,a)f(a),a)(TS)A(a),a)(Dl(a),a)(SA(a),a)(T,A,(a),a)(TS(a),a)(aQa)(T,(S),a)(T,(T),a)(LSIa)(Ha)(S,a)OX课后答案网 “移进-归约”过程：步骤栈输入串动作0 #W(a),a)#预备1 #(aja),A,(a),a)#进2 #(a,a),A,(a),a)#进3 #

14、(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)#进16#(T,S,(a),a)#归仃 #(T,(a),a)#归18#(T,(a),a)#进19#(T,(a),a)#进20#(T,(a),

15、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)=”aA(LASTVT(S)=a,-)LASTVT(T)=,af,)(2)aA()aA(=G6是算符文法，并且是算符优先文法(3)优先函数aA()f44244g55523gagAg(g)g(4)栈输入字符

16、串动作课后答案网#(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#归successP13450. s s 1. s s2. S AS3. Sr A S4. St as，5. St b6. s b7. At SA课后答案网8. A S A 9. A SA 10. A a 11

17、. A aSd确定化:SAab025,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,101161100060000Aaab a A aS bDFA构造LR(0)项目集规范族也可以用 GO函数来计 算得到。所得到的项目集规范族与上图中的项

18、目A； S A A； SA A； a S-；AS，A SSr AS ，Sr b ， ASA，a J=Iib J=I2，S AS，S r b，A SA? A aJ=S b , Ar SA , A a a = Iib = I2SSr A S，S ASSb，A SA，aJ=I1bJ= I2A S A，SASSb，A SA，AS ， SASS b，ASA，AsSr b , A SA, A a= 15 Sr AS , Sr b , Ar SA ,a =Ii b = 12 ,S AS , ，S ,H , S AS ,A S , Sr AS , Sr b ,s A ATsSRbSSb，-slorooo o

19、0000 000 o 0000 000 o 00 WGGG SG agggg aggg AG AGGGG AGGG AG AGGAsTA4 abxJAJA s TA审s TA s s舄 b abs)A“ 亠4 4 yab舄人6 abs)“ 亠5 5 5 5r . 6 6 6 (i一一一一)74 ab课后答案网 GO (7 , S)= At S，A , St AS, St b , At SA , At a = I5 GO (7 , A)= At SA，, St A S , St AS , St b , At SA , A、a=丨6项目集规范族为 C = l1 , I2 , I3 , I4 , I

20、5 , I6 , I7 不是SLR文法状态3, 6, 7有移进归约冲突状态 3： FOLLOW)=#不包含 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)文法。bAAaaS0:S S #-3:a A a - a

21、/b aS t J 课后答案网 AT SA a/bAa4:I St b #/a/bb6:A S Aa/bA SAa/bA aa/bSASa/b-SJba/b9:S TASa/bAtS Aa/bAtSAa/bAtaa/bS TASa/bSr bSb2:StA S#/a/bStAS#/a/bStb#/a/bAtSAa/bAtaa/b7:StAS -#/a/bAtS Aa/bAtSAa/bAtaa/bStAS ba/ba/b10:S a/bAA第六章/*第六章会有点难P164- 5(1)E E1+ T if (El.type = int) and (T.type =int )the n E.type

22、 := intelse E.type := realE T E.type := T.typeT num.num T.type := realT num T.type := intP164-7S L1|L2 S.val:=L1.val+(L2.val/2L2Jength)S L S.val:=L.valL L1B L.val:=2*L1.val + B.val;L.le ngth:=L1.le ngth+1L B L.val:=B.c;L.le ngth :=1B 0B.c:=0B 1B.c:=1P217 1a*(-b+c)a+b*(c+d/e)-a+b*(-c+d)第七章abc+abcde/+

23、*+abcd+*+A (C D)(A B) (一C D)AB C D(A B) (C -D E)AB CD Eif (x+y)*z =0 then (a+b)f c else ab f c xy+z*0= ab+c f abc ff Y或 xy+z*0= P1 jez ab+c f P2 jumpabcffP1 P2P217-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)+,

24、 a, b(2), (1), -(3)+, c, d(4)*, (2), (3)(5)+, (1), c(6)-, (4), (5)间接码表：(1)(2)(3)(4)(1)(5)(6)T1T2T3TT5T6T36T ,T ,-, ,c b,d,b,1 2 5 4 ,T1,T,T5T a,c a , , +*,+-,)1234567P2184自下而上分析过程中把赋值句翻译成四元式的PLACE 四元式步骤：A:=B*(-C+D)A-B-A-B-CA-B-C(,C,-,i*(-E*=Ei:TDT1 D+ - TD1 B- -T-1 T1 A-B- -2 T2T BAB- A AB-B-A-A-E i

25、E (+ ) E*(E(E(EE(E =*(* i:EEEEE+DD +)01)23456911)11 1111(T(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(18(19(产1290生 (,C,-, (+, T ,D, (*,B,T1课后答案网 (T3*,-B,A,) T2,T3)ii:=EE+E A-AT -B- (T2: 的四元式： A T , TT2T1

26、) T3T,2-,AT23)P218- 5/*设 A : 10*20, B、C、D: 20,宽度为 w= 4 则 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 + j课后答案网 T13:=D FT14:=4*T12 T15:= T13T14 T16:=T11+T15T17:=C T18:=4*T16 T19:=T17T18 T20:=T7+T19Tn:=T20*

27、/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, -, -, 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 ,

28、 1, 106)105. (j, -, -, 109)106. (+, C, 1, T1)107. (:=, T1, -, C)108. (j, -, -, 100)109. (j idSr F do MS1backpatch(S1. nextlist, nextquad); backpatch(F.truelist,M.quad); emit(F.place := F.place + 1);emit( j -, F.place , F.end,M.quad);S.n extlist := F.falselis t;F For I : = E1 to E2 F.falselist:=makel

29、ist( nextquad);emit( j, E1.place,E2.place ,0 );课后答案网 emit(I.PIace := El.place); F.truelistmakelist( nextquad);emit( j,-,-,-);F.place := I.place;F.e nd := E2.place;I idp:=lookup(id.name);if p nil the nI.place := pelse errormM.quad := nextquad*/方法2:Sf for id:=E1 to E2 do S1Sf F S1Ff for id:=E1 to E2 d

30、oF forid : =E1toE2 doINITIAL=NEWTEMP;emit( := , E1.PLACE, - , INITIAL); FINAL=NEWTEMP;emit( := , E2.PLACE, - , FINAL); p:= n extquad+2;emit( j , INITIAL , FINAL p);F.n extlist:=makelist (n extquad);emit( j,);F.place:=lookup(id .n ame);if F.placenil the nemit(F.place := INITIAL)F.quad:=nextquad;F.fi

31、nal:=FINAL;S FS1backpatch(S1. nextlist, n extquad) p:=nextquad+2;emit( j , F.place , F.finalp );S.n extlist:= merge(F. nextlist,makelist (n extquad);emit( j,);emit( succ , F.place ,-,课后答案网F.place);emit( j, , , F.quad);第九章P270- 9(1) 传名即当过程调用时， 其作用相当于把被调用段的过 程体抄到调用出现处， 但必须将其中出现的任一 形式参数都代之以相应的实在参数。A:=2

32、;B:=3;A:=A+1;A:=A+(A+B);print A;. A=9(2) 传地址 即当程序控制转入被调用段后， 被调用段首先把 实在参数抄进相应的形式参数的形式单元中， 过 程体对形参的任何引用或赋值都被处理成对形 式单元的间接访问。当被调用段工作完毕返回 时，形式单元(都是指示器)所指的实参单元就 持有所希望的值。 A:=2;B:=3;T:=A+B 把 T,A,A 的地址抄进已知单元 J1,J2,J3 x: = J1;y:=J2;z:=J3II把实参地址抄进形式单元，且 J2=J3 Yf :=y f +1Z f :=z f +x fIIYf:对 y 的间接访问Zf:对z的间接访问 p

33、rint AA=8(3) 得结果 每个形参均对应两个单元，第一个存放实参地 址，第二个存放实参值， 在过程体中对形参的任 何引用或赋值都看成是对它的第二个单元的直 接访问，但在过程工作完毕返回前必须把第二个 单元的内容放到第一个单元所指的那个实参单 元中 A:=2;B:=3;T:=A+B 把 T,A,A 的地址抄进已知单元 J1,J2,J3 x1:=J1;x2:=T;y1:=J2;y2:=A;课后答案网 http:IIz1:=J3;z2:=A; / 将实参的地 址和值分别放进两个形式单元中 y2:=y2+1; z2:=z2+x2;/ 对形参第二个单元的直接访问 x1 f:= x2; y1 f

34、:=y2; z1 f :=z2 / 返回、八前 把 第个 单 元 的 内 容 存 放 到 第 元 所 指 的 实 参 地 址 中 print AA=7(4) 传值即被调用段开始工作时， 首先把实参的值写进相 应的形参单元中， 然后就好像使用局部变量一样 使用这些形式单元A:=2;B:=3; x:=A+B y:=Az:=Ay:=y+1 z:=z+xprint AA=2过程调用不改变A的值第十章P306-1P306-2BiBZb4read A,BF:=1C:=A*AD:=B*BB Bif CvD goto lE:=A*AF:=F+1E:=E+FB2；b bwrite EhaltE:=B*BF:=F+2E:=E+FB3write Eif E100 goto L2haltB4L2:F:=F-1goto LiB5基本块为 Bi、B2、B3、B4、B5P307-4I:=1haltB2有回路，所以B2是循环，B2既是入口节点， 又是出口节点(1) 代码外提：不存在不变运算，故无代码外 提(2) 强度削弱：A:=K*I B:=J*I* +(3) 删除基本归纳变量：IV100可以用A100*K 或 B100*J 代替P307-5