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

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

3、向邊條數相等3 .文法G: S-> xSx|y所識別的語后是_C。A. xyx B. (xyx)*C. xnyxn(n >0) D . x*yx*4 .如果文法 G是無二義的，則它的任何句子a A 。A .最左推導和最右推導對應的語法樹必定相同B .最左推導和最右推導對應的語法樹可能不同C .最左推導和最右推導必定相同D.可能存在兩個不同的最左推導，但它們對應的語法樹相同5 .構造編譯程序應掌握 D_oA .源程序B.目標語言C.編譯方法D.以上三項都是6 .四元式之間的聯系是通過 _B 實現的。A.指示器B.臨時變量C.符號表D.程序變量7 .表達式AV B) A (C V D)

4、的逆波蘭表示為_B。A . n ABV A CD VB. An B V CD V A C. AB V n CDV AD. An B V A CD V8 .優化可生成_D 的目標代碼。A .運行時間較短B.占用存儲空間較小C.運行時間短但占用內存空間大D.運行時間短且占用存儲空間小9 .下列C優化方法不是針對循環優化進行的。C.刪除多余運算D .代碼外提B.說明標識符的過程或函數的靜態層次D.標識符的行號A.強度削弱B.刪除歸納變量10 .編譯程序使用_B_區別標識符的作用域。A.說明標識符的過程或函數名C.說明標識符的過程或函數的動態層次三、判斷題(對的打，錯的打X,每小題1分，共10分)2

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

6、據表達式會使用括號。X7 .靜態數組的存儲空間可以在編譯時確定。X8 .進行代碼優化時應著重考慮循環的代碼優化，這對提高目標代碼的效率將起更大作用。X9 .兩個正規集相等的必要條件是他彳門產生的符號串是相同的。R10 . 一個語義子程序描述了一個文法所對應的翻譯工作。X1 .什么是S-屬性文法？什么是L-屬性文法？它們之間有什么關系？S-屬性文法是只含有綜合屬性的屬性文法。（2分）L-屬性文法要求對于每個產生式 A X1X2- Xn,其每個語義規則中的每個屬T或者是綜合屬性，或者是Xj的一個繼承屬性，且該屬性僅依賴于：（1） 產生式Xj的左邊符號X1,X2Xj-1的屬性；（2） A的繼承屬性。

7、（2分）S-屬性文法是L-屬性文法的特例。（1分）2 .什么是L L （ 1 ）分析器3 .什么是LR （0）分析器所謂LR（0）分析，是指從左至右掃描和自底向上的語法分析，且在分析的每一步，只須根據分析棧當前已移進和歸約出的全部文法符號，并至多再向前查看0個輸入符號，就能確定相對于某一產生式左部符號的句柄是否已在分析棧的頂部形成，從而也就可以確定當前所應采取的分析動作（是移進還是按某一產生式進行歸約等 ）五、綜合題（共40分）1. （10分）對于文法 GS:S f 1A | 0B | e A f 0S | 1AA B f 1S | 0BB（3分）請寫出三個關于 GS的句子；（4分）符號串11

8、A0S是否為 G S的句型？試證明你的結論。（3分）試畫出001B關于G S的語法樹。答：（1）三個0和1數量相等的串（每個1分）（2） S => 1A => 11AA => 11A 0S2. （10分）設有語言 L= a | a C 0,1 + ,且a不以0開頭，但以 00結尾23分）試寫出描述 L的正規（7分）構造識別 L的DFADFA的狀態車t換圖）。答：（1 ） （3分）正規表達式： 1（0|1）（2 ） （ 7分）第一步（3分）：將五:給出詳細過程，并畫出構造過程中的00達式轉換為NFANFA、 DFA的狀態轉換圖，以及最小第二步（2分）：將NFA確定化 狀態輸入

9、I 0I 1S一 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分）DFA : （1 分）t0q 0一重新命名q 1 q 2f。 q 2 q 4q 3q 2q 4q 41q 1q 3q 3q 3q 3：（1 分）A=q0,ql,q2,q3 ,E =第三步（2分）：將DFA最小化 將狀態劃分終態與非終態兩個集合: 根據A、E集合的情況，對A集合無狀態輸入 I 0I 1q 0Aq 1AAq 2EAq 3AA將狀態集A劃分為兩個集合：A=q0,ql,q3,B=2根據A、B集合的情況，對A集合進行劃分狀態

