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

歷年試題及答案一 （每項(xiàng)選擇2分，共20分）選擇題1將編譯程序分成若干個(gè)“遍”是為了_。a.提高程序的執(zhí)行效率b.使程序的結(jié)構(gòu)更加清晰c.利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率d.利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率2構(gòu)造編譯程序應(yīng)掌握_。a.源程序 b.目標(biāo)語(yǔ)言c.編譯方法 d.以上三項(xiàng)都是3變量應(yīng)當(dāng)。a.持有左值 b.持有右值c.既持有左值又持有右值 d.既不持有左值也不持有右值4編譯程序絕大多數(shù)時(shí)間花在_上。a.出錯(cuò)處理 b.詞法分析c.目標(biāo)代碼生成 d.管理表格5詞法分析器的輸出結(jié)果是_。a.單詞的種別編碼 b.單詞在符號(hào)表中的位置c.單詞的種別編碼和自身值 d.單詞自身值6正規(guī)式MI和M2等價(jià)是指_。a. MI和M2的狀態(tài)數(shù)相等 b.Ml和M2的有向弧條數(shù)相等。C.M1和M2所識(shí)別的語(yǔ)言集相等 d. Ml和M2狀態(tài)數(shù)和有向弧條數(shù)相等7中間代碼生成時(shí)所依據(jù)的是。 a語(yǔ)法規(guī)則 b詞法規(guī)則 c語(yǔ)義規(guī)則 d等價(jià)變換規(guī)則8后綴式ab+cd+/可用表達(dá)式_來(lái)表示。 a a+b/c+d b (a+b)/(c+d) c a+b/(c+d) d a+b+c/d9程序所需的數(shù)據(jù)空間在程序運(yùn)行前就可確定，稱為_管理技術(shù)。 a.動(dòng)態(tài)存儲(chǔ) b.棧式存儲(chǔ) c.靜態(tài)存儲(chǔ) d.堆式存儲(chǔ)10.堆式動(dòng)態(tài)分配申請(qǐng)和釋放存儲(chǔ)空間遵守_原則。 a.先請(qǐng)先放 b.先請(qǐng)后放 c.后請(qǐng)先放 d.任意二（每小題10分，共80分）簡(jiǎn)答題1.畫出編譯程序的總體結(jié)構(gòu)圖，簡(jiǎn)述各部分的主要功能。2.已知文法GE: EET+|TTTF* | FFF | a 試證：FF*是文法的句型，指出該句型的短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄. 3為正規(guī)式(a|b) *a(a|b)構(gòu)造一個(gè)確定的有限自動(dòng)機(jī)。4設(shè)文法G(S)： S(L)|a S|a LL，S|S (1) 消除左遞歸和回溯； (2) 計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW； (3) 構(gòu)造預(yù)測(cè)分析表。5 已知文法 A-aAd| aAb| 判斷該文法是否SLR（1）文法，若是構(gòu)造相應(yīng)分析表，并對(duì)輸入串a(chǎn)b#給出分析過(guò)程。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，請(qǐng)給出LR分析過(guò)程（即狀態(tài)，符號(hào)，輸入串的變化過(guò)程）。8將下面的語(yǔ)句翻譯成四元式序列： while ACBA(1) A-aAd(2)A- aAb(3)A- (2)構(gòu)造識(shí)別活前綴的DFA FOLLOW(A)=d,b,# 對(duì)于狀態(tài)I0：FOLLOW(A)a= 對(duì)于狀態(tài)I1：FOLLOW(A)a= 因?yàn)?，在DFA中無(wú)沖突的現(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#的分析過(guò)程 步驟 狀態(tài)棧 符號(hào)棧 當(dāng)前字符 剩余字符串 動(dòng)作 1 0 # a b# 移進(jìn) 2 02 #a b # 歸約A- 3 023 #aA b # 移進(jìn) 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 對(duì)文法開始符H,有#H#存在，即有=，#,也即；，#d. #, b#。 對(duì)形如Pab，或PaQb，有a=b，由Ma|b得：a=b； 對(duì)形如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的分析過(guò)程表:句子abaab的分析過(guò)程步驟 狀態(tài) 符號(hào)棧 輸入串 所得產(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 識(shí)別成功 8 【解答】該語(yǔ)句的四元式序列如下（其中E1、E2和E3分別對(duì)應(yīng)：ACBD, A=1和A