1、編譯原理考試題及答案匯總一、選擇1將編譯程序分成若干個“遍”是為了 _B_。A . 提高程序的執行效率B. 使程序的結構更加清晰C. 利用有限的機器內存并提高機器的執行效率D. 利用有限的機器內存但降低了機器的執行效率2正規式 MI 和 M2 等價是指 _C_。A . MI 和 M2 的狀態數相等 B.Ml 和 M2 的有向弧條數相等。C .M1 和 M2 所識別的語言集相等 D. Ml 和 M2 狀態數和有向弧條數相等3中間代碼生成時所依據的是_C_。A.語法規則 B 詞法規則 C 語義規則 D 等價變換規則4.后綴式 ab+cd+/可用表達式_B_來表示。A. a+b/c+d B . (a

2、+b)/(c+d) C a+b/(c+d) D a+b+c/d6 一個編譯程序中，不僅包含詞法分析， _A_，中間代碼生成，代碼優化，生成等五個部分。A( ) 語法分析 B( ) 文法分析 C( ) 語言分析 D( ) 解釋分析 7詞法分析器用于識別 _C_。A( ) 字符串 B( ) 語句 C( ) 單詞 D( ) 標識符 8 語法分析器則可以發現源程序中的_D_。A( ) 語義錯誤 B ( ) 語法和語義錯誤 C( ) 錯誤并校正 D ( ) 語法錯誤 9 下面關于解釋程序的描述正確的是_B_。(1)解釋程序的特點是處理程序時不產生目標代碼(2)解釋程序適用于 COBOL 和 FORTRA

3、N 語言(3)解釋程序是為打開編譯程序技術的僵局而開發的A( ) (1)(2) B ( ) (1) C ( ) (1)(2)(3) D ( ) (2)(3) 10 解釋程序處理語言時 , 大多數采用的是_B_方法。A( ) 源程序命令被逐個直接解釋執行B( ) 先將源程序轉化為中間代碼 , 再解釋執行C( ) 先將源程序解釋轉化為目標程序 , 再執行D( )以上方法都可以11 編譯過程中 , 語法分析器的任務就是(1) 分析單詞是怎樣構成的 (2)(3) 分析語句和說明是如何構成程序的A( ) (2)(3) B ( ) (2)(3)(4)C( ) (1)(2)(3) D ( ) (1)(2)(

4、3)(4)12 編譯程序是一種 _C_。A. ( ) 匯編程序 B ( ) 翻譯程序 C ( ) 解釋程序 D ( ) 目標程序 13 文法 G 所描述的語言是 _C_的集合。A. ( )文法 G 的字母表 V 中所有符號組成的符號串B( )文法 G 的字母表 V 的閉包 V* 中的所有符號串C( )由文法的開始符號推出的所有終極符串D. ( ) 由文法的開始符號推出的所有符號串14 文法分為四種類型，即 0 型、 1 型、 2 型、 3 型。其中 3 型文法是 _B_。A. ( ) 短語文法 B ( ) 正則文法 C ( ) 上下文有關文法 D ( ) 上下文無關文法 15 一個上下文無關文

5、法 G 包括四個組成部分，它們是：一組非終結符號，一 組終結符 號，一個開始符號，以及一組 _D_ 。A( ) 句子 B( ) 句型 C( ) 單詞 D( ) 產生式16 通常一個編譯程序中， 不僅包含詞法分析， 語法分析， 中間代碼生成， 代碼優化， 目 標 代碼生成等五個部分，還應包括 _C_。A. ( ) 模擬執行器B. ( )解釋器C. ( ) 表格處理和出錯處理D.( )符號執行器目標代碼_B_。分析單詞串是如何構成語句和說明的(4) 分析程序的結構17.文法 GN=( bN ， B，N ,NTb | bB ,BtbN)，該文法所描述 的語言是 CA. ( ) L(GN)=bi1i

