編譯原理模擬試卷和答案

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

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

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 目標(biāo)程序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、一個(gè)上下文無關(guān)文法 G 包括四個(gè)組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號，一個(gè)開始符號，以及一組（ ）。A 句子B 句型C 單詞D 規(guī)則二、【判斷題】(本大題共10小題，每小題2分，共20分)正確的填T，錯(cuò)誤的填F，填在答題卷相應(yīng)題號處。11、計(jì)算機(jī)高級語言翻譯成低級語言只有解釋一種方式。   （ ）12、如果一個(gè)文法存在某個(gè)句子對應(yīng)兩棵或者兩棵以上不同的語法樹，則說這個(gè)文法是二義的。   （ ）13、

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

6、本大題共10小空，每小空2分，共20分）請將答案填寫在答題卷相應(yīng)題號處。21、掃描器的任務(wù)是從（ ）中識別出一個(gè)個(gè)（ ）。22、若源程序是用高級語言編寫的，（ ）是機(jī)器語言程序或匯編程序，則其翻譯程序稱為 （ ）。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。編譯原理模擬試卷一 答案一、【單項(xiàng)選擇題】(本大題共10小題，每小題2分，共20分)題號12345678910答案ACDBBBCCBD二、【判斷題】(本大題共10小題，每小題2分，共20分)題號11121314151617181920答案FTTFTTFFFF三、【填空題】（本大題共10小空，每小空2分，共20分）21、 (

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

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

11、是符合題目要求的，請將正確選項(xiàng)前的字母填在答題卷相應(yīng)題號處。1、通常一個(gè)編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括（ ）A 解釋器B 模擬執(zhí)行器C 表格管理和出錯(cuò)處理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、一個(gè)句型中的最左（ ）稱為該句型的句柄。A 短語B 簡單短語C 素短語D 終結(jié)符號4、設(shè) G 是一個(gè)給定的文法， S 是文法的開始符號，如果 S

12、->x( 其中 xV*), 則稱 x 是文法 G 的一個(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、若一個(gè)文法是遞歸的，則它所產(chǎn)生的語言的句子（ ）。A 是無窮多個(gè)B 是有窮多個(gè)C 是可枚舉的D 個(gè)數(shù)是常量7、把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由（ ）完成的。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) 項(xiàng)目二、【判斷題】(本大題共10小題，每小題2分，共20分)正確的填T，錯(cuò)誤的填F，填在答題卷相應(yīng)題號處。11、“用高級語言書寫的源程序都必須通過編譯，產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行”這種說法。   （ ）12、最左推導(dǎo)常被稱為規(guī)范推導(dǎo)。 （ ）13、一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。 （ ）14、在程序中標(biāo)識符的出現(xiàn)僅為使用性的。   （ ）15、僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無用的。 （ ）16、削減運(yùn)算強(qiáng)度破壞了臨時(shí)變量在一基本塊內(nèi)僅被定義一次的特性。 （ ）17、在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達(dá)式外提

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

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

17、句子(a，a)，a)的規(guī)范歸約過程及每一步的句柄。編譯原理模擬試卷二 答案一、【單項(xiàng)選擇題】(本大題共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、標(biāo)準(zhǔn)答案：S aAb aBcAb aidtcAb aidtcBcAb aidtc cAb aidtccAbaidtccBb aidtcc b aidtccb是句型，也是句子。復(fù)習(xí)范圍或考核目標(biāo)：考核句型和句子，參考“第四章 文法和語言”第2節(jié)。28、標(biāo)準(zhǔn)答案：DFA與NFA的區(qū)別表現(xiàn)為兩個(gè)方面:一是NFA可以若干個(gè)開始狀態(tài)，而DFA僅只一個(gè)開始狀態(tài)。 另一方面，DFA的映象M是從K×到K，而NFA的映象M是從K×到K的子集， 即映象M將產(chǎn)生一個(gè)狀態(tài)集合（可能為空集），而不是單個(gè)狀態(tài)。復(fù)習(xí)范圍或考核目標(biāo)：考核DFA 與 NFA 的區(qū)別，參

19、考“第三章 詞法分析程序”第3節(jié)。29標(biāo)準(zhǔn)答案：三元式：          .(+,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ù)習(xí)范圍或考核目標(biāo)：考核“三元式”、“四元式”，參考教材“第八章語法制導(dǎo)翻譯和中間代碼生成”第3節(jié)。30、標(biāo)準(zhǔn)答案：句型歸約規(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ù)習(xí)范圍或考核目標(biāo)：考核句子的規(guī)范歸約及句柄，參考“第四章 文法和語言”第4、5節(jié)。北京語言大學(xué)網(wǎng)絡(luò)教育學(xué)院編譯原理模擬試卷三注意： 1.試卷保密，考生不得將試卷帶出考場或撕頁，否則成績作廢。請監(jiān)考老師負(fù)責(zé)監(jiān)督。2.請各位考生注意考試紀(jì)律，考試作弊全部成績以零分計(jì)算。3.本試卷滿分100分，答題時(shí)間為90分鐘。4.本試卷分為試題卷和答題卷，所有答案必須答在答題卷上，答在試題卷上不給分。一、【單項(xiàng)選擇題】(本大題共10小題，每小題2分，共20分)在每小題列出的四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的，請將正確選項(xiàng)

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、一個(gè)文法所描述的語言是（ ）。A 唯一的B 不唯一的C 可能唯一，也可能不唯一D 都不對5、（ ）和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的。A 語法分析B 中間代碼生成C 詞法分析D 目標(biāo)代碼生成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，錯(cuò)誤的填F，填在答題卷相應(yīng)題號處。11、由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。 （ ）12、如果一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語法樹，則稱這個(gè)文法不是二義的。（ ）13、中間代碼生成時(shí)所依據(jù)的是詞法規(guī)則。（ ）14、產(chǎn)生式是用于定義詞法成分的一種書寫規(guī)則。（ ）15、逆波蘭法表示的表達(dá)式亦稱前綴式。（ ）16、在 SLR（1）分析法的名稱中，S的含義是簡單的。（ ）17、綜合屬性是用于“自上而下”傳遞信息。（ ）18、符號表中的信息欄中登記了每個(gè)名字的 屬性和特征等有關(guān)信息 ，如類型、種屬、所占單元大小、地址等等。  （ ）19、

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