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

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

3、 和 M2 狀態數和有向邊條數相等3 .文法 GSHxSx|y 所識別的語言是_C。A.xyxB.(xyx)*Cxnyxn(n0)D.x*yx*4 .如果文法 G 是無二義的，則它的任何句子 a_AA.最左推導和最右推導對應的語法樹必定相同B.最左推導和最右推導對應的語法樹可能不同C.最左推導和最右推導必定相同D.可能存在兩個不同的最左推導，但它們對應的語法樹相同5.構造編譯程序應掌握 D_oA.源程序 B.目標語言C.編譯方法D.以上三項都是6.四元式之間的聯系是通過_B 實現的。7 .表達式(AVB)A(CVD)的逆波蘭表示為_B。A.nABVACDMB.ABVCDVAC.ABVnCtD/

4、AD.ABVACDV8 .優化可生成_D 的目標代碼。A.運行時間較短 B.占用存儲空間較小C.運行時間短但占用內存空間大 D.運行時間短且占用存儲空間小9 .下列C優化方法不是針對循環優化進行的。A.強度削弱 B.刪除歸納變量 C.刪除多余運算 D.代碼外提10 .編譯程序使用_B_區別標識符的作用域。A.說明標識符的過程或函數名 B.說明標識符的過程或函數的靜態層次C.說明標識符的過程或函數的動態層次 D.標識符的行號三、判斷題(對的打，錯的打 X,每小題 1 分，共 10 分)2 .一個有限狀態自動機中，有且僅有一個唯一的終態。x3 .一個算符優先文法的每個非終結符號間都也可能存在優先關

5、系。X4 .語法分析時必須先消除文法中的左遞歸。X6 .逆波蘭表示法表示表達式時無須使用括號。R9 .兩個正規集相等的必要條件是他們對應的正規式等價。X1 .編譯程序是對高級語言程序的編譯執行。X2 .一個有限狀態自動機中，有且僅有一個唯一的初始態。R3 .一個算符優先文法的每個非終結符號間都不存在優先關系。R4 .LL(1)語法分析時必須先消除文法中的左遞歸。R5 .LR 分析法在自左至右掃描輸入串時就能發現錯誤，但不能準確地指出出錯地點。R6 .逆波蘭表示法表示表達式時根據表達式會使用括號。X7 .靜態數組的存儲空間可以在編譯時確定。X8 .進行代碼優化時應著重考慮循環的代碼優化，這對提高

6、目標代碼的效率將起更大作用。X9 .兩個正規集相等的必要條件是他們產生的符號串是相同的。R10 .一個語義子程序描述了一個文法所對應的翻譯工作。X1.什么是S-屬性文法什么是L-屬性文法它們之間有什么關系A.指示器B.臨時變量C.符號表S-屬性文法是只含有綜合屬性的屬性文法。（2 分）2.（10 分）設有語言 L=a|aC0,1+,且 a 不以 0 開頭，但以 00 結尾3 分）試寫出描述 L 的正規表達式;（7 分）構造識別 L 的 DFA（要求給出詳細過程，并畫出構造過程中的 NFA、DFA 的狀態轉換圖，以及最小L-屬性文法要求對于每個產生式 AX1X2-Xn,其每個語義規則中的每個屬性

7、或者是綜合屬性,或者是 Xj 的一個繼承屬性，且該屬性僅依賴于：（1） 產生式 Xj 的左邊符號 X1,X2Xj-1 的屬性；（2） 紳勺繼承屬性。（2 分）S-屬性文法是 L-屬性文法的特例。（1 分）2.什么是 LL（1）分析器2.什么是 LR（0）分析器所謂LR（0）分析，是指從左至右掃描和自底向上的語法分析，且在分析的每一步，只須根據分析棧當前已移進和歸約出的全部文法符號，并至多再向前查看0個輸入符號，就能確定相對于某一產生式左部符號的句柄是否已在分析棧的頂部形成，從而也就可以確定當前所應采取的分析動作五、綜合題（共 40 分）1. （10 分）對于文法 GS:S 一 1A|0B|A

8、一 0S|1AAB-1S|0BB（1）（3 分）請寫出三個關于 GS的句子；（4 分）符號串 11A0S 是否為 GS的句型試證明你的結論。（3 分）試畫出 001B 關于 GS的語法樹。答：（1）三個 0 和 1 數量相等的串（每個 1 分）（2）S=1A=11AA=11A0S（3）（是移進還是按某一產生式進行歸約等）DFA 的狀態轉換圖）答:（1）（3 分）正規表達式：1（0|1）*00將狀態劃分終態與非終態兩個集合：A=q0,q1,根:據 A、 E 集合的情況，對 A 集合進行劃分狀態輸入I0I1q 0一Aq 1AAq 2EAq 3AA（2）（7 分）第一步（3 分）：將正規表達式轉換為

