編譯原理模擬試卷和答案

1、北京語言大學網(wǎng)絡(luò)教育學院編譯原理模擬試卷一注意： 1.試卷保密，考生不得將試卷帶出考場或撕頁，否則成績作廢。請監(jiān)考老師負責監(jiān)督。2.請各位考生注意考試紀律，考試作弊全部成績以零分計算。3.本試卷滿分100分，答題時間為90分鐘。4.本試卷分為試題卷和答題卷，所有答案必須答在答題卷上，答在試題卷上不給分。一、【單項選擇題】(本大題共10小題，每小題2分，共20分)在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在答題卷相應(yīng)題號處。1、一個編譯程序中，包含詞法分析、（ ）、中間代碼生成、代碼優(yōu)化、目標代碼生成等五個部分。A 語法分析B 文法分析C 語言分析D 解釋分析2

2、、詞法分析器用于識別（ ）。A 字符串B 語句C 單詞D 標識符3、語法分析器則可以發(fā)現(xiàn)源程序中的（ ）。A 語義錯誤B 語法和語義錯誤C 錯誤并校正D 語法錯誤4、下面關(guān)于解釋程序的描述正確的是（ ）。 (1) 解釋程序的特點是處理程序時不產(chǎn)生目標代碼。 (2) 解釋程序適用于 COBOL 和 FORTRAN 語言。 (3) 解釋程序是為打開編譯程序技術(shù)的僵局而開發(fā)的。A (1)(2)B (1)C (1)(2)(3)D (2)(3)5、解釋程序處理語言時 , 大多數(shù)采用的是（ ）方法。A 源程序命令被逐個直接解釋執(zhí)行B 先將源程序轉(zhuǎn)化為中間代碼 , 再解釋執(zhí)行C 先將源程序解釋轉(zhuǎn)化為目標程序

3、 , 再執(zhí)行D 以上方法都可以6、編譯過程中 , 語法分析器的任務(wù)就是（ ）。 (1) 分析單詞是怎樣構(gòu)成的 (2)  分析單詞串是如何構(gòu)成語句和說明的 (3) 分析語句和說明是如何構(gòu)成程序的 (4) 分析程序的結(jié)構(gòu)A (2)(3)B (2)(3)(4)C (1)(2)(3)D (1)(2)(3)(4)7、編譯程序是一種（ ）。A 匯編程序B 翻譯程序C 解釋程序D 目標程序8、文法 G 所描述的語言是（ ）的集合。A 文法 G 的字母表 V 中所有符號組成的符號串B 文法 G 的字母表 V 的閉包 V* 中的所有符號串C 由文法的開始符號推出的所有終極符號串D 由文法的開始符號推出

4、的所有符號串9、文法分為四種類型，即0型、1型、2型、3型。其中3型文法是（ ）。A 短語文法B 正規(guī)文法C 上下文有關(guān)文法D 上下文無關(guān)文法10、一個上下文無關(guān)文法 G 包括四個組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，以及一組（ ）。A 句子B 句型C 單詞D 規(guī)則二、【判斷題】(本大題共10小題，每小題2分，共20分)正確的填T，錯誤的填F，填在答題卷相應(yīng)題號處。11、計算機高級語言翻譯成低級語言只有解釋一種方式。   （ ）12、如果一個文法存在某個句子對應(yīng)兩棵或者兩棵以上不同的語法樹，則說這個文法是二義的。   （ ）13、

5、甲機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系統(tǒng)功能完全相同。 （ ）14、正則文法其產(chǎn)生式為 A->a ， A->Bb, A,BVN ， a 、 bVT 。 （ ）15、程序所需的數(shù)據(jù)空間在程序運行前就可確定，稱為靜態(tài)存儲管理技術(shù)。 （ ）16、遞歸下降法允許任一非終結(jié)符是直接左遞歸的。 （ ）17、算符優(yōu)先關(guān)系表不一定存在對應(yīng)的優(yōu)先函數(shù)。  （ ）18、自底而上語法分析方法的主要問題是候選式的選擇。 （ ）19、LR 法是自頂向下語法分析方法。   （ ）20、簡單優(yōu)先文法允許任意兩個產(chǎn)生式具有相同右部。 （ ）三、【填空題】（

