編譯原理課后習(xí)題答案

1、第一章1典型的編譯程序在邏輯功能上由哪幾部分組成？答：編譯程序主要由以下幾個(gè)部分組成：詞法分析、語法分析、語義分析、中間代碼生成、中間代碼優(yōu)化、目標(biāo)代碼生成、錯(cuò)誤處理、表格管理。2. 實(shí)現(xiàn)編譯程序的主要方法有哪些？答：主要有：轉(zhuǎn)換法、移植法、自展法、自動(dòng)生成法。3. 將用戶使用高級語言編寫的程序翻譯為可直接執(zhí)行的機(jī)器語言程序有哪幾種主要的方式？答：編譯法、解釋法。4. 編譯方式和解釋方式的根本區(qū)別是什么？答：編譯方式：是將源程序經(jīng)編譯得到可執(zhí)行文件后，就可脫離源程序和編譯程序單獨(dú)執(zhí)行，所以編譯方式的效率高，執(zhí)行速度快；解釋方式：在執(zhí)行時(shí)，必須源程序和解釋程序同時(shí)參與才能運(yùn)行，其不產(chǎn)生可執(zhí)行程序

2、文件，效率低，執(zhí)行速度慢。第二章1. 喬姆斯基文法體系中將文法分為哪幾類？文法的分類同程序設(shè)計(jì)語言的設(shè)計(jì)與實(shí)現(xiàn)關(guān)系如何？答：1）0型文法、1型文法、2型文法、3型文法。2）2. 寫一個(gè)文法，使其語言是偶整數(shù)的集合，每個(gè)偶整數(shù)不以0為前導(dǎo)。答：zsme | bs1|2|3|4|5|6|7|8|9me | d | mdd0|sb2|4|6|8e0|b3. 設(shè)文法g為：n d|ndd 0|1|2|3|4|5|6|7|8|9請給出句子123、301和75431的最右推導(dǎo)和最左推導(dǎo)。答：nndn3nd3n23d23123nndnddddd1dd12d123nndn1nd1n01d01301nndnddd

3、dd3dd30d301nndn1nd1n31nd31n431nd431n5431d543175431nndnddndddnddddddddd7dddd75ddd754dd7543d754314. 證明文法 sises|is| i是二義性文法。答：對于句型iises存在兩個(gè)不同的最左推導(dǎo)：sisesiisessisiises所以該文法是二義性文法。5. 給出描述下面語言的上下文無關(guān)文法。（1） l1=anbnci |n=1,i=0 （2） l2=aibj|j=i=1（3） l3=anbmcmdn |m,n=0答：（1） sabaaab | abbcb | e（2） sasb |abaa | e（

4、3） sasd | a | eabac | e6. 設(shè)計(jì)一個(gè)最簡的dfa m,使其能夠識別所有的被3整除的無符號十進(jìn)制整數(shù)。答：7. 設(shè)計(jì)一個(gè)dfa,使其能夠接受被4整除的二進(jìn)制數(shù)。答：8. 寫出表達(dá)下列各項(xiàng)的正則表達(dá)式。（1）二進(jìn)制數(shù)且為5的倍數(shù)。（2）=a,b,c,第一個(gè)a位于第一個(gè)b之前的字符串。（3）=a,b,c,包含偶數(shù)個(gè)a的字符串。（4）=0，1,不包含11子串的字符串。答：（1）可以先畫出相應(yīng)的有限自動(dòng)機(jī):添加新的開始狀態(tài)s和終止?fàn)顟B(tài)t:根據(jù)以上自動(dòng)機(jī)，列出以下方程： s=a a=0a+1b+t b=0c+1d c=0e+1a d=0b+1c e=0d+1e解以上方程組： e=1

