[編譯原理與技術]考試卷

1、西南科技大學網絡教育學院（2015）/（2016）學年 第 2 學期試題單A卷課程名稱： 編譯原理與技術 專業(yè)班級： 命題教師： 周宏毅 學生姓名： 學 號： 成 績： 考試時間： 月 日一、 簡答題 ( 每題4分，共5題，共20分 )1. 什么是編譯程序？ 編譯程序也叫編譯系統(tǒng)，是把用高級語言編寫的面向過程的源程序翻譯成目標程序的語言處理程序。主要是進行詞法分析和語法分析，又稱為源程序分析，分析過程中發(fā)現有語法錯誤，給出提示信息。2. 按編譯方式在計算機上執(zhí)行用高級語言編寫的程序，一般需經過那兩個階段，各自的任務是什么？ 編譯階段:詞法分析,語法分析,語義分析運行階段:中間代碼生成,中間代碼

2、優(yōu)化，目標代碼生成3. 編譯程序的組織形式，按邏輯可分為那幾個階段？ 詞法分析器、語法分析器、語義分析器、中間代碼生成器、獨立于機器的代碼優(yōu)化器、代碼生成器、依賴于機器的代碼優(yōu)化器4. 寫出“abc”的前綴、后綴及子串？前綴:a,ab后綴:c,bc字串:abc5. 數據空間的存儲分配策略有哪些？ 首次擬合法 最佳擬合法 最差擬合法二、 問答與作圖題 ( 每題12分，共1題，共12分 )6. 已知文法G(S)為: SS+DD*SDDD，HH Ha(S) 1、給出句型“(D，Ha)”最左推導和最右推導；2、給出句型“D*D+D”的語法樹；3、給出句型“(D，Ha)”的短語和素短語；最左推導：S=D

3、=H=(S)=(S+D)=(D+D)=(D,H+D)=(D,H+H)=(D,H+a) (一步0.25分,共2分)最右推導：S=D=H=(S)=(S+D)=(S+H)=(S+a)=(D+a)=(D,H+a) (一步0.25分,共2分)*DSD+SDSD+SD*SDS語法樹： 短語：“(D,Ha)”，“D,Ha”，“D,H”，“a”素短語：“D,H”，“a ”三、 計算題1 ( 每題13分，共1題，共13分 )7. 已知正規(guī)式(a)b*)*1、求等價的NFA；2、將NFA確定化3、若所求DFA可最小化，則求其最小化DFA；若無，說明原因。1、NFA M2、確定化：abI000,1,2 /I10,1

4、,20,1,20,1,2NFA M：3、最小化：ab01/111原圖已最小化四、 計算題2 ( 每題17分，共1題，共17分 )8. 已知文法G（D）為： Dint L| real LLL,id | id1、提公因子和消除左遞歸；2、計算每個非終結符的FIRST和FOLLOW；3、證明該文法是否為LL（1）文法？1提公因子和消除左遞歸:DTLTint | realLid LL,id L|2構造First和Follow集合First(D)=int，real Follow(D)=#First(T)=int，real Follow(T)=idFirst(L)=id Follow(L)=#First(

5、L)=，, Follow(L)=#3S Tint S Treal =；S L,id L S T=；該文法是LL(1)文法五、 計算題3 ( 每題13分，共1題，共13分 )9. 對文法G(S)：S a | b | (T)T T，S | S1、構造各非終結符的FIRSTVT和LASTVT集合；2、構造算符優(yōu)先表。1求FIRSTVT和LASTVT: FIRSTVT（）=a，b，( LASTVT() =,，a，b，）FIRSTVT（T）= a，b，（ LASTVT(T) =,，a，b，） （一條1.5分,共6分）2關系表 ab(),ab(=,=六、 計算題4 ( 每題13分，共1題，共13分 )10

6、. 已知文法G（E）：1. E E+T2. E T 3. T T*F 4. T F5. F (E)6. F i 的LR分析表為：Acction Goto Si +*（ ） $ETF0S5S41231S6Acc2r2s7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S5S119r1S7r1r110r3r3r3r311r5r5r5r5請按以下格式給出“i+i*i$”的LR分析過程。步驟棧輸入動作說明步驟棧輸入動作說明10i+i*i$ s5移入i 20i5 +i*i$ r6歸約i 30F3 +i*i$ r4 歸約F40T2 +i*i$ r2 歸約T50E1q +i*i$ s6 移入+60E1+6 i*i$ s5移入i 70E1+6i5 *i$ r6歸約i 80E1+6F3 *i$ r4 歸約F90E1+6T9 *i$ s7 移入*100E1+6T9*7 i$ s5移入i 11 0E1+6T9*7i5 $ r6歸約i 12 0E1+6T9*7F10 $ r3歸約T*F130E1+6T9 $ r1歸約E+T14 0E1 $ acc接受七、 計算題5 ( 每題12分，共1題，共1