6、本大題共10小空，每小空2分，共20分）請將答案填寫在答題卷相應(yīng)題號處。21、掃描器的任務(wù)是從（ ）中識別出一個個（ ）。22、若源程序是用高級語言編寫的，（ ）是機器語言程序或匯編程序，則其翻譯程序稱為 （ ）。23、編譯方式與解釋方式的根本區(qū)別在于（ ）。24、對編譯程序而言，輸入數(shù)據(jù)是（ ），輸出結(jié)果是（ ）。25、產(chǎn)生式是用于定義（ ）的一種書寫規(guī)則。 26、語法分析最常用的兩類方法是（ ）和（ ）分析法。四、【簡答題】（本大題共4小題，每小題10分，共40分）請將答案填寫在答題卷相應(yīng)題號處。27、什么是句子？什么是語言？28、寫一文法，使其語言是偶正整數(shù)的集合,要求： （假定0為正整

7、數(shù)）   (1) 允許0打頭；   (2) 不允許0打頭。29、現(xiàn)有文法GS： SaAbABcA|BBidt|請問aidtcBcAb是句型還是句子，為什么？30、構(gòu)造正規(guī)式相應(yīng)的 NFA : 1(0|1)*101。編譯原理模擬試卷一 答案一、【單項選擇題】(本大題共10小題，每小題2分，共20分)題號12345678910答案ACDBBBCCBD二、【判斷題】(本大題共10小題，每小題2分，共20分)題號11121314151617181920答案FTTFTTFFFF三、【填空題】（本大題共10小空，每小空2分，共20分）21、 (

8、源程序 )；( 單詞符號 )；22、 ( 目標程序 )；( 編譯程序 )；23、 ( 是否生成目標代碼 )；24、 ( 源程序 )；( 目標程序 )；25、 ( 語法成分 )；26、 ( 自上而下 )；( 自下而上 )；四、【簡答題】（本大題共4小題，每題10分，共40分）27、標準答案：(1)設(shè)G是一個給定的文法，S是文法的開始符號，如果S->x(其中xVT*),則稱x是文法的一個句子。 (2)設(shè)GS是給定文法，則由文法G所定義的語言L(G)可描述為： L(G)xS->x,xVT* 。復(fù)習范圍或考核目標：考核句子和語言，參考“第四章 文法和語言”第1節(jié)。28、標準答案：(1)GS

9、=(S,P,D,N,0,1,2,9,P,S) P: S->PD|D P->NP|N D->0|2|4|6|8 N->0|1|2|3|4|5|6|7|8|9 (2)GS=(S,P,R,D,N,Q ,0,1,2,9,P,S) P: S->PD|P0|D P->NR|N R->QR|Q D->2|4|6|8 N->1|2|3|4|5|6|7|8|9 Q->0|1|2|3|4|5|6|7|8|9復(fù)習范圍或考核目標：考核文法，參考“第四章 文法和語言”第2節(jié)。29、標準答案：SaAbaBcAbaidtcAbaidtcBcAb是句型但不是句子。復(fù)

10、習范圍或考核目標：考核句型和句子，參考“第四章 文法和語言”第2節(jié)。30、標準答案：1(0|1)* 101對應(yīng)的NFA為 復(fù)習范圍或考核目標：考核正規(guī)式和NFA，參考“第三章 詞法分析程序”第3節(jié)。北京語言大學網(wǎng)絡(luò)教育學院編譯原理模擬試卷二 注意： 1.試卷保密，考生不得將試卷帶出考場或撕頁，否則成績作廢。請監(jiān)考老師負責監(jiān)督。2.請各位考生注意考試紀律，考試作弊全部成績以零分計算。3.本試卷滿分100分，答題時間為90分鐘。4.本試卷分為試題卷和答題卷，所有答案必須答在答題卷上，答在試題卷上不給分。一、【單項選擇題】(本大題共10小題，每小題2分，共20分)在每小題列出的四個選項中只有一個選項

