程序设计语言编译原理第3版课后答案（精编版）

1、.优选 .p36-6第二章(1)l( g1) 是 09 组成的数字串(2)最左推导 :nndnddnddddddd0 ddd01dd012 d0127nnddd3d34nndnddddd最右推导 :5dd56d568nndn 7nd 7n 27nd 27n 127d1270127nndn 4d 434nndn 8nd 8n 68d 68568p36-7g(s)o n d1|3|5|7| 92|4|6|8|o0| nso| aoaad | np36-8文法：et| et| ettf | t * f | t / ff( e )|i最左推导 :eetttftitit *fif *fii *fii *

2、 iett *ff * fi *fi *( e )i *(et )i *(tt )i *(ft )i *(it )i *( if )i *(ii )最右推导 :eetet *fet * ief * iei* iti * ifi* iii * ietf * tf *ff *( e )f *(et )f *(ef )f *(ei )f *(ti )f *(fi )f *(ii )i *(ii )语法树： /*e+te+te-te+tftt*fe-tftfiffitfifiiifieeeiii+i+ii-i-ii+i*i*/p36-9句子 iiiei 有两个语法树：sisesiseiiiseiiii

3、eisisiisesiiseiiiieip36-10/*sts | tt( s) | ( )*/p36-11/* l1:sacaaab | abcl2:scc |aba bl3:aa | bbc | bcs a bl4:s a babaab | abb |a | b 0 a1|1b0 | a*/p647(1)第三章习题参考答案1(0|1)* 101xy01101x12345y1确定化：x1,2,32,32,3,42,3,52,3,4,y0 2,32,32,3,52,32,3,511,2,32,3,42,3,42,3,42,3,4,y2,3,4,001203001101405106111最小化：

4、 0,1,2,3,4,5, 6 0,1,2,3,4,51,3,5 0,1,2,3,4,51,2,4,601 0,1,2,3,4, 5, 6 0,1,2,3,41,3,50 0,1,2,3, 4, 5, 6 0,1,2,31,30,1,2,31,2,4 0,1,02,34,15, 6 0,11 0,1 1,201 2,3 3 2,3401 0, 1, 2,3, 4, 5, 6001200101304105111p648(1)(1 | 0)* 01(2)(1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9)( 0 |1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

5、)* (0 | 5) | (0 | 5)(3)0 *1(0 | 10* 1) * | 1* 0(0 | 10* 1) *p6412(a)aa,b01a确定化：00,11a0,10,10b11给状态编号：ab012112203333aa01abbb2b3a最小化： 0,1, 0,1 a 2,3 a2,310,1 b 0,3 2,3 b 23 0,1, 2, 3aabb012ab(b)bba023abaabbaa14a5已经确定化了 ,进展最小化最小化： 0,1, 0,1 a2, 3,4, 51 0,1 b 2, 4 2, 3,4 ,5 a 1, 3, 0, 5 2,3,4 ,5 b 2, 3,4

6、 ,5 2, 4 a 3, 5 a 1, 0 2 ,4 b 3,5 3,5 b 3, 5 2, 4 0,1,2, 4,3, 5 0,1 a1 0,1 b 2, 4 2, 4 a 1, 0 2 ,4 b 3, 5 3, 5 a 3,5 3,5 b 2, 4bba012abap6414(1)01010(2):(0|10)*xy201x1y0确定化：x,1,y01,y121,y1,y221,y给状态编号：01012112213333001010111230最小化： 0,1, 2, 3 0,1 01 2,3 01,3 0,1 1 2 2, 3 1 3 0,1, 2, 3011101300第四章p811

7、(1) 按照 t,s的顺序消除左递归g (s)sa | | (t )tstt, st|递归子程序： procedure s; beginif sym='a' or sym='' then abvance else if sym='('then beginadvance;t;if sym=')' then advance; else error;end; procedure t; begins;tendelseerrorend; procedure t; beginif sym=','then beginadvanc