6、0B( ) L(GN)=b2i1i0C. ( ) L(GN)=b2i+11i0 D.( ) L(GN)=b2i+11i 118.一個句型中的最左B_稱為該句型的句柄。A. ( ) 短語 B .( )簡單短語C. ( ) 素短語D.( )終結符號19.設 G 是一個給定的文法，S 是文法的開始符號，如果 S-x(其中 x V*),則稱 x 是 文法 G 的一個 _B_。A. ( ) 候選式 B . ( ) 句型 C . ( ) 單詞 D . ( ) 產生式20.文法 GE ：ETTIE+TTTFIT*FFtaI (E)該文法句型 E F * (E T) 的簡單短語是下列符號串中的 _。( E+T

7、) E + T F F*(E+ T)A. ( ) 和 B . ( ) 和 C . ( ) 和 D . ( ) 21.若一個文法是遞歸的，則它所產生的語言的句子_A_。A. ( ) 是無窮多個B . ( ) 是有窮多個C. ( ) 是可枚舉的D . ( ) 個數是常量22.詞法分析器用于識別 _C_。A. ( )句子 B .( )句型C . ( ) 單詞 D . ( ) 產生式23.在語法分析處理中，_ FIRST 集合、FOLLOW 集合、SELECT 集合均是_B_。A . ( ) 非終極符集B. ( )終極符集 C . ( ) 字母表 D . ( )狀態集24.在自底向上的語法分析方法中，

8、分析的關鍵是_A_。A .( ) 尋找句柄 B .( ) 尋找句型 C .( ) 消除遞歸 D .( ) 選擇候選式25.在 LR 分析法中，分析棧中存放的狀態是識別規范句型_C_的 DFA 狀態。A .( ) 句柄 B .( ) 前綴 C .( ) 活前綴 D .( ) LR(0) 項目26.文法 G 產生的 _D_的全體是該文法描述的語言。A. ( ) 句型 B. ( ) 終結符集 C. ( ) 非終結符集 D. ( ) 句子27.若文法 G 定義的語言是無限集，則文法必然是_A_A. ( ) 遞歸的 B . ( ) 前后文無關的C . ( ) 二義性的 D . ( ) 無二義性的28.四

9、種形式語言文法中， 1 型文法又稱為 _A_文法。A. ( ) 短語結構文法 B . ( ) 前后文無關文法C. ( ) 前后文有關文法 D . ( ) 正規文法29.一個文法所描述的語言是 _A_。A. ( ) 唯一的B. ( ) 不唯一的C. ( ) 可能唯一，好可能不唯一 D . ( ) 都不對30._B_和代碼優化部分不是每個編譯程序都必需的。A. ( ) 語法分析 B . ( ) 中間代碼生成C. ( ) 詞法分析 D . ( ) 目標代碼生成31._B_ 是兩類程序語言處理程序。A. ( ) 高級語言程序和低級語言程序B . ( ) 解釋程序和編譯程序C. ( ) 編譯程序和操作系

10、統D. ( ) 系統程序和應用程序32.數組的內情向量中肯定不含有數組的 _A_ 的信息。A . ( ) 維數 B . ( ) 類型 C . ( ) 維上下界 D . ( ) 各維的界差33.一個上下文無關文法 G 包括四個組成部分， 它們是： 一組非終結符號， 一組終結符號，一個開始符號，以及一組_D_ 。A. ( ) 句子 B . ( ) 句型C( ) 單詞 D ( ) 產生式34 文法分為四種類型，即 0 型、 1 型、 2 型、 3 型。其中 2 型文法是 _D_。A . ( ) 短語文法 B ( ) 正則文法C( ) 上下文有關文法 D ( ) 上下文無關文法 35一個上下文無關文法

11、 G 包括四個組成部分，它們是：一組非終結符號，一組終結符號， 一個開始符號，以及一組 _D_ 。A( ) 句子 B ( ) 句型 C ( ) 單詞 D ( ) 產生式 36 _A_是一種典型的解釋型語言。A( ) BASIC B ( ) C C ( ) FORTRAN D( ) PASCAL 37與編譯系統相比，解釋系統 _D_。A( ) 比較簡單 , 可移植性好 , 執行速度快B( ) 比較復雜 , 可移植性好 , 執行速度快C ( ) 比較簡單 , 可移植性差 , 執行速度慢D( ) 比較簡單 , 可移植性好 , 執行速度慢 38用高級語言編寫的程序經編譯后產生的程序叫_B_。A( )

