編譯原理試題匯總+編譯原理期末試題(8套含答案+大題集)

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

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

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

4、D( ) (1)(2)(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( ) 上下文有關(guān)文法 D( ) 上下文無關(guān)文法15 一個上下文

5、無關(guān)文法 G 包括四個組成部分，它們是：一組非終結(jié)符號，一 組終結(jié)符號，一個開始符號，以及一組 _D_。A( ) 句子 B( ) 句型 C( ) 單詞 D( ) 產(chǎn)生式16 通常一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目 標代碼生成等五個部分，還應(yīng)包括_C_。A( ) 模擬執(zhí)行器 B ( ) 解釋器C( ) 表格處理和出錯處理 D( ) 符號執(zhí)行器17 文法 GN= （ b ， N ， B ， N ， Nb bB ， BbN ），該文法所描述 的語言是CA( ) L(GN)=bi i 0 B( ) L(GN)=b2i i 0C( ) L(GN)=b2i+1 i 0D

6、( ) L(GN)=b2i+1 i 118 一個句型中的最左_B_稱為該句型的句柄。A( ) 短語 B( ) 簡單短語 C( ) 素短語 D( ) 終結(jié)符號19設(shè) G 是一個給定的文法，S 是文法的開始符號，如果 S->x( 其中 xV*), 則稱 x 是文法 G 的一個_B_。A( ) 候選式 B ( ) 句型 C( ) 單詞 D( ) 產(chǎn)生式20 文法 GE ：E TE TT FT FF a （ E ）該文法句型 E F (E T) 的簡單短語是下列符號串中的_。 （ E T ） E T F F (E T)A( ) 和 B( ) 和 C( ) 和 D( ) 21 若一個文法是遞歸的，

7、則它所產(chǎn)生的語言的句子_A_。A( ) 是無窮多個 B ( ) 是有窮多個C( ) 是可枚舉的 D( ) 個數(shù)是常量22 詞法分析器用于識別_C_。A( ) 句子 B ( ) 句型 C( ) 單詞 D( ) 產(chǎn)生式23 在語法分析處理中， FIRST 集合、 FOLLOW 集合、 SELECT 集合均是_B_。A . ( ) 非終極符集 B ( ) 終極符集 C( ) 字母表 D . ( ) 狀態(tài)集24 在自底向上的語法分析方法中，分析的關(guān)鍵是_A_。A .( ) 尋找句柄 B .( ) 尋找句型 C .( ) 消除遞歸 D .( ) 選擇候選式25 在 LR 分析法中，分析棧中存放的狀態(tài)是識

8、別規(guī)范句型_C_的 DFA 狀態(tài)。A .( ) 句柄 B .( ) 前綴 C .( ) 活前綴 D .( ) LR(0) 項目26 文法 G 產(chǎn)生的_D_的全體是該文法描述的語言。A( ) 句型 B( ) 終結(jié)符集 C( ) 非終結(jié)符集 D( ) 句子27 若文法 G 定義的語言是無限集，則文法必然是 _A_A( ) 遞歸的 B ( ) 前后文無關(guān)的C ( ) 二義性的 D( ) 無二義性的28 四種形式語言文法中，1 型文法又稱為 _A_文法。A( ) 短語結(jié)構(gòu)文法 B ( ) 前后文無關(guān)文法C( ) 前后文有關(guān)文法 D( ) 正規(guī)文法29 一個文法所描述的語言是_A_。A( ) 唯一的B(

9、 ) 不唯一的C( ) 可能唯一，好可能不唯一 D( ) 都不對30 _B_和代碼優(yōu)化部分不是每個編譯程序都必需的。 A( ) 語法分析 B ( ) 中間代碼生成C( ) 詞法分析 D( ) 目標代碼生成31_B_是兩類程序語言處理程序。A( ) 高級語言程序和低級語言程序 B ( ) 解釋程序和編譯程序C( ) 編譯程序和操作系統(tǒng)D( ) 系統(tǒng)程序和應(yīng)用程序32 數(shù)組的內(nèi)情向量中肯定不含有數(shù)組的_A_的信息。A . ( ) 維數(shù) B( ) 類型 C( ) 維上下界 D( ) 各維的界差33. 一個上下文無關(guān)文法 G 包括四個組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號， 一個開始符號，以及

10、一組 _D_。A( ) 句子 B( ) 句型C( ) 單詞 D( ) 產(chǎn)生式34 文法分為四種類型，即 0 型、1 型、2 型、3 型。其中 2 型文法是_D_。A . ( ) 短語文法 B ( ) 正則文法C( ) 上下文有關(guān)文法 D( ) 上下文無關(guān)文法35一個上下文無關(guān)文法 G 包括四個組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號， 一個開始符號，以及一組 _D_。A( ) 句子 B( ) 句型 C( ) 單詞 D( ) 產(chǎn)生式36_A_是一種典型的解釋型語言。A( ) BASIC B( ) C C( ) FORTRAN D( ) PASCAL 37與編譯系統(tǒng)相比，解釋系統(tǒng)_D_。A(

11、 ) 比較簡單 , 可移植性好 , 執(zhí)行速度快B( ) 比較復雜 , 可移植性好 , 執(zhí)行速度快C ( ) 比較簡單 , 可移植性差 , 執(zhí)行速度慢D( ) 比較簡單 , 可移植性好 , 執(zhí)行速度慢38用高級語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫_B_。A( ) 源程序 B ( ) 目標程序 C( ) 連接程序 D( ) 解釋程序 39編寫一個計算機高級語言的源程序后 , 到正式上機運行之前，一般要經(jīng)過_B_這幾步:(1) 編輯 (2) 編譯 (3) 連接 (4) 運行A . ( ) (1)(2)(3)(4) B( ) (1)(2)(3) C( ) (1)(3) D( ) (1)(4) 40把匯編

12、語言程序翻譯成機器可執(zhí)行的目標程序的工作是由_A_完成的。A( ) 編譯器 B( ) 匯編器C( ) 解釋器 D( ) 預處理器 41詞法分析器的輸出結(jié)果是_C_。A( ) 單詞的種別編碼B( ) 單詞在符號表中的位置C( ) 單詞的種別編碼和自身值 D( ) 單詞自身值42 文法 G ：SxSx|y 所識別的語言是_C_。A( ) xyx B( ) (xyx)* C ( ) xnyxn(n0) D( ) x*yx* 43如果文法 G 是無二義的，則它的任何句子_A_。A( ) 最左推導和最右推導對應(yīng)的語法樹必定相同 B( ) 最左推導和最右推導對應(yīng)的語法樹可能不同 C( ) 最左推導和最右推

13、導必定相同D( ) 可能存在兩個不同的最左推導，但它們對應(yīng)的語法樹相同 44構(gòu)造編譯程序應(yīng)掌握_D_。A( ) 源程序 B ( ) 目標語言C( ) 編譯方法 D( ) 以上三項都是45四元式之間的聯(lián)系是通過_B_實現(xiàn)的。A( ) 指示器 B ( ) 臨時變量C( ) 符號表 D( ) 程序變量46表達式( A B)(CD)的逆波蘭表示為_B_。A . ( ) ABCD B ( ) A BCDC( ) AB CD D( ) A B CD47. 優(yōu)化可生成_D_的目標代碼。A( ) 運行時間較短B( ) 占用存儲空間較小C( ) 運行時間短但占用內(nèi)存空間大 D( ) 運行時間短且占用存儲空間小4

14、8下列_C_優(yōu)化方法不是針對循環(huán)優(yōu)化進行的。A . ( ) 強度削弱 B ( ) 刪除歸納變量C( ) 刪除多余運算 D( ) 代碼外提49編譯程序使用_B_區(qū)別標識符的作用域。 A . ( ) 說明標識符的過程或函數(shù)名B( ) 說明標識符的過程或函數(shù)的靜態(tài)層次C( ) 說明標識符的過程或函數(shù)的動態(tài)層次 D . ( ) 標識符的行號50編譯程序絕大多數(shù)時間花在_D_ 上。 A( ) 出錯處理 B( ) 詞法分析 C( ) 目標代碼生成 D( ) 表格管理51 編譯程序是對_D_。A( ) 匯編程序的翻譯 B ( ) 高級語言程序的解釋執(zhí)行C( ) 機器語言的執(zhí)行 D( ) 高級語言的翻譯52

15、采用自上而下分析，必須_C_。A( ) 消除左遞歸B ( ) 消除右遞歸C( ) 消除回溯D( ) 提取公共左因子53在規(guī)范歸約中，用_B_來刻畫可歸約串。A( ) 直接短語B( ) 句柄C( ) 最左素短語D( ) 素短語54 若 a 為終結(jié)符，則 A -> a 為_B_項目。A( ) 歸約 B ( ) 移進 C( ) 接受 D( ) 待約55間接三元式表示法的優(yōu)點為_A_。A( ) 采用間接碼表，便于優(yōu)化處理 B ( ) 節(jié)省存儲空間，不便于表的修改C( ) 便于優(yōu)化處理，節(jié)省存儲空間 D( ) 節(jié)省存儲空間，不便于優(yōu)化處理56基本塊內(nèi)的優(yōu)化為_B_。A . ( ) 代碼外提，刪除歸

16、納變量 B( ) 刪除多余運算，刪除無用賦值C( ) 強度削弱，代碼外提 D( ) 循環(huán)展開，循環(huán)合并57 在目標代碼生成階段，符號表用_D_。 A( ) 目標代碼生成 B( ) 語義檢查 C( ) 語法檢查 D( ) 地址分配58若項目集 Ik 含有 A -> ，則在狀態(tài) k 時，僅當面臨的輸入符號 aFOLLOW(A)時，才采取“A -> ”動作的一定是_D_。A . ( ) LALR 文法 B( ) LR(0)文法C( ) LR(1)文法 D( ) SLR(1)文法59堆式動態(tài)分配申請和釋放存儲空間遵守_D_原則。A . ( ) 先請先放 B( ) 先請后放C( ) 后請先放

17、 D . ( ) 任意二、判斷1計算機高級語言翻譯成低級語言只有解釋一種方式。(×) 2在編譯中進行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯誤。(×)3甲機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系 統(tǒng)功能完全相同。 ( )4正則文法其產(chǎn)生式為 A->a ， A->Bb, A,BVN ， a 、 bVT 。 (×)5每個文法都能改寫為 LL(1) 文法。 () 6遞歸下降法不允許任一非終極符是直接左遞歸的。 () 7算符優(yōu)先關(guān)系表不一定存在對應(yīng)的優(yōu)先函數(shù)。 (×) 8自底而上語法分析方法的主要問題是候選式的選擇。 (×

18、;)9LR 法是自頂向下語法分析方法。 (×)10簡單優(yōu)先文法允許任意兩個產(chǎn)生式具有相同右部。 (×) 11“ 用高級語言書寫的源程序都必須通過編譯, 產(chǎn)生目標代碼后才能投入運行 ”這種說法。( × )12若一個句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。( × )13一個句型的句柄一定是文法某產(chǎn)生式的右部。 ( )14在程序中標識符的出現(xiàn)僅為使用性的。 ( × )15僅考慮一個基本塊，不能確定一個賦值是否真是無用的。 ( )16削減運算強度破壞了臨時變量在一基本塊內(nèi)僅被定義一次的特性。 ( )17在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有

19、不變表達式外提和削減運算強度。 ( × )18數(shù)組元素的地址計算與數(shù)組的存儲方式有關(guān)。 ( × )19編譯程序與具體的機器有關(guān),與具體的語言無關(guān)。 ( × ) 20遞歸下降分析法是自頂向上分析方法。( )21產(chǎn)生式是用于定義詞法成分 的一種書寫規(guī)則。 ( × )22LR 法是自頂向下語法分析方法。 (×)23在 SLR （ 1 ）分析法的名稱中，S 的含義是簡單的。( ) 24綜合屬性是用于 “ 自上而下 ” 傳遞信息。( × )25符號表中的信息欄中登記了每個名字的 屬性和特征等有關(guān)信息 ，如類型、種屬、所占 單元大小、地址等等。

20、( × )26程序語言的語言處理程序是一種應(yīng)用軟件。 ( × ) 27一個 LL(l)文法一定是無二義的。 ( × ) 28正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。 ( × )29一張轉(zhuǎn)換圖只包含有限個狀態(tài)，其中有一個被認為是初態(tài)，最多只有一個終態(tài)。 ( ) 30目標代碼生成時，應(yīng)考慮如何充分利用計算機的寄存器的問題。 ( × )31逆波蘭法表示的表達式亦稱后綴式 。 ( )32如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是二義的。 ( )33數(shù)組元素的地址計算與數(shù)組的存儲方式有關(guān)。( × )34對于數(shù)據(jù)空間的存

21、貯分配， FORTRAN 采用動態(tài)貯存分配策略。 ( × )35編譯程序是對高級語言程序的解釋執(zhí)行。( × ) 36一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。( × ) 37語法分析時必須先消除文法中的左遞歸 。 ( × )38LR 分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準確地指出出錯地點。 ( ) 39逆波蘭表示法表示表達式時無須使用括號。 ( ) 40靜態(tài)數(shù)組的存儲空間可以在編譯時確定。 ( × ) 41進行代碼優(yōu)化時應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對提高目標代碼的效率將起更大作用。( × ) 42兩個正規(guī)集相等的必要條

22、件是他們對應(yīng)的正規(guī)式等價。( × ) 43一個語義子程序描述了一個文法所對應(yīng)的翻譯工作。 ( × )44r 和 s 分別是正規(guī)式，則有 L(r|s)=L(r)L(s)。( × ) 45確定的的自動機以及不確定的自動機都能正確地識別正集()46分析作為單獨的一遍來處理較好。 ( × )47 LR 分析器的任務(wù)就是產(chǎn)生 LR 分析表。 ( ) 48歸約和規(guī)范推導是互逆的兩個過程。 ( )49同心集的合并有可能產(chǎn)生新的“移進”/ “歸約” 沖突 (×)50.lR 分析技術(shù)無法適用二義文法。 ( × )51樹形表示和四元式不便于優(yōu)化，而三元式

23、和間接三元式則便于優(yōu)化。 ( × )52序中的表達式語句在語義翻譯時不需要回填技術(shù)。 ( ) 三、填空1編譯程序的工作過程一般可以劃分為詞法分析,語法分析,語義分析,中間代碼 生成,代碼優(yōu)化等幾個基本階段,同時還會伴有_表格處理_和 _出錯處理_。 2若源程序是用高級語言編寫的,_目標程序_是機器語言程序或匯編程序, 則其翻譯程序稱為 _編譯程序_ 。 3編譯方式與解釋方式的根本區(qū)別在于_是否生成目標代碼_。 4對編譯程序而言,輸入數(shù)據(jù)是_源程序_, 輸出結(jié)果是_目標程序_。 5產(chǎn)生式是用于定義_語法成分_的一種書寫規(guī)則。 6語法分析最常用的兩類方法是_自上而下_和_自下而上_分析法

24、7設(shè) G 是一個給定的文法，S 是文法的開始符號，如果 S->x( 其中 xVT*), 則稱 x 是文 法的一個_句子_。8遞歸下降法不允許任一非終極符是直接_左_遞歸的。 9自頂向下的語法分析方法的基本思想是：從文法的_開始符號_開始，根據(jù)給定的輸 入串并按照文法的產(chǎn)生式一步一步的向下進行_直接推導_，試圖推導出文法的_句子_，使之與給定的輸入串_匹配_。 10自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地 向上進行_直接歸約_ ，力求歸約到文法的_開始符號_。 11常用的參數(shù)傳遞方式有_傳地址_，傳值和傳名。 12在使用高級語言編程時,首先可通過編譯程序

25、發(fā)現(xiàn)源程序的全部_語法_錯誤和語義的部分錯誤。13一個句型中的最左簡單短語稱為該句型的_句柄_。14對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為 _語義規(guī)則_ 。 15一個典型的編譯程序中，不僅包括_詞法分析_、_語法分析_、_中間代碼生成_、 代碼優(yōu)化、目標代碼生成等五個部分，還應(yīng)包括表格處理和出錯處理。16 從功能上說，程序語言的語句大體可分為_執(zhí)行性_語句和_說明性_語句兩大類。 17 產(chǎn)生式是用于定義_語法范疇_的一種書寫規(guī)則。18語法分析是依據(jù)語言的_語法_規(guī)則進行的，中間代碼產(chǎn)生是依據(jù)語言的_語義_規(guī) 進行的。19語法分析器的輸入是_單詞符號串_，其輸出是_語法單位_。20

26、產(chǎn)生式是用于定義_語法成分_的一種書寫規(guī)則。21逆波蘭式 ab+c+ d*e- 所表達的表達式為_(a+b+c)*d-e_ 。 22語法分析最常用的兩類方法是_自上而下_和_自下而上_分析法。23計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑：_解釋_和_編譯_。24掃描器是_詞法分析器_，它接受輸入的_源程序_，對源程序進行_詞法分析_ 并識別出一個個單詞符號，其輸出結(jié)果是單詞符號，供語法分析器使用。 25自上而下分析法采用_移進_、歸約、錯誤處理、_接受_等四種操作。26一個 LR 分析器包括兩部分：一個總控程序和_一張分析表_。27后綴式 abc-/所代表的表達式是_a/(b-c)_。 2

27、8局部優(yōu)化是在_基本塊_范圍內(nèi)進行的一種優(yōu)化。29詞法分析基于_正則_文法進行，即識別的單詞是該類文法的句子。 30語法分析基于_上下文無關(guān)_文法進行，即識別的是該類文法的句子。語法分析的有效 工具是_語法樹_。 31分析句型時，應(yīng)用算符優(yōu)先分析技術(shù)時，每步被直接歸約的是_最左素短語_，而應(yīng)用 LR 分析技術(shù)時，每步被直接歸約的是_句柄_。 32語義分析階段所生成的與源程序等價的中間表示形式可以有_逆波蘭_、_三元式表示_與_四元式表示_等。33按 Chomsky 分類法，文法按照_規(guī)則定義的形式_進行分類。34一個文法能用有窮多個規(guī)則描述無窮的符號串集合（語言）是因為文法中存在有_遞歸 _定

28、義的規(guī)則。35一個名字的屬性包括_類型_和_作用域_。四、綜合題1. 已知文法 G(E)E T|ETTF|T *FF (E)|i(1)給出句型(T *Fi)的最右推導；(2)給出句型(T *Fi)的短語、簡單短語、句柄、素短語、最左素短語。解： (1) 最右推導：E ->T->F->(E)->(E T)->(E F)->(E i)->(Ti)->(T*Fi)(2) 短語：(T*Fi) ，T*Fi ，T*F，i簡單短語：T*F,i句柄：T*F素短語：T*F,i最左素短語：T*F2. 構(gòu)造正規(guī)式 1(0|1)*101 相應(yīng)的 DFA 。解：先構(gòu)造 N

29、FA ：確定化：重新命名，令 AB 為 B、AC 為 C、ABY 為 D 得：所以，可得 DFA 為：3. 文法：S->MH|aH ->LSo| K ->dML| L ->eHfM->K|bLM判斷 G 是否為 LL(1) 文法，如果是，構(gòu)造 LL(1) 分析表。 解：各符號的 FIRST 集和 FOLLOW集為：各產(chǎn)生式SELECT集為：SELECTS->MHd,b,e,#,oS->aaH ->LSoeH ->#,f,oK ->dMLdK ->e,#,oL ->eHfeM->Kd,e,#,oM-> bLMb預

30、測分析表由于預測分析表中無多重入口，所以可判定文法是 LL(1)的。4. 對下面的文法 G ：E ->TE'E'->+E| T ->FT'T' ->T| F-> PF'F'-> *F'| P->(E)|a|b|(1)計算這個文法的每個非終結(jié)符的 FIRST 集和 FOLLOW 集。 (4 分)(2)證明這個方法是 LL(1) 的。(4 分) (3)構(gòu)造它的預測分析表。(2 分) 解：（1）計算這個文法的每個非終結(jié)符的 FIRST 集和 FOLLOW集。FIRST 集合有：FIRST(E)=FIRS

31、T(T)=FIRST(F)=FIRST(P)=(,a,b,;FIRST(E')=+, FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,;FIRST(T')=FIRST(T)U=(,a,b, ;FIRST(F)=FIRST(P)=(,a,b,;FIRST(F')=FIRST(P)=*, ;FIRST(P)=(,a,b,;FOLLOW 集合有：FOLLOW(E)=),#;FOLLOW(E')=FOLLOW(E)=),#; FOLLOW(T)=FIRST(E')UFOLLOW(E)=+,),#;/不包含F(xiàn)OLLOW(T')=FOLLO

32、W(T)=FIRST(E')UFOLLOW(E)=+,),#; FOLLOW(F)=FIRST(T')UFOLLOW(T)=(,a,b,+,),#;/不包含F(xiàn)OLLOW(F')=FOLLOW(F)=FIRST(T')UFOLLOW(T)=(,a,b,+,),#; FOLLOW(P)=FIRST(F')UFOLLOW(F)=*,(,a,b,+,),#;/不包含(2)證明這個方法是 LL(1)的。各產(chǎn)生式的 SELECT 集合有：SELECT(E->TE')=FIRST(T)=(,a,b,;SELECT(E'->+E)=+;SEL

33、ECT(E'->)=FOLLOW(E/)=),#SELECT(T->FT')=FIRST(F)=(,a,b,;SELECT(T'->T)=FIRST(T)=(,a,b,;SELECT(T'->)=FOLLOW(T/)=+,),#;SELECT(F->PF')=FIRST(P)=(,a,b,;SELECT(F'->*F')=*;SELECT(F'-> )=FOLLOW(F')=(,a,b,+,),#;SELECT(P->(E)=(SELECT(P->a)=aSELECT(

34、P->b)=bSELECT(P->)=可見，相同左部產(chǎn)生式的 SELECT 集的交集均為空，所以文法 GE是 LL(1)文法。(3)構(gòu)造它的預測分析表。 文法 GE的預測分析表如下：5.已知文法 GS 為：S->a|(T)T-> T,S|S(1)計算 GS 的 FIRSTVT 和 LASTVT 。 (2)構(gòu)造 GS 的算符優(yōu)先關(guān)系表并說明 GS 是否未算符優(yōu)先文法。 (3)給出輸入串 (a,a)# 的算符優(yōu)先分析過程。解：（1）各符號的 FIRSTVT 和 LASTVT：（2）算符優(yōu)先關(guān)系表：（3）句子(a,a)#分析過程如下：6.已知文法為：S->a|(T)T-

35、>T,S|S構(gòu)造它的 LR(0)分析表。解：加入非終結(jié)符 S' ，方法的增廣文法為：S'->SS->aS->S->(T)T ->T,ST ->S 下面構(gòu)造它的 LR(0)項目集規(guī)范族為：從上表可看出,不存在移進- 歸約沖突以及歸約歸約沖突，該文法是 LR(0)文法。 從而有下面的 LR(0)分析表：7.已知文法為： A ->aAd|aAb| 判斷該文法是否是 SLR(1) 文法，若是構(gòu)造相應(yīng)分析表，并對輸入串 ab# 給出分析過程。 解：增加一個非終結(jié)符 S/后，產(chǎn)生原文法的增廣文法有： S'->A A ->a

36、Ad|aAb| 下面構(gòu)造它的 LR(0)項目集規(guī)范族為：從上表可看出, 狀態(tài) I0 和 I2 存在移進- 歸約沖突，該文法不是 LR(0)文法。對于 I0 來說有：FOLLOW(A)a=b,d,#a= ，所以在 I0 狀態(tài)下面臨輸入符號為 a 時移進，為 b,d,#時歸約，為其他時報錯。對于 I2 來說有也有與 I0 完全相同的結(jié)論。這就是說，以上的移進 - 歸約沖突是可以解決的，因此該文法是 SLR(1)文法。其 SLR(1)分析表為：對輸入串 ab#給出分析過程為：編譯原理歷年試題及答案 一 （每項選擇2分，共20分）選擇題 1將編譯程序分成若干個“遍”是為了_b_。 a.提高程序的執(zhí)行效

37、率 b.使程序的結(jié)構(gòu)更加清晰 c.利用有限的機器內(nèi)存并提高機器的執(zhí)行效率 d.利用有限的機器內(nèi)存但降低了機器的執(zhí)行效率 2構(gòu)造編譯程序應(yīng)掌握_d_。 a.源程序 b.目標語言 c.編譯方法 d.以上三項都是 3變量應(yīng)當c。 a.持有左值 b.持有右值 c.既持有左值又持有右值 d.既不持有左值也不持有右值 4編譯程序絕大多數(shù)時間花在_d_上。 a.出錯處理 b.詞法分析 c.目標代碼生成 d.管理表格 5詞法分析器的輸出結(jié)果是_c_。 a.單詞的種別編碼 b.單詞在符號表中的位置 c.單詞的種別編碼和自身值 d.單詞自身值 6正規(guī)式MI和M2等價是指_c_。 a. MI和M2的狀態(tài)數(shù)相等 b.

38、Ml和M2的有向弧條數(shù)相等。 C.M1和M2所識別的語言集相等 d. Ml和M2狀態(tài)數(shù)和有向弧條數(shù)相等 7中間代碼生成時所依據(jù)的是c。 a語法規(guī)則 b詞法規(guī)則 c語義規(guī)則 d等價變換規(guī)則 8后綴式ab+cd+/可用表達式_b_來表示。 a a+b/c+d b (a+b)/(c+d) c a+b/(c+d) d a+b+c/d 9程序所需的數(shù)據(jù)空間在程序運行前就可確定，稱為_c_管理技術(shù)。 a.動態(tài)存儲 b.棧式存儲 c.靜態(tài)存儲 d.堆式存儲 10.堆式動態(tài)分配申請和釋放存儲空間遵守_d_原則。 a.先請先放 b.先請后放 c.后請先放 d.任意 二（每小題10分，共80分）簡答題 1.畫出編

39、譯程序的總體結(jié)構(gòu)圖，簡述各部分的主要功能。 2. 已知文法GE: EET+|T TTF* | F FF | a 試證：FF*是文法的句型，指出該句型的短語、簡單短語和句柄. 3為正規(guī)式(a|b) *a(a|b)構(gòu)造一個確定的有限自動機。 4 設(shè)文法G(S)： S(L)|a S|a LL，S|S (1) 消除左遞歸和回溯； (2) 計算每個非終結(jié)符的FIRST和FOLLOW； (3) 構(gòu)造預測分析表。 5 已知文法 A->aAd| aAb| 判斷該文法是否SLR（1）文法，若是構(gòu)造相應(yīng)分析表，并對輸入串a(chǎn)b#給出分析過程。 6 構(gòu)造算符文法GH的算符優(yōu)先關(guān)系（含）。 GH：HH;M|M M

40、d|aHb 7已構(gòu)造出文法G（S） （1）S BB （2）B aB （3）B b 1）。給出DFA圖 2）.給出LR分析表 3）假定輸入串為abaab，請給出LR分析過程（即狀態(tài)，符號，輸入串的變化過程）。 8 將下面的語句翻譯成四元式序列： while A<CB<D do if A=1 then C:=C+l else while A D do A:=A+2； 9 對下面的流圖， (1)求出流圖中各結(jié)點N的必經(jīng)結(jié)點集D(n)， (2)求出流圖中的回邊， (3)求出流圖中的循環(huán)。 參 考 答 案 一單項選擇題 1. 將編譯程序分成若干個“遍”是為了使編譯程序的結(jié)構(gòu)更加清晰，故選b。

41、 2. .構(gòu)造編譯程序應(yīng)掌握源程序、目標語言及編譯方法等三方面的知識，故選d。 3. 對編譯而言，變量既持有左值又持有右值，故選c。 4. 編譯程序打交道最多的就是各種表格，因此選d。 5. 詞法分析器輸出的結(jié)果是單詞的種別編碼和自身值，選C。 6. 正規(guī)式M1和M2所識別的語言集相等，故選C。 7. 選c。 8. 選b。 9. 選C 10. 堆式動態(tài)分配申請和釋放存儲空間不一定遵守先請后放和后請先放的原則，故選d 二簡答題 1 【解答】 編譯程序的總體結(jié)構(gòu)圖如圖1.2所示。 詞法分析器：輸入源程序，進行詞法分析，輸出單詞符號。 語法分析器：在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則（文法規(guī)則）把

42、單詞符號串分 解成各類語法單位，并判斷輸入串是否構(gòu)成語法上正確的“程序”。 中間代碼生成器：按照語義規(guī)則把語法分析器歸約（或推導）出的語法單位翻譯成一定 形式的中間代碼，比如說四元式。 優(yōu)化：對中間代碼進行優(yōu)化處理。 目標代碼生成器：把中間代碼翻譯成目標語言程序。 表格管理模塊保存一系列的表格，登記源程序的各類信息和編譯各階段的進展情況。編 譯程序各階段所產(chǎn)生的中間結(jié)果都記錄在表格中，所需信息多數(shù)都需從表格中獲取，整個編 譯過程都在不斷地和表格打交道。 出錯處理程序?qū)Τ霈F(xiàn)在源程序中的錯誤進行處理。此外，編譯的各階段都可能出現(xiàn)錯誤， 出錯處理程序?qū)Πl(fā)現(xiàn)的錯誤都及時進行處理。 2 【解答】 該句型