11、是符合題目要求的，請將正確選項前的字母填在答題卷相應(yīng)題號處。1、通常一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標代碼生成等五個部分，還應(yīng)包括（ ）A 解釋器B 模擬執(zhí)行器C 表格管理和出錯處理D 符號執(zhí)行器2、文法 GN= （ b ， N ， B ， N ， NbbB ， BbN ），該文法所描述的語言是（ ）。A L(GN)=bii0B L(GN)=b2ii0C L(GN)=b2i+1i0D L(GN)=b2i+1i13、一個句型中的最左（ ）稱為該句型的句柄。A 短語B 簡單短語C 素短語D 終結(jié)符號4、設(shè) G 是一個給定的文法， S 是文法的開始符號，如果 S

12、->x( 其中 xV*), 則稱 x 是文法 G 的一個（ ）。 A 候選式B 句型C 單詞D 產(chǎn)生式5、文法 GE ：       ETE T       TFT F       Fa （ E ） 該文法句型 E F (E T) 的簡單短語是下列符號串中的（ ）。 （ E T ）   E T      F    F (E

13、 T)A 和 B 和 C 和 D 6、若一個文法是遞歸的，則它所產(chǎn)生的語言的句子（ ）。A 是無窮多個B 是有窮多個C 是可枚舉的D 個數(shù)是常量7、把匯編語言程序翻譯成機器可執(zhí)行的目標程序的工作是由（ ）完成的。A 編譯器B 匯編器C 解釋器D 預(yù)處理器8、在語法分析處理中， FIRST 集合、 FOLLOW 集合、 SELECT 集合均是（ ）。A 非終極符集B 終極符集C 字母表D 狀態(tài)集9、在自底向上的語法分析方法中，分析的關(guān)鍵是（ ）。A 尋找句柄B 尋找句型C 消除遞歸D 選擇候選式10、在 LR 分析法中，分析棧中存放的狀態(tài)是識別規(guī)范句型（ ）的 DFA 狀態(tài)。A 句柄B 前綴C

14、活前綴D LR(0) 項目二、【判斷題】(本大題共10小題，每小題2分，共20分)正確的填T，錯誤的填F，填在答題卷相應(yīng)題號處。11、“用高級語言書寫的源程序都必須通過編譯，產(chǎn)生目標代碼后才能投入運行”這種說法。   （ ）12、最左推導(dǎo)常被稱為規(guī)范推導(dǎo)。 （ ）13、一個句型的句柄一定是文法某產(chǎn)生式的右部。 （ ）14、在程序中標識符的出現(xiàn)僅為使用性的。   （ ）15、僅考慮一個基本塊，不能確定一個賦值是否真是無用的。 （ ）16、削減運算強度破壞了臨時變量在一基本塊內(nèi)僅被定義一次的特性。 （ ）17、在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達式外提

15、和削減運算強度。  （ ）18、一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。 （ ）19、數(shù)組元素的地址計算與數(shù)組的存儲方式無關(guān)。 （ ）20、編譯程序與具體的機器有關(guān)，與具體的語言無關(guān)。 （ ）三、【填空題】（本大題共10小空，每小空2分，共20分）請將答案填寫在答題卷相應(yīng)題號處。21、后綴式abc-/所代表的表達式是（ ）。 22、遞歸下降法不允許任一非終結(jié)符是直接（ ）遞歸的。23、自頂向下的語法分析方法的基本思想是：從文法的（ ）開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進行（ ），試圖推導(dǎo)出文法的（ ），使之與給定的輸入串（ ）。24、自底向上的語法

