(完整word版)編譯原理期末考試題目及答案(word文檔良心出品)

1、x 一、填空題（每空 2 分，共 20 分） 1編譯程序首先要識(shí)別出源程序中每個(gè) 單詞，然后再分析每個(gè) 句子 并翻譯其意義。 2編譯器常用的語法分析方法 有自底向上 和 自頂向下 兩種。 3通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對(duì)源程序的 分析 ，中間代碼生成、代碼 優(yōu)化與目標(biāo)代碼的生成則是對(duì)源程序的 綜合 。 4程序設(shè)計(jì)語言的發(fā)展帶來了日漸多變的運(yùn)行時(shí)存儲(chǔ)管理方案，主要分為兩大類，即 靜態(tài)存儲(chǔ)分配 方案和 動(dòng)態(tài)存儲(chǔ)分配 5對(duì)編譯程序而言，輸入數(shù)據(jù)是 源程序 ，輸出結(jié)果是 目標(biāo)程序 。 1計(jì)算機(jī)執(zhí)行用高級(jí)語言編寫的程序主要有兩種途徑： 解釋和編譯 。 2掃描器是

2、詞法分析器，它接受輸入的 源程序，對(duì)源程序進(jìn)行 詞法分析 并識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是單詞符 號(hào)，供語法分析器使用。 3自下而上分析法采用 移進(jìn) 、歸約、錯(cuò)誤處理、 接受 等四種操作。 4一個(gè) LL （1）分析程序需要用到 一張分析表 和符號(hào)棧 。 5. 后綴式 abc-/所代表的表達(dá)式是 a/（b-c）。 二、單項(xiàng)選擇題（每小題 2 分，共 20 分） 1. 詞法分析器的輸出結(jié)果是 _C。 A . 單詞的種別編碼 B . C. 單詞的種別編碼和自身值 D. 2. 正規(guī)式 M 1 和 M 2 等價(jià)是指 _C_ 。 A . M1 和 M2 的狀態(tài)數(shù)相等 C. M1 和 M2 所識(shí)別的語言

3、集相等 3. 文法 G: ST xSx|y 所識(shí)別的語言是 _C. 單詞在符號(hào)表中的位置 單詞自身值 B . M1 和 M2 的有向邊條數(shù)相等 D . M1 和 M2 狀態(tài)數(shù)和有向邊條數(shù)相等 8. 優(yōu)化可生成 _D_的目標(biāo)代碼。 A 運(yùn)行時(shí)間較短 C 運(yùn)行時(shí)間短但占用內(nèi)存空間大 B 占用存儲(chǔ)空間較小 D 運(yùn)行時(shí)間短且占用存儲(chǔ)空間小 9下列 _C_優(yōu)化方法不是針對(duì)循環(huán)優(yōu)化進(jìn)行的。 A. 強(qiáng)度削弱 B 刪除歸納變量 10.編譯程序使用_B_區(qū)別標(biāo)識(shí)符的作用域。 A. 說明標(biāo)識(shí)符的過程或函數(shù)名 C .說明標(biāo)識(shí)符的過程或函數(shù)的動(dòng)態(tài)層次 三、判斷題（對(duì)的打，錯(cuò)的打X,每小題 1 分，共 10 分） 2一

4、個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。A. xyx B. (xyx)* C. xnyxn(n 0) D. x*yx* 4.如果文法 G 是無二義的，則它的任何句子 a_ _ 。 A 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹必定相同 B 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹可能不同 C 最左推導(dǎo)和最右推導(dǎo)必定相同 D 可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語法樹相同 5構(gòu)造編譯程序應(yīng)掌握 _ D_ 。 A 源程序 B 目標(biāo)語言 C 編譯方法 6四元式之間的聯(lián)系是通過 _B_實(shí)現(xiàn)的。 A 指示器 B 臨時(shí)變量 C 符號(hào)表 7.表達(dá)式（A B） A （CV D）的逆波蘭表示為_B_。 A . ABVA CD