5、*0d a=0*1b+0*t代入 c=01*0d+1a代入 c=01*00b+01*01c+1a c=xb+ya 其中x=(01*01)*01*00 y=(01*01)*1代入 b=0c+10b+11c b=(0|11)c+10b b=(10)*(0|11)c將c=xb+ya代入上式 b=ub+va b=u*va其中u=(10)*(0|11)x v=(10)*(0|11)y將b=u*va代入 a=0*1u*va+0*t a=(0*1u*v)*0*t將a代入 s=(0*1u*v)*0*t串(0*1u*v)*0*即為所求。（2）該題目理解為：至少有一個(gè)a和一個(gè)b，且a出現(xiàn)在b的前面（可以有間隔），

6、則答案為：c*a(a|c)*b(a|b|c)*（3）(b|c)*a(b|c)*a)*(b|c)*(a(b|c)*a | b | c)*（4）(0|10)*(1|e)第三章1. 詞法分析器的功能是什么？答：讀源程序的字符序列，逐個(gè)拼出單詞，并構(gòu)造相應(yīng)的內(nèi)部表示token；同時(shí)檢查源程序中的詞法錯(cuò)誤。2. 試分析分隔符（空格、跳格及回車等）對詞法分析的影響。答：空格、跳格、回車等分隔符號對詞法分析不起作用，可以刪除。但是回車符號可以用于錯(cuò)誤定位，所以在刪除回車符號前需要統(tǒng)計(jì)回車的個(gè)數(shù)。3. 給出識別c語言全部實(shí)型常數(shù)的自動(dòng)機(jī)。答：(+|-|e)(1-90-9*|0)(.0-90-9*|e) (e(

7、+|-|e)0-90-9*)4. 寫出識別c語言中所有單詞的lex程序。答：l=a-z | a-zd=0-9d1=1-9%(l|_)(l|d|_)*return (1);d1d*return (2);+return (3);第四章1. 設(shè)有如下文法gs:saabbcd | eaasd | ebsah | ec | ecsf | cg | e(1) 求每個(gè)產(chǎn)生式的predict集。(2) 該文法是否為ll(1)文法？為什么？答：(1)predict(saabbcd)=apredict(s e)=#,d,f,a,h predict(aasd)=a,dpredict(a e)=h,a,d,b,epr

