编译原理第三版课后习题集答案解析

《编译原理第三版课后习题集答案解析》由会员分享，可在线阅读，更多相关《编译原理第三版课后习题集答案解析（26页珍藏版）》请在装配图网上搜索。

1、 目录P36-61P36-71P36-81P36-92P36-102P36-112P6473P6484P64124P64146P8117P8128P81311P133111P133211P133313P134514P164518P164718P217118P217319P218419P218520P218621P218721P2191221P270923P36-6(1)是09组成的数字串(2)最左推导:最右推导:P36-7G(S)P36-8文法：最左推导:最右推导:语法树：/*/P36-9句子iiiei有两个语法树：P36-10/*/P36-11/*L1:L2:L3:L4:*/第三章习题参考答

2、案P647(1)XYX1234Y5 0 1 1 0 1 1确定化：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, 0320 1 01 0 0 1 1 0654 0 1 0 1 1 1最小化： 002 1 1 0 0 1 0543 0 1 0 1 1 1P648(1) (2)(3)P6412(a) a10 a,b a确定化：ab00,110,10,1110给状态编号：ab012112203333 a10 a a b b b32 b a最小化： a a210 b ba b(b)032

3、b b a a b a a b541 b a a a已经确定化了,进行最小化最小化：021 b b a a baP6414 (1) 010 1 0(2):YX2 0 1Y1X 0确定化：01X,1,Y1,Y21,Y1,Y221,Y给状态编号：01012112213333 010 0 1 032 1 1 1 0最小化： 0310 1 1 1 0 0第四章P811(1) 按照T,S的顺序消除左递归递归子程序：procedure S;beginif sym=a or sym= then abvanceelse if sym=( then beginadvance;T;if sym=) then ad

