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

1、*/TFiFi1i+i*iP36-9句子iiiei有两个语法树：S => iSeS = iSei => iiSei = iiieiS => iS => iiSeS n iiSei = iiieiP36-10/个个个个个个个个个个个个S tTSTT-6)1()* JP36-11/个个个个个个个个个个个个个LI:S t ACA -» aAbabC > cC I sL2:SABAaA sB > bBc bcSABA T aAb 8BTaBbI £L4:SABA fOAlleB f1801 A* J第三章习题参考答案P64-7(1)0_liMl1

2、S 八 £101确定化: /01 -X7<i>(1,2, 34)<i>小1,2, 3)2, 32, 3, 42.32, 32, 3, 4(2, 3, 4) 3, 52, 3, 4(2, 3, 5)2, 32, 3,4, Y2, 3,4, Y) 3, 5)(2, 3, 4,)0,1,234,5, 6O23,4,5o = 1,3,5 0,1,234,5 = 124,60,234,5,6O23,4o = l,3,50,123,4,5,6O,l,2,3o = 1,3 0J,2,3 =1,2,40,l,2,34,5,6OJO = 1) 0=l，22,30 = 3 23,

3、 =40,l,2,3,4,5,6P64-8(1)(110)*01(2)(1I2I3I4I5I6I7I819)(0111 2131415 I 61 7 1819)*(01 5) I (01 5)(3)0*1(01 io4lf 11*0(01104l/P64 - 12(a)a确定化:ab00, 110,10, 1110小4)力给状态编号:ab012112203333最小化:a0,1,2,304=1 01=22,3= 0,3 2,3 = 3 。1，2,3最小化:0,1, 2,3,4,5)0内0=10上=2,42,345。= 1,3,0,52,3,4,5产2,3,4,52,4. = 1,02,4 =

4、3,53,5. = 3,53,5卜=2,40,1,2,4,3,5。" = 1 2,4. = 1,0 3,5 = 3,5。，虫=2,42,4 = 3,53,5 = 2,4P64 - 14(2):01(X,1,Y)1, Y>21,Y1, Y>221, Y>力6巾力给状态编号:01012112213333最小化:00,1,2,3O,l)o = l 2,3。= 1,3。，1，2,304)1 = 2(2,3), = 3P81-1(1)按照T,S的顺序消除左递归G'T tSTTf sr i£递归子程序： procedure S;beginif sym='

5、;a or sym=， then abvance else if sym=* (' then begin advance;!; if sym=')then advance;else error; end else errorend;procedure T;begins；rend;procedure Tf ； beginif sym=，,，then begin advance; s；rend end;其中：sym：是输入串指针IP所指的符号 advance：是把IP调至下一个输入符号 error：是出错诊察程序(2)FIRST(S) = a, ()FIRST(T) = a, ()

6、 FIRST ()= , £ FOLLOW (S) = ),# FOLLOW (T) = ) FOLLOW (T9 = ) 预测分析表aA()nsStciSf八Sf (T)TTfsrTsrTtST，VTiet f,sr是LL文法P81-2文法：E.TE，T t FTVTsF PF'FJ *F'IePf (E)lalbl 八(1)FIRST(E) = (,a,b/FIRST (E，) = +> e FIRST(T) = (,a,b, 1 FIRST(r)= G a,b/, £ ) FIRST(F) = (,a,b/ FIRST (F') = *,

