《編譯原理》歷年試題及答案.doc

歷年試題及答案一 （每項選擇2分，共20分）選擇題1將編譯程序分成若干個“遍”是為了_b_。a.提高程序的執(zhí)行效率b.使程序的結(jié)構(gòu)更加清晰c.利用有限的機器內(nèi)存并提高機器的執(zhí)行效率d.利用有限的機器內(nèi)存但降低了機器的執(zhí)行效率2構(gòu)造編譯程序應(yīng)掌握_d_。a.源程序 b.目標(biāo)語言c.編譯方法 d.以上三項都是3變量應(yīng)當(dāng)c。a.持有左值 b.持有右值c.既持有左值又持有右值 d.既不持有左值也不持有右值4編譯程序絕大多數(shù)時間花在_d_上。a.出錯處理 b.詞法分析c.目標(biāo)代碼生成 d.管理表格5詞法分析器的輸出結(jié)果是_c_。a.單詞的種別編碼 b.單詞在符號表中的位置c.單詞的種別編碼和自身值 d.單詞自身值6正規(guī)式MI和M2等價是指_c_。a. MI和M2的狀態(tài)數(shù)相等 b.Ml和M2的有向弧條數(shù)相等。C.M1和M2所識別的語言集相等 d. Ml和M2狀態(tài)數(shù)和有向弧條數(shù)相等7中間代碼生成時所依據(jù)的是c。 a語法規(guī)則 b詞法規(guī)則 c語義規(guī)則 d等價變換規(guī)則8后綴式ab+cd+/可用表達式_b_來表示。 a a+b/c+d b (a+b)/(c+d) c a+b/(c+d) d a+b+c/d9程序所需的數(shù)據(jù)空間在程序運行前就可確定，稱為_c_管理技術(shù)。 a.動態(tài)存儲 b.棧式存儲 c.靜態(tài)存儲 d.堆式存儲10.堆式動態(tài)分配申請和釋放存儲空間遵守_d_原則。 a.先請先放 b.先請后放 c.后請先放 d.任意二（每小題10分，共80分）簡答題1.畫出編譯程序的總體結(jié)構(gòu)圖，簡述各部分的主要功能。2.已知文法GE: EET+|TTTF* | FFF | a 試證：FF*是文法的句型，指出該句型的短語、簡單短語和句柄. 3為正規(guī)式(a|b) *a(a|b)構(gòu)造一個確定的有限自動機。4設(shè)文法G(S)： S(L)|a S|a LL，S|S (1) 消除左遞歸和回溯； (2) 計算每個非終結(jié)符的FIRST和FOLLOW； (3) 構(gòu)造預(yù)測分析表。5 已知文法 A-aAd| aAb| 判斷該文法是否SLR（1）文法，若是構(gòu)造相應(yīng)分析表，并對輸入串a(chǎn)b#給出分析過程。6構(gòu)造算符文法GH的算符優(yōu)先關(guān)系（含）。 GH：HH;M|M Md|aHb7已構(gòu)造出文法G（S）（1）S BB（2）B aB（3）B b1）。給出DFA圖2）.給出LR分析表3）假定輸入串為abaab，請給出LR分析過程（即狀態(tài)，符號，輸入串的變化過程）。8將下面的語句翻譯成四元式序列： while ACBA(1) A-aAd(2)A- aAb(3)A- (2)構(gòu)造識別活前綴的DFA FOLLOW(A)=d,b,# 對于狀態(tài)I0：FOLLOW(A)a= 對于狀態(tài)I1：FOLLOW(A)a= 因為，在DFA中無沖突的現(xiàn)象，所以該文法是SLR(1)文法。 (3)SLR(1)分析表 狀態(tài) ACTION GOTO a B d # A 0 S2 r3 r3 r3 1 1 acc 2 S2 r3 r3 r3 3 3 S5 S4 4 r1 r1 r1 5 r2 r2 r2 (4)串a(chǎn)b#的分析過程 步驟 狀態(tài)棧 符號棧 當(dāng)前字符 剩余字符串 動作 1 0 # a b# 移進 2 02 #a b # 歸約A- 3 023 #aA b # 移進 4 0235 #aAb # 歸約A- aAb 5 01 #A # 接受 6 【解答】 由Md和Ma得：FIRSTVT(M)=d,a； 由H-H;得：FIRSTVT(H)=； 由HM得：FIRSTVT(M) cFIRSTVT(H)，即FIRSTVT(H)=;,d,a 由Md和Mb得：LASTVT(M)=d,b； 由H-，；m得：LASTVT(H)=； 由HM得：LASTVT（M）cLASTVT(H），即LASTVT(H)=;,d,b 對文法開始符H,有#H#存在，即有=，#,也即；，#d. #, b#。 對形如Pab，或PaQb，有a=b，由Ma|b得：a=b； 對形如PaR，而bFIRSTVT(R)，有ab。 由H；M得：；FIRSTVT(M)，即：d，：a 由MaH得：aFIRSTVT(H)，即：a；，a;，即：；，d；，b； 由MHb得：LASTVT(H)b，即：；b，db，bb 由此得到算符優(yōu)先關(guān)系表，見表3.5。7 【解答】（1）LR分析表如下：（2）分析表狀態(tài) ACTION GOTO a b # S B0 s3 s4 1 21 acc 2 S3 S4 53 s3 s4 64 r3 r3 5 R1 R1 r1 6 R2 R2 R2 (3) 句子abaab的分析過程表:句子abaab的分析過程步驟 狀態(tài) 符號棧 輸入串 所得產(chǎn)生式0 #0 # abaad# 1 #03 #a baad# 2 #034 #ab aab# Bb3 #036 #aB aab# BaB4 #02 #B aab# 5 #023 #Ba ab# 6 #0233 #Baa b# 7 #02334 #Baab # 8 #02336 #BaaB # 9 #0236 #BaB ad# 10 #025 #BB ad# 11 #01 #S d# 12 # # d# 13 識別成功 8 【解答】該語句的四元式序列如下（其中E1、E2和E3分別對應(yīng)：ACBD, A=1和