编译原理课后习题答案(陈火旺+第三版)

1、课后答案网第二章p36-6(1)l(gi)足09组成的数字岀(2)敁左推导：n =>nd =>ndd =>nddd=>dddd=>0ddd=>01dd=>012d=>0127 n =>nd odd=>3d 0 34n =>nd =>ndd =>ddd=>5dd=>56d=>568 最右推好:n=>nd=>n7=> nd7 => n27 => nd27 => n127 => d127 => 0127 n=>nd=>n4=> d4=>

2、;34n=>nd=>n8=> nd8 => n68 => d68=>568p36-7g(s)ol|3|5|7|9n ->2|4|6|8|od-*0|ns->o|aoa-> ad|np36-8文法:e ->t1e + 11e-t t-» f|t*f|t/f f -> (e)|i敁左推s:e =>e + t=>t+t=>f+t=>i+t=>i + t*f =>i+f *f =>i+i *f =>i+ i *i e =>t=>t*f =>f*f =>i*

3、f =>i *(e) =>i *(e+t) =>i (t + t) =>i *(f+t) =>i*(i + t)=>i*(i + f=>i*(i + i)w右推e =>e + t=>e + t*f =>e + t*i =>e + f*i =>e+i*i=>t+i*i =>f+i*i =>i+i*i e=>t=>f*t=>f*f =>f (£)=> f*(e + t)=>f*(e + f)=>f*(e+i) => f *(t+i) => f *

4、(f+i) => f *(i+i> =>i*(i+ i):/*#*#h：*»*»*3j：*»：*i+i+ii-i-ii+i*i*«*/p36-9句子iiiei有两个语法树: s => ises => isei => iisei => iiiei s=>is=> iises => iisei => iiieip36-10/*»*«*»*«««s ->ts|t t->(s)|() _中中«寧本丰中丰寧半*中寧/

5、p36-11/本*本拿*拿傘准 l1:aca-> a ab | ab c > cc | e l2: s - ab a-> aa| £ b bbc | be l3:s - ab a-> aab| b -* abb| s l4: s->-a|b aoa1| r b1bo| a *傘*傘傘傘傘水拿/第三章习题参考答案p64-7(1)q_>00确定化:01ix)4>(1, 2, 3)<|>4>小1,2,3(2, 3(2, 3, 4)2.32, 3)(2, 3, 4(2, 3, 1)【2, 3,5)(2, 3, 4(2, 3, 5(2

6、, 32, 3, 4, y)(2, 3, 4, y(2, 3, 5)2, 3, 4,)to小化:课后答案网http:/www. khdaw. com课后答案网0juw6oj,23.40 = (13,5) 04,23,4t5i = (u,4,6) 0山，4，5，60j3,4q = 1 功 oj 从，4，5，0123 = 13 0j43 =u,4 0j，2j4，5，6 oj =1 oj = (u)230 = 3 (23), = 4 0,(l,23,445,61 1p64-8(1)(l 10).01(2)a|2|3|4|5|6|7|8|9)(0|l|2|3|4|5|6|7|8|9)"(0|

7、5)|(0|5)(3)0'l(0|10*l)*|f0(0|10*lf确定化:ab【0)【0,1(1)【0, l)(0,1)(1)(u(0)课后答案网http:/www. khdaw. com课后答案网 小小<1洽状态编么ab012112203333最小化：01)423 <0ja = (1 (0j)b = 2 (23a = 03 23b = 3 0j，2，3(b)己经确定化了，进行扱小化课后答案网http:/www. khdaw. com课后答案网最小化:0.1，2,3.4,5(0，1，1>0,1 = 2,42,3,4,5a = 13.0,52,3,4,5b = 2,3

8、,4,5(2,4.=1，0)2,4x=3,5)(3,5a = 3,53,5b=2,40，1，2,4,3,5(0，1.=1)0,lb=2,4(2,4. = l0)2,4x=3,5(3,5a = 3,53,5b=2,4(2):(0(10) 砌定化:01(x，1, y)(1, y)(2)(l.y)(l, y)(2)(2)1, y)<b小«b洽状态编a:01012112213333最小化:04,2.30，1。= 1>0,lh = 22,30 = 1323)= 30，1，2，3第四章p81 -1(1) 按照t.s的顺序消除左递ih g(s)s->a|a|(t) t ->

9、sr t'-*，st|£ 递 fcl-fwf?： procedure s; beginif sjnn=，a or sym二 then abvance else if sym=(课后答案网http:/www. khdaw. com课后答案网 then beginadvance, tf if sym: then advance,else error; end else error end;procedure t;begins.t end;procedure t9; beginif sym= ,' then begin advance; s;t end end;其屮：sym

10、:足输入串指针ip所指的符兮 advance:足把ip调至f个输入符3 error:足出错诊察程序(2)first(s) = a. ，( first (t) = (a，0 first (t)=c. ) follow(s) = ),# follow(t) = )f0ll0w(tr) = o) 预测分析表a應)#ss>as(t)tt->st't-»stt->stt*t ->£t st是ll(1)文法p81 -2文法：课后答案网http:/www. khdaw. com课后答案网t.->t|£f ->pf'p->

11、(e)|a|b|a(1)first(e) = (,a,b. "first (e3 = +, c first (t) = (, a.b, )first (d = (, a.b, ", e jfirst (f) = (, a.b, 】first (f ) = *, c first(p) = (,a,b,")f0ll0w(e) = #,)f0ll0w(e') = #,)f0ll0w(t) = +, ), #followcf > = (+,>, #1follows) = (, a.b, +,),#follow(f) = «, a, b, ,

12、+,),# follow(p) = *, (, a.b, ,+，)，#(2)考虑卜列产牛式：e' ->+e|£t" ->t|rp->(e)|a|a|bfirst(+e) hfirst( £ ) = +) a c ) = <b first (+e) a follow (£' ) = + d #, =小 first (t) afirstc £)= (, a, b, a e = 4> first (t) nfollow(t* ) = (, a. b. ') d +)#) = first (*fp)

13、 a first(£)= a e = <t> first (*?) a follow (f* ) = *a (, a, b, #) = 4) first (e)nfirst (a) flfirst (b) nfirsto = <l> 所以，该文法式ll(1)文法.(3)+()ab類eeie'e->te'e ->ierete'e'e*->+ee'tt->ftt->ft't->ft,t->ftrt ->£t ->tt ->£t->t

14、t ->tt ->tt ->£ff->pfffpf1fpfff->pffp.f'->sf'->efr->£：f' fpp->(e)p ->ap->bprocedure e;beginif synf* c or sym= a* or sym- b or sym= then begin t; e endelse errorend procedure e ;inif sym= +then begin advance; e endsym<>p #* then errorelse i

15、f sym) endprocedure t;beginif sym c or sym= a then begin f; t else error endprocedure v ;andorendsym=，bdeginif sym= f or sym= a* then t else if sym then endprocedure f;beginif synf c or sym二 a or then begin p; f end else errororerrorsym- bendprocedure r ;beginif sym=then begin advance: f" end e

16、ndprocedure p:beginif sym= a or sym= b or sym= then advance else if sym= c thenbeginadvance, e; if sym=) then advance else error end else error end,p81-3/*«*(1) s.满足三个条件(2) 不足对于a不满足篆件3。(3) 不足.a、b均不满足条件3。(4) 足.满足三个条件。 *»*«*»*/第五章p133 - 1e=>e+t=>e+t*f短i§: e+t*f, t*f.直接短&

17、#174;: t*f句w: t*fp133 - 2文法：s->a|a|(t)t->t,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,s,s),s) =«s.s.s),s) =>(t).s.s),s) =>(cr.s),s,s),s)=>(s,s),s.

18、s).s)=>(a,s).s,s),s)=>(.a),s,s),s) =>(a.a) a,s),s)=>(a.).(t).s)=>«(.a).(s).s)(a.) a,(a).s) =>(a.a) a,(a).a)w右推导：s=>(t)x> (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) => (t,a) => (s,a) => (cd,a) =

