编译原理_第三版_课后答案

编译 原理 课后题答案第二章P36-6(1)L(Gi)是09组成的数字串(2)最左推导:N n ND n NDD n NDDD n DDDD n 0DDD n 01DD n 012 D n 0127N n ND n DD n 3D n 34N n ND n NDD n DDD n 5DD n 56 D n 568最右推导:NnNDnN7nND7nN27nND27nN127nD127n0127N n ND n N4 n D4 n 34Nn ND n N8n ND8n N68n D68n568P36-7G(S)O t 113151719N t 21416181ODt0|NStO|AOA t AD | NP36-8文法：E t TIE + TIE - TTt F|T*F|T/FFt(E)Ii最左推导:E n E + T n T + T n F + T n i + T n i + T * F n i + F * F n i + i * F n i + i * i E n T n T * F n F * F n i * F n i *( E) n i *( E + T) n i *( T + T) n i *( F + T) n i *(i + T) n i *(i + F) n i *(i + i)最右推导:E n E + T n E + T * F n E + T * i n E + F * i n E + i * i n T + i * i n F + i * i n i + i * iE n T n F * T n F * F n F *( E) n F *( E + T) n F *( E + F) n F *( E + i)n F *( T + i) n F *( F + i) n F *( i + i) n i *( i + i)r t. / I . TS/rr/A* A* A* A* A* A* A* A* A* A* A* A* A* A*语法树：/*TFiFiii+i+i*1* *1*4* *4* *4* /xjx xtxxrxr /P36-9iii-i-iii+i*i句子 iiiei 有两个语法树：S n iSeS n iSei n iiSei n iiieiS n iS n iiSeS n iiSei n iiieiP36-10/ *A*A*A* *A* *A* *A* *A* *A* *A* *A* *A* *A* *A* *A*/S T TS I TT T (S )I()A* A* A* A A A A A A A A*4*4*4* /xrx xtx/P36-11/ *A*A*A* *A* *A* *A* *A* *A* *A* *A* A/ xrxr*4*4* / xrx xtx/第三章习题参考答案P64-71(01)*1010确定化: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,1 1最小化：0,1,2,3,4,5,60,123,4,5 =1,3,50,123,4,5 = 1,2,4,60,1,2,3,4,05,610,1,2,3,40 =1,3,50,1,2,3,40,5,60,1,2,30 =1,30,1,2,31=1,2,40,1,2,034,5,610,10 =1 0,11=1,22,300 =32,311 =40,10,2,3,4,51,6P64-8(1)(1| 0)*01(2)(1| 2|3| 4|5|6|7|8|9)(0|1| 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,b确定化：ab00,110,10,1110给状态编号：ab012112203333最小化：0,1,2,30,1 =1 0,1 =2 2,3a = 0,3 2,3 = 3 0,1,a2,3ba a(b)ab已经确定化了,进行最小化最小化：0,1, 2,3,4,50,1 = 10,1 = 2,4ab2,3,4,5 = 1,3,0,52,3,4,5 = 2,3,4,5ab2,4 = 1,0a3,5 = 3,5a2,4 = 3,5b3,5 = 2,4b0,1,2,4,3,50,1 = 1a2,4 = 1,0a3,5 = 3,5a0,1 = 2,4b2,4 = 3,5b3,5 = 2,4bP64 - 141最小化：0,1,2,30,1=02,3 = 1,3o0,1,2,30,1112,3 =311确定化：01X,1,Y1,Y21,Y1,Y221,Y给状态编号：01012112213333(1) 按照T,S的顺序消除左递归G( S)S T a lAl(T)T T STTt, ST I s递归子程序：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; Tend;procedure T;beginif sym=,then beginadvance;S; Tendend;其中:sym:是输入串指针IP所指的符号advance:是把IP调至下一个输入符号 error:是出错诊察程序(2)FIRST(S) = a，(FIRST(T) = a，(FIRST(厂) = , FOLLOW(S)=)，#FOLLOW(T)=)FOLLOW(厂) = )预测分析表a()#SS aS T人S T (T)TT T STT T STT T STT TT T, ST是LL(1)文法P81-2文法：E T TE EE T + E I 8T T FTTt T I 8F T PFF t *F I 8P T (E )1 a I b I人(1)FIRST(E) = (,a,bFIRST(E) = +, & FIRST(T) = (,a,bFIRST(T) = (,a,b，& FIRST(F) = (,a,bFIRST(F) = *, & FIRST(P) = (,a,bFOLLOW(E)=#,)FOLLOW(E)=#,)FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F) = (,a,b，+,),#FOLLOW(F) = (,a,b，+,),#FOLLOW(P) = *,(,a,b，+,),#(2)考虑下列产生式:E T+ E18Tt T18F t*F 18P T (E)1人I aIbFIRST(+E) HFIRST( & ) = + n& = FIRST(+E) n FOLLOW(E) = +n#,) = FIRST(T) nFIRST( & ) = (,a,b,ne = FIRST(T) n FOLLOW(T) = (,a,bn+,),# = FIRST(*F) nFIRST( & ) = * n & = FIRST(*F) n FOLLOW(F) = * n(,a,b，+,),# = FIRST(E) n FIRST(a) nFIRST(b) n FIRST)= 所以，该文法式LL(1)文法.(3)+*()ab#EE T TEE T TEE T TEE T TEEE T+ EE T8E T8TT T FTT T FTT T FTT T FTT，TtwTt TT tsT t TT t TT t TT tsFF t PFF t PFF t PFF t PFF，FJeF*f fFtsF tsF tsF tsF tsF tsPP t (E)P t aP t bP t人(4) procedure E; beginif sym= ( or sym= a or sym= b or sym=then begin T; E endelse errorend procedure E;beginif 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 endelse errorend procedure T;beginif sym= ( or sym= a or sym= b or sym= then Telse if sym=* then errorend procedure F;beginif sym= ( or sym= a or sym= b or sym=then 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=then advanceelse if sym=( then beginadvance; E;if sym=) then advanceelse errorendelse errorend;P81-3/ *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i*/(1) 是，满足三个条件。(2) 不是，对于A不满足条件3。(3) 不是，A、B均不满足条件3。(4) 是，满足三个条件。*i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* *i* /第五章P133 - 1E n E + T n E + T * F短语: E+T*F, T*F, 直接短语: T*F 句柄: T*FP133 - 2文法：S T alAl( T)T T T, SIS(1) 最左推导:S n(T)n(T,S)n(S,S)n(a,S)n(a,(T) n(a,(T,S)n(a,(S,S)n(a,(a,S)n(a,(a,a) S n(T,S)n(S,S)n(T),S)n (T,S),S)n(T,S,S),S)n(S,S,S),S)n(T),S,S),S) n (T,S),S,S), S) n (S,S),S,S),S) n (a,S),S,S),S) n (a,a),S,S),S) n ( a,a),A , S), S) n ( a,a),A ,( T), S) n ( a,a),A ,( S), S) n ( a,a),A ,( a), S) n ( a, a ),A ,( a), a)最右推导:S n (T) n (T, S) n (T,(T) n (T,(T, S) n (T,(T, a) n (T,(S, a) n (T,(a, a) n (S,(a, a) n (a,(a, a) Sn(T,S)n(T,a)n(S,a)n(T),a)n(T,S),a)n(T,(T),a)n(T,(S),a) n (T,(a), a) n (T, S,(a), a) n (T，人,(a), a) n (S，人,(a), a) n (T),A ,(a), a) n (T, S),a ,(a), a) n (T,a),a ,(a), a) n (S,a),a ,(a), a) n (a,a),a ,(a), a)(2)(a,a),(a),a)(S,a),(a),a)(T,a)，(a),a)O,(a),a)(!Tl,(a),a)(C,(a),a)(T,(a),a)(CUS,(a),a)(T,(a),a)(T,(S),a)(T,(T),a)(T,S),a)(IH,a)(S,a)(T,S)IT!S“移进-归约”过程：步骤 栈 输入串 动作0#(a,a),(a),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)#进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(=G 6是算符文法，并且是算符优先文法(2) 优先函数a()f44244g55523gag A()（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#success动作预备 进 进 归进进进归进进归归进归归进归P134 - 5(1)0. S jS4. S T AS -& A T S - A 9.(2)5.1. S T S -S TbA t SA -2. S T -AS6. S t b -10. A -T -a11.3. S T A - S7. A T SAA T a 确定化：SAab0,2,5,7,101,2,5,7,8, 10 2,3,5,7,10111,2,5,7,8, 10 2,5,7,8, 102,3,5,7,9,10112,3,5,7,102,4,5,7,8, 10 2,3,5,7,10112,5,7,8, 102,5,7,8, 102,3,5,7,9,10112,3,5,7,9,102,4,5,7,8, 10 2,3,5,7,10112,4,5,7,8, 10 2,5,7,8, 102,3,5,7,9,1011115: A T S - A S t - ASS tbA tSAA T abaA b1： A T a -2: S t b -baa3: S T S -A T S - AA tSAA T aS t ASS t b -0： S t-S S t-AS S t -b A t-SA A T -a4： S t A - S S t-AS S t -bA t-SAA T -a6: A T SA - S t A - S S t - ASS T-b A t-SAA T -a7： S t AS - A T S - A S t-ASS T-bA t-SAA T -aI = S0GO（ I ，a）=0GO（I ，b）=0GO（I ，S）=0GO（I ，A）=0GO（ I ，a）=3GO（I ，b）=3GO（I ，S）=3GO（I ，A）=3GO（ I ，a）=4GO（I ，b）=4GO（I ，S）=4GO（I ，A）=4GO（ I ，a）=5GO（I ，b）=5GO（I ，S）=5GO（I ，A）=5GO（ I ，a）=6GO（I ，b）=6GO（I ，S）=6GO（I ，A）=6GO（I7，a）=GO（I7，b）=GO（I7，S）=GO（I7，A）=DFA构造LR(O)项目集规范族也可以用GO函数来计算得到。所得到的项目集规范族与上图中的项目集一样:，S f AS，S Tb，A tSA，A a A f a = I1S, f b - =12S 不是SLR文法状态3， 6， 7有移进归约冲突状态 3：FOLLOW(S) = #不包含 a,b状态6： FOLLOW(S) = #,a,b包含a,b,；移进归约冲突无法消解 状态7： FOLLOW(A) = a,b包含a,b；移进归约冲突消解 所以不是SLR文法。 构造例如LR(1)项目集规范族 见下图： 对于状态5,因为包含项目A f ASa/b ，所以遇到搜索符号a或b时,应该用A f AS -，A f S - A，A tSA，A fa，S f AS，S fb = I3S f A S，S f AS，S f b，A f SA，A f a = I4A f a =I1S f b =I2AfSA， SfAS， Sfb， AfSA， Afa=IAfSA， Sf AS， SfAS， Sfb， AfSA，5 Afa=I6A f a =I1S f b =I2Sf AS， AfSA， SfAS， Sfb， AfSA， Afa=I7S f AS， SfAS， Sfb， AfSA， Afa=I归约。又因为状态5包含项目A fa a / b ，所以遇到搜索符号a时，应该移进。因此 存在“移进-归约”矛盾，所以这个文法不是LR(1)文法。4A f a =I1S f b =I2AfSA， SfAS， Sfb， AfSA， Afa=IAfSA， Sf AS， SfAS， Sfb， AfSA，5 Afa=I6A f a =I1S f b =I2Sf AS， AfSA， SfAS， Sfb， AfSA， Afa=I7 Sf AS， SfAS， Sfb， AfSA， Afa=I4A f a =I1S f b =I2AfSA， SfAS， Sfb， AfSA， Afa=IAfSA， Sf AS， SfAS， Sfb， AfSA，5 Afa=I6项目集规范族为 C= 11，12，13，14，15，16, 17 S、亠亡第六章/*第六章会有点难P164 - 5(1)Et El+T if (E1 .type = int) and (T.type = int ) then E.type := int else E.type := realEtTE.type:=T.typeT t num.num T.type := realTtnum T.type := int(2)P164 一 7S t L1|L2S.val:=L1.val+(L2.val/2 L2.length )StLS.val:=L.valLtLlBL.val:=2*Ll.val + B.val;L.length:=Ll.length+lLtBL.val:=B.c;L.length :=lBt0B.c:=0BtlB.c:=l*A* *A* *A* *A* *A* *A* *A* *A* *A* *A* *A* *A* *A* *A* *A* *A*J*4*4* /第七章P217 - 1a*(-b+c)a+b*(c+d/e)-a+b*(-c+d)-iA v -(C v -D)abc+*abcde/+*+abcd+*+A_i CD iv iv(A a B) v (iC v D)AB a C D v v(AvB)a(CviDaE)AB v CD E a v a辻 (x+y)*z =0 t hen (a+b) f c else afbfcxy+z*O二 ab+c f abc ft Y或 xy+z*0= Pl jez ab+c f P2 jump abc ftP1 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)+,a, b(2),(1),-(3)+,c, d(4)*,(2),(3)(5)+,(1),c(6)(4),(5)间接码表(1)(2)(3)(4)(1)(5) (6) 四元式序列:(1)(2)(3)(4)(5)(6)(7)+,+,*,+,+,TT54P218-4自下而上分析过程中把赋值句翻译成四元式的步骤:A:=B*(-C+D)步骤输入串栈PLACE四元式(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-(9)C+D)i=E*(-A-B-(10)+D)i=E*(-iA-B-C(11)+D)i=E*(-EA-B-C(12)+D)i=E*(EA-B- T(13)D)i=E*(E+A-B- T -(14)i=E*(E+iA-B- T -D1A-B- T -D(15)i=E*(E+E(16)i=E(EA-B- T(17)i=E*(E)A-B- T -c(18)i=E+E2A-B-T(19)i=EA- T 2(20) 3A产生的四元式：(,C,-,T)(+,T ,D, T )12(*,B, T , T )(:=,T3,2-,A3)3P218 -5(,C,-, T )1(+,T ,D, T )12(*,B,T , T )(:=, T ,2-,A3) 3/宽度为w=4设 A : 10*20, B、C、D： 20,T1:= i * 20T1:=T1+jT2:=A84T3:=4*T1Tn:=T2T3 /这一步是多余的T4:= i + jT5:=B4T6:=4*T4T7:=T5T6T8:= i * 20T8:=T8+jT9:=A84T10:=4*T8T11:=T9T10T12:= i + jT13:=D4T14:=4*T12T15:= T13T14T16:=T11+T15T17:=C4T18:=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, -,100)-真链链首假链106,104103真链：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.(jW, A,D, 111)110.(j, 100)111.(+,A,2, T2)112.(:=,T2,-, A)113.(j, 109)114.(j,100)P219-12/ *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* /(1)MAXINT - 5MAXINT - 4MAXINT - 3MAXINT - 2MAXINT - 1MAXINT(2)翻译模式方法1:for El :二 E2 to E3 do SS T F do MSiF T For I := E to E1 2I T idM T S T F do MS 1backpatch(S1.nextlist,nextquad);backpa tch( F.tr uelis t,M .quad);emit(F.place ：= F.place + 1);emit( j , F.place ， F.end ， M.quad);S.nex tlist :二 F.falselis t;F T For I ：= E to E 2F.falselis t:二 makelis t(nex tq uad);emit( j， E1.place ， E2.place ，0 ); emit(I.Place ：二El.place);F.truelist :二 makelist( nextquad);emit( j，-，-，-);F.place := I.place;F.end := E2.place;I T idp:=lookup(id.name);if p nil thenI.place := pelse errorM TM.quad := nextquad/方法2：s一forid:=E1toE2do S1s一F S1F一forid:=E1toE2doF T forid := EltoE 2 doINITIAL=NEWTEMP;emit( ：=, El.PLACE,-, INITIAL);FINAL=NEWTEMP;emit( ：=, E2.PLACE,-, FINAL);p:= nextquad+2;emit(j， INITIAL ， FINAL ， p);F.nex tlist:二makelis t( nex tq uad);emit( j，);F.place:=lookup(id.name);if F.place nil t hen emi t(F.place ： = INITIAL)F.quad:二nex tq uad;F.final:=FINAL;S FS1backpa tch(Sl.nex tlist, nex tq uad)p:=nextquad+2;emit(j ， F.place ， F.final , p );S.nex tlist :二 merge(F.nex tlist, makelis t( nex tq uad); emit( j,)；emit( succ, F.place -, F.place);emit( j, F.quad);第九章P270 - 9(1) 传名即当过程调用时，其作用相当于把被调用段的过程体抄到调用出现处，但必须将其中出现的 任一形式参数都代之以相应的实在参数。A:=2;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:=Jl;y:=J2;z:=J3 Y f :=y f +1Z f :=zf +xf/把实参地址抄进形式单元，且J2=J3/ Yf：对y的间接访问Zf：对z的间接访问print AA=8(3)得结果每个形参均对应两个单元，第一个存放实参地址，第二个存放实参值，在过程体中对形参的 任何引用或赋值都看成是对它的第二个单元的直接访问，但在过程工作完毕返回前必须把第二个单元的内容放到第一个单元所指的那个实参单元中A:=2;B:=3;T:=A+B 把T,A,A的地址抄进已知单元J1,J2,J3 x1:=J1;x2:=T;y1:=J2;y2:=A;z1:=J3;z2:=A;/将实参的地址和值分别放进两个形式单元中 y2:=y2+1; z2:=z2+x2;/对形参第二个单元的直接访问 xl f：=x2; yl f :=y2; zl f :=z2/返回前把第二个单元的内容存放到第一个单元所指的实参地址中 print AA=7(4) 传值即被调用段开始工作时，首先把实参的值写进相应的形参单元中，然后就好像使用局部变量 一样使用这些形式单元A:=2;B:=3;x:=A+By:=Az:=Ay:=y+1z:=z+xprint AA=2过程调用不改变 A 的值第十章P306-1P306-2read A,BF:=1C:=A*A B1D:=B*Bif C100 goto L2L2: f：=F-1goto L基本块为B、B、B、B、B12345P307-4B2有回路，所以B2是循环，B2既是入口节点，又是出口节点(1) 代码外提：不存在不变运算，故无代码外提(2) 强度削弱：A:=K*I B:=J*I*-+(3) 删除基本归纳变量：1100可以用A100*K或B100*J代替P307-5B2,B3是循环，B2是入口节点，也是出口节点(1) 代码外提：B:=J+1(2) 删除归纳变量