編譯原理期末考試題目及答案

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

2、一個個單詞符號，其輸出結果是單詞符號，供語法分析器使用。3自下而上分析法采用移進、歸約、錯誤處理、接受等四種操作。4一個LL（1）分析程序需要用到一張分析表和符號棧。5后綴式abc-/所代表的表達式是a/(b-c)。 二、單項選擇題（每小題2分，共20分）1詞法分析器的輸出結果是_C。A 單詞的種別編碼 B 單詞在符號表中的位置C 單詞的種別編碼和自身值 D 單詞自身值2 正規(guī)式 M 1 和 M 2 等價是指_C_。 A M1和M2的狀態(tài)數(shù)相等 B M1和M2的有向邊條數(shù)相等C M1和M2所識別的語言集相等 D M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等 3 文法G：SxSx|y所識別的語言是_C_。A

3、 xyx B (xyx)* C xnyxn(n0) D x*yx* 4如果文法G是無二義的，則它的任何句子_A_。A最左推導和最右推導對應的語法樹必定相同 B最左推導和最右推導對應的語法樹可能不同 C最左推導和最右推導必定相同 D可能存在兩個不同的最左推導，但它們對應的語法樹相同 5構造編譯程序應掌握_D_。A源程序B目標語言 C 編譯方法 D以上三項都是 6四元式之間的聯(lián)系是通過_B_實現(xiàn)的。 A指示器 B臨時變量 C符號表 D程序變量 7表達式(AB)(CD)的逆波蘭表示為_B_。A ABCD B ABCD C ABCD D ABCD 8. 優(yōu)化可生成_D_的目標代碼。A運行時間較短 B占

4、用存儲空間較小C運行時間短但占用內(nèi)存空間大 D運行時間短且占用存儲空間小9下列_C_優(yōu)化方法不是針對循環(huán)優(yōu)化進行的。A. 強度削弱 B刪除歸納變量 C刪除多余運算 D代碼外提10編譯程序使用_B_區(qū)別標識符的作用域。 A. 說明標識符的過程或函數(shù)名 B說明標識符的過程或函數(shù)的靜態(tài)層次C說明標識符的過程或函數(shù)的動態(tài)層次 D. 標識符的行號三、判斷題（對的打，錯的打，每小題1分，共10分）2一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。x3一個算符優(yōu)先文法的每個非終結符號間都也可能存在優(yōu)先關系。X4語法分析時必須先消除文法中的左遞歸 。X6逆波蘭表示法表示表達式時無須使用括號。R9兩個正規(guī)集相等的

5、必要條件是他們對應的正規(guī)式等價。 X1編譯程序是對高級語言程序的編譯執(zhí)行。X2一個有限狀態(tài)自動機中，有且僅有一個唯一的初始態(tài)。R3一個算符優(yōu)先文法的每個非終結符號間都不存在優(yōu)先關系。R4LL（1）語法分析時必須先消除文法中的左遞歸 。 R5LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準確地指出出錯地點。 R6逆波蘭表示法表示表達式時根據(jù)表達式會使用括號。 X7靜態(tài)數(shù)組的存儲空間可以在編譯時確定。X8進行代碼優(yōu)化時應著重考慮循環(huán)的代碼優(yōu)化，這對提高目標代碼的效率將起更大作用。X9兩個正規(guī)集相等的必要條件是他們產(chǎn)生的符號串是相同的。 R10一個語義子程序描述了一個文法所對應的翻譯工作。 X

6、1什么是S-屬性文法？什么是L-屬性文法？它們之間有什么關系？S-屬性文法是只含有綜合屬性的屬性文法。 （2分）L-屬性文法要求對于每個產(chǎn)生式AX1X2Xn，其每個語義規(guī)則中的每個屬性或者是綜合屬性，或者是Xj的一個繼承屬性，且該屬性僅依賴于：（1） 產(chǎn)生式Xj的左邊符號X1,X2Xj-1的屬性；（2） A的繼承屬性。 （2分）S-屬性文法是L-屬性文法的特例。 （分）什么是L（）分析器什么是L（）分析器所謂LR()分析，是指從左至右掃描和自底向上的語法分析，且在分析的每一步，只須根據(jù)分析棧當前已移進和歸約出的全部文法符號，并至多再向前查看0個輸入符號，就能確定相對于某一產(chǎn)生式左部符號的句柄是

7、否已在分析棧的頂部形成，從而也就可以確定當前所應采取的分析動作 (是移進還是按某一產(chǎn)生式進行歸約等)。 五、綜合題（共40分）1（10分）對于文法 GS ： S 1A | 0B | A 0S | 1AA B 1S | 0BB (3 分 ) 請寫出三個關于 GS 的句子； (4 分 ) 符號串 11A0S 是否為 G S 的句型？試證明你的結論。 (3 分 ) 試畫出 001B 關于 G S 的語法樹。 答：（1） 三個 0 和 1 數(shù)量相等的串 （每個1分）（2） S = 1A = 11AA = 11A 0S （3） 2.（10分）設有語言 L= | 0,1 + ，且不以 0 開頭，但以 00

8、 結尾 。 2 分）試寫出描述 L 的正規(guī)表達式； （分）構造識別 L 的 DFA （要求給出詳細過程，并畫出構造過程中的 NFA 、 DFA 的狀態(tài)轉換圖，以及最小DFA的狀態(tài)轉換圖 ) 。 答：（ 1 ）（分）正規(guī)表達式： 1(0|1) * 00 （ 2 ）（分）第一步（分）：將正規(guī)表達式轉換為 NFA 第二步（分）：將 NFA 確定化為 DFA ：（分） 狀態(tài) 輸入 I 0 I 1 t 0 1 S A,D,B q 0 q 1 A,D,B D,B,C D,B 重新命名 q 1 q 2 q 3 D,B,C D,B,C,Z D,B q 2 q 4 q 3 D,B D,B,C D,B q 3 q