12、源程序 B ( ) 目標程序 C( ) 連接程序 D( ) 解釋程序 39編寫一個計算機高級語言的源程序后, 到正式上機運行之前，一般要經過_B_這幾步:(1)編輯 (2) 編譯 (3) 連接 (4) 運行A . ( ) (1)(2)(3)(4) B( ) (1)(2)(3) C( ) (1)(3) D( ) (1)(4)40把匯編語言程序翻譯成機器可執行的目標程序的工作是由_A_完成的。A( ) 編譯器 B ( ) 匯編器C( ) 解釋器 D( ) 預處理器 41詞法分析器的輸出結果是_C_。A( ) 單詞的種別編碼B( ) 單詞在符號表中的位置C( ) 單詞的種別編碼和自身值 D ( )

13、單詞自身值42.文法 G : STxSx|y 所識別的語言是 _C。A. ( ) xyx B . ( ) (xyx)* C . ( ) xnyxn(n 0) D . ( ) x*yx*43.如果文法 G 是無二義的，則它的任何句子aAoA ( ) 最左推導和最右推導對應的語法樹必定相同B( ) 最左推導和最右推導對應的語法樹可能不同C( ) 最左推導和最右推導必定相同D ( ) 可能存在兩個不同的最左推導， 但它們對應的語法樹相同 44 構造編譯程序應掌握 _D_oA( ) 源程序 B ( ) 目標語言C( ) 編譯方法 D( ) 以上三項都是45.四元式之間的聯系是通過 _B實現的。A( )

14、 指示器 B ( ) 臨時變量C( ) 符號表 D ( ) 程序變量46. 表達式(AVB)A(CVD)的逆波蘭表示為 _B_A . ( )nABVACDVB.( ) AnBVCDVAC. ( ) ABVnCDVAD.( ) AnBVACDV47. 優化可生成_D的目標代碼。A( ) 運行時間較短 B( ) 占用存儲空間較小C( ) 運行時間短但占用內存空間大 D ( ) 運行時間短且占用存儲空間小48._ 下列_C化方法不是針對循環優化進行的。A . ( ) 強度削弱 B ( ) 刪除歸納變量C( ) 刪除多余運算 D ( ) 代碼外提49. 編譯程序使用_B區別標識符的作用域。A . (

15、) 說明標識符的過程或函數名B( ) 說明標識符的過程或函數的靜態層次C( ) 說明標識符的過程或函數的動態層次D . ( ) 標識符的行號 50編譯程序絕大多數時間花在 _D_ 上。A( ) 出錯處理 B( ) 詞法分析 C( ) 目標代碼生成 D( ) 表格管理51 編譯程序是對 _D58. 若項目集 Ik 含有 A - a ?，則在狀態 k 時，僅當面臨的輸入符號 時，才采取“ A- a ? ”動作的一定是_D_。A . ( ) LALR文法 B . ( ) LR(0) 文法C. ( ) LR(1) 文法 D . ( ) SLR(1) 文法59.堆式動態分配申請和釋放存儲空間遵守_D_原

16、則。A . ( )先請先放 B . ( ) 先請后放C. ( ) 后請先放 D . ( )任意、判斷I .計算機高級語言翻譯成低級語言只有解釋一種方式。(X)2.在編譯中進行語法檢查的目的是為了發現程序中所有錯誤。(X)3. 甲機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系 統功能完全相同。(V)4. 正則文法其產生式為 A-a ， A-Bb, A,B VN ， a 、 bVT 。 (X)5. 每個文法都能改寫為 LL(1) 文法。 (V)6. 遞歸下降法不允許任一非終極符是直接左遞歸的。 (V)7. 算符優先關系表不一定存在對應的優先函數。 (X)8.自底而上語法分析方法的

17、主要問題是候選式的選擇。(X)9. LR 法是自頂向下語法分析方法。 (X)10. 簡單優先文法允許任意兩個產生式具有相同右部。 (X)II.“ 用高級語言書寫的源程序都必須通過編譯 , 產生目標代碼后才能投入運行 ”這種 說法。(X)12.若一個句型中出現了某產生式的右部，則此右部一定是該句型的句柄。 (X)13.一個句型的句柄一定是文法某產生式的右部。 (V)52.采用自上而下分析，必須_C_。A. ( )消除左遞歸B. ( ) 消除右遞歸C. ( )消除回溯 D . ( )提取公共左因子53.在規范歸約中，用 _B來刻畫可歸約串。A. ( )直接短語 B . ( )句柄C. ( )最左素