5、 V B . AqB V CD VA D 以上三項(xiàng)都是 D 程序變量 C AB V CDVA D ABVA CD V C 刪除多余運(yùn)算 D 代碼外提 B .說明標(biāo)識(shí)符的過程或函數(shù)的靜態(tài)層次 D. 標(biāo)識(shí)符的行號(hào) (3) 3個(gè)算符優(yōu)先文法的每個(gè)非終結(jié)符號(hào)間都也可能存在優(yōu)先關(guān)系。 4語法分析時(shí)必須先消除文法中的左遞歸 。X 6. 逆波蘭表示法表示表達(dá)式時(shí)無須使用括號(hào)。 R 9兩個(gè)正規(guī)集相等的必要條件是他們對(duì)應(yīng)的正規(guī)式等價(jià)。 X 1 編譯程序是對(duì)高級(jí)語言程序的編譯執(zhí)行。 X 2. 個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的初始態(tài)。 R 3個(gè)算符優(yōu)先文法的每個(gè)非終結(jié)符號(hào)間都不存在優(yōu)先關(guān)系。 R 4. LL

6、（1）語法分析時(shí)必須先消除文法中的左遞歸 。R 5. LR 分析法在自左至右掃描輸入串時(shí)就能發(fā)現(xiàn)錯(cuò)誤，但不能準(zhǔn)確地指出出錯(cuò)地點(diǎn)。 R 6. 逆波蘭表示法表示表達(dá)式時(shí)根據(jù)表達(dá)式會(huì)使用括號(hào)。 X 7. 靜態(tài)數(shù)組的存儲(chǔ)空間可以在編譯時(shí)確定。 X 8進(jìn)行代碼優(yōu)化時(shí)應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對(duì)提高目標(biāo)代碼的效率將起更大作用。 X 9 .兩個(gè)正規(guī)集相等的必要條件是他們產(chǎn)生的符號(hào)串是相同的。 R 10. 一個(gè)語義子程序描述了一個(gè)文法所對(duì)應(yīng)的翻譯工作。 X 1.什么是S-屬性文法？什么是L-屬性文法？它們之間有什么關(guān)系？ S-屬性文法是只含有綜合屬性的屬性文法。 （2 分） L-屬性文法要求對(duì)于每個(gè)產(chǎn)生式

7、A X1X2Xn,其每個(gè)語義規(guī)則中的每個(gè)屬性或者是綜合屬性, 屬性，且該屬性僅依賴于： （1） 產(chǎn)生式 Xj 的左邊符號(hào) X1,X2Xj-1 的屬性； （2） A 的繼承屬性。 （2 分） S-屬性文法是 L-屬性文法的特例。 （1分） 2 .什么是 L L（1）分析器 2 .什么是 L R（0）分析器 所謂 LR（ 0 ）分析，是指從左至右掃描和自底向上的語法分析，且在分析的每一步，只須根據(jù)分析棧當(dāng)前已移進(jìn) 和歸約出的全部文法符號(hào)，并至多再向前查看 0 個(gè)輸入符號(hào)， 就能確定相對(duì)于某一產(chǎn)生式左部符號(hào)的句柄是否 已在分析棧的頂部形成，從而也就可以確定當(dāng)前所應(yīng)采取的分析動(dòng)作 （是移進(jìn)還是按某一產(chǎn)

8、生式進(jìn)行歸約等 ） 五、綜合題（共 40 分） 1. （10 分）對(duì)于文法 GS: S T 1A | 0B | AT 0S | 1AA B 宀 1S | 0BB （3 分）請(qǐng)寫出三個(gè)關(guān)于 GS的句子； （4 分）符號(hào)串 11A0S 是否為 G S 的句型？試證明你的結(jié)論。 （3 分）試畫出 001B 關(guān)于 G S的語法樹。 答： 或者是 Xj 的一個(gè)繼承 (3) （1）三個(gè) 0 和 1 數(shù)量相等的串 （每個(gè) 1 分） (2) S = 1A = 11AA = 11A 0S 2. （10 分）設(shè)有語言 L= a | a 0,1 + ，且a不以 0 開頭，但以 00 結(jié)尾。 3分）試寫出描述 L 的