7、 e FIRST(P)=(,a,b,1 FOLLOW(E)=#,) FOLLOW (EJ ) = #,) FOLLOW (T)=+,),# FOLLOW(V ) = +,),#) FOLLOW(F) = (, a, bj,+,),# FOLLOW (r) = (, a, b,+,),# FOLLOW(P) = *, (, a, bj,+,),#(2)考虑下列产生式：rTs*广|£P(E)lAkd/?FIRST (+E) n FIRST ( e ) = + A e = <1>FIRST (+E) A FOLLOW (E' ) = + n #,) 二 UFIRST (

8、T) AFIRSTC £)= (, a,b/Ae = <|>FIRST (T) A FOLLOW (丁)二(, a, bj n +,), #二小FIRST (*F，) n FIRST ( e ) = F £ = FFIRST (*F') n FOLLOW (F')二住 C (, a, b，+,),#二 <1)FIRST (E)n FIRST (a) n FIRST (b) Cl FIRST 0=6 所以，该文法式LL文法.(3)+*()abAnEEtTE'EtTE'EtTE'EtTE'E'E'

9、t+ETTtFTTtFTTfFTTfFTrr fT7 £r tTr fTr tTFFPF'FfPF'FfPF'Ft PF'F'F'F'F'f£F'f£F' fgF'F'pPf(E)P - ClPfbP->A(4) procedure E; beginif sym=(or sym=，a' or sym=' b' or sym=， then begin T; E' end else error endprocedure E;begini

10、f sym='+'then begin advance; E endelse if sym<')' and sym<>'#' then error endprocedure T;beginif sym=' (' or sym=，a or sym=' b' or sym=' then begin F; T end else errorendprocedure T;beginif sym=(or sym=，a or sym=' b' or sym二 then Telse if

11、sym='*' then errorendprocedure F;beginif sym=(or sym=，a' or sym=' b' or sym= then begin P; F' end else errorendprocedure F'beginif sym=,*，then begin advance; F' endendprocedure P;beginif sym=' a or sym=，b' or sym=' then advance else if sym二(then beginadvan

12、ce; E;if sym=，)' then advance else errorendelse error end;P81-3/个个个个个个个个个个个个个个个(1)是，满足三个条件。(2)不是，对于A不满足条件3。(3)不是，A、B均不满足条件3。(4)是，满足三个条件。* /'第五章P133 - 1E n E+TnE+T*F短语：E+T*F, T*F,直接短语：T*F句柄：T*FP133-2文法：S -。1八1() rfns(1)最左推导：S =(r)=(r,S) = (S,S) = (a,S) = (a,(r)n(a,(7S) = (a.(S.S)n(a.(a,S)=(a,

13、(。) 5 = (T,S) = (S,S) = (T),S) = (r,S),S) = (7;S,S),S) = (S,S,S),S) = (),S,S),S) =(T,S),S,S),S) = (S,S),S,S),S)=(4 S),S,S),S) => (Sm),S,S),S)=(4M)J ,S),S) = (a,a) J ,(r),S) = (GM),八,(S),S) = (m) J,(a),S)= (nM)J,(n),a)最右推导：S => (T) n (T,S) => (T,(D) =>(r,(rS) = (/)=> (T,(S,a) = (T,(

14、71;,«) => (S,(a,a) => (a, (a, a)S => (T,S) => (T,a) => (5,a) = (T)m) = (T,S),)=> (T,(T)m) = (T,(S),a) =(T,(a)M)=> (T,S,(a),a) = (TJ ,(“),)=> (S,A,(«)>«) => (T),A ,(),“) => (r,S),3(a),a) = (Tm)J ,(a)M)=> (Sm),a ,(),.) => (a,a),A ,(4),“) (2) (a. a)

15、/, (a), a) ( a), (a),a) (T,a)/, (a),a) (LS，(a),a) (CT)./, (a), a) (S, (a),a) (T, (a), a)(LS, (a), a)(T, (a), a) (T, (S),a) (T, (T),a) (L_S)，a) (垃,a) (S, a) (T,S) (T)S“移进-归约”过程：步骤 栈 输入串 动作0#(&, a), ", (a), a)# 预备1 #(2,a), ", (a), a)#进2 #(旦,a), ", (a), a)#进3 #(5 a) J, (a), a)# 进4 #(

16、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#(1)J, (a), a)# 进12#(SJ, (a), a)# 归13#(TJ, (a), a)# 归14#(CT,", (a), a)#进15#(cr,(a), a)#进16#(T,S,(a), a)#归17#(T,(a), a)#归18#(T,(a), a) #进19#(T,(a), a) #进2

17、0#(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>>A>>(<<<<)>>

18、f<<<>>Ge是算符文法，并且是算符优先文法#(a, (a, a) #预备#(a,(a, a)#进#(a,(a, a)#进#(t,(a, a)#归# (t, n (t,( # (t, (a # (t, (t # (t, (t,(a, a) #进a, a) U进,a) #进,a) n归a) #进# (t, (t, a # (t, (t, s # (t, (t # (t, (t) # (t, s # (t n (t ) # s)#进)#归)#归)#进)#归)#归#进#归successP134 - 50. S'f s1. S' > S 2. S

19、>3. S > A S4. Sf AS 5. Sf b6. s > b -i. A > 9SA8. A > S , A 9. A > SA -10. A fa11. Af c八优先函数aA()f44244g55523SAab(0,2, 5, 7, 10)1,2, 5, 7, 8,10 )2, 3, 5, 7, 101161,2, 5, 7, 8, 10 )2, 5, 7, 8, 102,3, 5, 7,9, 10 116(2, 3, 5, 7, 10)2,4, 5, 7, 8, 10 )2, 3, 5, 7, 101162,5, 7, 8, 102, 5,