8、e;s;tendend;其中 :sym:是输入串指针ip 所指的符号advance是:把 ip 调至下一个输入符号error:是出错诊察程序(2)first(s)=a,(first(t)=a,(first( t )=,follow(s)=),# follow(t)=)follow( t )=)a(),#s ttstastststst(t)sttt, st预测分析表是 ll(1) 文法p812文法：eteee |tfttt |fpff* f|p(1)( e) | a | b |first(e)=(,a,b,first(e')=+, first(t)=(,a,b,first(t')

9、=(,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)考虑以下产生式:ee|tt|f* f |p( e)| a|bfirst(+e) first()=+ = first(+e) follow(e')=+ #,)=first(t) first()=(,a,

10、b, = first(t) follow(t')=(,a,b,+,),#=first(*f') first( )=* = first(*f') follow(f')=* (,a,b,+,),#=first(e) first(a) first(b) first()= +*()ab#e e' tt'ete 'ete ' ete ' ete 'eeeetttftttttfttttfttttfttt所以 ,该文法式ll(1)文法 . (3)f f'pffppffpffpff ppfbffppfff* fff( e

11、)a(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 errorend procedure t; beginif sym=&#

12、39;(' 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'

13、 or sym='b' or sym='' then begin p; f' endelse errorend procedure f' beginif sym='*'then begin advance; f' endend procedure p; beginif sym='a' or sym='b' or sym='' then advanceelse if sym='(' thenbeginadvance; e;if sym=')' t

14、hen advance else errorend;p813endelse error/*(1) 是，满足三个条件。(2) 不是，对于a 不满足条件3。(3) 不是， a、 b 均不满足条件3。(4) 是，满足三个条件。*/p133 1第五章eetet * f短语 :e+t*f, t*f,直接短语 : t*f句柄 : t*fp133 2文法：sa|( t)tt, 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

15、, 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)( a, a), , s), s)( a, a ), ,( t), ( a, a), ,( a), a)最右推导 :s)(a, a), ,( s), s)( a,a ), ,( a), s)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)(

16、t, a)( s,a)( t ), a)( t ,s), a)( t ,( t), a)( t ,( s), a)( t,( a), a)( t ,s,( a), a)( t, ,( a), a)( s, ,( a ), a)( t ), ,( a ), a)(2)( t , s), ,( a ), a)(t, a ), ,( a ), a)(s,a ), ,( a ), a)(a,a ), ,( a ), a)(a,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

17、)(t,(t),a)(t,s),a)(t),a) (s,a)(t,s) (t) s" 移进 -归约过程：步骤栈输入串动作(s,a),(a),a)0#(a,a),(a),a)#预备1#(a,a),(a),a)# 进2#(3#(a,a),(a),a)# 进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#(s13#(t,(a),a)# 归,(a),a)#

18、归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,(t23#(t,(t),a)#),a)#进归24#(t,s),a)#归25#(t),a)#归26#(t),a)#进27#(s,a)#归28#(t,a)#归29#(t,30#(t,aa)#进)#进31#(t,s)#归32#(t33#(t)#归进34#s#归p133 3(1) firstvt(s)=a,(firstvt(t)=,a,(lastvt(s)=a,)

19、g6 是算符文法，并且是算符优先文法(3)优先函数faffff(),ggaggg(),lastvt(t)=,a,) (2)a(),a>>>>()<<<=><>,<<<>>a(),f44244g555234栈输入字符串动作# a,(a,a)#预备#(a, (a,a)#进#(a#(t, (a,a)#, (a,a)#进归sas789a010112a3s4d56确定化：0,2,5,7,101,2,5,7,8,102,3,5,7,10s1,2,5,7,8,102,5,7,8,102,4,5,7,8,10a2,3,5

20、,7,102,3,5,7,9,102,3,5,7,10a111111b666# 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#归successp134 5(1)0. ss1.ss 2. sas 3. sa s4. sas5. sb 6. sb7. asa8. asa9. asa10. aa11. aa(2)12,5,7,8,102,5,7,8,102,3,5,7,9,101162,3,5,7,9,102,4,5,7,8,102,3

