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

1、<編譯原理 >歷年試題及答案一 (每項(xiàng)選擇 2 分，共 20 分)選擇題1 將編譯程序分成若干個(gè)“遍”是為了_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)語(yǔ)言c.編譯方法d.以上三項(xiàng)都是 3 .變量應(yīng)當(dāng)c_。 a.持有左值b.持有右值c. 既持有左值又持有右值 d.既不持有左值也不持有右值4 編譯程序絕大多數(shù)時(shí)間花在 _d_ 上。a.岀錯(cuò)處理b.詞法分析c.目標(biāo)代碼生成 d.管理表格5 詞法分析器的輸岀結(jié)果是_c。a.單詞的種別編碼 b.單

2、詞在符號(hào)表中的位置c.單詞的種別編碼和自身值d.單詞自身值6.正規(guī)式MI和M2等價(jià)是指_c_。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ù)的是一COa.語(yǔ)法規(guī)則b詞法規(guī)則 c.語(yǔ)義規(guī)則d.等價(jià)變換規(guī)則8.后綴式ab+cd+/可用表達(dá)式 _b_來(lái)表示。 a. a+b/c+d b .(a+b)(c+d) C .a+b(c+d) d . a+b+c/d 9 .程序所需的數(shù)據(jù)空間在程序運(yùn)行前就可確定，稱為C管理技術(shù)。 堆式靜態(tài)存儲(chǔ) 10. d.堆式存儲(chǔ)a.動(dòng)態(tài)存儲(chǔ)b.棧式存儲(chǔ)c.

3、動(dòng)態(tài)分配申請(qǐng)和釋放存儲(chǔ)空間遵守 d原則。任意先請(qǐng)后放b.c.后請(qǐng)先放d.a.先請(qǐng)先放二(每小題 10 分，共 80 分)簡(jiǎn)答題 1.畫(huà)岀編譯程序的總體結(jié)構(gòu)圖，簡(jiǎn)述各部分的主要功能。2.已知文法 GE: E ET+T T TF* | F F F | 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)Ia SlaL L ， S|S消除左遞歸和回溯； (1)(2) 計(jì)算每個(gè)非終結(jié)符的 FIRST 和 FOLLOW ； (3) 構(gòu)造預(yù)測(cè)分析表。5 已知文法A->aAdI aAbI

4、判斷該文法是否 SLR (1)文法，若是構(gòu)造相應(yīng)分析表，并對(duì)輸入串a(chǎn)b#給岀分析過(guò)程。 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，請(qǐng)給岀LR分析過(guò)程(即狀態(tài)，符號(hào)，輸入串的變化過(guò)程) 。8 將下面的語(yǔ)句翻譯成四元式序列：while A<C B<D do if A=1 thenC:=C+l else while A Ddo A:=A+2 ；9對(duì)下面的流圖， (1)求出流圖中各結(jié)點(diǎn)

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

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

7、錄在表格中，所需信息多數(shù)都需從表格中獲取，整個(gè)編譯過(guò)程都在不斷地和表格打交道。 出錯(cuò)處理程序?qū)Τ霈F(xiàn)在源程序中的錯(cuò)誤進(jìn)行處理。此外，編 譯的各階段都可能出現(xiàn)錯(cuò)誤，出錯(cuò)處理程序?qū)Πl(fā)現(xiàn)的錯(cuò)誤都及時(shí)進(jìn)行處理。2 【解答】該句型對(duì)應(yīng)的語(yǔ)法樹(shù)如下：該句型相對(duì)于 E 的短語(yǔ)有 FF* ；相對(duì)于 T 的短語(yǔ)有 FF*,F;相對(duì)于 F的短語(yǔ)有 FF;簡(jiǎn)單短語(yǔ)有 FF;句柄為 F.3 【解答】 最簡(jiǎn) DFA 如圖 2.66 所示。4 【解答】 (1)S(L)IaS' S'S LS L' L'S L' 評(píng)分細(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)造識(shí)別活前綴的 (2)FOLLOW(A)=d,b,#對(duì)于狀態(tài) IO : FOLLOW(A) a= 對(duì)于狀態(tài)I1 : FOLLOW(A) a= 因?yàn)?，在DFA中無(wú)沖突的現(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#的分析過(guò)程動(dòng)作符號(hào)棧剩余字符串步驟狀態(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 對(duì)文法開(kāi)始符 存在，即有# = #,#VFIRSTVT(H) ,LASTVT(H)>#,也即 #< , #<d. #<a, ; >#, d>#, b># < P aQb,有 a=b,由 M a|b 得：P ab對(duì)形如 ，或 ,對(duì)形如 P Rb aLASTVT(R).

11、對(duì)形女口 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)系表，見(jià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的分析過(guò)程 (3) 句子 abaab的分析過(guò)程表 :句子 abaab 所得產(chǎn)生式 輸入串 步驟 狀態(tài) 符號(hào)棧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識(shí)別成功8 【解答】 該語(yǔ)句

13、的四元式序列如下 (其中 E1、E2 和 E3 分別對(duì)應(yīng)： A<C B<D, A=1D 并且關(guān) 系運(yùn)算符優(yōu)先級(jí)高) ： 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/*跳過(guò) else 后的語(yǔ)句 */ 107 (j,_,_,112)/*E3 為 T*/108 (j ,A,D,110)/*E3 為 F*/ 109 (j,_,_,112),A,2,A) ( /