9、 NFA第二步（2 分）：將 NFA 確定化為 DFA（1分）狀態輸入I0I1S一A,D,BA,D,BD,B,CD,BD,B,CD,B,C,ZD,BD,BD,B,CD,BD,B,C,ZD,B,C,ZD,BDFA 的狀態轉換圖（1 分）q0一一q1重新訪名q1q2q3q2q4q3L ,q3q2q3q4q4q3t01第三步（2 分）：將DFA 最小化：（1 分）將狀態集 A 劃分為兩個集合：A=qO,ql,q3,B=2根:據 A、 B 集合的情況，對 A 集合進行劃分狀態輸入I0I1q 0一Aq 1BAq 3BA將狀態集 A 劃分為兩個集合：A=qO,C=ql,q3根據 A、C 集合的情況，對 C

10、 集合進行劃分狀態輸入I0I1qiBAq3BA3.(20 分)給定文法 GE:EE+T|TT 一 T*F|FF 一(E)|i該文法是 LL(1)文法嗎(要求給出詳細過程，如果是 LL(1),給出分析表)答：(1)該文法不是 LL(1)文法，因為有左遞歸，消除左遞歸可獲得一個 LL(1)文法(2)消除左遞歸，得新文法(3 分)E-TEE一+TE|T-FTT一*FT|eF 一(E)|i(3)求產生式右部的 First 集分)First(TE)=First(T)=First(F)=(,i（2 分）最小 DFA 的狀態轉換圖(1 分)First（+TE，）=+First(FT)=First(F)=(,

11、iFirst(*FT)=*First(E)=(First(i)=i(4)求所有非終結符的 Follow 集分)Follow(E)=$,)Follow(E)=Follow(E)=$,)Follow(T)=First(E)UFollow(E)=+U$,)=$,+,)Follow(T)=Follow(T)=$,*,)Follow(F)=First(T)UFollow(T)UFollow(T)=$,*,)(5)求所有產生式的 Select 集分)Select(EfTE)=First(TE)=(,iSelect(Ef+TE)=First(+TE)=+Select(E)=Follow(E)=$,)Sele

12、ct(TfFT)=First(FT)=(,iSelect(Tf*FT)=First(*FT)=*Select(T-e)=Follow(T)=$,+,)Select(F-(E)=First(E)=(Select(F-i)=First(i)=i(6)對相同左部的所有 Select 即求交集分)Select(Ef+TE)nSelect(E-e)=Select(T*FT)nSelect(Tfe)=Select(Ff(E)nSelect(Ffi)=所以，改造后的文法是 LL(1)文法，其分析表如下(7)LL(1)分析表(5 分)VTi()$E-TEEfTEEEf+TETfFTTfFTTT-eT一*FTF

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

14、T*F(4)T 一 FF 一(E)F 一 i(2)相應的 LR(0)的 DFA(10 分)I1 狀態中有移進一規約沖突Follow(E)=$不含+可解決移進一規約沖突I2 狀態中有移進一規約沖突Follow(E)=+,),$不含*(5)(6)(3)沖突與解決(3 分)可解決移進一規約沖突I8 狀態中有移進一規約沖突Follow(E)=+,),$不含*可解決移進一規約沖突(4)SLR 分析表(5 分)ACTIONGOTO+*i()$ETF0S5S41231S6接受2r3S7r3r33r5r5r5R5r5r54S5S49235r7r7r7r7r7r76S5S4837S5S4118r2S7r2r29

15、S6S1010r6r6r6r6r6r611r4r4r4r4r4r4二、單項選擇題(每小題 2 分，共 20 分)1 .語言是 C_A 終結符與非終結符的符號串的集合 B.2 .編譯程序分兩階段工作，前階段完成的工作是A 詞法分析、語法分析和代碼優化C.詞法分析、語法分析、語義分析和中間代碼生成3 .一個句型中稱為句柄白是該句型的最左 CA.句型 B.短語 C.直接短語 D4 .自動機識別的語言是 DA0 型語言 B.1 型語言 C.2 型語言 D.3 型語言5 .自動機所完成的任務是從字符串形式的源程序中識別出一個個具有獨立含義的最小語法單位即 BA,字符 B,單詞 C.句子 D.句型非終結符符號串的集合 C.終結符符號串的集合 D_CB.代碼生成、代碼優化和詞法分析D.詞法分析、語法分析和代碼優化最左直接短語.產生式的集合6 .對應 Chomsky 四種文法的四種語言之間的關系是7 .詞法分析的任務是 AA.