編譯原理試題及答案期末復(fù)習(xí)版pdf資料

1、<編譯原理 >歷年試題及答案一 (每項選擇 2 分，共 20 分)選擇題1 將編譯程序分成若干個“遍”是為了_b_。a.提高程序的執(zhí)行效率b.使程序的結(jié)構(gòu)更加清晰c.利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率d.利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(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.單

2、詞在符號表中的位置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ù)的是一COa.語法規(guī)則b詞法規(guī)則 c.語義規(guī)則d.等價變換規(guī)則8.后綴式ab+cd+/可用表達(dá)式 _b_來表示。 a. a+b/c+d b .(a+b)(c+d) C .a+b(c+d) d . a+b+c/d 9 .程序所需的數(shù)據(jù)空間在程序運行前就可確定，稱為C管理技術(shù)。 堆式靜態(tài)存儲 10. d.堆式存儲a.動態(tài)存儲b.棧式存儲c.

3、動態(tài)分配申請和釋放存儲空間遵守 d原則。任意先請后放b.c.后請先放d.a.先請先放二(每小題 10 分，共 80 分)簡答題 1.畫岀編譯程序的總體結(jié)構(gòu)圖，簡述各部分的主要功能。2.已知文法 GE: E ET+T T TF* | F F F | a 試證：FF*是文法的句型，指岀該句型的 短語、簡單短語和句柄 .3為正規(guī)式 (a|b) *a(a|b) 構(gòu)造一個確定的有限自動機(jī)。4 設(shè)文法 G(S)：S (L)Ia SlaL L ， S|S消除左遞歸和回溯； (1)(2) 計算每個非終結(jié)符的 FIRST 和 FOLLOW ； (3) 構(gòu)造預(yù)測分析表。5 已知文法A->aAdI aAbI

4、判斷該文法是否 SLR (1)文法，若是構(gòu)造相應(yīng)分析表，并對輸入串a(chǎn)b#給岀分析過程。 6 .構(gòu)造算符文法 GH的算符優(yōu)先關(guān)系(含#) 。 GH : H H;M|M M d|aHb 7 已構(gòu)造岀文法 G(S)(1 ) S BB( 2) B aB ( 3) B b 1)。給岀 DFA 圖2).給岀LR分析表3).假定輸入串為abaab，請給岀LR分析過程(即狀態(tài)，符號，輸入串的變化過程) 。8 將下面的語句翻譯成四元式序列：while A<C B<D do if A=1 thenC:=C+l else while A Ddo A:=A+2 ；9對下面的流圖， (1)求出流圖中各結(jié)點

5、N 的必經(jīng)結(jié)點集 D(n) ， (2)求出流圖中的回邊， (3) 求出流圖中的循環(huán)。參考答案一單項選擇題 1. 將編譯程序分成若干個 “遍” 是為了使編譯程序的結(jié)構(gòu)更加清晰， 故選 b。 2.構(gòu)造編譯程序應(yīng)掌握源程序、目標(biāo)語言及編譯方法等三方面的知識，故選d。 對編譯而言， 變量既持有左值又持有右值，故選3. c。 編譯程序打交道最多的就是各種表格，因此選 4. d。 詞法分析器輸出的結(jié)果是單詞的種別編碼和自身值，選C。 5. 正規(guī)式 M1 和 M2 6. 所識別的語言集相等，故選 C。 選 7. c。 選 b 8. 。 選 9. C堆式動態(tài)分配申請和釋放存儲空間不一定遵守先請后放和后請先放的

6、原則，故選 d10.二簡答題1 【解答】所示。 1.2 編譯程序的總體結(jié)構(gòu)圖如圖詞法分析器： 輸入源程序， 進(jìn)行詞法分析， 輸出單詞符號。 語法分析器： 在詞法分析的基礎(chǔ)上， 根據(jù)語言的語法規(guī)則 (文法規(guī)則) 把單詞符號串分 解成各類語法單位， 并判斷輸入串是否構(gòu)成 語法上正確的“程序” 。 中間代碼生成器：按照 語義規(guī)則把語法分析器歸約(或推導(dǎo))出的語 法單位翻譯成一定 優(yōu)化：對中間代碼形式的中間代碼，比如說四元式。 目標(biāo)代碼生成器：把中間代碼翻譯進(jìn)行優(yōu)化處理。成目標(biāo)語言程序。 譯 表格管理模塊保存一系列的表格， 登記源程序的各類信息和編譯各階段的進(jìn)展情 況。編程序各階段所產(chǎn)生的中間結(jié)果都記