20、7, 8, 102,3, 5, 7,9, 10 1162,3, 5, 7, 9, 10)2, 4, 5, 7, 8, 10 (2, 3, 5, 7, 101162,4, 5, 7, 8, 10 )2, 5, 7, 8, 102,3, 5, 7,9, 10 11611<t)4)<l><l>6<t)4)<l><l>A1s13：S'f SA fSA Af型A f SASS f /s5: Af S A S f AS S3b ASA A >4A6：ASA- Sf AS S f AS S-b ASAab一bA-ra 4SasaA1A

21、飞AtOSf6 S fAS S-b AtSA A a A4: S > A - S S fAS S-bA->型S7:SfAS-A fSA S fAS S-bb1 '1a4 f aA > 1A > 6i确定化:构3LR(O)项目集规范族也可卜用Ho驾经计算得到所得到而目集规范族和上WI的*01：S' tS,#A fSAa/bASAa/bA t aa/bSr ASa/bS -ba/by5:A f SA , a/b8：S fa/bSAS a/bS f AS a/bS f 4S a/bS T b a/bS -b a/bA SA a/bA f SA a/bA faa

22、/bA faa/b项目集一样:二S' fS9 S >9 AS, S > ,b,A > 取，A fa G0(/。，a) = yA. > Cl = /jG0(/0,b) = S > 1>二GO(Zo,S) = S'>S，A>S A,A > 'SA , A > 'Ci,SfAS, STb 二 lG0(/。，A) = S > A S , S > 'AS,S > 9b, A > S4 ,A fa 二 /4GO(Z3,a) = ./A > ci = / go(z3,b) = S

23、 >-/?GOU3,S) = A>S.A, S> uAS »S > ,b, A > S4 ,A f a 二 4GOU3,A) = A > SA > 9 S > 4 , S ,S > , AS, S >，b,A > '5?1, A > uci= /6GON，a) = ./V > ci = / 1G0(/b) = S > 1>二 ,G0(Z4,S) = S > AS , A > S A .S >9 AS, S > ub .A > 9SA . A > a )

24、= /7GOTA) = S > A S , S > 'AS,S > ,b, A.> S4 ,Afa"/4GOq,a) = yA. > Cl = / 1GO(A，b) = S >=GOq,S) = A>SA, S> , AS *S >，b, A > 'SA ,A>a = l5GO(Z5,A) = A > SA , S > A , S ,SfAS, S b,A > uSA 9 A > ci二4Goq,a) = yA. > Cl ) /1go(/6,b) = S 二 /)一go(

25、/6,S) = S > AS , A > S , A，S > , AS» S > b,A > '5?19 A > uci=go(/6,A) = S > A , S , S > ,AS,S > /7, A > 'SA ,A f二乙go(/7,a) = yA. > Cl = / 1go(/7,b) = S >二 ,)go(/7,S) = A f SA, S > AS，S > ab 9 A > 'SA ,二 4go(/7,A) = A > SA , S > A ,

26、S ,Sf AS, S b,A.> ,S4 , A > ,a 二，6项目集规范族为c=/,八，/4, /5, /6, 77不是SLR文法状态3, 6. 7有移进归约冲突状态 3： FOLLOWS ) = #不包含 a,b状态6： FOLLOW(S)=礼a, b包含a, b,：移进归约冲突无法消解状态7： FOLLOMA)=a,b包含a,b；移进归约冲突消解所以不是SLR文法。(4)构造例如LR(1)项目集规范族见下图：对于状态5,因为包含项目A fAS-4/口，所以遇到搜索符号a或b时,应该用Af AS 归约。又因为状态5包含项目A -« a/,所以遇到搜索符号a时，应该

27、移进。因此 存在“移进-归约”矛盾，所以这个文法不是LR(1)文法。/*第六章会有点难P164 - 5(1)E>E1+T if (El. type = int) and (T. type = int ) then E. type := int else E. type := realE>TE. type := T. typeT > num. num T. type := realT > numT. type : = intP164 一 7S f Ll L2 S. val: =L1. val+ (L2. val/2 L letlRlh)S>LS. val:=L. v

28、alLf LIB L. val:=2*Ll. val + B. val;L. length:=L1. length+1L fBL. val:=B.c;L.length :=1Bf 0B. c:=0Bf 1B. c:=l*/第七章P217 - 1a*(-b+c) a+b* (c+d/e) - a+b* (-c+d)u4 v i(C v I。)abc+*abcde/+*+ abcd+*+A-CD v v(A aB)v(iCv£>)(A v 8)八(C v 1£) a E)AB7 CD (§>£ a v aif (x+y) *z =0 then (

29、a+b) t c else a t b t c xy+z*0= ab+c t abc t t ¥或 xy+z*0= Pl jez ab+c t P2 jump abc t tP217 - 3-(a+b)*(c+d)-(a+b+c)的 三元式序列：1/ 12 3 / / /+, a, b(1),-+, c, d*, (2), (3)5 6/ /+, a, b+, (5), c(4), (6)间接三元式序列： 三元式表：(1) +, a, b(2) (1), 一(3) +, c, d(4) *, (2), (3)(5) +, (1), c(6) (4), (5)间接码表：(1)(2)K)

