编译原理第三版课后答案

1、编译原理_第三版课后答案编译原理课后题答案第二章P36-6(1)是(T9组成的数字串(2)最左推导：NaNDa NDD => NDDD => DDDDaODDD => OIDD => 012Z) => 0127N a NDa DDa3D = 34N a NDa NDDn DDDaDDa56Da 恋最右推导：NaNDaNg ND7 => 227 => ND21 =>127 => D127 => 0127N => ND => N4 => Z)4 => 34N a NDn Ng NDS => N68 =>

2、 D68 => 568P36-7GG)Ot1|3|5 卩 |9Nt2|4|6|8|ODtO|NStOAOAADNP36-8一/ 节 4 * FT TFz(v最左推导：E=>E + T=>T+T=>F + T=>/ + 7'=>z + T*F=>/ + F*F=>f + f*F>z + z*f E=>T=>T*F=>F*F=>/*F=>z*(E)=>z*(E + T)=>z*(T+T)=>/*(F + T) =>/*(f + T)=>/*(f + F)>/*(/ + /

3、)最右推导：£=>E + T=>£ + T*F=>E + 7'*/=>E + F*/=>£ + /*/=>7' + z*/=>F + /*z>/ + /* £=> 7'=>F*T>F*F=>F*(E)=>F*(E + T)=>F*(£ + F)>F*(£ + /) =>F*(T + /)=>F*(F + /)=>F*(/ + O>/*(/ + /)语法树:/ *编译原理_第三版课后答案P36-11T

4、FFFTFi i 111Fi1i+i*iFi1i+i+iP36-9句子iiiei有两个语法树:S n iSeS n iSei => iiSei n iiiwiS n iS => USeS => iiSei n iiieiP36-10S TSTTt(S)|()编译原理_第三版一课后答案L1:SACA t aAbabC t cC | £L2:St ABA aAsBibBc'bcL3：SABA -> aAb eBt aBb | sL4:SABA t 0A11 eB T1B0|4/*第三章习题参考答案P64-7Q_MuoiQ(1)编译原理_第三版_课后答案P6

5、4-81101确定化:01X4>1,2, 3<1>4><1>1,2, 32, 32, 3, 42, 32, 32, 3, 4(2, 3, 4(2, 3, 52, 3, 4(2, 3, 52, 32, 3, 4, Y2, 3,4, Y(2, 3, 52, 3, 4,100111最小化:0 丄2,345, 60 丄2,345° = 135 0 丄 2,345 = 12460 丄 2,3你5, 60 丄 2,3,4。= 1,3,50 丄 2,3, 4, 5, 60 丄 2,3。= 1,30 丄 2,3 = 1,2,40,1,2,34,5,6 叫=1 0,

6、1 = 1,2230 = 3 2,3】 = 40,1,2,3,4,5,60010010111编译原理_第三版课后答案(110/01(2)(l|2|3|4|5|6|7|8|9X0|l|2|3|4|5|6|7|8|9)*(0|5)|(0|5)(3)0*1(0 110+1)* 11*0(0110*1)*P64 - 12(a)a, b确定化:ab00,110,1(0, 1110<l><|)<|)给状态编号:ab012112203333最小化:0,1, 2,30也=1 0厂22,3打=03 23, = 30,1,3aabbbbaabaabbaaa已经确定化了，进行最小化最小化:编

7、译原理_第三版_课后答案0,1, 2,3,4,5OJL = 10,1严2,42,3,4,5. = 1,3,0,52,3,4,5. = 2,3,4,52,4“ = 1,02,4严3,53,5“ = 3,53,5. = 2,40,1,2,4,3,5OJL = 12,4“ = 1,03削=3,50J厂 242,4严3,53,5. = 2,4bba=. AabaP64 - 140(2):确定化:01X, 1, Y1,Y(21,Y1,Y(2(21,Y<l><|)<b给状态编号:010121122133330编译原理第三版 课后答案101110最小化：0,1, 2,30,1。= 1

8、 0,1, = 22,3。= 1,32,3】 = 30J,，0111=« A00P81 - 1第四章(1)按照T,S的顺序消除左递归编译原理_第三版课后答案GQ)StgFI(T)T ST'厂t,S厂|w递归子程序：procedure S;beginif sym二，a，or sym"then abvanceelse if sym二'('then beginadvance;T;if sym=)' then advance;else error;endelse errorend;procedure T;beginS；end;procedure ;b

9、eginif sym二,then beginadvance;S；endend;其中：sym:是输入串指针IP所指的符号advance:是把IP调至下一个输入符号error :是出错诊察程序FIRST(S) = a, (FIRST(T) = a, (FIRST () = ,FOLLOW (S)二),#FOLLOW (T) = )FOLLOW () = )预测分析表a-()9sS t aS"St(7)TtstTSTTiSTVTier是LL(1)文法P81 -2文法：E TE'E' ->+EeTtFT'r tsF T PF'F'T*F'

10、|gP t (E) | a | b |人编译原理_第三版_课后答案FIRST (E) = (, a, b, 3FIRST (E，) = +, e FIRST (T) = (, a, b, 3FIRST(T) = (,a,b，£ FIRST (F) = (, a, b, 3FIRST(F')二*, e FIRST (P) = (, a, b, 3FOLLOW (E) = #,)FOLLOW(E ) = #,)FOLLOW (T)二+,),#FOLLOW(T')二+,),#FOLLOW(F) = (, a, b, ",+,),#FOLLOW(F')二(,

11、 a, b, +,),#FOLLOW(P)二*, (, a, b, +,),#考虑下列产生式:(2)编译原理_第三版课后答案(4)E J+E|wrr£尸 J*F|wPT(E)F|a|bFIRST (+E) A FIRST ( e ) = + A e = *FIRST (+E) Cl FOLLOW (E，)二+ Q #,)二 4)FIRST(T) nFIRST( e ) = (, a,b/ A e = 4>FIRST (T) A FOLLOW (T')二(, a, b, J Q +,), #二 4)FIRST (*F,) A FIRST ( e )二* A e = 4)F

12、IRST(*F') QFOLLOW(F')二* A (, a, b, +,),# = 4>FIRST (E) A FIRST (a) A FIRST (b) A FIRST 0 = 4)所以，该文法式LL(1)文法.+*()ab4#EEtTE'EtTE'Et7E'EtTE、E'EJ+EEJeEJwTTtFTTtFTTtFTTtFTT，TT TT »T TTJTT TT 8FF PF'FtPF'F PFFtPFF'FJsFJwFJeFJwFtsFtwpPt(E)PmPTbP"procedure E;

13、beginif sym二'C 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 error endprocedure T;beginif sym二'C or syma， or symb or sym编译原理_第三版课后答案then begin F; T endelse errorendprocedure T ;begin

14、if sym二'C or sym=，athen Telse if sym二'thenendprocedure F;beginif sym二'C or sym=，a then begin P; F' end else errorendor sym=，b or svm=，erroror sym=，b or sym=，procedure F，;beginif sym二'*'then begin advance; F endendprocedure P;beginif sym二'a or sym=，b or sym二'then advan

15、ceelse if sym二'('thenbeginadvance; E;if sym二then advanceelse errorendelse errorend;编译原理_第三版课后答案P81 -3/(1)是，满足三个条件。(2)不是，对于A不满足条件3。(3)不是，A、B均不满足条件3。是，满足三个条件。/第五章P133-1EdE+TdE+T 汰 F短语：E+T*F, T*F,直接短语：T*F句柄:T*FP133-2文法：StgFI(T)TT,SS最左推导：S => (T)=> S) => (S,S) => (a,S) => (a,(O) =

16、> (a,(7S) => (a,(S,S) =>S) => («,(«,«)S => (T,S) => (S,S) => (T),S) => (T,S),S)=> ( 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)=> (“,“),人,S),S) =>,(7J),S) => (<),a,(S)

17、,S) => (a,a)T,(a),S)=> (a,a),人,(a),a)最右推导：S n (T) => (T,S) n (T,(T) => (T,(T,S) n (T,(T,a) n (7；(S,a) => (T,(«,«)=> (S,(aQ) => a(a,a)s n (T,s)=> (T,a) n (S,a) => (T),a) => (T,S),a) n (7(T),a) => (T,(S),a)=> (),。)=> (T,S,(a),a) n (人，),a) => (SQ,(a),

18、a) n (7V，(a),a) => (T,S),A,(a),a) n (7»Q,(a),a) => (S,a),A,(«),«) n ( d)Q,(a)Q(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

19、#(a, a)/, (a), a)# 预备1 #(a, a), (a), a)# 进2 #(a, a), ", (a), a)# 进3 #(a, a), ", (a), a)# 进4 #(a,a), (a), a)# 进#(s#(T#(?#(T,a#(ps10 #(T11 #(T),a)，J (a)，a)#J5,a)，J (a)，a) #sa)v J (a)L a)#)> (a)L)#)(a)L)#->-(a)L a)#12 #(s13 #(T14 #(p15 #(T16 #(ps17 #(T18 #(?19 #(?(20 #(T(a,J (a) )：)#

20、69; .J (a)La)# a J (a)L a)#“ (a)La)#(a)9 a)#,(a)La)#(a)a)#st a)9 a)#)1)#fff毎 fff编译原理_第三版一课后答案#(T, (S),a)#(T, (T),a)#(T, (T)#(T,S#(T),a)#(T),a)#(S,a)#(T,a)#(T,#(T,a)#进#(T,S)#归#(T)#归#(T)n进#S#归进归归进归归进2122232425262728293031323334P133-3编译原理_第三版一课后答案FIRSTVT(S)二a, ： (FIRSTVT(T)二 (LASTVT(S)二&，)LASTVT(T)

21、 = ,a, ：)a4()9a>>a>>(<<<二<)>><<<>>是算符文法，并且是算符优先文法(3)优先函数栈输入字符串动作(4)编译原理_第三版课后答案# (a, (a, a) ) #预备#(a, (a, a) #进#(af (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 ) #进

22、编译原理_第三版_课后答案# S#归successP134-..9.10.11.SASaASA3确定化:SAab0,2,5, 7, 101,2, 5, 7,8, 102, 3, 5, 7, 101161,2, 5, 7, & 102, 5, 7,&102, 3, 5, 7, 9, 101162, 3, 5, 7, 102, 4, 5, 7, 8, 102, 3, 5, 7, 101162, 5, 7, & 102, 5, 7,&102, 3, 5, 7, 9, 101162, 3, 5, 7, 9, 10 2, 4, 5, 7, 8

23、, 102, 3, 5, 7, 101162,4, 5, 7, 8, 10 2, 5, 7,&102, 3, 5, 7, 9, 10116114)4)4)4)6eASSa AS bSAbaA4：St4SSJS Sb ASA7：StASAssSTbAciDFA构造LR(O)项目集规范族也可以用GO函数来计算得到。所得到 的项目集规范族与上图中的项目集一样：二， , , , G0(, a) G0(, b) = =G0(, S) = ,二GO(, A) , , , , G0(,a) = 二G0(,b) = 二G0(,S) = , , ,二G0(,A) = , , ,二G0(,a) = 二G0

24、(,b) = 二G0(,S) = , , ,二G0(,A) = , , ,二G0(,a) = 二G0(,b) = 二G0(,S) = , , ,二G0(,A) = , , ,二G0(,a) = 二G0(,b) = 二G0(,S) = , , ,二G0(,A) = , , ,二G0(,a) = 二G0(,b) = 二G0(,S) = , , ,二G0(,A) = , , ,二项目集规范族为C二(3)不是SLR文法状态3, 6, 7有移进归约冲突状态 3： FOLLOW (S, ) = #不包含 a,b状态6： FOLLOW(S) = #, a, b包含a, b,；移进归约冲突无法消解状态7： F

25、OLLOW(A) = a, b包含a,b；移进归约冲突消解所以不是SLR文法。(4)构造例如LR(1)项目集规范族见下图：对于状态5,因为包含项目,所以遇到搜索符号a或b时，应 该用归约。又因为状态5包含项目,所以遇到搜索符号a时，应该 移进。因此存在“移进-归约”矛盾，所以这个文法不是LR(1)文法。bbbAAA1:SJS#AS-Aa/bASAa/b4 Tda/bSt ASa/bSiba/b5：4tS4 a/bSt4Sa/bSt4Sa/bS >ba/bA > SAa/bA T Cla/b8：St ASa/bSt4Sa/bS > /?a/bASAa/bA T Cla/bSaa

26、SSaS9：St4S a/ba/ba/ba/bSt4Sa/bS ba/b编译原理_第三版_课后答案5：SAbaaSbb2：7：St4S/a/bSt4S #/d/bSt AS阳a/bASAa/bS t b阳a/ba/bASAa/bA taa/bA-aa/bSt4Sa/bSiba/bA10：S Tb ci/b编译原理_第三版_课后答案第六章P164-5(1)EE1+T if (El .type = int) and (T. type = int ) then E. type :二 intelse E. type :二 realET E. type :二 T.typeTnum. num T. typ

27、e := realTnumT.type :二 int(2)P164-7SL1|L2 S.val:=L1. val+(L2. val/2)SL S. val:=L. valLL1B L.val:=2*L1. val + B.val;L. length:二LI. length+1LBL. val:二B c;L. length :二 1BOB. c:二0BlB. c:二1第七章P217-1a* (一b+c)a+b* (c+d/e)abcde/+*+_a+b* (-c+d)u4 v (C v D)(A a 5) v (-iC v D)ACDi v vAa CD vv(A v 5) a (C v iD

28、a E)A5vCDEa v aif (x+y)*z =0 t hen(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 tPl P2P217-3-(a+b)*(c+d)-(a+b+c)的三元式序列：(1)+, a, b(2), (1),-(3)+, c, d*, (2), (3)(5)+, a, b(6)+, (5), c-，(4), (6)间接三元式序列三元式表：(1)+, a, b(2), (1),-(3)+,c, d*,(2),(5)+,(1),C(6)-,(

29、4),间接码表：(1)(2)(3)(4)(1)(5)(6)四元式序列:(1)+, a, b, +, c, d, *, +, a, b, +, , c,一，P218-4自下而上分析过程中把赋值句翻译成四元式的步栈PLACE 四元式骤:A:二B*(-C+D)A:二B*(-C+D):二B*(-C+D)iAB*(-C+D)i:=A-*(-C+D) 1 :=1A-B*(-C+D)i:=EA-B*(-C+D)i:=EA-B(7)(-C+D)i:=E*A-B-C+D)i:二E*(A-BC+D)i:二E* (-A-B(10)+D)i:=E*(-i A-B-C(11) +D)i:二E*(-E A-B-C(12)

30、 +D)i:二 E* (EA-B步骤输入串(, C, -，)编译原理一第三版_课后答案(13) D)i:=E*(E+ A-B-(14) )i:=E*(E+i A-B-D(15)i:二E*(E+EA-B-D(16) )i:二E (EA-B(17)i:=E*(E)A-B(18)i:=E+EA-B-(*, B,)(19)i:=EA-(：=,_, A)(+, DJ(20) A产生的四元式:(, C,)(+，、D,)(*, B,)(r 一，A)P218-5设 A : 10*20, B、C、D： 20,宽度为 w=4 则T1:二 i * 20T1:二Tl+jT2:=A-84T3:二4*T1T4:= i +

31、 jT5:=B-4T6:二4*T4T7:二T5T6T8:= i * 20T8:二T8+jT9:二A-84T10:二4*T8Tll:=T9T10T12:= i + jT13:=D-4T14:二4*T12T15:= T13T14T16:二T11+T15T17:二C-4T18:二4*T16编译原理_第三版_课后答案T19:=T17T18T20:二T7+T19Tn:二T20P218-6100.(jnz, A, -, 0)101.(j, -, -, 102)102.(jnz, B, -, 104)103.(j, -，-，o)104.(jnz, C, -, 103)105.(j, -, -, 106)10

32、6.(jnz, D, -, 104)-假链链首107.(j, -, -, 100)-真链链首假链：106,104, 103真链：107,100100.(j，A, C, 102)101.(j,0)102.(j,B, D, 104)103.(j,101)104.(j 二,A,106)105.(j,109)106.(+,C, S Tl)107.(:二,Tl, ", C)108.(j,100)109.(jW,A, D, 111)110.(j,100)111.(+,A,T2)112.(:二,T2,A)113.(j,109)114.(j,-100)P219-12编译原理_第三版_课后答案(1)M

33、AXINT - 5MAXINT - 4MAXINT - 3MAXINT - 2MAXINT - 1MAXINT(2)翻译模式方法1：for El := E2 to E3 do SS FdoMS】F > For / := E、to E21 idM T£backpatch(SI. nextlist, nextquad);backpatch(F. truelist, M. quad);emit(F. place ":二'F. place ' + ' 1);emit( ' j, ' F place S F end S M. quad);

34、S. nextlist :二 Ffalselist;F. falselist:二 makelist(nextquad);emit( 'j>, ' El. place "， E2. placeemit(I. Place ':二'El.place);F.truelist :二 makelist(nextquad);emit ( ' j,-，-')；F place :二 I. place;F. end :二 E2 place;p:二looku);if p > nil thenI. place :二 pelse errorM. qu

35、ad :二 nextquad1%x T%/方法2：S* for id:二El to E2 do SIS- F SIF* for id:二El to E2 dodoINITIAL二NEWTEMP;emit(':二，'El.PLACE' ,-，' INITIAL):FINAL=NEWTEMP;emit(':二，'E2. PLACE' ,-，' FINAL);p:= nextquad+2;emit( 'j ， INITIAL ', ' FINAL ' ,' p);F.nextlist:二makelist(nextquad);emit( ' j,');F.place:=looku);if F. place nil thenemit(F. place 二'INITIAL)F quad：二nextquad;F.final:=FINAL;StFSIbackpatch(S1. nextlist, nextquad)p:二nextquad+2;emit( 'j , F. place "， F. final , p );S.nextlist :二 merge(Fnextlist, makelist(nextquad);emit( ' j, 一