18、短語D. ( ) 素短語54.若 a 為終結符，則A -a? aB為 B_項目。A. ( )歸約 B. ( )移進 C . ( )接受 D. ( ) 待約55.間接三元式表示法的優點為_A_。A( ) 采用間接碼表，便于優化處理C ( ) 便于優化處理， 節省存儲空間 56 基本塊內的優化為 _B_。A . ( ) 代碼外提，刪除歸納變量C( ) 強度削弱，代碼外提 D 57 在目標代碼生成階段，符號表用 _ A( ) 目標代碼生成 B( ) 語義檢查B ( ) 刪除多余運算，刪除無用賦值( ) 循環展開，循環合并D_。C( ) 語法檢查 D( ) 地址分配a FOLLOW(A)A( ) 匯編

19、程序的翻譯C ( ) 機器語言的執行B ( ) 高級語言程序的解釋執行D ( ) 高級語言的翻譯B ( ) 節省存儲空間，不便于表的修改D ( ) 節省存儲空間，不便于優化處理1 4 .在程序中標識符的出現僅為使用性的。(X)15.僅考慮一個基本塊， 不能確定一個賦值是否真是無用的。(V)16.削減運算強度破壞了臨時變量在一基本塊內僅被定義一次的特性。(V)017.在中間代碼優化中循環上的優化主要有不變表達式外提和削減運算強度。(x)18.數組元素的地址計算與數組的存儲方式有關。(x)19.編譯程序與具體的機器有關 ,與具體的語言無關。 (x)20.遞歸下降分析法是自頂向上分析方法。(V)21

20、.產生式是用于定義詞法成分 的一種書寫規則。 (x)22.LR 法是自頂向下語法分析方法。(x)23.在 SLR ( 1 )分析法的名稱中， S 的含義是簡單的。 (V)24. 綜合屬性是用于 “ 自上而下 ” 傳遞信息。 (x)25.符號表中的信息欄中登記了每個名字的屬性和特征等有關信息 ，如類型、種屬、所占 單元大小、地址等等。 (x)26.程序語言的語言處理程序是一種應用軟件。(x)27. 一個 LL(l) 文法一定是無二義的。 (x)28.正規文法產生的語言都可以用上下文無關文法來描述。(x)29. 一張轉換圖只包含有限個狀態， 其中有一個被認為是初態， 最多只有一個終態。 (V)30

21、.目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。(x)31. 逆波蘭法表示的表達式亦稱后綴式 。(V)32.如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的。(V)33. 數組元素的地址計算與數組的存儲方式有關。 (x)34. 對于數據空間的存貯分配， FORTRAN 采用動態貯存分配策略。(X)35. 編譯程序是對高級語言程序的解釋執行。 (x)36. 一個有限狀態自動機中，有且僅有一個唯一的終態。 (x)37.語法分析時必須先消除文法中的左遞歸。 (x)38.LR 分析法在自左至右掃描輸入串時就能發現錯誤， 但不能準確地指出出錯地點。 (V)39.逆波蘭表示法表

22、示表達式時無須使用括號。 (V)40.靜態數組的存儲空間可以在編譯時確定。(x)41. 進行代碼優化時應著重考慮循環的代碼優化，這對提高目標代碼的效率將起更大作用。(x)42.兩個正規集相等的必要條件是他們對應的正規式等價。(x)43.一個語義子程序描述了一個文法所對應的翻譯工作。(x)44. r 和 s 分別是正規式，則有 L(r|s)=L(r)L(s)。(x)45.確定的的自動機以及不確定的自動機都能正確地識別正集(V)46.分析作為單獨的一遍來處理較好。(x)47. LR 分析器的任務就是產生 LR 分析表。 (V)48. 歸約和規范推導是互逆的兩個過程。 (V)49. 同心集的合并有可