16、分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進行（ ），力求歸約到文法的（ ）。25、常用的參數(shù)傳遞方式有（ ），傳值和傳名。 26、在使用高級語言編程時，首先可通過編譯程序發(fā)現(xiàn)源程序的全部（ ）錯誤和部分語義錯誤。四、【簡答題】（本大題共4小題，每小題10分，共40分）請將答案填寫在答題卷相應(yīng)題號處。27、現(xiàn)有文法GS： SaAbABcA|BBidt|請問aidtccb是句型還是句子，為什么？28、簡述 DFA 與 NFA 有何區(qū)別？29、寫出表達式(a+b)/(a-b)-a(a+b*c)的三元式序列及四元式序列。30、已知文法G(S) Sa|(T) TT，S|S 寫出

17、句子(a，a)，a)的規(guī)范歸約過程及每一步的句柄。編譯原理模擬試卷二 答案一、【單項選擇題】(本大題共10小題，每小題2分，共20分)題號12345678910答案CCBBBABBAC二、【判斷題】(本大題共10小題，每小題2分，共20分)題號11121314151617181920答案FFTFTTFFFF三、【填空題】（本大題共10小空，每小空2分，共20分）21、 ( a/(b-c) )；22、 ( 左 )；23、 ( 開始符號 )；( 直接推導(dǎo) )；( 句子 )；( 匹配 )；24、 ( 直接歸約 )；( 開始符號 )；25、 ( 傳地址 )；26、 ( 語法 )；四、【簡答題】（本大題

18、共4小題，每題10分，共40分）27、標準答案：S aAb aBcAb aidtcAb aidtcBcAb aidtc cAb aidtccAbaidtccBb aidtcc b aidtccb是句型，也是句子。復(fù)習范圍或考核目標：考核句型和句子，參考“第四章 文法和語言”第2節(jié)。28、標準答案：DFA與NFA的區(qū)別表現(xiàn)為兩個方面:一是NFA可以若干個開始狀態(tài)，而DFA僅只一個開始狀態(tài)。 另一方面，DFA的映象M是從K×到K，而NFA的映象M是從K×到K的子集， 即映象M將產(chǎn)生一個狀態(tài)集合（可能為空集），而不是單個狀態(tài)。復(fù)習范圍或考核目標：考核DFA 與 NFA 的區(qū)別，參

19、考“第三章 詞法分析程序”第3節(jié)。29標準答案：三元式：          .(+,a,b)           .(-,a,b)           .(/,)           .(*,b,c)        &#

20、160;  .(+,a,)           .(-,) 四元式：          .(+,a,b,T1)           .(-,a,b,T2)           .(/,T1,T2,T3)       &#

21、160;   .(*,b,c,T4)           .(+,a,T4,T5)           .(-,T3,T5,T6)復(fù)習范圍或考核目標：考核“三元式”、“四元式”，參考教材“第八章語法制導(dǎo)翻譯和中間代碼生成”第3節(jié)。30、標準答案：句型歸約規(guī)則句柄 (a，a)，a)Sa a (S，a)，a)TS S (T，a)，a)Sa a (T，S)，a)TT，S T，S (T)，a) S (T) (T) (S，a)

22、 TSS (T，a) Saa (T，S) TT，S T，S (T) S(T)(T) S復(fù)習范圍或考核目標：考核句子的規(guī)范歸約及句柄，參考“第四章 文法和語言”第4、5節(jié)。北京語言大學網(wǎng)絡(luò)教育學院編譯原理模擬試卷三注意： 1.試卷保密，考生不得將試卷帶出考場或撕頁，否則成績作廢。請監(jiān)考老師負責監(jiān)督。2.請各位考生注意考試紀律，考試作弊全部成績以零分計算。3.本試卷滿分100分，答題時間為90分鐘。4.本試卷分為試題卷和答題卷，所有答案必須答在答題卷上，答在試題卷上不給分。一、【單項選擇題】(本大題共10小題，每小題2分，共20分)在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項

