版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、附錄 部分習(xí)題參考答案第1章參考答案:1,2,3,4,5,6,7解答:略!第2章參考答案:1,2,3:解答:略!4. 解答: a: b: c: d: 5. 解答:用e表示<表達(dá)式>,t表示<項(xiàng)>,f表示<因子>,上述文法可以寫為: e t | e+t t f | t*f f (e) | i最左推導(dǎo):e=>e+t=>e+t+t=>t+t+t=>f+t+t=>i+t+t=>i+f+t=>i+i+t=>i+i+f=>i+i+ie=>e+t=>
2、;t+t=>f+t=>i+t=>i+t*f=>i+f*f=>i+i*f=>i+i*i最右推導(dǎo):e=>e+t=>e+f=>e+i=>e+t+i=>e+f+i=>e+i+i=>t+i+i=>f+i+i=>i+i+ie=>e+t=>e+t*f=>e+t*i=>e+f*i=>e+i*i=>t+i*i=>f+i*i =>i+i*ii+i+i和i+i*i的語法樹如下圖所示。i+i+i、i+i*i的語法樹6. 解答:(1) 終結(jié)符號(hào)為:or,and,not,(,),tru
3、e,false非終結(jié)符號(hào)為:bexpr,bterm,bfactor開始符號(hào)為:bexpr(2) 句子not(true or false)的語法樹為:7. 解答:(1) 把a(bǔ)nbnci分成anbn和ci兩部分,分別由兩個(gè)非終結(jié)符號(hào)生成,因此,生成此文法的產(chǎn)生式為:s aba aab|abb cb|e(2) 令s為開始符號(hào),產(chǎn)生的w中a的個(gè)數(shù)恰好比b多一個(gè),令e為一個(gè)非終結(jié)符號(hào),產(chǎn)生含相同個(gè)數(shù)的a和b的所有串,則產(chǎn)生式如下: s ae|ea|bss|sbs|ssbe aebe|beae|e(3) 設(shè)文法開始符號(hào)為s,產(chǎn)生的w中滿足|a|b|2|a|。因此,可想到s有如下的產(chǎn)生式 (其中b產(chǎn)生1到2
4、個(gè)b): s asbs|bsasb b|bb(4) 解法一:s 奇數(shù)頭整數(shù)奇數(shù)尾 |奇數(shù)頭奇數(shù)尾 |奇數(shù)尾 奇數(shù)尾 1|3|5|7|9 奇數(shù)頭 2|4|6|8|奇數(shù)尾 整數(shù) 整數(shù)數(shù)字|數(shù)字 數(shù)字 0|奇數(shù)頭解法二:文法g=(s,a,b,c,d,0,1,2,3,4,5,6,7,8,9,p,s)sab | baac | db1|3|5|7|9d2|4|6|8|bc0|d(5) 文法g=(n,s,n,m,d,0,1,2,3
5、,4,5,6,7,8,9 ,s,p)sn0 | n5nmd|em1|2|3|4|5|6|7|8|9dd0 | dm |e(6) gs:sasa | bsb | csc | a | b | c |e8. 解答:(1) 句子abab有如下兩個(gè)不同的最左推導(dǎo):s => asbs => abs =>abasbs => ababs => abab s => asbs => absasbs => abasbs => ababs => abab 所以此文法是二義性的。(2) 句子abab的兩個(gè)相應(yīng)
6、的最右推導(dǎo): s => asbs => asbasbs => asbasb => asbab => abab s => asbs => asb => absasb => absab => abab(3) 句子abab的兩棵分析樹: (a)(b)(4) 此文法產(chǎn)生的語言是:在a,b上由相同個(gè)數(shù)的a和b組成的字符串。9,10:解答:略!第3章習(xí)題解答:1. 解答:(1) (2) (3)
7、60;× (4) × (5) (6) 2. 分析 有限自動(dòng)機(jī)分為確定有限自動(dòng)機(jī)和非確定有限自動(dòng)機(jī)。確定有限自動(dòng)機(jī)的確定性表現(xiàn)在映射d:q×vt ->q是單值函數(shù),也就是說,對(duì)任何狀態(tài) qq和輸入字符串a(chǎn)vt,d (q,a)唯一確定下一個(gè)狀態(tài)。顯然,本題給出的是一個(gè)確定的有限自動(dòng)機(jī),它的狀態(tài)轉(zhuǎn)換圖是c中的。 它所接受的語言可以用正則表達(dá)式表示為00(0|1)*,表示的含義為由兩個(gè)0開始的后跟任意個(gè)
8、(包含0個(gè))0或1組成的符號(hào)串的集合。 2. 解答:a: b: c: d: e: 3,4解答:略!5解答:6解答:(1) (0|1)*01(2) (1|2|9)(0|1|2|9)*| e)(0|5)(3) (0|1)*(011)(0|1)*(4) 1*|1*0(0|10)*(1|e) (5) a*b*c*z*(6) (0|10*1)*1(7) (00|11)*(01|10)(00|11)*(01|10)(00|11)*)*(8) 分析設(shè)s是符合要求的串,|s|=2k+1 (k0)。則 ss10|s21
9、,|s1|=2k (k>0),|s2|=2k (k0)。且s1是0,1上的串,含有奇數(shù)個(gè)0和奇數(shù)個(gè)1。 s2是0,1上的串,含有偶數(shù)個(gè)0和偶數(shù)個(gè)1??紤]有一個(gè)自動(dòng)機(jī)m1接受s1,那么自動(dòng)機(jī)m1如下:和l(m1)等價(jià)的正規(guī)式,即s1為:(00|11)|(01|10)(00|11)*(01|10)*(01|10)(00|11)*類似的考慮有一個(gè)自動(dòng)機(jī)m2接受s2,那么自動(dòng)機(jī)m2如下:和l(m2)等價(jià)的正規(guī)式,即s2為:(00|11)|(01|10)(00|11)*(01|10)*因此,s為:(00|11)|(01|10)(00|11)*(01|10)*(01|10)(00|11)*
10、0|(00|11)|(01|10)(00|11)*(01|10)*17解答:(1) 以0開頭并且以0結(jié)尾的,由0和1組成的符號(hào)串。(2) a|a0,1*(3) 由0和1組成的符號(hào)串,且從右邊開始數(shù)第3位為0。(4) 含3個(gè)1的由0和1組成的符號(hào)串。a|a0,1+,且a中含有3個(gè)1 (5) 包含偶數(shù)個(gè)0和1的二進(jìn)制串,即a|a0,1*,且a中有偶數(shù)個(gè)0和1 8. 解答:01q0*q1q2q3q2q3q0q1q1q0q3q29. 解答:(1) dfa m=(0,1,q0,q1,q2,q0,q2,d)其中d定義如下:d (q0,0)=q1&
11、#160; d (q0,1)=q0d (q1,0)=q2 d (q1,1)=q0d (q2,0)=q2 d (q2,1)=q0狀態(tài)轉(zhuǎn)換圖為:(2) 正規(guī)式: 1*01*01*01* dfa m=(0,1,q0,q1,q2,q3,q0,q3,d),其中d定義如下:d (q0,0)=q1 d (q0,1)=q0d (q1,0)=q2 d (q1,1)=q1d (q
12、2,0)=q3 d (q2,1)=q2d (q3,1)=q3 狀態(tài)轉(zhuǎn)換圖為:10. 解答:(1) dfa m=(0,1,q0,q1,q2,q3,q0,q3,d),其中d定義如下:d (q0,0)=q1 d (q0,1)=q2d (q1,0)=q1 d (q1,1)=q3d (q2,0)=q3 d (q2,1)=q1狀態(tài)轉(zhuǎn)換圖為:(2)
13、dfa m=(0,1,q0,q0,q0,d),其中d定義如下:d (q0,0)=q0 d (q0,1)=q0狀態(tài)轉(zhuǎn)換圖為:11 解答:(1) (a|b)*a(a|b) 求出nfa m:確定化,得到dfa m:化簡(jiǎn): 在第步中求出的dfa m中沒有等價(jià)狀態(tài),因此它就是最小化的dfa m。(2) (a)b)*a(a|b)(a|b) 求nfa m: 確定化,得到dfa m:化簡(jiǎn),在第步中求出的dfa m中沒有等價(jià)狀態(tài),因此它已經(jīng)是最小化的dfa m了。12.解答:對(duì)應(yīng)的nfa為: 增加狀態(tài)x、y,再確定化:iiaibx,5a,t,y
14、 a,t,ya,t,ybb b,t,yb,t,y t,yt,y 得到的dfa為: 最小化:該自動(dòng)機(jī)已經(jīng)是最小化的dfa了。13解答:其中a代表1元硬幣,b代表5角硬幣14解答:正規(guī)式為:(0|1)*(00|01) 化簡(jiǎn):(0|1)*0(0|1)不確定的有窮自動(dòng)機(jī)為:確定化,并最小化得到:正規(guī)文法為:s1s | 0aa0b | 0 | 1c | 1b0b | 0 | 1c | 1c1s | 0a15.解答: 正規(guī)式:(dd*:| e)dd*(.dd*| e),d代表az的字母 nfa為: dfa為:16.解答:詞法分析器對(duì)源程序采取非常局部的觀點(diǎn),因此象c語言的語句fi (a = f (x) )
15、 中,詞法分析器把fi當(dāng)作一個(gè)普通的標(biāo)識(shí)符交給編譯的后續(xù)階段,而不會(huì)把它看成是關(guān)鍵字if的拼寫錯(cuò)。pascal語言要求作為實(shí)型常量的小數(shù)點(diǎn)后面必須有數(shù)字,如果程序中出現(xiàn)小數(shù)點(diǎn)后面沒有數(shù)字情況,它由詞法分析器報(bào)錯(cuò)。17. 解答:此時(shí)編譯器認(rèn)為/* then part return q else/* else part */是程序的注釋,因此它不可能再發(fā)現(xiàn)else 前面的語法錯(cuò)誤。分析 這是注釋用配對(duì)括號(hào)表示時(shí)的一個(gè)問題。注釋是在詞法分析時(shí)忽略的,而詞法分析器對(duì)程序采取非常局部的觀點(diǎn)。當(dāng)進(jìn)入第一個(gè)注釋后,詞法分析器忽略輸入符號(hào),一直到出現(xiàn)注釋的右括號(hào)為止,由于第一個(gè)注釋缺少右括號(hào),所以詞法分析器在
16、讀到第二個(gè)注釋的右括號(hào)時(shí),才認(rèn)為第一個(gè)注釋處理結(jié)束。為克服這個(gè)問題,后來的語言一般都不用配對(duì)括號(hào)來表示注釋。例如ada語言的注釋始于雙連字符(-),隨行的結(jié)束而終止。如果用ada語言的注釋格式,那么上面函數(shù)應(yīng)寫成long gcd(p,q)long p,q; if (p%q = 0)- then part return q else- else part return gcd(q, p%q);18. 解答:略!第4章習(xí)題解答:1,2,3,4 解答 略!5. 解答:(1)× (2) (3)× (4) (5)(6)(7)×(8)×6. 解答:(1)a: b:
17、c: d: e:(2)a: b: c: d: e:7.解答:(1) 消除給定文法中的左遞歸,并提取公因子:bexprbterm or bterm btermbfactor and bfactor bfactornot bfactor | (bexpr) | true |false (2) 用類c語言寫出其遞歸分析程序: void bexpr(); bterm(); while(lookahead ='or') match (
18、9;or'); bterm(); void bterm(); bfactor(); while(lookahead ='and') match ('and'); bfactor(); void bfactor(); if (llokahead='not') t
19、hen match ('not'); bfactor(); else if(lookahead='(') then match ('); bexpr(); &
20、#160;match(')'); else if(lookahead ='true') then match ('true) else if (lookahead='false') then match ('false'); else error;8. 解答:消除所給文法的左遞歸
21、,得g': s (l)|a l sl' l' ,sl' |e 實(shí)現(xiàn)預(yù)測(cè)分析器的不含遞歸調(diào)用的一種有效方法是使用一張分析表和一個(gè)棧進(jìn)行聯(lián)合控制,下面構(gòu)造預(yù)測(cè)分析表:根據(jù)文法g'有:first(s) = ( , a )follow(s) = ) , , , #first(l) =
22、 ( , a )follow(l) = ) first(l') = ,follow(l') = ) 按以上結(jié)果,構(gòu)造預(yù)測(cè)分析表m如下:文法g'是ll(1)的,因?yàn)樗膌l(1)分析表不含多重定義入口。預(yù)測(cè)分析器對(duì)輸入符號(hào)串(a,(a,a)做出的分析動(dòng)作如下:步驟棧剩余輸入串輸出1#s(a,(a,a)#2#)l(a,(a,a)#s (l)3#)la,(a,a)#4#)l'sa,(a,a)#l sl'5#)l'aa,(a,a)#s a6#)l',(a,a)#7#)l's,(a,a)#l' ,sl'8#)l's(
23、a,a)#9#)l')l(a,a)#s (l)10#)l')la,a)#11#)l')l'sa,a)#l sl'12#)l')l'aa,a)#s a13#)l')l',a)#14#)l')l's,a)#l' ,sl'15#)l')l'sa)#16#)l')l'aa)#s a17#)l')l')#18#)l')#l'e19#)l')#20#)#l'e21# 9. 解答:各非終結(jié)符
24、的first集:first(s)=first(a)efirst(b)eeb=a,b, efirst(a)=be=b,efirst(b)ea=a,efirst(c)=first(a) efirst(d)first(b) =a,b,cfirst(d)=ac=a,c各個(gè)候選式的first集為:first(ab)=a,b, e first(bc)=bfirst(e)e first(b)bfirst(ad)=a first(ad)=a,b,cfirst(b)=b first(as)=afirst(c)=c 各非終結(jié)符的follow集的計(jì)算:follow(s)=#follow(d) =#follow(a)
25、=(first(b)e)follow(s)first(d) =a,#,cfollow(b)=follow(s) =#follow(c)=follow(s) =#follow(d)=follow(b)follow(c) =#10解答:(1) 求first和follow集 first(e)=first(t)=(,a,b, first(e')=+, e first(t)=first(f)=(,a,b, first(t')=(,a,b, , e first(f)=first(p)=(,a,b, first(f')=*,e first(p)=(,a,b, (計(jì)算順序)follow
26、(e)= #, ) (1,7)follow(e')= follow(e)=#,) (1)(使用的產(chǎn)生式)follow(t) = first(e')efollow(t') (1,4) = +),#=+,),#follow(t')= follow(t)=+,# (3)follow(f)= first(t')efollow(t) (3,4) = (,a,b,+ ,),#follow(f')= follow(f) (5) = (,a,b,+ ,),#follow(p)= first(f')efollow(f) (5,6) =*,(,a,b,+ ,
27、),# (2) 證明: a. 文法不含左遞歸;b. 每個(gè)非終結(jié)符的各個(gè)侯選式的first集不相交;c. first(e')follow(e')=+, e#,),=ffirst(t')follow(t')=(,a,b, e+,)=ffirst(f')follow(f')=*, e,a,( ,+,#= f改造后的文法滿足ll(1)文法的三個(gè)條件,是ll(1)文法。(3) 預(yù)測(cè)分析表如下所示。ab*+()#eete'ete'ete'ete'e'e'+ee'ee'ettft'tft&
28、#39;tft'tft't't'tt'tt'et'tt'tt'et'effpf'fpf'fpf'fpf'f'f'ef'ef'*f'f'ef'ef'ef'ef'eppapbpp(e)11. 解答:(1)sabc aaebbea. 文法不含左遞歸; b. s,a,b各候選式的first集不相交;c. first(a)follow(a)=a,eb=f first(b)follow(b)=b,ef=f該文法為ll
29、(1)文法。(2) sabaabe bbe a. 文法不含左遞歸;b. s,a,b各候選式的first集不相交;c. first(a)follow(a)=a,b, eb=b f 該文法不是ll(1)文法。12. 解答: 最右推導(dǎo):e=>t=>f=>(e)=>(et)=>(ef)=>(ei)=> (ti)=>(t*fi)語法樹:圖4.1 句型(t*fi)的語法樹 短語:(t*fi),t*fi,t*f,i 素短語:t*f,i最左素短語:t*f 由于e =>e+t =>e+t*f,故e+t*f為該文法的句型 短語:t*f、e+t*f 直接短
30、語: t*f 句柄: t*f13. 解答:最左推導(dǎo):s=> (t) => (t,s) => (s,s) => (a,s) => (a,(t) => (a,(t,s) => (a,(s,s) => (a,(a,s) => (a,(a,a)最右推導(dǎo):s=> (t) => (t,s) => (t,(t) => (t,(t,s) => (t,(t,a) => (t,(t,a) => (t,(a,a) => (s,(a,a) => (a,(a,a)文法中s和t的firstvt和lastvt集為:f
31、irstvt(s)=a,( firstvt(t)=,a, ( lastvt(s)=a, ) lastvt(t)=,a,) 文法gs的算符優(yōu)先關(guān)系表: 根據(jù)優(yōu)先關(guān)系表,對(duì)每個(gè)終結(jié)符或#建立符號(hào)f與g,把f(和g)分成一組。根據(jù)gs的算符優(yōu)先關(guān)系表,畫出如下的有向圖。優(yōu)先函數(shù)如下:用算符優(yōu)先分析法分析句子(a,(a,a)。給定的輸入符號(hào)串是文法的一個(gè)句子。14.解答:(1).拓廣文法(0)s' às (1)s àas (2)s àbs (3)s àc(2).寫出所有的項(xiàng)目1. s' à · s 2.
32、s' à s· 3. s à · as 4. s àa · s 5. s àas· 6. s à · bs 7. s àb · s 8. sàbs· 9. s à · c 10. s à c ·(3).求項(xiàng)目集規(guī)范族每個(gè)項(xiàng)目集中的各個(gè)項(xiàng)目不沖突,則是lr(0)文法。(4).構(gòu)造lr(0)分析表狀態(tài)actiongotoabc#ss0s2 s5s31s1 accs2 s2 s5s34s3 r3r3r3r3s4 r
33、1r1r1r1s5 s2 s5s36s6 r2r2r2r215. 解答:(1) 該文法的拓廣文法g'為 0s' s 1s sab 2s br 3r s 4r a其lr(0)項(xiàng)目集規(guī)范族和識(shí)別活前綴的dfa如下:i0 = s'·s, s·sab, s·bri1 = s's·, ss·abi2 = sb·r, r·s, r·a, s·sab, s·bri3 = ssa·bi4 = sbr·i5 = rs·, ss·abi6 =
34、ra·i7 = ssab·顯然,i1和i5存在移進(jìn)-歸約沖突。求s'和r的follow集: follow(s')=# follow(r)=follow(s)=a,#在i5中,出現(xiàn)的移進(jìn)歸約沖突,且follow(r)a=a,不能用slr(1)方法解決。因此,此文法不是slr(1)文法。 (2) 該文法的拓廣文法g'為 0s' s1s asab2s ba3a aa4a b5b b其lr(0)項(xiàng)目集規(guī)范族和識(shí)別活前綴的dfa如下:i0 = s'&
35、#183;s, s·asab, s·ba, b·bi1 = s's·i2 = bb·i3 = sa·sab, s·asab, s·ba, b·bi4 = sb·a, a·aa, a·b, b·bi5 = sas·ab, a·aa, a·b, b·bi6 = sasa·b, b·bi7 = aa·a, a·aa, a·b, b·bi8 = ab·i9
36、= sba·i10 = sasab·i11 = aaa·顯然,上述狀態(tài)中沒有出現(xiàn)沖突。顯然,該文法是lr(0)的文法,因此也是slr(1)的。 求各個(gè)非終結(jié)符的follow集,以便構(gòu)造分析表:follow(s')=# follow(s)=a,b,# follow(a)=a,b,# follow(b)=a,b,#構(gòu)造的slr(1)分析表如下:16. 解答:(1) 構(gòu)造其拓廣文法g'的產(chǎn)生式為 0s' s
37、1s a2a ba3a e4b ab5b b構(gòu)造其lr(0)項(xiàng)目集規(guī)范族和goto函數(shù)(識(shí)別活前綴的dfa)如下:i0 = s'·s, #, s·a, #, a·ba, #, a·, #, b·ab, a/b/#, b·b, a/b/# i1 = s's·, #i2 = sa·, #i3 = ab·a, #, a·ba, #, a·, #,
38、 b·ab, a/b/#, b·b, a/b/#i4 = bb·, a/b/# i5 = ba·b, a/b/#, b·ab, a/b/#, b·b, a/b/#i6 = aba·, #i7 = bab·, a/b/#該文法的lr(1)項(xiàng)目集規(guī)范族中沒有沖突,所以該文法是lr(1)文法。構(gòu)造lr(1)分析表如下:以上分析表無多的定義入口,所以該文法為lr(1)文法
39、。(3)對(duì)于輸入串a(chǎn)bab,其分析過程如下: 17. 解答:(1) 對(duì)于產(chǎn)生式saaab|bbba 來說first(aaab)first(bbba)=ab=fa,bvn僅有一條候選式。因此,這個(gè)文法是ll(1)的。(2) 下面構(gòu)造這個(gè)文法的識(shí)別活前綴的dfa。i0 = s'·s, s·aaab, s·bbba, a·, b· i1 = s's·i2 = sa·aabi3 = sb·bbai4 = saa·ab, a·i5 = sbb·ba, b·i6 = sa
40、aa·bi7 = sbbb·ai8 = saaab·i9 = sbbba·由于follow(a)=follow(b)=a, b,因此項(xiàng)目集i0中存在歸約-歸約沖突。在i0狀態(tài)下,當(dāng)輸入符號(hào)是a或是b時(shí),不知用ae還是be進(jìn)行歸約。故此文法不是slr(1)的。但是,此文法時(shí)lr(1)的。18. 解答:該文法的拓廣文法g'為 0s' s1s (sr2s a3r ,sr4r )構(gòu)造其lr(0)項(xiàng)目集規(guī)范族和goto函數(shù)(識(shí)別活前綴的dfa)如下:i0 = s'·s, s·(sr, s·ai1 = s'
41、;s·i2 = s(·sr, s·(sr, s·ai3 = sa·i4 = s(s·r, r·,sr, r·)i5 = s(sr·i6 = r)·i7 = r,·sr, s·(sr, s·ai8 = r,s·r, r·,sr, r·)i9 = r,sr·每個(gè)lr(0)項(xiàng)目集中沒有沖突。因此,此文法是lr(0)文法。其分析表如下:19解答: 略!第5章習(xí)題解答:1,2,3 解答: 略!4. 解答:(1) 設(shè)s,l,b的值的屬性用
42、val表示:s's printf(s.val)sl1.l2 s.val:= l1.val+ l2.val/2l2.lengthsl s.val:=l.valll1b l.val:=l1.val*2+b.val,l.length = l1.length+1 lb l.val:=b.val),l.length:=2 b0 b.val:=0b 1 b.val:=1(2) 為s,l引入屬性h,用來記錄配對(duì)的括號(hào)個(gè)數(shù):s's printf(s.h)sa s.h:=0s(l) s.h:=s.h+1ll(1),s s.h:=l(1).h+s.hls l.h:=s.h)(3) 為d引入一個(gè)綜合
43、屬性h,用來記錄d中含id的個(gè)數(shù):pd printf(d.h)dd1;d2 d.h:=d1.h+d2.hdid:t d.h:= 1dproc id; d1;s d.h:=d1.h+15. 解答:輸入串為bcccaadadadb時(shí)的語法樹為:采用修剪語法樹的方法,按句柄方式自下而上歸約該語法樹,在歸約時(shí)調(diào)用相應(yīng)的語義規(guī)則,由此得到最終的翻譯結(jié)果為:34242421.6. 解答: (a+b)+(c+d/(e-3)*87. 解答:(1) ab-c+*(2) a not c d not or not or(3) abcde/+*+(4) a b and c not d or or (5) a-bc-d
44、+*+(6) a b or c d not e and or and8. 解答:三元式四元式 (+,a,b)1.(+,a,b,t1) (-,1,-)2.(-,t,-, t2) (+,c,d)3.(+,c,d,t3) (*,2,3)4.(*, t2,t 3,t4) (+,a,b)5.(+,a,b,t5) (+,c,5)6.(+, t5,c, t6) (-,4,6)7.(-, t4, t6 ,t7)9. 解答:四元式代碼為:1. (jnz,a,_, x)2. (j,_,_,3)3. (jnz,b,_,5)4. (j,_,_,y)5. (jnz,c,_,y)6. (j,_,_,7)7. (jnz,d
45、,_,y)8. (j,_,_,x)10. 解答:11. 解答:(1) 四元式序列為: 1(j<,a,c,3)8.(:=,t,-,c) 2.(j,-,-,14)9.(j,-,-,14) 3.(j<,b,d,5)11.(j,-,-,14)4.(j,-,-,14)12.(+,a,2,t2) 5.(j=,a,1,7)13.(:=, t2,-,a)6.(j,-,-,10) 14.7.(+,c,1,t1) (2) 四元式序列為:1. (j0,x,0,3)7. (j,_,_,12)2. (j,_,_,8)8. (,x,2,t2)3. (j,y,0,5)9. (:,t2,_,x)4. (j,_,_
46、,8)10. (,y,3,t3)5. (,x,y,t1)11. (:,t3,_,y)6. (:,t1,_,z)12. (3) 四元式序列為:0. (+,a,3,t0)1. (:=,t0 , ,t1)2. (*,c,a,t2)3. (*,t2,2,t3)4. (:=, t3, ,b)5. (j<,x,0,7)6. (j, , ,0)7.(4) 四元式序列為:0. (*,b,2,t0)1. (:=, t0, ,i)2. (:=,100, , t1 )3. (j, , , 6)4. (+,i,1,t2 )5. (:=, t2, , i)6. (j>, i,t1,15)7. (+, a,
47、b, t3 )8. (+, c, d, t4 )9. (*,t3, t4, t5) 10. (+, a, b, t6 )11. (+, t6 c, t7 )12. ( -, t5, t7, t8) 13. ( :=, t8, , x )14. (j, , , 4)15.12. 解答:略!第6章習(xí)題解答:1,2,3,4,5 解答:略!6. 解答:本題考查的要點(diǎn)是掌握棧式動(dòng)態(tài)存儲(chǔ)分配策略中運(yùn)行的布局,填充過程活動(dòng)記錄display表的內(nèi)容。運(yùn)行棧的布局遵循“先進(jìn)后出”原則,即一個(gè)過程調(diào)用另一個(gè)過程時(shí),被調(diào)用過程則在調(diào)用過程的棧頂構(gòu)筑自己的數(shù)據(jù)區(qū),形成自己的活動(dòng)記錄,包括自己的display表。而d
48、isplay表內(nèi)容的項(xiàng)數(shù)與過程的嵌套層次有關(guān),一般比過程的嵌套層數(shù)大1。(1) demo a此時(shí)的運(yùn)行棧只有主程序demo和過程a的2個(gè)數(shù)據(jù)區(qū),過程a只引用主程序demo全局?jǐn)?shù)據(jù)和其自身的局部數(shù)據(jù),因此其display表內(nèi)容有2項(xiàng),即主程序數(shù)據(jù)區(qū)首址和過程a的主程序數(shù)據(jù)區(qū)首址。(2) demo ab 此時(shí)的運(yùn)行棧只有主程序demo、過程a和過程b的3個(gè)數(shù)據(jù)區(qū),過程b嵌套定義在過程a中,要引用主程序demo全局?jǐn)?shù)據(jù)、過程a的數(shù)據(jù)和其自身的局部數(shù)據(jù),因此其display表內(nèi)容有3項(xiàng),即主程序數(shù)據(jù)區(qū)首址、過程a的主程序數(shù)據(jù)區(qū)首址和過程b本身的數(shù)據(jù)區(qū)首址。(3) demo abb 此時(shí)的運(yùn)行棧包括主程
49、序demo、過程a和2個(gè)過程b的實(shí)例的4個(gè)數(shù)據(jù)區(qū),過程b要引用的數(shù)據(jù)區(qū)還是3個(gè):主程序demo全局?jǐn)?shù)據(jù)、過程a的數(shù)據(jù)和當(dāng)前活躍過程b的局部數(shù)據(jù)(棧頂數(shù)據(jù)項(xiàng)),因此其display表內(nèi)容還是有3項(xiàng),即主程序數(shù)據(jù)區(qū)首址、過程a的主程序數(shù)據(jù)區(qū)首址和當(dāng)前活躍過程b本身的數(shù)據(jù)區(qū)首址。(4) demo abba 此時(shí)的運(yùn)行棧包括主程序demo、2個(gè)過程a和2個(gè)過程b的實(shí)例的5個(gè)數(shù)據(jù)區(qū),但過程a只引用主程序demo全局?jǐn)?shù)據(jù)和其自身的局部數(shù)據(jù),因此其display表內(nèi)容只有2項(xiàng),即主程序數(shù)據(jù)區(qū)首址和過程a的主程序數(shù)據(jù)區(qū)首址。各個(gè)運(yùn)行時(shí)刻運(yùn)行棧的布局和使用的display表如圖。第7章習(xí)題解答:1. 解答:a:
50、局部 b:全局 c:代碼外提d:削減運(yùn)算強(qiáng)度 e:刪除歸納變量2,3. 解答:略!4. 解答:程序流圖如下:回邊為:b4b3,循環(huán)l=b3,b45.解答:各結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集d(n)如下: d(n0) = n0 d(n1) = n0, n1 d(n2) = n0, n1, n2 &
51、#160; d(n3) = n0, n1, n2, n3 d(n4) = n0, n1, n2, n4 d(n5) = n0, n1, n2, n5 d(n6) = n0, n1, n2, n5, n6 d(n7) = n0, n1, n2,
52、n5, n6, n7 回邊和循環(huán): 因?yàn)?d(n5) = n0, n1, n2, n5 ,且 n5 n2,所以 n5 n2為一條回邊。根據(jù)它求出的循環(huán) l1 = n2, n5, n3, n4。 因?yàn)閐(n6) = n0, n1, n2, n5, n6 ,且 n6 n1,所以n6 n1為一條回邊。根據(jù)這條回邊,求出的循環(huán) l2 = n6, n1, n5, n3, n4, n2。6. 解答:(1) 首先劃分基本塊并畫出其程序流圖,其中有三個(gè)基本塊b1,b2,b3,有一條回邊b
53、2 b2,相應(yīng)的循環(huán)是b2。 (2) 強(qiáng)度削弱: 在b2中a和b為乘法運(yùn)算,可以削弱它們的運(yùn)算強(qiáng)度,變乘法為加法。優(yōu)化結(jié)果如下圖。 (3) 刪除歸納變量:在循環(huán)中,i是循環(huán)的基本歸納變量,a,b是同族的歸納變量,且有線性關(guān)系,變換循環(huán)控制條件,流圖如下。(4) 代碼外提:由于刪除歸納變量后有r :=k * 100,是循環(huán)不變運(yùn)算,可以提到前置結(jié)點(diǎn)b2'中。7. 解答:8. 解答:(1) dag如下: (2) 優(yōu)化后的三地址代碼為:t3:srt4:sra:5*t4b:t3t4 9. 解答:(本題中假設(shè)采用字節(jié)地址,兩個(gè)字節(jié)作為一個(gè)機(jī)器字。)(1)程序的中間代碼如下:
54、; b1: read n /* 置初值 */ i := 2 &
55、#160; b2: if i > n goto b4 /* 第一個(gè)for語句 */ b3: t1 := i t2 := addr(a) /* 數(shù)組a
56、的基地址 */ t1 := 2 * t1 t2t1 := true
57、160; i := i + 1 goto b2 b4: i := 2 t3 := n * 0.5
58、 t3 := t3 + 1 /* t3是對(duì)t3的值取整 */ b5: if i > t3 goto b12
59、0; b6: t4 := i t5 := addr(a) t4:= 2 * t4
60、160; if t5t4 goto b8 b7: goto b11 b8: j := 2 * i b9: if j > n goto b11 /* 第三個(gè)for語句 */ b10: t6 := j
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024版文具采購合同3篇
- 專用木結(jié)構(gòu)工程承包合同書2024年版版B版
- 專業(yè)橋架施工包工協(xié)議范例(2024版)版B版
- 2025年4S店汽車銷售及二手車置換服務(wù)合同范本3篇
- 2024跨國技術(shù)轉(zhuǎn)讓與合作合同
- 專業(yè)項(xiàng)目建議書編寫委托協(xié)議簡(jiǎn)化版版B版
- 2025年度科研場(chǎng)地租賃合同終止及設(shè)備回收協(xié)議3篇
- 2025年度老舊小區(qū)墻體拆除及改造工程勞務(wù)分包合同范本4篇
- 2025年度酒店會(huì)議室租賃協(xié)議書(含全方位服務(wù)套餐)
- 二零二五年度食堂食堂食堂食堂員工餐廳食品安全監(jiān)管合同
- 金色簡(jiǎn)約蛇年年終總結(jié)匯報(bào)模板
- 農(nóng)用地土壤環(huán)境質(zhì)量類別劃分技術(shù)指南(試行)(環(huán)辦土壤2017第97號(hào))
- 反向開票政策解讀課件
- 工程周工作計(jì)劃
- 房地產(chǎn)銷售任務(wù)及激勵(lì)制度
- 六年級(jí)語文下冊(cè)14文言文二則《學(xué)弈》課件
- 2024年內(nèi)蒙古中考語文試卷五套合卷附答案
- 并購指南(如何發(fā)現(xiàn)好公司)
- 垃圾分類亭合同協(xié)議書
- 物權(quán)轉(zhuǎn)移協(xié)議
- 高三高考地理一輪課時(shí)練習(xí):洋流(單選題)
評(píng)論
0/150
提交評(píng)論