43、對應(yīng)的語法樹如下：該句型相對于E的短語有FF*；相對于T的短語有FF*,F;相對于F的短語有F;F;簡單短語有F;F;句柄為F. 3 【解答】 最簡DFA如圖2.66所示。 4 【解答】 (1) S(L)|aS SS| LSL LSL| 評分細則：消除左遞歸2分，提公共因子2分。 (2) FIRST和FOLLOW FIRST)S)(，a FOLLOW(S)#，) FIRST(S)，a, FOLLOW(S)#，) FIRST(L)(，a FOLLOW(L) ) FIRST(L)， FOLLOW(L ) 5 【解答】 (1)拓廣文法 (0)S->A (1) A->aAd (2)A-&g

44、t; aAb (3)A-> (2)構(gòu)造識別活前綴的DFA FOLLOW(A)=d,b,# 對于狀態(tài)I0：FOLLOW(A)a= 對于狀態(tài)I1：FOLLOW(A)a= 因為，在DFA中無沖突的現(xiàn)象，所以該文法是SLR(1)文法。 (3)SLR(1)分析表 狀態(tài) ACTION GOTO a B d # A 0 S2 r3 r3 r3 1 1 acc 2 S2 r3 r3 r3 3 3 S5 S4 4 r1 r1 r1 5 r2 r2 r2 (4)串a(chǎn)b#的分析過程 步驟 狀態(tài)棧 符號棧 當前字符 剩余字符串 動作 1 0 # a b# 移進 2 02 #a b # 歸約A-> 3 02

45、3 #aA b # 移進 4 0235 #aAb # 歸約A-> aAb 5 01 #A # 接受 6 【解答】 由Md和Ma得：FIRSTVT(M)=d,a； 由H-H;得：FIRSTVT(H)=； 由HM得：FIRSTVT(M) cFIRSTVT(H)，即FIRSTVT(H)=;,d,a 由Md和Mb得：LASTVT(M)=d,b； 由H-，；m得：LASTVT(H)=； 由HM得：LASTVT（M）cLASTVT(H），即LASTVT(H)=;,d,b 對文法開始符H,有#H#存在，即有=，#<FIRSTVT(H)，LASTVT(H)>#,也即；，#<d. #&l

46、t;a,；，d>#, b>#。 對形如Pab，或PaQb，有a=b，由Ma|b得：a=b； 對形如PaR，而bFIRSTVT(R)，有a<b，對形如PRb，而aLASTVT(R) 有a>b。 由H；M得：；<FIRSTVT(M)，即：<d，：<a 由MaH得：a<FIRSTVT(H)，即：a；，a<d，aa 由HH；.得：LASTVT(H)>，即：；，d>；，b； 由MHb得：LASTVT(H)>b，即：；b，d>b，bb 由此得到算符優(yōu)先關(guān)系表，見表3.5。 7 【解答】 （1）LR分析表如下： （2）分析表 狀態(tài)

47、 ACTION GOTO a b # S B 0 s3 s4 1 2 1 acc 2 S3 S4 5 3 s3 s4 6 4 r3 r3 5 R1 R1 r1 6 R2 R2 R2 (3) 句子abaab的分析過程 表:句子abaab的分析過程 步驟 狀態(tài) 符號棧 輸入串 所得產(chǎn)生式 0 #0 # abaad# 1 #03 #a baad# 2 #034 #ab aab# Bb 3 #036 #aB aab# BaB 4 #02 #B aab# 5 #023 #Ba ab# 6 #0233 #Baa b# 7 #02334 #Baab # 8 #02336 #BaaB # 9 #0236 #B

48、aB ad# 10 #025 #BB ad# 11 #01 #S d# 12 # # d# 13 識別成功 8 【解答】 該語句的四元式序列如下（其中E1、E2和E3分別對應(yīng)：A<CB<D, A=1和AD并且關(guān)系運算符優(yōu)先級高）： 100 (j<,A,C,102) 101(j,_,_,113） /*E1為F*/ 102 (j<,B,D,104) /*El為T*/ 103 (j,_,_,113) /*El為F*/ 104 (j=,A,1,106) /*Ez為T*/ 105 (j,_,_,108） /*EZ為F*/ 106 (,C,1,C) /*C:=C+1*/ 107 (

49、j,_,_,112) /*跳過else后的語句*/ 108 (j,A,D,110) /*E3為T*/ 109 (j,_,_,112) /*E3為F*/ 110 (,A,2,A) /*A:=A+2*/ 111 (j,_,_,108) /*轉(zhuǎn)回內(nèi)層while語句開始處*/ 112(j,_,_,100) /*轉(zhuǎn)回外層while語句開始處*/ 113 9 【解答】 (1)流圖中各結(jié)點N的必經(jīng)結(jié)點集D(n)， D(l)1，D(2)1,2，D(3)1,2,3，D(4)=1,2,3,4，D(5)1,2,5， D(6)1,2,5,6 (2)求出流圖中的回邊， 5->2，4->3 (3)求出流圖中的