19、> (t,s),a) => (t,(t),a)(t,(s),a)，(t,(a)，a) => (t，s，(a)>，a) => «t/，)，a) => (s，)，a) => (t),(a)fi) =x>(t，s)，)，a>=>(t，av，(a)m)，(s,a)/，(a)，a)=>(a，i)，a，(a)，a)(2)(a, a),", (a), a)课后答案网http:/www. khdaw. com(s, a) f，(a), a) (t.a), (a)，a)(ls).； (a), a) (也， (a), a) (s

20、. (a), a) (t， (a), a)(ls. (a), a) (l(a)f a)(t,(s),a)(t, <t),a)(ls),a)<(n. ) (s,a)(ls)0林(黾 a), (a), a)#1#(<(8 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)

21、#10#(t), (a), a)#11#(t)，、(a), a)# 进12tt(s，(a), a)# 归13#(t,；(a), a)# 归11#(t, (a), a)#15#(t.",(a)，a>#16#(t.s，(a), a)#174(t，(a), a)#“移进-归约”过稈：步骤 栈 输入率 动作(a), a)#a预进进进进h归进进ih归进进归ih18#(t,19#(tf (20#(t, (a21#(t. (s22#(t. (t2324# (t, (t)#(t,s25ff(ta), a)#),a)林进进进l/d进归 归归26ili28(t29ilff30ff7s*(tff31