8、edict(bsah)=a,d,hpredict(b ec)=epredict(b e)=bpredict(csf)=a,fpredict(c cg)=a,f,gpredict(c e)=g,b(2)由于predict(aasd) predict(a e)，所以該文法不是ll(1)文法。2. 下列描述括號匹配的文法中，哪些是ll(1)文法？(1)s(ss | es ) | e(2)s(s)s | e(3)ss(s)s | e(4)s(s | ss(s) | e答：(1)不是，(2)是，(3)不是，(4)不是3. 已知文法ge:ee+t | ttt*f | ffi | (e)請按遞歸下降法構(gòu)造該

9、文法的語法分析程序。答：求產(chǎn)生式的predict集合：predict(ee+t)=i,(predict(et)=i,(predict(tt*f)=i,(predict(tf)=i,(由于文法中非終極符號e和t對應(yīng)的產(chǎn)生式的predict集合的交集都不為空，所以該文法不滿足自頂向下分析的條件，現(xiàn)對文法進(jìn)行等價(jià)變換得到如下文法：etee+te | etftt*ft | efif(e)求新文法的predict集合：predict(ete)=(,ipredict(e+te)=+predict(ee)=#,)predict(tft)=i,(predict(t*ft)=*predict(te)=+,),#

10、predict(fi)=ipredict(f(e)=(由于以上文法中任意非終極符號對應(yīng)的產(chǎn)生式的predict集合的交集都為空，所以滿足自頂向下分析的條件，所以可以寫出如下的遞歸下降語法分析偽代碼：void e() if(token(,i) t();e(); else error();void e() if(token+) match(+);t();e(); else if(token#,) ; else error();void t() if(tokeni,() f();t(); else error();void t() if(token*) match(*);f();t(); else

11、if(token+,),#) ; else error();void f() if(tokeni) match(i); else if(token() match();e();match(); else error();4. 構(gòu)造一個(gè)ll(1)文法g，它能識別語言l:l=w | w為字母表s上不包括兩個(gè)相鄰的1的非空串，其中s=0，1。并證明你所構(gòu)造的文法是ll(1)文法。答：a0e | 1fb0e | 1fc0eeb | efc | epredict(a0e)=0predict(a1f)=1predict(b0e)=0predict(b1f)=1predict(eb)=0,1predict(

12、ee)=#predict(fc)=0predict(fe)=#對任意非終極符號對應(yīng)的產(chǎn)生式的predict集合的交集都為空，所以該文法是ll(1)文法。5. 已知文法ga為：aaabe | abbb | d(1) 試給出與ga等價(jià)的ll(1)文法ga。(2) 構(gòu)造ga的ll(1)分析表并給出輸入串a(chǎn)ade#的分析過程。答：(1)所求ga為：aaa(1)aabe (2)a e(3)bdb(4)bbb (5)b e(6)predict(aaa)=apredict(aabe)=apredict(ae)=#,dpredict(bdb)=dpredict(bbb)=bpredict(be)=e對任意非終

13、極符號對應(yīng)的產(chǎn)生式的predict集合的交集都為空，所以該文法是ll(1)文法。(3) 分析表如下：abde#a(1)a(2)(3)(3)b(4)b(5)(6)aade#的分析過程如下分析棧輸入流動(dòng)作a#aade#替換(1)aa #aade#匹配a #ade#替換(2)abe#ade#替換(1)aabe#ade#匹配abe#de#替換(3)be#de#替換(4)dbe#de#匹配be#e#替換e#e#匹配#成功第五章（這章答案是錯(cuò)的）1. 設(shè)有下列文法：(1)saaaabab(2)sassbsassssc(3)sassbasaaa(4)scasccbbccbbbacaaa構(gòu)造上述文法的lr(0

14、)歸約活前綴狀態(tài)機(jī)，并給出lr(0)分析表。答：(1)(2)(3)(4)2. 設(shè)有下列文法：(1)ssas | b(2)sbsb | csc | b | c(3)sbsb | bsc | d(4)sasb | bsa | ab(5)ssab | brrs | a(6)ssab | babbaaa | b(7)saaab | bbbabeae(8)aaabe | babdb | e說明上述文法是否為slr(1)文法。若是，請構(gòu)造slr(1)分析表；若不是，請說明理由。答：(1)(2)(3)(4)(5)(6)(7)(8)3. 設(shè)有下列文法：saad | bbd | abe | baeagbg說明該

15、文法是lr(1)文法，但不是lalr(1)文法。答：4. 設(shè)有下列文法：(1)ee+t | tttf | tf(e) | f* | a | b(2)saa | bac | dc | bdaad說明上述文法是否為slr(1)文法？是否為lalr(1)文法？并構(gòu)造相應(yīng)的分析表。答：(1)(2)5. 設(shè)有下列文法：lmlb | ame說明上述文法是否為lr(1)文法，若不是，請說明理由。答：第六章1.試寫出下列類型的內(nèi)部表示： eger b.array 1.5 of record i:integer; b:boolean end c.array 1.5 of record a:array

16、1.10; r:record i,j:integer end end d. record r: record x,y:real end;a: array 1.10 of integer end2. 設(shè)當(dāng)前層數(shù)為l，可用區(qū)距為101，且有下列程序段： const mm=333；nn=444； type atype = array1.10 of real; rtype = record i,j:integer end; var a,b:atype; x,y:real 試寫出各標(biāo)識符的內(nèi)部表示。3. 設(shè)當(dāng)前層數(shù)和區(qū)距分別為l和off，且有函數(shù)說明首部： function f（a：atype；var

17、b：atype；var x：real）：integer 其中atype的定義見題5，試寫出f的內(nèi)部表示。4. 要求在下面括號中寫上相應(yīng)（層數(shù)）和區(qū)距（off）。 （）（）procedure g（a：atype；（）（）var b：atype；（）（）var x：real（）（）（）（）.5. 給出下面c程序掃描到語句c=a+b+x時(shí)相應(yīng)的全局符號表(采用順序表結(jié)構(gòu))。main（）int a=0;float c=1.0;float a=3.0;float x=1.3;float b=0.3; int b=10; c=a+b+x;6. 給出題1中程序掃描到語句c=a+b+x時(shí)相應(yīng)的全局符號表(采用

18、外拉鏈的散列表結(jié)構(gòu))。7. 根據(jù)標(biāo)識符的作用域規(guī)則，分別給出圖6.5的程序中，過程p、q、r、s中有效的標(biāo)識符。第七章1. 將算術(shù)表達(dá)式 (a+b)*(c+d)-(a+b+c) 翻譯成四元式序列。2. 將下列語句翻譯成四元式序列：a. if x0 then x:=0 else x:=1b. while x0 do x:=x-1c. if x0 then x:=x+1 else if x 0 dowhile y 0 do begin y:=y-x; x:=x-1 end3. 給出如下程序段的四元式序列。(四元式的操作符可用自身代替)。其中a：array of 1.10 of integer。 a

19、:=1;while a=10 do begin if ab then aa:=ab+2; else a:=a+1; b:=b+1; end4. 試將for語句翻譯成四元式序列。5. 試將until語句翻譯成四元式序列。6. 試將case語句翻譯成四元式序列。7. 試給出4、5、6題中翻譯過程的語法制導(dǎo)程序。第八章1. 將下面的程序段劃分為基本塊并畫出其程序流圖。read(a);read(b);f:=1;c:=a*a;d:=b*b;if c100 goto l2;goto l3;l2:f:=f-1;goto l1;l3:write(e);2. 假設(shè)有如下語句序列，寫出常表達(dá)式優(yōu)化前和優(yōu)化后的四元

20、式中間代碼。(1)i:=1;(2)a:=20;j:=i*(i+1);b:=a*(a+10);k:=2*(i+j);c:=a*b;3. 假設(shè)有如下語句序列或表達(dá)式，寫出公共表達(dá)式優(yōu)化前和優(yōu)化后的四元式中間代碼。(1)x:=x*y+z; y:=x*y+z; z:=x*y+z;(2)(a*b+c)/(a*b-c)+(c*b+a-d)/(a*b+c)4. 寫出如下循環(huán)語句不變式外提后的四元式中間代碼。while i=100 dobeginu:=a*b;m:=u*u;s:=s+m*m;i:=i+1;end5. 寫出下面循環(huán)語句不變式外提后的四元式中間代碼，其中數(shù)組各下標(biāo)的類型為1.10。while i=

21、100 dobeginj:=1;while j=100 dobegink:=1;while k=100 doaijk:=0;endend第九章1.過程活動(dòng)記錄包含哪些信息？各信息的作用？何時(shí)填寫它們？2.下面是一個(gè)調(diào)用遞歸函數(shù)的pascal程序program pp(input,output) var k:integer; function f(n:integer):integer begin if n 0 then y:=y+1 else if x 0 then y:=y-1的目標(biāo)代碼，其中的變量均為非形參實(shí)型變量。 試寫出程序段while x 0 then y :=y-x else whil

22、e y 0 do y := y + xend的目標(biāo)代碼，其中變量均為非形參實(shí)型變量。 試為for循環(huán)語句設(shè)計(jì)目標(biāo)代碼。 試為repeat循環(huán)語句設(shè)計(jì)目標(biāo)代碼。 試為case語句設(shè)計(jì)目標(biāo)代碼。28acknowledgements my deepest gratitude goes first and foremost to professor aaa , my supervisor, for her constant encouragement and guidance. she has walked me through all the stages of the writing of thi

23、s thesis. without her consistent and illuminating instruction, this thesis could not havereached its present form. second, i would like to express my heartfelt gratitude to professor aaa, who led me into the world of translation. i am also greatly indebted to the professors and teachers at the depar

24、tment of english: professor dddd, professor ssss, who have instructed and helped me a lot in the past two years. last my thanks would go to my beloved family for their loving considerations and great confidence in me all through these years. i also owe my sincere gratitude to my friends and my fellow classmates who gave me their help and time in listening to me and helping me work out my problems during the difficult course of the thesis. my deepest gratitude goes first and foremost to professor aaa , my supervisor, for her constant encou