30、/3 4 15 6 zr zf z< / /四元式序列:JZ XJZ JZ JZ JZ 1 2 3 4 5 6 7 z /( /( / /P218-4自下而上分析过程中把赋值句翻译成四元式的步骤:A:=B*(-C+D)步骤输入串栈PLACE 四元式(1)A:=B* (-C+D):二B*(-C+D)iAB* (-C+D)iA-*(-C+D)i=iA-B*(-C+D)i=EA-B*(-C+D)i=EA-BXJZ 7 8 9 /f /fw )+ D X7 c + D (-YC+BA-7 lx /(11)+D)i=E*(-EA-BCC, T)1(12)+D)i=E*(EA-B T1(13)D)i

31、=E*(E+A-B T(14)i=E*(E+iA-B Z -D(15)i=E*(E+EA-B-D(+, T., D，八) 1M(16)i=E(EA-B T、 A-B T；-A-B-7F(20) A(17)i=E*(E)(18)i=E+E(*,B, T2, TJ(19)i=E(:二，T,-, A)产生的四元式：J7 XJr)T2T3,a)询,C, -，(+, T, D, (*, B, T2, (:二,外,一P218 - 5/*设 A ： 10*20, B、C、D： 20,宽度为 w=4 则Tl:=i*20Tl:=Tl+jT2:=A-84T3:=4叮 1Tn:=T2T3 这一步是多余的T4:=i+

32、jT5:=B-4T6:=4*T4T7:=T5T6T8:= i * 20T8:=T8+jT9:=A-84T10:=4*T8Tll:=T9T10T12:=i+jT13:=D-4T14:=4*T12T15:=T13(T14T16:=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,一, 106)106. (jnz, D, 104)一假链链首107. (j,

33、 -，100) 一其链链首假链:106,104, 103) 真链：107, 100)P218 - 7100. (j<, A, C, 102)101. (j, 一, 0)102. (j<f B, D, 104)103. (j, 一, 101)104. (j= A, T' , 106)105. (j, 一，109)106. (+, C, T' , Tl)107. (:= Tl, 一，0108. (j,100)109. (jW, A, D, 111)110. (j,100)111. (+, A, '2' , T2)112. (:= T2, -，A)113.

34、 (j,109)114. (j,- 100)P219 - 12/ <Tw TwTwTw <Tw(1)MAXINT - 5MAXINT - 4MAXINT - 3MAXINT - 2MAXINT - 1MAXINT(2)翻译模式方法1：for El := E2 to E3 do SS f/doMS1F t For / := Ex toE2I t idM T£S » F do A/S'jbackpatch(Sl. next list, nextquad);backpatch(F. truelist, M. quad);emit (F. place '

35、：='F. place ' + ' 1);emit ( ' j«, ' F. place ' F. end ； M. quad);S. nextlist := F. falselist;)F > For I := E to E、 F. falselist := make 1 ist (nextquad);emit( 'j>, ' El. place ' E2. place 0'); emit (I. Place ':二'El. place);F truelist := make

36、list(nextquad);emit ( 4 j,;F place ：= I.place;F. end ：= E2. place;I fidp：=lookup(id. name);if p <> nil thenI.place := pelse error)M. quad ：= nextquad)方法2：S-* for id:二El to E2 do SIS F SIF-* for id:=El to E2 doF f fond := EUoE2 doINITIAL=NEWTEMP;emit(EL PLACE', -，' INITIAL);FINAL=NEWTEM

37、P;emit(E2.PLACE', -，' FINAL);p：= nextquad+2;emit( 'j INITIAL ' FINAL',' p);F nextlist：=makelist(nextquad);emit( ' j,一,一,');F. place ： =lookup (id. name);if F. place nil thenemit(F. place ='INITIAL)F.quad：=nextquad;E final:=FINAL;)SfFSbackpatch(Sl. nextlist, nextquad) p:=nextquad+2;emit ( 'j , F. place ' F. final ' p );S. nextlist := merge(F. nextlist, makelist(nextquad); emit( ' j,一,一,')；emit( 'succ,' F.