9、正規(guī)表達(dá)式； （7分）構(gòu)造識(shí)別 L 的 DFA （要求給出詳細(xì)過程，并畫出構(gòu)造過程中的 NFA、DFA 的狀態(tài)轉(zhuǎn)換圖，以及最小 DFA 的狀態(tài)轉(zhuǎn)換圖）。 答： （1 ）（3分）正規(guī)表達(dá)式： 1（0|1） * 00 2）（7分）第一步（3分）：將正規(guī)表達(dá)式轉(zhuǎn)換為 NFA 第三步（2分）：將 DFA 最小化：（1分） 將狀態(tài)劃分終態(tài)與非終態(tài)兩個(gè)集合：A=qO,q1,q2,q3,E=q4 根據(jù)A、E集合的情對(duì)A集合進(jìn)行劃狀態(tài)輸入 I0 I 1 q0 A q1 A A q2 E A q3 A A 將狀態(tài)集A劃分為兩個(gè)集合：A=qO,q1,q3,E=2 根據(jù)A、E集合的情況，對(duì)A集合進(jìn)行劃分 狀態(tài)輸入

10、I0 I 1 q0 A q1 B A狀態(tài)輸入 I 0 I 1 t 0 S 一 A,D,B q 0 A,D,B D,B,C D,B 重新命名 q 1 q 2 D,B,C D,B,C,Z D,B = q 2 q 4 D,B D,B,C D,B q 3 q 2 D,B,C,Z D,B,C,Z D,B q 4 q 4 1 q 1 q 3 q 3 q 3 q 3 第二步（2分）：將 NFA 確定化為 DFA :（ 1分） DFA 的狀態(tài)轉(zhuǎn)換圖（1分） q3 B A 將狀態(tài)集A劃分為兩個(gè)集合：A=qO,C=ql,q3 根據(jù)A、C集合的情況，對(duì)C集合進(jìn)行劃分 狀態(tài)輸入 I0 I 1 ql B A q3 3.