21、,5,7,101162,4,5,7,8,102,5,7,8,102,3,5,7,9,10116116sbsbsasasaasasbaaaaasaaaas3: sa a a s ssssa saaasb5: asa6: asasssa aasb saaass s aaa sasb saaabaasbsabaa0: sss4: sas7: sasasassaassabaabba1: aa2: sbdfa构造 lr(0)工程集标准族也可以用go 函数来计算得到。所得到的工程集标准族与上图中的工程集一样 :i 0 = ss ， sas， sb， asa， aa go(go(i 0 ， a)=aa= i

22、 1i 0 ， b)=sb= i 2go(i 0 ，s)=ss ， asa， asa， aa ， sas， sb = i 3go(i 0 ， a)=sas ， sas， sb， asa， aa = i 4go(go(i 3 ， a)=aa= i 1i 3 ， b)=sb= i 2go(i 3 ， s)=as a ， sas， sb， asa， aa = i 5go(i 3 ， a)=asa ， sas， sas， sb ， asa， aa = i 6go(i 4 ， a)=aa= i 1.go(i 4 ， b)=sb= i 2go(i 4 ， s)=sas ， asa ， sas， sb， a

23、sa， aa = i 7go(i 4 ， a)=sas ， sas， sb， asa， aa = i 4go(go(i 5 ， a)=aa= i 1i 5 ， b)=sb= i 2go(i 5 ， s)=as a ， sas， sb， asa， aa = i 5go(i 5 ， a)=asa ， sas， sas， sb ， asa， aa = i 6go(i 6 ，a)=aa= i 1go(i 6 ，b)=sb=i 2go(i 6 ，s)=sas ，asa，sas， sb ，asa， aa =i 7go(i 6 ，a)=sas， sas， sb ， asa， aa = i 4go(go(i

24、7 ， a)=aa= i 1i 7 ， b)=sb= i 2go(i 7 ， s)=asa， sas， sb ， asa， aa = i 5go(i 7 ， a)=asa ， sas ， sas， sb， asa， aa = i 6工程集标准族为c=(3) 不是 slr 文法i 1 ， i 2 ， i 3 ， i 4 ， i 5 ， i 6 ， i 7 bbb1：s a a a ssssasaa asb#a/b a/b a/b a/ba/bas5：a s s s aasa as asb saaa/b a/b a/b a/b a/ba/ba8：s s s a aa s asb saaa/b a/

25、b a/b a/ba/baasas3：0：s s ss asb#/a/b #/a/b3：aaa/b优选 .状态 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，因为包含工程 aasa / b ，所以遇到搜索符号a或 b 时，应该用 aas归约。 又因为状态5 包含工程 aaa/ b ，所以遇到搜索符号a 时， 应该移进。 因此存在&q

26、uot; 移进-归约矛盾，所以这个文法不是lr(1)文法。asa6：a a a ss9：sasaa asba/ba/b a/bsb4：ss aaassab# / a/bsaa/b a/ba/ba/ba/bsabaasb2：s s s aaas asb saa#/a/b #/a/b #/a/b a/ba/b7：s asa a ssas sa saa asb# / a/ba/ba/b a/b a/ba/bb10：sba/baa5：aaaaasaasa/ba/bsbba/b第六章/*第六章会有点难p164 5(1)ee1 t if (e1.type = int) and (t.type = int

27、) then e.type := intelse e.type := realete.type := t.type tnum.num t.type := realtnumt.type := int (2)p164 7ssl1|l2ls.val:=l1.val+(l2.val/2l 2.length )s.val:=l.valll1bl.val:=2*l1.val + b.val;l.length:=l1.length+1优选 .lbl.val:=b.c;l.length :=1b0b.c:=0b1b.c:=1*/p217 1a*(-b+c)abc+*第七章a+b*(c+d/e)abcde/+*