23、前的字母填在答題卷相應(yīng)題號處。1、文法 G 產(chǎn)生的（ ）的全體是該文法描述的語言。A 句型B 終結(jié)符集C 非終結(jié)符集D 句子2、若文法 G 定義的語言是無限集，則文法必然是（ ）。A 遞歸的B 前后文無關(guān)的C 二義性的D 無二義性的3、四種形式語言文法中，1型文法又稱為（ ）文法。A 短語結(jié)構(gòu)文法B 前后文無關(guān)文法C 前后文有關(guān)文法D 正規(guī)文法4、一個文法所描述的語言是（ ）。A 唯一的B 不唯一的C 可能唯一，也可能不唯一D 都不對5、（ ）和代碼優(yōu)化部分不是每個編譯程序都必需的。A 語法分析B 中間代碼生成C 詞法分析D 目標代碼生成6、（ ）是兩類程序語言處理程序。A 高級語言程序和低級

24、語言程序B 解釋程序和編譯程序C 編譯程序和操作系統(tǒng)D 系統(tǒng)程序和應(yīng)用程序7、數(shù)組的內(nèi)情向量中肯定不含有數(shù)組的（ ）的信息。A 維數(shù)B 類型C 維上下界D 各維的界差8、（ ）是一種典型的解釋型語言。A BASICB CC FORTRAND PASCAL9、文法分為四種類型，即0型、1型、2型、3型。其中2型文法是（ ）。A 短語文法B 正則文法C 上下文有關(guān)文法D 上下文無關(guān)文法10、與編譯系統(tǒng)相比，解釋系統(tǒng)（ ）。A 比較簡單、可移植性好、執(zhí)行速度快B 比較復(fù)雜、可移植性好、執(zhí)行速度快C 比較簡單、可移植性差、執(zhí)行速度慢D 比較簡單、可移植性好、執(zhí)行速度慢二、【判斷題】(本大題共10小題，

25、每小題2分，共20分)正確的填T，錯誤的填F，填在答題卷相應(yīng)題號處。11、由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。 （ ）12、如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法不是二義的。（ ）13、中間代碼生成時所依據(jù)的是詞法規(guī)則。（ ）14、產(chǎn)生式是用于定義詞法成分的一種書寫規(guī)則。（ ）15、逆波蘭法表示的表達式亦稱前綴式。（ ）16、在 SLR（1）分析法的名稱中，S的含義是簡單的。（ ）17、綜合屬性是用于“自上而下”傳遞信息。（ ）18、符號表中的信息欄中登記了每個名字的 屬性和特征等有關(guān)信息 ，如類型、種屬、所占單元大小、地址等等。  （ ）19、

26、程序語言的語言處理程序是一種應(yīng)用軟件。（ ）20、解釋程序適用于 COBOL 和 FORTRAN 語言。（ ）三、【填空題】（本大題共10小空，每小空2分，共20分）請將答案填寫在答題卷相應(yīng)題號處。21、語法分析器的輸入是（ ），其輸出是（ ）。22、一個句型中的最左簡單短語稱為該句型的（ ）。23、對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為（ ）。24、一個典型的編譯程序中，不僅包括詞法分析、（ ）、（ ）、代碼優(yōu)化、目標代碼生成等五個部分，還應(yīng)包括表格處理和出錯處理。25、從功能上說，程序語言的語句大體可分為（ ）語句和（ ）語句兩大類。 26、循環(huán)優(yōu)化的三種重要技術(shù)包括刪除歸納變量、（ ）和（ ）。四、【簡答題】（本大題共4小題，每小題10分，共40分）請將答案填寫在答題卷相應(yīng)題號處。27、現(xiàn)有文法GS： SaAbABcA|BBidt|請問ab是句型還是句子，為什么？28、寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以0開頭。29、常見的存儲分配策略有幾種？它們都適合于什么性質(zhì)的語言？30、已知文法G(E) ET|ET TF|T *F F(E)|i (1