23、能產生新的“移進” / “歸約” 沖 突 (x)50.lR 分析技術無法適用二義文法。 (x) 51 樹形表示和四元式不便于優化，而三元式和間接三元式則便于優化。(x)52 序中的表達式語句在語義翻譯時不需要回填技術。(V)三、填空1 .編譯程序的工作過程一般可以劃分為詞法分析 ,語法分析 ,語義分析 ,中間代碼 生成,代碼優化等幾個基本階段 ,同時還會伴有 _表格處理_和 _出錯處理_。2 .若源程序是用高級語言編寫的 ,_目標程序 _是機器語言程序或匯編程序 , 則其翻譯程序稱為 _編譯程序 _ 。3 .編譯方式與解釋方式的根本區別在于 _是否生成目標代碼 _。4 .對編譯程序而言 ,輸入

24、數據是 _源程序_, 輸出結果是 _目標程序5產生式是用于定義 _語法成分的一種書寫規則。6.語法分析最常用的兩類方法是 自上而下和自下而上分析法7.設 G 是一個給定的文法，S 是文法的開始符號，如果 S-x(其中 x VT*),則稱 x 是文法的一個_句子_。8.遞歸下降法不允許任一非終極符是直接 _左_遞歸的。9.自頂向下的語法分析方法的基本思想是 ：從文法的_開始符號開始，根據給定的輸入串并按照文法的產生式一步一步的向下進行直接推導_ ，試圖推導出文法的_句子_ ,使之與給定的輸入串 _匹配 。10.自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產生式一步一步地向上進行_

25、直接歸約 ，力求歸約到文法的_開始符號_。11常用的參數傳遞方式有 傳地址，傳值和傳名。12.在使用高級語言編程時，首先可通過編譯程序發現源程序的全部_語法錯誤和語義的部分錯誤。13. 一個句型中的最左簡單短語稱為該句型的_句柄_。14 對于文法的每個產生式都配備了一組屬性的計算規則，稱為 語義規則 。15 . 一個典型的編譯程序中，不僅包括_詞法分析 、_語法分析、中間代碼生成、代碼優化、目標代碼生成等五個部分，還應包括表格處理和出錯處理。16 .從功能上說，程序語言的語句大體可分為_執行性_語句和說明性語句兩大類。17 .產生式是用于定義_語法范疇的一種書寫規則。18 語法分析是依據語言的

26、 語法_規則進行的，中間代碼產生是依據語言的 _語義 規進行的。19 .語法分析器的輸入是 單詞符號串,其輸出是_語法單位。20.產生式是用于定義 語法成分的一種書寫規則。21 .逆波蘭式 ab+c+ d*e- 所表達的表達式為 _(a+b+c)*d-e _。22 .語法分析最常用的兩類方法是 _自上而下和自下而上分析法。23 .計算機執行用高級語言編寫的程序主要有兩種途徑：_ 解釋_和編譯 _。24 .掃描器是_詞法分析器,它接受輸入的_源程序,對源程序進行詞法分析 并識別出一個個單詞符號，其輸岀結果是單詞符號，供語法分析器使用。25 .自上而下分析法采用 移進_、歸約、錯誤處理、_接受_等

27、四種操作。26 . 一個 LR 分析器包括兩部分：一個總控程序和一張分析表_。27 .后綴式 abc-/所代表的表達式是 _ a/(b-c) 。28 .局部優化是在 _基本塊范圍內進行的一種優化。29 .詞法分析基于正則_文法進行，即識別的單詞是該類文法的句子。30 .語法分析基于上下文無關文法進行，即識別的是該類文法的句子。語法分析的有效工具是語法樹。31 .分析句型時，應用算符優先分析技術時，每步被直接歸約的是最左素短語,而應用 LR 分析技術時，每步被直接歸約的是 句柄_。32 .語義分析階段所生成的與源程序等價的中間表示形式可以有逆波蘭、三元式表示與四元式表示等。33 .按 Choms

