完整word版編譯原理期末考試題目及答案2

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

2、器使用。3. 自下而上分析法采用移進 、歸約、錯誤處理、4. 一個 LL （1）分析程序需要用到 一張分析表5. 后綴式abc-/所代表的表達式是 a/（b-c）。源程序 ，輸出結果是 目標程序 。解釋和編譯 。，對源程序進行 詞法分析 并識別出一個個單詞符號，其輸出結果是單詞符接受 等四種操作。 和 符號棧 。二、單項選擇題（每小題 2分,共 20分）1. 詞法分析器的輸出結果是_A . 單詞的種別編碼C. 單詞的種別編碼和自身值2. 正規(guī)式 M 1 和 M 2 等價是指 _A . M1 和 M2 的狀態(tài)數(shù)相等C. M1 和 M2 所識別的語言集相等3. 文法G: StxSx|y所識別的語言

3、是_GC。BDC_。單詞在符號表中的位置單詞自身值BDA . xyx B . （xyx）* C. xnyxn（n 0）4如果文法 G 是無二義的,則它的任何句子A 最左推導和最右推導對應的語法樹必定相同C 最左推導和最右推導必定相同5構造編譯程序應掌握 D_ 。A 源程序B 目標語言C6四元式之間的聯(lián)系是通過_B_實現(xiàn)的。A 指示器B 臨時變量7. 表達式（nAV B） A （CV D）的逆波蘭表示為A n ABVA CD VB 8. 優(yōu)化可生成 _D_的目標代碼。A 運行時間較短C .運行時間短但占用內存空間大AnM1 和 M2 的有向邊條數(shù)相等M1 和 M2 狀態(tài)數(shù)和有向邊條數(shù)相等D .

4、x*yxa_。B .最左推導和最右推導對應的語法樹可能不同D .可能存在兩個不同的最左推導,但它們對應的語法樹相同編譯方法C .符號表B_。BV CD VAC.D.以上三項都是D .程序變量AB Vn CDVAD . AnBVA CD V占用存儲空間較小 運行時間短且占用存儲空間小9. 下列 _C_優(yōu)化方法不是針對循環(huán)優(yōu)化進行的。A.強度削弱B .刪除歸納變量10. 編譯程序使用_B_區(qū)別標識符的作用域。A. 說明標識符的過程或函數(shù)名C .說明標識符的過程或函數(shù)的動態(tài)層次B.D.C 刪除多余運算D 代碼外提B 說明標識符的過程或函數(shù)的靜態(tài)層次D. 標識符的行號三、判斷題（對的打錯的打X,每小題

5、2.一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。分，共 10 分）1x3個算符優(yōu)先文法的每個非終結符號間都也可能存在優(yōu)先關系。4語法分析時必須先消除文法中的左遞歸6逆波蘭表示法表示表達式時無須使用括號。R9 兩個正規(guī)集相等的必要條件是他們對應的正規(guī)式等價。1 編譯程序是對高級語言程序的編譯執(zhí)行。X2.個有限狀態(tài)自動機中，有且僅有一個唯一的初始態(tài)。3個算符優(yōu)先文法的每個非終結符號間都不存在優(yōu)先關系。4 LL （1）語法分析時必須先消除文法中的左遞歸。5. LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準確地指出出錯地點。6逆波蘭表示法表示表達式時根據(jù)表達式會使用括號。X7靜態(tài)數(shù)組的存儲空

6、間可以在編譯時確定。X8進行代碼優(yōu)化時應著重考慮循環(huán)的代碼優(yōu)化，這對提高目標代碼的效率將起更大作用。9 兩個正規(guī)集相等的必要條件是他們產生的符號串是相同的。R10 一個語義子程序描述了一個文法所對應的翻譯工作。X1什么是S-屬性文法？什么是L屬性文法？它們之間有什么關系？S-屬性文法是只含有綜合屬性的屬性文法。（2分）L-屬性文法要求對于每個產生式 A X1X2Xn,其每個語義規(guī)則中的每個屬性或者是綜合屬性, 屬性，且該屬性僅依賴于：（1）產生式Xj的左邊符號X1,X2Xj-1的屬性；（2）A的繼承屬性。S-屬性文法是 L屬性文法的特例。(2 分)(1分)或者是Xj的一個繼承2 .什么是L L