22、irl32l/dtts34p133 - 3 (1) firstvt (s)=a, ,() firstvt(t) = (, ,a, ，() lastvt(s) = (at ) lastvt(t) = , a, )(2)a島()9a>>*>>(<<<=<)>><<<>>g6足锌符文法.并11边铮符优宄文法(3)优先函数a()f44244855523uru栈i # 井备预作 动 进进in输入字符串 (a. (a, a) ) #a. (a, a) )# ,(a, a)# ,(a, a)# (t,# (t.(# (

23、t, (a ft (t. (t# (t. (t.(a, a) #进a. a) #进,a)#进,a»#归a) #进进归 归进进归# # # 舞 券# s#归successp134 - 5(1)o.s'->.sl.s'->s.2. s-> as 3. s-> a s4. s - as 5. s -> b6. s->b7. a-> sa8. a->s*a9 a->sa- 10. a->.a11. a->a-(2)蝴定化:saab(0, 2, 5, 7,10)(1，2, 5, 7, 8, 10 )(2, 3,

24、5, 7,10(11)6(1. 2, 5, 7, 8, 102,5,7,8,102, 3, 5, 7f 9, 1011)(6)2, 3, 5, 7, 102, 4. 5, 7, 8, 10 )(2, 3, 5, 7, 10)11(2, 5, 7, 8, 10【2, 5, 7, 3, 10(2, 3, 5,1, 9, 10 )11(6)(2, 3, 5, 7, 9, 10 )(2, 4, 5, 7, 8, 10 )(2, 3. 5. 7,10111(6)(2, 4, 5, 7,8,10 j(2, 5, 7, 8, 10(2,3,5, 7, 9, 10 )11(6)(114>4>小(6

25、)小小4><t>$5. a->s aaa->s. aa-> saa> aa-> aa> a4 s-> a sas->basaa-> as-> b a->sa7:s-> as- a->s < aa-> sadfa构进lr(0)项目集规范族也以用go函数來计算得到。所得到的项吕集规范族与上图中的 硕目集一样：i0 = (s* -> s. s-> as. s-> b. a-> sa. a-> a ) go (i。，a)= a. > a ) go(io，b)

26、= l s b ) = 1,go (i。，s)= s > s t a > s- a，a> sa i a > .a，s > as s > -b = ijgo(io. a) = 00(13，a) = g0(i3. b)= go(i3，s)= go(i3, a)=( g0(i4，a) = ( g0(i4. b)=( g0(i4，s) = go(i4, a)= g0(i5, a) = g0(i5, b)= go(i5, s)=( go(i5, a)= g0(ifi. a)= g0(ifi, b)= g0(i6. s) = g0(l6, a) = g0(i7. a)

27、= g0(i7 . b) = g0(i? . s) = g0(i7 . a) = s -> a. s s _9as s -b，a>，a> .a )= i4a> a ) = 1,s > b . )=i，a s a，s as f s -b a sa，a a = a> sa，s a. s，s as t sb，a sa，a a = i石 a> a ) = ijs > b . ) = !2s as a s- a» s as 9 sb，a .sa，a -a )= i7 s a. s，s asi s b，a sa. aa = i4 a > a

28、) = ijs > b . = !-)a-»s a， s > as t s -> -b a sa, a a ) = 1, a> sa，s a. s s 9as > s b，a -sa a a = i5 a> a ) = 1s h> . ) = 1，s > as a s. a，s 'as * s -b a -sa. a -a j= i7s a- s » s -as 1 s -b» a .sa，a .a = i4 a > a ) = 1,s > b ) -a>s a. s -> as, s