11、 (20 分)給定文法 GE: E T E+T | T T T T*F | F F T (E) | i 該文法是 LL(1)文法嗎？(要求給出詳細(xì)過程，如果是 LL (1),給出分析表) 答：(1)該文法不是 LL (1)文法，因?yàn)橛凶筮f歸，消除左遞歸可獲得一個(gè) LL (1)文法 (2)消除左遞歸，得新文法 (3 分) E T TE ET +TE | T T FT T T *FT | F T (E) | i (3) 求產(chǎn)生式右部的 First 集(2.5 分) First(TE ) = First(T)= First(F)=(,i First(+TE ) = + First(FT ) = Fi

12、rst(F)=(,i First(*FT ) = * First(E) = ( First(i) = i (4) 求所有非終結(jié)符的 Follow 集(2.5 分) Follow(E) = $,) Follow(E ) = Follow( E) = $,) Follow(T) = First(E ) U Follow(E)=+ U $,)=$,+,) Follow(T ) = Follow( T) =$,*,) Follow(F) = First(T ) U Follow(T) U Follow(T ) = $,*,) (5) 求所有產(chǎn)生式的 Select 集(2.5 分) Select (E

13、T TE ) =First(TE )= =(,i Select (E- +TE )=First(+TE )= + Select (E- ) =Follow(E ) = $,) Select (T - FT ) =First(FT )= =(,i 最小 DFA 的狀態(tài)轉(zhuǎn)換圖（l分） (2 分) Select (T T *FT )=First(*FT ) =* Select ( TT ) = Follow(T ) =$,+,) Select ( F (E) ) =First(E)= ( Select ( F i ) =First(i)= i (6) 對(duì)相同左部的所有 Select 即求交集(2.5

14、 分) Select (ET +TE)n Select (ET )= Select (T T *FT )n Select (T ) =Q 1. （10 分）對(duì)于文法 G : S aSbS|aS|d 證明該文法是二義性文法。 答：一個(gè)文法，如果存在某個(gè)句子有不只一棵語法分析樹與之對(duì)應(yīng)，那么稱這個(gè)文法是二義性文法。 句子 aadbd 有兩棵語法樹（5 分，劃一棵樹給 3 分）。如下圖：（6分） (1) (2) 由此可知，S aSbS|aS|d 定義的文法是二義性文法。 3. （20 分）給定一個(gè)簡單的算術(shù)表達(dá)式文法 GE: E T E+T | T T T T*F | F F T （E） | i 該

15、文法是 SLR（1）文法嗎？（要求給出詳細(xì)過程，如果是 答： （1）該文法的拓廣文法是： （2 分）d d d Select ( F T (E) )n Select (F T i ) =Q 所以, 改造后的文法是 LL (1) 文法, 其分析表如下 (7) LL（1）分析表（ 5 分） V T V N + * i ( E E T TE E T TE E ET +TE T T T FT T FT T TT S T T *FT F F T (E) ET S TT S (5 分) SLR 文法，給出分析表） E f E (1) E E+T (2) E T (3) T T*F (4) T f F (5

16、) F f (E) (6) F f i (7) (2) 相應(yīng)的 LR ( 0)的 DFA (10 分) (3) 沖突與解決 (3 分) 11 狀態(tài)中有移進(jìn)一規(guī)約沖突 Follow(E )= $ 不含 + 可解決移進(jìn)一規(guī)約沖突 12 狀態(tài)中有移進(jìn)一規(guī)約沖突 Follow(E)= + ，$ 不含 * 可解決移進(jìn)一規(guī)約沖突 18 狀態(tài)中有移進(jìn)一規(guī)約沖突C.把中間代碼變換成依賴具體機(jī)器的目標(biāo)代碼 D .把匯編語言翻譯成機(jī)器語言 Follow（E）= + , $ 不含 * 可解決移進(jìn)一規(guī)約沖突 SLR 分析表 （5 分） ACTION GOTO + i ( ) $ E T S5 S4 2 3 T S6-

17、 接受 2 r3 S7 r3 r3 3 r5 r5 r5 R5 r5 r5 4 S5 S4 9 2 3 5 r7 r7 r7 r7 r7 r7 6 S5 S4 8 3 7 S5 S4 11 8 r2 S7 r2 r2 9 S6 S10 10 r6 r6 r6 r6 r6 r6 11 r4 r4 r4 r4 r4 r4 4. 自動(dòng)機(jī)識(shí)別的語言是 D A 0 型語言 B . 1 型語言 C . 2 型語言 D . 3 型語言 5. 自動(dòng)機(jī)所完成的任務(wù)是從字符串形式的源程序中識(shí)別出一個(gè)個(gè)具有獨(dú)立含義的最小語法單位即 B A . 字符 B .單詞 C .句子 D .句型 6. 對(duì)應(yīng) Chomsky 四種文法的四種語言之間的關(guān)系是 B A . L0 L1 L2 L3 B . L3 L2 L1 L0 C . L3=L2 L1 L0 D . L0 L1 L2=L3 7 .詞法分析的任務(wù)是 A A .識(shí)別單詞 B .分析句子的含義 C .識(shí)別句子 D .生成目標(biāo)代碼 8. 常用的中間代碼形式不含 D A.三元式 B .四元式 C .逆波蘭式 D .語法樹 9. 代碼優(yōu)化的目的是 C A .節(jié)省時(shí)間 B .節(jié)省空間 C .節(jié)省時(shí)間和空間 D .把編譯程序進(jìn)行等價(jià)交換 二、單項(xiàng)選擇題（每小題 2 分，共 20 分） 語言是 _ C_