4、vance;else error; endelse errorend;procedure T;beginS;end;procedure ;beginif sym=, then beginadvance;S;endend;其中:sym:是输入串指针IP所指的符号advance:是把IP调至下一个输入符号error:是出错诊察程序(2)FIRST(S)=a,(FIRST(T)=a,(FIRST()=,FOLLOW(S)=),#FOLLOW(T)=)FOLLOW()=)预测分析表a(),#ST是LL(1)文法P812文法：(1)FIRST(E)=(,a,b,FIRST(E)=+,FIRST(T)=(

5、,a,b,FIRST(T)=(,a,b,FIRST(F)=(,a,b,FIRST(F)=*,FIRST(P)=(,a,b,FOLLOW(E)=#,)FOLLOW(E)=#,)FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=(,a,b,+,),#FOLLOW(F)=(,a,b,+,),#FOLLOW(P)=*,(,a,b,+,),#(2)考虑下列产生式:FIRST(+E)FIRST()=+=FIRST(+E)FOLLOW(E)=+#,)=FIRST(T)FIRST()=(,a,b,=FIRST(T)FOLLOW(T)=(,a,b,+,),#=FIRST(*F)FI

6、RST()=*=FIRST(*F)FOLLOW(F)=*(,a,b,+,),#=FIRST(E)FIRST(a)FIRST(b)FIRST()=所以,该文法式LL(1)文法.(3)+*()ab#EETTFFP(4)procedure E;beginif sym=( or sym=a or sym=b or sym= then begin T; E end else errorendprocedure E;beginif sym=+ then begin advance; E end else if sym) and sym# then errorendprocedure T;beginif s

7、ym=( 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 T else if 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

8、;beginif sym=a or sym=b or sym= then advance else if sym=( thenbeginadvance; E;if sym=) then advance else errorendelse errorend;P813/*(1) 是，满足三个条件。(2) 不是，对于A不满足条件3。(3) 不是，A、B均不满足条件3。(4) 是，满足三个条件。*/第五章P1331短语: E+T*F, T*F,直接短语: T*F句柄: T*FP1332文法：(1)最左推导:最右推导:(2)(a,a),(a),a)(S,a),(a),a)(T,a),(a),a)(T,S

9、),(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#(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#

10、(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#归P1333(1) F

11、IRSTVT(S)=a,(FIRSTVT(T)=,a,(LASTVT(S)=a,)LASTVT(T)=,a,)(2)a(),a(=,是算符文法，并且是算符优先文法(3)优先函数a(),f44244g55523（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#归successP1345(1)

12、0.1.2.3.4.5.6.7.8.9.10.11.(2)1987 S A S11100 a432 A S d56确定化：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,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,10116116 A S3:5:6: S A a

13、 b S a A S b S A b a A4:0:7: A Sb a a b b a2:1: DFA构造LR(0)项目集规族也可以用GO函数来计算得到。所得到的项目集规族与上图中的项目集一样:=，GO(，a)= =GO(，b)= =GO(，S)= ，=GO(，A)= ，=GO(，a)= =GO(，b)= =GO(，S)= ，=GO(，A)= ，=GO(，a)= =GO(，b)= =GO(，S)= ，=GO(，A)= ，=GO(，a)= =GO(，b)= =GO(，S)= ，=GO(，A)= ，=GO(，a)= =GO(，b)= =GO(，S)= ，=GO(，A)= ，=GO(，a)= =GO

14、(，b)= =GO(，S)= ，=GO(，A)= ，=项目集规族为C=，(3)不是SLR文法状态3，6，7有移进归约冲突状态3：FOLLOW(S)=#不包含a,b状态6：FOLLOW(S)=#,a,b包含a,b,；移进归约冲突无法消解状态7：FOLLOW(A)=a,b包含a,b；移进归约冲突消解所以不是SLR文法。(4)构造例如LR(1)项目集规族见下图：对于状态5，因为包含项目，所以遇到搜索符号a或b时，应该用归约。又因为状态5包含项目，所以遇到搜索符号a时，应该移进。因此存在“移进-归约”矛盾，所以这个文法不是LR(1)文法。 b b b8：1：5： A A A S a a S3： S a

15、 S3：0： a a A a A6：9：4： S b S A b a a S b b7：2：10： S b A A5：第六章/*第六章会有点难P1645(1)EE1T if (E1.type = int) and (T.type = int )then E.type := intelse E.type := realETE.type := T.typeTnum.num T.type := realTnumT.type := int(2)P1647SL1|L2S.val:=L1.val+(L2.val/2)SLS.val:=L.valLL1BL.val:=2*L1.val + B.val; L.

16、length:=L1.length+1LBL.val:=B.c; L.length :=1B0 B.c:=0B1B.c:=1*/第七章P2171a*(-b+c)abc+*a+b*(c+d/e)abcde/+*+-a+b*(-c+d)abcd+*+if (x+y)*z =0 then (a+b)c else abcxy+z*0= ab+cabc￥或 xy+z*0= P1 jez ab+c P2 jump abcP1 P2P2173-(a+b)*(c+d)-(a+b+c)的三元式序列:(1) +, a, b(2) , (1), -(3) +, c, d(4) *, (2), (3)(5) +, a

17、, 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) +, a, b, (2) , , -, (3) +, c, d, (4) *, , , (5) +, a, b, (6) +, , c, (7) -, , , P2184自下而上分析过程中把赋值句翻译成四元式的步骤:A:=B*(-C+D)步骤输入串栈PLACE四元式(1)A:=B*(-

18、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(,C,-, )(12)+D)i:=E*(EA-B-(13)D)i:=E*(E+A-B-(14)i:=E*(E+iA-B-D(15)i:=E*(E+EA-B-D(+,D,)(16)i:=E(EA-B-(17)i:=E*(E)A-B-(18)

19、i:=E+EA-B-(*,B,)(19)i:=EA-(:=,-,A)(20) A产生的四元式：(,C,-, )(+,D,)(*,B,)(:=,-,A)P2185/*设A ：10*20，B、C、D：20，宽度为w4 则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:=

20、4*T16T19:=T17T18T20:=T7+T19Tn:=T20*/P2186100. (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,100P2187100. (j, A, C, 102)101. (j, -, -, 0)102. (j,E1.place ,E2.place

21、 ,0);emit(I.Place :=E1.place);F.truelist := makelist(nextquad);emit(j,-,-,-);F.place := I.place;F.end := E2.place;p:=lookup(id.name); if p nil thenI.place := pelse error M.quad := nextquad*/方法2：S for id:=E1 to E2 do S1S F S1F for id:=E1 to E2 dodoINITIAL=NEWTEMP;emit(:=，E1.PLACE， -， INITIAL);FINAL=N

22、EWTEMP;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.placenil thenemit(F.place := INITIAL)F.quad:=nextquad;F.final:=FINAL;backpatch(S1.nextlist, nextquad)p:=nextquad+2;emit(j, F.place, F.final , p );S.nex

23、tlist := merge(F.nextlist, makelist(nextquad);emit(j,);emit(succ， F.place ， -， F.place);emit(j, F.quad);第九章P2709(1) 传名即当过程调用时，其作用相当于把被调用段的过程体抄到调用出现处，但必须将其中出现的任一形式参数都代之以相应的实在参数。A:=2; B:=3; A:=A+1; A:=A+(A+B); print A; A=9(2) 传地址即当程序控制转入被调用段后，被调用段首先把实在参数抄进相应的形式参数的形式单元中，过程体对形参的任何引用或赋值都被处理成对形式单元的间接访问。当被

24、调用段工作完毕返回时，形式单元（都是指示器）所指的实参单元就持有所希望的值。A:=2;B:=3;T:=A+B把T,A,A的地址抄进已知单元J1,J2,J3x:J1;y:=J2;z:=J3 /把实参地址抄进形式单元，且J2=J3Y:=y+1 Z:=z+x / Y：对y的间接访问 Z：对z的间接访问print AA=8(3) 得结果每个形参均对应两个单元，第一个存放实参地址，第二个存放实参值，在过程体中对形参的任何引用或赋值都看成是对它的第二个单元的直接访问，但在过程工作完毕返回前必须把第二个单元的容放到第一个单元所指的那个实参单元中A:=2;B:=3;T:=A+B把T,A,A的地址抄进已知单元J

25、1,J2,J3x1:=J1;x2:=T; y1:=J2;y2:=A; z1:=J3;z2:=A; /将实参的地址和值分别放进两个形式单元中y2:=y2+1; z2:=z2+x2; /对形参第二个单元的直接访问x1：x2; y1:=y2; z1:=z2 /返回前把第二个单元的容存放到第一个单元所指的实参地址中print AA=7(4) 传值即被调用段开始工作时，首先把实参的值写进相应的形参单元中，然后就好像使用局部变量一样使用这些形式单元A:=2;B:=3;x:=A+By:=Az:=Ay:=y+1z:=z+xprint AA=2过程调用不改变A的值P306-1P306-2 read A,BB1

26、F:=1 C:=A*A D:=B*BB3B2 if C100 goto - halt -: F:=F-1 goto -基本块为、P307-4I:=1read J,KA:=K*IB:=J*IT:=K*100L: C:=A*B write C A:=A+K B:=B+J if AT goto LhaltB2有回路，所以B2是循环，B2既是入口节点，又是出口节点（1） 代码外提：不存在不变运算，故无代码外提（2） 强度削弱：A:=K*I B:=J*I *+（3） 删除基本归纳变量：I100 可以用A100*K或B100*J代替A:=0I:=1L1: A:=C+A if C=R goto L2C:=C+1goto L1L2: B:=J+1C:=B+IR:=B+100P307-5A:=0I:=1L1: A:=C+A if C=T goto L2C:=C+1goto L1L2: B:=J+1C:=B+IT:=B+100B2,B3是循环，B2是入口节点，也是出口节点（1） 代码外提：B:=J+1（2） 删除归纳变量26 / 26