9、 2 q 3 D,B,C,Z D,B,C,Z D,B q 4 q 4 q 3 DFA 的狀態(tài)轉換圖（分） 第三步（分）：將DFA 最小化 ：（分） 將狀態(tài)劃分終態(tài)與非終態(tài)兩個集合：，根據(jù)、集合的情況，對集合進行劃分狀態(tài) 輸入 I 0 I 1 將狀態(tài)集劃分為兩個集合：，根據(jù)、集合的情況，對集合進行劃分狀態(tài) 輸入 I 0 I 1 將狀態(tài)集劃分為兩個集合：，根據(jù)、集合的情況，對集合進行劃分狀態(tài) 輸入 I 0 I 1 最小DFA 的狀態(tài)轉換圖（分） （20分）給定文法 GE ： E E+T | T T T*F | FF (E) | i 該文法是 LL(1) 文法嗎？（要求給出詳細過程，如果是LL（1）

10、，給出分析表）答：（1）該文法不是LL（1）文法，因為有左遞歸，消除左遞歸可獲得一個LL（1）文法 （2分）（2） 消除左遞歸，得新文法 (3分)E TEE +TE| T FTT *FT |F (E) | i (3)求產(chǎn)生式右部的First集 (2.5分)First(TE) = First(T)= First(F)=(,i First(+TE) = + First(FT) = First(F)=(,i First(*FT) = * First(E) = ( First(i) = i （4） 求所有非終結符的Follow集(2.5分)Follow(E) = $,) Follow(E) = Fol

11、low(E) = $,) Follow(T) = First(E)Follow(E)=+ $,)=$,+,) Follow(T) = Follow(T) =$,*,) Follow(F) = First(T)Follow(T) Follow(T)= $,*,) （5） 求所有產(chǎn)生式的Select集 (2.5分)Select（E TE）=First(TE)= (,i Select（E +TE）=First(+TE)= + Select（E ）= Follow(E) = $,) Select（T FT）=First(FT)= (,i Select（T *FT）=First(*FT)= *Selec

12、t（T ）= Follow(T) =$,+,) Select（F (E)）=First(E)= ( Select（F i）=First(i)= i （6）對相同左部的所有Select即求交集(2.5分)Select（E +TE）Select（E ）= Select（T *FT）Select（T ）= Select（F (E)）Select（F i）= 所以，改造后的文法是LL（1）文法，其分析表如下（7） LL(1) 分析表（ 5 分） V N V T + * i ( )$E E TE E TE E E +TE E E TT FTT FT TT T *FTT T FF (E)F i1（10分）

13、對于文法G：SaSbS|aS|d證明該文法是二義性文法。答：一個文法，如果存在某個句子有不只一棵語法分析樹與之對應，那么稱這個文法是二義性文法。（5分）句子aadbd有兩棵語法樹（5分，劃一棵樹給3分）。如下圖：（分）SaSSabSdddSSabSSad(1) (2)由此可知，SaSbS|aS|d定義的文法是二義性文法。（20分）給定一個簡單的算術表達式文法 GE ： E E+T | T T T*F | FF (E) | i 該文法是 SLR(1) 文法嗎？（要求給出詳細過程，如果是SLR文法，給出分析表）答：(1) 該文法的拓廣文法是： (2分)E E （1）E E+T （2）E T （3）

14、T T*F （4）T F （5）F (E) （6）F i （7）（2） 相應的LR（0）的DFA：（10分）)(FTI0:E .EE .E+T E . T T .T*FT .FF .(E)F .i I1:E E.E E.+T I2:E T. T T.*FEFI3:T F.TI4:F (.E)E .E+T E . T T .T*FT .FF .(E)F .i （iI6:E E+.TT .T*FT .FF .(E)F .i +*（iiTI8:E E+T.T T.*F*I7:T T*.FF .(E)F .i F（iI9:F (E.)E E.+T EI10:F (E) .+I5:F i.FI11:T

15、T*F.（3） 沖突與解決 (3分） I1狀態(tài)中有移進規(guī)約沖突Follow(E)= $ 不含 + 可解決移進規(guī)約沖突 I2狀態(tài)中有移進規(guī)約沖突Follow(E)= +，），$ 不含 * 可解決移進規(guī)約沖突 I8狀態(tài)中有移進規(guī)約沖突Follow(E)= +，），$ 不含 * 可解決移進規(guī)約沖突(4) SLR分析表 (5分)ACTIONGOTO+*i（）$ETF0S5S41231S6接受2r3S7r3r33r5r5r5R5r5r54S5S49235r7r7r7r7r7r76S5S4837S5S4118r2S7r2r29S6S1010r6r6r6r6r6r611r4r4r4r4r4r4二、單項選擇題

16、（每小題2分，共20分）1語言是_C_A終結符與非終結符的符號串的集合 B 非終結符符號串的集合 C終結符符號串的集合 D產(chǎn)生式的集合2編譯程序分兩階段工作，前階段完成的工作是_C_A詞法分析、語法分析和代碼優(yōu)化 B代碼生成、代碼優(yōu)化和詞法分析C詞法分析、語法分析、語義分析和中間代碼生成 D詞法分析、語法分析和代碼優(yōu)化3一個句型中稱為句柄的是該句型的最左C A句型 B短語 C直接短語 D最左直接短語4自動機識別的語言是 DA0型語言 B1型語言 C2型語言 D3型語言5自動機所完成的任務是從字符串形式的源程序中識別出一個個具有獨立含義的最小語法單位即 B A 字符 B單詞 C句子 D句型6對應Chomsky四