1、中國地質大學（北京）繼續教育學院 2015年11課程考試編譯原理模擬題（補）一 單項選擇題1.（ ）是兩類程序語言處理程序。A. 高級語言程序和低級語言程序B. 解釋程序和編譯程序C. 編譯程序和操作系統D. 系統程序和應用程序2. 編譯程序前三個階段完成的工作是（ ）。A. 詞法分析、語法分析和代碼優化B. 代碼生成、代碼優化和詞法分析C. 詞法分析、語法分析、語義分析和中間代碼生成D. 詞法分析、語法分析和代碼優化3. 一個上下文無關文法G包括四個組成部分：一組終結符，一組非終結符，一個開始符號，以及一組（ ）。A. 字符串B. 產生式C. 非開始符號D. 文法4. 詞法分析器的輸出結果是

2、（ ）。A. 單詞的種別編碼B. 單詞在符號表中的位置C. 單詞的種別編碼和自身值D. 單詞自身值5. 一個句型中稱為句柄的是該句型的最左（ ）。A. 非終結符號B. 短語C. 句子D. 直接短語6. 高級語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于（ ）分析方法。A. 自左向右B. 自頂向下C. 自底向上D. 自右向左7. 在通常的語法分析方法中，（ ）特別適用于表達式的分析。A. 算符優先分析法B. LR分析法C. 遞歸下降分析法D. LL（1）分析法8. 優化可生成_的目標代碼。A. 運行時間較短B. 占用存儲空間較小C. 運行時間短但占用內存空間大D. 運行時間短且占用存儲空間

3、小9.（ ）是兩類程序語言處理程序。A. 系統程序和應用程序B.編譯程序和操作系統C. 解釋程序和編譯程序D.高級語言程序和低級語言程序10. 經過編譯所得到的目標程序是（ ）。A. 四元式序列B. 間接三元式序列C. 二元式序列D. 機器語言程序或匯編語言程序11. 程序的基本塊是指（ ）。A. 一個子程序B. 一個僅有一個入口和一個出口的語句C. 一個沒有嵌套的程序段D. 一組順序執行的程序段，僅有一個入口和一個出口12. 一個上下文無關文法G包括四個組成部分：一組終結符，一組非終結符，一個開始符號，以及一組（ ）。A. 字符串B. 產生式C. 非開始符號D. 文法13. 文法G產生的（

4、）的全體是該文法描述的語言。A. 句型B. 終結符集C. 非終結符集D. 句子14. 詞法分析器用于識別（ ）。A. 字符串B. 語句C. 單詞D. 標識符15. 常用的中間代碼形式不含（ ）。A. 三元式B. 四元式C. 逆波蘭式D. 語法樹16. 下列_優化方法不是針對循環優化進行的。A. 強度削弱B. 刪除歸納變量C. 刪除多余運算D. 代碼外提二 填空題1. 一個名字的屬性包括（ ）和作用域。2. 一張轉換圖只包含有限個狀態,其中有一個被認為是初態，而且實際上至少要有一個（ ）。3. 規范規約是最（ ）規約。4. 語法分析器的輸入是（ ），其輸出是語法單位。5. 語法分析的有效工具是（

5、 ）。6. 一個LR分析器包括兩部分：一個總控程序和（ ）。7. 中間代碼產生（ ）是依據語言的規則進行的。8. 編譯方式與解釋方式的根本區別在于（ ）。9. 編譯程序的工作過程一般劃分為5個階段：詞法分析、（ ）、語義分析與中間代碼生成，代碼優化及目標代碼生成。10. 掃描器的任務是從源程序中識別出一個個（ ）。11. 詞法分析基于（ ）文法進行，即識別的單詞是該類文法的句子。12. 語法分析的有效工具是（ ）。13. 語法分析最常用的兩類方法是（ ）和自下而上分析法。14. 分析句型時，應用算符優先分析技術時，每步被直接歸約的是（ ）。三 判斷題1.一個有限狀態自動機中，有且僅有一個唯一的

6、終態。 （ ）2. 正規文法產生的語言都可以用上下文無關文法來描述。 （ ）3. 確定的自動機以及不確定的自動機都能正確地識別正規集。 （ ）4. 如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的。（ ）5. 綜合屬性是用于“自上而下”傳遞信息。 （ ）6. 遞歸下降分析法是自頂向上分析方法。 （ ）7. 一個算符優先文法可能不存在算符優先函數與之對應。 （ ）8. LR法是自頂向下語法分析方法。 （ ）9.產生式是用于定義詞法成分的一種書寫規則。 （ ）10. 一個句型的句柄一定是文法某產生式的右部。 （ ）11. 每個文法都能改寫為LL(1)文法。（ ）12. 語法分析時

7、必須先消除文法中的左遞歸 。（ ）13. 規范歸約和規范推導是互逆的兩個過程。 （ ）14. 算符優先關系表不一定存在對應的優先函數。 （ ）15. LR法是自頂向下語法分析方法。 （ ）16. 對中間代碼的優化依賴于具體的計算機。 （ ）四 簡答題1. 寫一個文法，使其語言是奇數集，且每個奇數不以0開頭。2. 已知文法GS為SaSb|Sb|b，試證明文法GS為二義文法。3. 文法G(S)SdABAaA|aBBb|描述的語言是什么？4. 寫一個文法使其語言為偶數集，且每個偶數不以0開頭。5. 證明文法G(S)SSaS|是二義性的。五、程序設計題1. 已知文法G(S)：Sa|(T)TT,S|S寫

8、出句子(a，a)，a)的規范歸約過程及每一步的句柄。2. 已知文法GE:EETE|(E)|iT*|+1) 將文法G改造成LL（1）文法；2) 構造文法G中每個非終結符的FIRST集合及FOLLOW集合；3) 構造LL（1）分析表。參考答案：1 單項選擇題12345678BCBCDBAD910111213141516CDDBDCDC二填空題1. 類型2. 終態3. 左4. 單詞符號串5. 語法樹6. 一張分析表7. 語義8. 是否生成目標代碼9. 語法分析10. 單詞符號11. 正則12. 語法樹13. 自上而下14. 最左素短語三判斷題12345678910111213141516四. 簡答題

9、1. 文法G(N)：NAB|BAAC|DB1|3|5|7|9DB|2|4|6|8C0|D2. 證明：由文法GS：SaSb|Sb|b，對句子aabbbb對應的兩棵語法樹為： 因此，文法GS為二義文法。3. L(G)=danbm |n>0, m04. 文法G(S)：SAB|B|A0AAD|CB2|4|6|8C1|3|5|7|9|BD0|C5. 證明：因為文法GS存在句子aa有兩個不同的最左推導，所以文法GS是是二義性的。 S=>SaS=>SaSaS=>aSaS=>aaS=>aaS=>SaS=>aS=>aSaS=>aaS=>aa五. 程序設計題1. 句型歸約規則句柄(a，a)，a)Saa(S，a)，a)TSS(T，a)，a)Saa(T，S)，a)TT，ST，S(T)，a)S(T)(T)(S，a)TSS(T，a)Saa(T，S)TT，ST，S(T)S(T)(T)S2. 1) 文法存在左遞歸，消除左遞歸后的文法為：E(