29、 -b. a> sa, a> a = i4 a sa. s a' s s > - as» s .b» a sa« a项目集规范族为c=(i丨，i2, i3, i4, is, i6. i7(3) 不足slr文法状态3, 6, 7有移进们杓冲突状态 3: follow (s'm 不包含 a,b状态6: follow(s= u.a.b包含a,b,:移进归约冲突无法消解状态7: follow(a) = (a,b)t!含a,b:移进归约冲关消解所以不ttslr文法， 构造例talr(l)项目集规范族见f图:对丁状态5,因为乜含项目a->

30、;as. a/b,所以遇到搜索符sa成b时,w该用a-> as 朽约、又冈为状态5包含项ra->a a/b.所以遇到搜索符sa吋.应该移进，闪此 存在“移进-归约”矛盾，所以这个文法不是lr(1)文法。1:s' -> s-林a->s aa/ba->saa/ba+aa/bs -> asa/bs -> ba/b5:a->sa-a/bs -> a sa/bs -> asa/bs ba/ba->-saa/baa/b/8：s -> a sa/bs -> asa/bs -> ba/ba-> saa/baa/b

31、sa/b4：s->b #/a/b0：s' 4 s#s->-as#/a/bsb#/a/ba->*saa/ba->.aa/b3:a> a - a/h6：as-aa/bsaa/ba-> aa/bs -> asa/bs -> ba/b9：s-> as-a/ba->s aa/ba->saa/ba-> aa/bs-> asa/bs-> ba/b so as#/a/bs十as湫a/bs -> b#/a/basaa/ba->aa/b1a7：s -> as-#/a/bas aa/ba-> saa/

32、ba->aa/ba/bs -> ba/ba第六章/* 第六彦会 fj 点难p164 - 5e >e1 +t (if (el. type = int) and (t. type - int ) then e. type ：= int else e. type ：= real e >te. type := t. type)t >num. num t. type := realt num (l type ：= int)(2)p164 - 7s->ll|l2 (s. val:=ll. val+(l2. val/2l2jmf111)s->l(s. val:=l.

33、 val)llibl. val:=2*ll. val + b. val;l. length：=ll. length+l)lbl.val：=b.c;l length ：=l) b->0b c:=0)b->1b. c:=l)第七章abtc+*abcde/+*+aebc«d+p217 - 1 a*(-b+c) a+b*(c+d/e)一 3+b* (一 c+d>aicdi v i v(aa b) v (-ic v d)ab acd v v(avb)a(cv-dae)ab vcde a v a(x+y)*z =0 then (a+b) t c else a t b f c x

34、y+z*0= ab+c t abc t f ¥ 或 xy+z*0= pl jez ab+c t p2 juxnp abc t tpl p2课后答案网 p217 - 3-(a+b)* (c+d) (a+b+c)的三元式序列：(1) +，a, b(2) 9, (1),-(3) +，c，d *, (2), (3)(5) +, a. b(6) +, (5), c，(6)w接三元式序列:三元式衣：(1) +, a. b(2) 9. (1),-(3) +, c. d *, (2), (3)(5) +, (1), c(6) _，间接b表:(1)(2)(3)(1)(5)(6)四元式序列:(1) +

35、a b. tj(2) ©. tlt - t2(3) +, c, d, t3 *，t2, t3, t4(5) +, a, b, t5(6) +, 1；, c, t6(7) - i；, t6. t7p218 - 4ft卜而上分析过w屮把翻译成四九式的jj>ffi: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课后答案网http:/www. khdaw. com课后答案网(6)*(-c*d)i ：=ea-b(-c+d)

36、i:=e*a-b-(8)-c+d)i:=e*(a-b(9)c+d)i:=e(-a-b(10)+d)a-bc(11)+d)i: =e* (-ea-bcw.c.-, t)(12)+d)i: =e* (ea-b-'瀛(13)d)i:二e* (e+a-bt -(14)i:=e* (e+ia-bt -d(15)i: =e* (e+ea-btj -d(+, t；,d, tj(16)i:=e(ea-bt，(17)i:e* (e)a-bt_ -(18)i:=e+ea-b-t/(.b. t.,1)(19)i:=ea-t3 2(:=，(20) a户生的四元式：t)ltdd 1 ri p218 - 5sa

37、: 10*20t b、c、d: 20.宽度力 w=4 则 t1 =1*20t1 =tl+jt2=a-84t3=4*t1tn =t2|t3 /这一步c多余的 t4 = i + jt5=b4t6=4*t4t7 =t5t6t8 = i*20t8=t8+jt9=a-84t10=4*t8til =t9(t10t12 = i + jt13=dlt14*t12ti5=t13t14t16=t11+t15 t17=c-4t18=4*t16t19=t17t18 t20 =t7+t19tn =t20 芈芈芈芈本本本本本本聿氺本本本*/p218 6100. (jnz, a. _，0)101.(j.-、102)102.

38、(jnz. b, .，104)103.(j. , ，0)101.(jnz, c,-103)105.(j. - ，106)106.(jnz，d,-.，104)107.(j.100)fi链:106, 104.103真链:107, 1001假链aw-ft链链竹p218 7100.(j<.a. c, 102)101.(j.-0)102.(j<,b, d, 104)103.(l-101)104.(j=.a. 'r , 106)105.(j.-t 109)106.(,c, ti)107.(:=,tl, - c)108.(j.-100)109.。彡，a, d, 111)110.(j.-&

39、gt; 100)111.(+.a, 2，t2)112.(:二.t2, - a)113.(l-109)111.(j.-100)p219 -12/*本本幸本寧本傘牟申拿寧拿*本*本本 maxint - 5 maxint - 4 maxint - 3 maxint - 2 maxint - 1 maxint(2) w汗投代旅1:for el := e2 to e3 do soe.s -> f dof ->foi i:= ei ti ->ids ->f doms,backpatch(sl. next list, next quad):backpatch (f. true lis

40、t, m quad); emit (f. placef > foi i ：= ej toe2 f. false list := makelist (next quad);emit( 4j 1 el. place f e2. place 0f )emit (i. place ： = ' el. place);f. truelist := makelist(nextquad);emit ( j，-;f. place : = i. place, f- end ：= e2. place;课后答案网http:/www. khdaw. comm £ *丰丰丰*«*/ 方法

41、2:s for id:=el(p: =lookup (id. name); if p <> nil theni. place := p else error) (m. quad := next quad)to e2 do sif -> forid := eltoe2 doinitial=newtemp;emit( el. place1.initial!:final=newtemp; emit( :=，' e2. place*,- p:= nextquad+2; emit( *j , initial ,f. nextlist:=makelist (nextfinal); final ' , p); quad)；课后答案网 emit( j, ，一，一)；f. place: = lookup (id. name)， if f.place nil then emit (f. place ： = ' initial) f. quad:=nextquad; f. final:=final; s->fs1backpatch (si. next list, next quad) p:=nextquad+2;emit ( j ，