50、循環(huán): 回邊5->2對應(yīng)的循環(huán)：2、5、3、4； 回邊4->3對應(yīng)的循環(huán)：3、4 編譯原理模擬試題一 一、是非題（請在括號內(nèi)，正確的劃，錯誤的劃×）（每個2分，共20分） 1計算機高級語言翻譯成低級語言只有解釋一種方式。(×) 2在編譯中進行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯誤。(×) 3甲機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系統(tǒng)功能完全相同。 ( ) 4正則文法其產(chǎn)生式為 A->a ， A->Bb, A,BVN ， a 、 bVT 。 (×) 5每個文法都能改寫為 LL(1) 文法。 () 6遞歸下降

51、法允許任一非終極符是直接左遞歸的。 () 7算符優(yōu)先關(guān)系表不一定存在對應(yīng)的優(yōu)先函數(shù)。 (×) 8自底而上語法分析方法的主要問題是候選式的選擇。 (×) 9LR 法是自頂向下語法分析方法。 (×) 10簡單優(yōu)先文法允許任意兩個產(chǎn)生式具有相同右部。 (×) 二、選擇題(請在前括號內(nèi)選擇最確切的一項作為答案劃一個勾，多劃按錯論)(每個4分，共40分) 1 一個編譯程序中，不僅包含詞法分析，_，中間代碼生成，代碼優(yōu)化，目標代碼生成等五個部分。 A( ) 語法分析 B( )文法分析 C( )語言分析 D( )解釋分析 2 詞法分析器用于識別_。 A( ) 字符串B( )語句C( )單詞 D( )標識符 3 語法分析器則可以發(fā)現(xiàn)源程序中的_。 A( ) 語義