7、（l）分析器2 .什么是L R（0）分析器所謂LR（ 0 ）分析，是指從左至右掃描和自底向上的語法分析，且在分析的每一步，只須根據(jù)分析棧當前已移進 和歸約出的全部文法符號，并至多再向前查看0個輸入符號，就能確定相對于某一產生式左部符號的句柄是否已在分析棧的頂部形成，從而也就可以確定當前所應采取的分析動作（是移進還是按某一產生式進行歸約等五、綜合題（共40分）1 （10分）對于文法GS:S 7 1A | 0B |(3(4(3A 7 0S | 1AA請寫出三個關于 GS的句子；符號串11A0S是否為G S 的句型？試證明你的結論。試畫出001B關于G S的語法樹。B 7 1S|OBB答：(1)(2

8、)(3)三個0和1數(shù)量相等的串S = 1A = 11AA = 11A 0S（每個1 分）SC2. （10分）設有語言L= a | a 0,1 + ，且a不以0開頭，但以00 3分）試寫出描述 L的正規(guī)表達式；（7分）構造識別 L的DFA （要求給出詳細過程，并畫出構造過程中的 DFA的狀態(tài)轉換圖）。答：（1 ）（3分）正規(guī)表達式：1（0|1） * 00（2 ）（7分）第一步（3分）：將正規(guī)表達式轉換為結尾。NFA、DFA的狀態(tài)轉換圖，以及最小NFA第二步（2分）：將NFA確定化狀態(tài)輸入I 0I 1S一A,D,BA,D,BD,B,CD,BD,B,CD,B,C,ZD,BD,BD,B,CD,BD,B

9、,C,ZD,B,C,ZD,BDFA的狀態(tài)轉換圖（1分）DFA :（1分）重新命名9第三步（2分）：將將狀態(tài)劃分終態(tài)與非終態(tài)兩個集合: 根據(jù)A、DFA最小化：（1分）A=qO,q1,對A集合進行劃分q2.q3,E = q4狀態(tài)輸入I 0I 1qO一Aq1AAE集合的情況,2EAqq將狀態(tài)集A劃分為兩個集合：A=qO,q1,q3 根據(jù)A、B集合的情況，狀態(tài)輸入 I0qOq1對A集合進行劃分I 1A,B=2q1,q3對c集合進行劃分狀態(tài)輸入I 0I 1q1BAq3BAc集合的情況,最小DFA的狀態(tài)轉換圖（1分）q3BA將狀態(tài)集A劃分為兩個集合：A=qO,C = 根據(jù)A、03. (20分)給定文法E

10、7 E+T | TT 7 T*F | FF 7 (E) | i該文法是LL(1)答：(1)該文法不是GE:文法嗎？（要求給出詳細過程,LL（ 1）文法，因為有左遞歸,（3分）如果是 LL （1）,給出分析表）消除左遞歸可獲得一個LL （1）文法 （2分）(2)消除左遞歸，得新文法E 7 TEE7 +TE |T 7 ft T7 *FT | F 7 (E)| i(3)求產生式右部的First集(2.5 分)First(TEFirst(+TEFirst(FTFirst(*FT)=First(T)= First(F)=(,i)=+)=First(F)=(,i)=*Follow 集(2.5 分)E) =

11、 $,)U Follow(E)=+ U $,)=$,+,)T) =$,*,)U Follow(T) U Follow(T )= $,*,)Select(ESelect(ESelect(ESelect(TSelect(TFirst(E) = (First(i) = i(4) 求所有非終結符的Follow(E) = $,)Follow(E ) = Follow(Follow(T) = First(EFollow(T ) = Follow(Follow(F) = First(T(5) 求所有產生式的Select集(2.5 分)7 tE ) =First(TE )= (,i7 +TE) =First(

12、+TE )= +7) = Follow(E ) = $,)7 ft ) =First(FT )= (,i7 *FT ) =First(*FT )= *SelectSelectSelect(T7 s) = Follow(T ) =$,+,) (F 7 (E) ) =First(E)= (F 7 i ) =First(i)= i（6）對相同左部的所有 Select即求交集（2.5分）SelectSelectSelect(E7 +te)Q Select (E (T7 *FT )n Select (T(F 7 (E) )n SelectLL (1)5分)所以，改造后的文法是（7）(F 7文法, ）=7

13、 s）二i ） =O其分析表如下V NE+ *E -i9 TE(E 7 tE )EE7 +TEE7 sETT -9 FTT 7 ft TT7 s T7 *FT T7sTFF 7 (E)F 7 iLL（1）分析表（V T$1. （10分）對于文法G :S aSbS|aS|d證明該文法是二義性文法。答：一個文法，如果存在某個句子有不只一棵語法分析樹與之對應，那么稱這個文法是二義性文法。 句子aadbd有兩棵語法樹（5分，(5 分)劃一棵樹給3 分）。如下圖：（6分）d(1)由此可知，S aSbS|aS|d定義的文法是二義性文法。3. （20分）給定一個簡單的算術表達式文法GE:E 7 E+T |

14、TT 7 T*F | FF 7 （E） | i該文法是SLR（1）文法嗎？（要求給出詳細過程，如果是SLR文法，給出分析表）答：（1）該文法的拓廣文法是：（2分）(10 分)(3) 沖突與解決 (3 分) -T E(1)E+T(2)T(3)T*F(4)F(5)(E)(6)i(7)(2)相應的LR (0)的 DFFETTEE11 狀態(tài)中有移進一規(guī)約沖突Follow(E )= $ 不含 + 可解決移進一規(guī)約沖突12 狀態(tài)中有移進一規(guī)約沖突Follow(E)= +，$ 不含 * 可解決移進一規(guī)約沖突18狀態(tài)中有移進一規(guī)約沖突Follow（E）= +, $ 不含 * 可解決移進一規(guī)約沖突SLR分析表

15、（5分）ACTIONGOTO+*i()$ETF0S5S41231S6接受2r3S7r3r33r5r5r5R5r5r54S5S49235r7r7r7r7r7r76S5S4837S5S4118r2S7r2r29S6S1010r6r6r6r6r6r611r4r4r4r4r4r4二、單項選擇題（每小題 2分，共20分）語言是C_終結符與非終結符的符號串的集合B .編譯程序分兩階段工作，前階段完成的工作是 詞法分析、語法分析和代碼優(yōu)化 詞法分析、語法分析、語義分析和中間代碼生成 一個句型中稱為句柄的是該句型的最左C1.A2.AC3.A .句型 B .短語 C .直接短語 D .自動機識別的語言是 D0型語言 B . 1型語言C . 2型語言4.A5.6.7.非終結符符號串的集合C .終結符符號串的集合D .產生式的集合CB.代碼生成、代碼優(yōu)化和詞法分析D .詞法分析、語法分析和代碼優(yōu)化最左直接短語D . 3型語言自動機所完成的任務是從字符串形式的源程序中識別出一個個具有獨立含義的最小語法單位即A .字符 B .單詞 C .句子 D .句型對應Chomsky四種文法的四種語言之間的關系是A . L0 Li L2 L3B .