10、輸入I 0I 1q。一Aq 1BAq 3BA將狀態集A劃分為兩個集合:A= q 0,C = q 1 , q 3 根據A、C集合的情況，對C集合進行劃分狀態輸入I 0I 1q 1BAq 3BA最小DFA的狀態轉換圖（1分）3 . (20分)給定文法GE:E E+T | TT 一 T*F | FF -(E) | i文法 （2分）該文法是LL(1)文法嗎？(要求給出詳細過程，如果是 LL (1),給出分析表) 答：(1)該文法不是LL (1)文法，因為有左遞歸，消除左遞歸可獲得一個LL (1)(2)消除左遞歸，得新文法(3分)E - TE'E' 一 +TE' | £

11、T - FT'T'一 *FT'| £F -(E) | i(3)求產生式右部的First集 (2.5分)First(TE ' ) = First(T)=First(F)=(,iFirst(+TE ' ) = +First(FT ' ) = First(F)=(,iFirst(*FT ' ) = *First(E) = (First(i) = i(4)求所有非終結符的Follow集(2.5分)Follow(E) = $,)Follow(E ' ) = Follow(E) = $,)Follow(T) = First(E &#

12、39; ) U Follow(E尸+U $,)=$,+,)Follow(T ' ) = Follow(T) =$,*,)Follow(F) = First(T ' ) U Follow(T) U Follow(T ' )= $,*,) (5)求所有產生式的Select集(2.5分)Select(E 一TE' )=First(TE ' )=(,iSelect(E' 一+TE') =First(+TE ')= +Select (E' 一 £ ) = Follow(E ' ) = $,)Select(T 一FT

13、' )=First(FT ' )=(,iSelect (T'一 *FT' ) =First(*FT ' )= *Select (T' 一 £ ) = Follow(T ' ) =$,+,)Select (F 一(E) =First(E)= (Select (F 一 i) =First(i)= i(6)對相同左部的所有Select即求交集(2.5分)Select (E' 一 +TE' ) n Select (E' 一 e )=Select (T' 一 *F)n Select (T' 一 e)

14、=Select (F 一(E) n Select ( F 一 i )=所以，改造后的文法是（7） LL（1）分析表（V N +EE'E' 一 +TE'TT'r一 eT'FLL (1)文法，其分析表如下5分)$E>£E>£T'feT'f8F 一 iV T*i(E 一 TE'E 一 TE'T 一 FT'T 一 FT'一 *FT'F 一 (E)1. （10分）對于文法G:S >aSbS|aS|d 證明該文法是二義性文法。答：一個文法，如果存在某個句子有不只一棵語法分析

15、樹與之對應，那么稱這個文法是二義性文法。（5分）句子aadbd有兩棵語法樹（5分，劃一棵樹給 3分）。如下圖：（6分）（1）（2）由此可知，S-*aSbS|aS|d定義的文法是二義性文法。3 . （20分）給定一個簡單的算術表達式文法GE:E E+T | TT 一 T*F | FF -（E） | iSLR文法，給出分析表）該文法是SLR（1）文法嗎？（要求給出詳細過程，如果是 答：（1）該文法的拓廣文法是：（2分）E' E(1)E fE+T(2)E 一T(3)T T*F(4)T 一F(5)F - (E)(6)F - i(7)(2)相應的LR (0)的DFA (10分)（3）沖突與解決（

16、3分） I1狀態中有移進一規約沖突Follow(E ' )= $ 不含 + 可解決移進一規約沖突 I2狀態中有移進一規約沖突Follow(E)=+,),$不含 * 可解決移進一規約沖突 I8狀態中有移進一規約沖突Follow(E)=+,),$不含 * 可解決移進一規約沖突(4) SLR分析表(5分)ACTIONGOTO+*i()$ETF0S5S41231S6接受2r3S7r3r33r5r5r5R5r5r54S5S49235r7r7r7r7r7r76S5S4837S5S4118r2S7r2r29S6S1010r6r6r6r6r6r611r4r4r4r4r4r4二、單項選擇題(每小題 2分

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