28、ky 分類法，文法按照規則定義的形式進行分類。34 . 一個文法能用有窮多個規則描述無窮的符號串集合語言)是因為文法中存在有 遞歸定義的規則。35 . 一個名字的屬性包括 類型和_作用域 。四、綜合題1.已知文法 G(E)ETT|E + TTTF|T *FFT(E)|i(1) 給出句型(T *F + i)的最右推導；(2) 給出句型(T *F + i)的短語、簡單短語、句柄、素短語、解：(1)最右推導：E -T-F-(E)-(E+ T)-(E+ F)-(E+ i)-(T + i)-(T*F(2)短語：(T*F + i) , T*F+ i , T*F, i簡單短語：T*F,i句柄：T*F素短語：

29、T*F,i最左素短語：T*F01AAABCBCADDCB重新命名，令+ i)01XAAAABAPIACABAC負ABYABVACAB2.構造正規式 1(0|1)*101 相應的 DFA。 解：先構造 NFA :確定化:AB 為 B、AC 為 C、ABY 為 D 得:S-MH|aH -LSo| jK -dML|jL -eHfM-K|bLM判斷 G 是否為 LL(1)文法，如果是，構造 LL(1)分析表。解：各符號的 FIRST 集和 FOLLOW!為：FIRSTFOLLOWS附M3 細H紅L何K仲2 細各產生式 SELEC 集為：SELECTS-MHd,b,e,#,oS-aaH -LSoeH -

30、j#,f,oK -dMLdK -je,#,oL -eHfeM-Kd,e,#,oM- bLMb預測分析表4S-炷-泗；1HM癩夕舐璽.Hk-LSoVM 1-皿匚由于預測分析表中無多重入口，所以可判定文法是LL(1)的。4.對下面的文法 G :E -TEE-+E| 旦T -FTT -T| 工F- PFF- *F| 皂P-(E)|a|bF(1)計算這個文法的每個非終結符的FIRST 集和 FOLLOW 集。(4 分)證明這個方法是 LL(1)的。(4 分)(3)構造它的預測分析表。(2 分)解：(1)計算這個文法的每個非終結符的FIRST 集和 FOLLOW 集FIRST 集合有： FIRST(E)

31、=FIRST(T)=FIRST(F)=FIRST(P)=(,a,bf;FIRST(E)=+,FIRST(T)=FIRST(F)=FIRST(P)=(,a,b;FIRST(T)=FIRST(T)U_=(,a,b,A,;FIRST(F)=FIRST(P)=(,a,b,A;FIRST(F)=FIRST(P)=*,;FIRST(P)=(,a,b,A;FOLLOW 集 合有：FOLLOW(E)=),#;FOLLOW(E)=FOLLOW(E)=),#; FOLLOW(T)=FIRST(E)UFOLLOW(E)=+,),#;/FOLLOW(T)=FOLLOW(T)=FIRST(E)UFOLLOW(E)=+,

32、),#;FOLLOW(F)=FIRST(T)UFOLLOW(T)=(,a,b,A,+,),#;/不包含FOLLOW(F)=FOLLOW(F)=FIRST(T)UFOLLOW(T)=(,a,b,A,+,),#;FOLLOW(P)=FIRST(F)UFOLLOW(F)=*,(,a,b,A,+,),#;/不包含證明這個方法是 LL(1)的。各產生式的 SELECT 集合有：SELECT(E-TE)=FIRST(T)=(,a,b,人;SELECT(E-+E)=+;SELECT(E- 旦)=FOLLOW(E/)=),# SELECT(T-FT)=FIRST(F)=(,a,b,A;SELECT(T-T)=

33、FIRST(T)=(,a,b,人;SELECT(T- 丄)=FOLLOW(T/)=+,),#;SELECT(F-PF)=FIRST(P)=(,a,b,A;SELECT(F-*F)=*;SELECT(F- 丄)=FOLLOW(F)=(,a,b,A,+,),#;SELECT(P-(E)=(SELECT(P-a)=aSELECT(P-b)=bSELECT(P-A)=A可見，相同左部產生式的SELECT 集的交集均為空，所以文法GE是 LL(1)不包含文法。(3)構造它的預測分析表。文法 GE的預測分析表如下：+羋(bAE4TE兮TE屈-+-4 T今FT-FT-FTX講丁F今TTT 弓TTTTTF4PFfTFF-FFy今PF- 今e- -s今- sP5.已知文法 GS為：S-aF|(T)T-