7、錄在表格中，所需信息多數(shù)都需從表格中獲取，整個編譯過程都在不斷地和表格打交道。 出錯處理程序?qū)Τ霈F(xiàn)在源程序中的錯誤進(jìn)行處理。此外，編 譯的各階段都可能出現(xiàn)錯誤，出錯處理程序?qū)Πl(fā)現(xiàn)的錯誤都及時進(jìn)行處理。2 【解答】該句型對應(yīng)的語法樹如下：該句型相對于 E 的短語有 FF* ；相對于 T 的短語有 FF*,F;相對于 F的短語有 FF;簡單短語有 FF;句柄為 F.3 【解答】 最簡 DFA 如圖 2.66 所示。4 【解答】 (1)S(L)IaS' S'S LS L' L'S L' 評分細(xì)則：消除左遞歸 2分，提公共因子2分。FOLLOW 和(2) FIR

8、ST) = # , , FIRST)S) = ( , a FOLLOW(S) ) , a, FOLLOW(S') = #FIRST(S') =, ),a FOLLOW(L) = FIRST(L) = ( )= FOLLOW(LFIRST(L') =, '5 【解答】 拓廣文法 (1) >(0)S->A (1) A->aAd (2)A->aAb (3)A - DFA構(gòu)造識別活前綴的 (2)FOLLOW(A)=d,b,#對于狀態(tài) IO : FOLLOW(A) a= 對于狀態(tài)I1 : FOLLOW(A) a= 因為，在DFA中無沖突的現(xiàn)象， 所

9、以該文法是SLR(I)文法。分析表 (3)SLR(1)狀態(tài) GOTOACTIONA#dB a1 r3 r3 r3 0 S2 acc 132 r3 r3 r3S2S5 S4 3 r1 r1 4 r1 r2 5r2r2(4)串a(chǎn)b#的分析過程動作符號棧剩余字符串步驟狀態(tài)棧當(dāng)前字符 b# # a 1 0 移進(jìn) A-> 歸約 # 02 2 #a b# 023 #aA b 3 移進(jìn) A-> aAb 歸約# #aAb 4 023501#5#A接受6.【解答】由 Md 和 Ma得：FIRSTVT(M)= d,a;由H-H;得：FIRSTVT(H)= ; 由H M 得：FIRSTVT(M) cFI

10、RSTVT(H)，即 FIRSTVT(H)=;,d,a由 Md 和 M b 得：LASTVT(M)=d,b;由 H-,; m 得：LASTVT(H)= ; ;H,有 #H#a=b;，而由 H M 得：LASTVT (M ) CLASTVT(H ),即 LASTVT(H)= ;,d,b 對文法開始符 存在，即有# = #,#VFIRSTVT(H) ,LASTVT(H)>#,也即 #< , #<d. #<a, ; >#, d>#, b># < P aQb,有 a=b,由 M a|b 得：P ab對形如 ，或 ,對形如 P Rb aLASTVT(R).

11、對形女口 PaR，而 b FIRSTVT(R),有 a<b有 a>b。由 H; M 得：；VFIRSTVT(M),即：VdVa由 MaH得：a<FIRSTVT(H),即：a< , a<d, a< a由 H H ; ''?得：LASTVT(H)>,即：;>,d>, b>由 M Hb 得： LASTVT(H)>b ，即：；> b， d>b，b>b由此得到算符優(yōu)先關(guān)系表，見表3.5 。7. 【解答】 ( 1 ) LR分析表如下：( 2)分析表狀態(tài) GOTO ACTION# SBb a2 s3 s4 0

12、 1acc 15S4 S326s4 s33r3 r3 4r1 R1 5 R1R2 6 R2 R2的分析過程 (3) 句子 abaab的分析過程表 :句子 abaab 所得產(chǎn)生式 輸入串 步驟 狀態(tài) 符號棧abaad# 0 #0baad# #03 1#a2 aab# B b#034 #abaab# 3 B aB#036 #aBaab# 4 #02 #Bab# #023 5 #Bab# #Baa #0233 6# #Baab 7 #02334# #02336 #BaaB 8ad# #BaB 9 #0236ad#BB 10 #025d# 11 #S #01d#12 #13識別成功8 【解答】 該語句

13、的四元式序列如下 (其中 E1、E2 和 E3 分別對應(yīng)： A<C B<D, A=1D 并且關(guān) 系運算符優(yōu)先級高) ： 100 (j<,A,C,102)/*E1 為 F*/ 101(j,_,_,113 )/*El 為 T*/ 102 (j<,B,D,104)/*El 為 F*/ 103 (j,_,_,113)/*Ez 為 T*/ 104 (j=,A,1,106)/*EZ 為 (j,_,_,108 ) F*/105,C,1,C) (/*C:=C+1*/106/*跳過 else 后的語句 */ 107 (j,_,_,112)/*E3 為 T*/108 (j ,A,D,110)/*E3 為 F*/ 109 (j,_,_,112),A,2,A) ( /