28、+-a+b*(-c+d)abcd+*+a(cd ) acd( ab)(cd) abc d( ab)(cde) abcd eif(x+y)*z =0then(a+b) celsea b cxy+z*0= ab+c abc￥ 或 xy+z*0= p1 jez ab+c p2 jump abcp1p2p217 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),

29、-(3)+, c, d (4)*, (2), (3) (5)+, (1), c (6)-, (4), (5) 间接码表：(1)(2)(3)(4)(1)(5) (5)(6) (6)四元式序列 :(1)+, a, b,t1(2),t1 , -, t2(3)+, c, d,t3(4)*,t2 ,t3 , t4(5)+, a, b,t5(6)+,t5 , c, t6(7)-,t4 ,t6 , t7p218 4自下而上分析过程中把赋值句翻译成四元式的步骤:a:=b*(-c+d)步骤输入串栈place四元式(1)a:=b*(-c+d)(2):=b*(-c+d)ia(3)b*(-c+d)i:=a-(4)*(

30、-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,-, t )1(12) +d)i:=e*(ea-b- t1(13) d)i:=e*(e+ a-b-t -1(14) )i:=e*(e+ia-b- t -d1(15)i:=e*(e+ea-b- t1(16)i:=e(ea-b- t2-d(+, t1,d, t )2(17)i:=e*(e)a-b- t -2(18

31、) i:=e+ea-b- t2(*,b, t2, t )3(19) i:=ea- t3产生的四元式：(:=, t3(20) a,-,a)(,c,-, t )1(+, t1,d, t )2(*,b, t2, t )3(:=, t3,-,a)p218 5/*设 a ： 10*20， b、c、d ： 20，宽度为w 4 那么t1:= i * 20 t1:=t1+jt2:=a 84 t3:=4*t1tn:=t2t3/ 这一步是多余的t4:= i + j t5:=b 4 t6:=4*t4 t7:=t5t6 t8:= i * 20 t8:=t8+j t9:=a 84 t10:=4*t8 t11:=t9t1

32、0 t12:= i + j t13:=d 4 t14:=4*t12t15:= t13t14t16:=t11+t15 t17:=c 4 t18:=4*t16t19:=t17t18 t20:=t7+t19 tn:=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,104， 103真链： 107,1

33、00p218 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.(j , a, d, 111)110.(j, -, -, 100)111.(+, a, 2 , t2)112.(:=, t2, -, a)113.(j, -, -, 109)114.(j, -, - 100)p219 12/* (1)m

34、axint5maxint4maxint3maxint2maxint1maxint(2)翻译模式方法 1：for e1 := e2 to e3 do ssf do ms1ffor i :iidme1 to e2sf 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.nextlist := f.falselist;ffor i :e1 to e 2f.falselist:= makeli

35、st(nextquad);emit( j>, e1.place , e2.place ,0 ); emit(i.place := e1.place);f.truelist := makelist(nextquad);.iidemit( j,-,-,- ); f.place := i.place; f.end := e2.place;p:=lookup(); if p <> nil theni. place := p else errormm.quad := nextquad*/方法 2：s for id:=e1 to e2 do s1 s f s1f for i

36、d:=e1 to e2 dofforid :e1toe 2 do initial=newtemp;emit( :=， e1.place ， -， initial); final=newtemp;emit( :=， e2.place ， -， final);p:= nextquad+2;emit(j, initial , final , p);f.nextlist:=makelist(nextquad); emit( j, , ); f.place:=lookup();if f.placenil thenemit(f.place := initial) f.quad:=nextqu

37、ad;f.final:=final;sfs1backpatch(s1.nextlist, nextquad) p:=nextquad+2;emit(j, f.place , f.final , p ); s.nextlist := merge(f.nextlist, makelist(nextquad); 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);printa;a=9(2) 传地址即当程序控制转入被调用段后，被调用段首先把实在参数抄进相应的形式参数的形式单元中，过