《編譯原理》模擬期末試題匯總_6套_含答案

1、編譯原理模擬試題一一、是非題（請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃，錯(cuò)誤的劃）（每個(gè)2分，共20分）1計(jì)算機(jī)高級(jí)語言翻譯成低級(jí)語言只有解釋一種方式。()2在編譯中進(jìn)行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤。()3甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。 ( )4正則文法其產(chǎn)生式為 A-a ， A-Bb, A,BVN ， a 、 bVT 。 ()5每個(gè)文法都能改寫為 LL(1) 文法。 ()6遞歸下降法允許任一非終極符是直接左遞歸的。 ()7算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。 ()8自底而上語法分析方法的主要問題是候選式的選擇。 ()9LR 法是自頂向下語法分析方

2、法。 ()10簡(jiǎn)單優(yōu)先文法允許任意兩個(gè)產(chǎn)生式具有相同右部。 ()二、選擇題(請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾，多劃按錯(cuò)論)(每個(gè)4分，共40分)1 一個(gè)編譯程序中，不僅包含詞法分析，_，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分。A( ) 語法分析 B( )文法分析C( )語言分析D( )解釋分析2 詞法分析器用于識(shí)別_。 A( ) 字符串 B( )語句C( )單詞 D( )標(biāo)識(shí)符3 語法分析器則可以發(fā)現(xiàn)源程序中的_。A( ) 語義錯(cuò)誤 B( ) 語法和語義錯(cuò)誤C( ) 錯(cuò)誤并校正 D( ) 語法錯(cuò)誤4 下面關(guān)于解釋程序的描述正確的是_。 (1) 解釋程序的特點(diǎn)是處理程序時(shí)不產(chǎn)

3、生目標(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)程序 , 再執(zhí)行 D( ) 以上方法都可以6 編譯過程中 , 語法分析器的任務(wù)就是_。 (1) 分析單詞是怎樣構(gòu)成的 (2) 分析單詞串是如何構(gòu)成語句和說明的 (3) 分析語句和說明是如何構(gòu)成程序的 (4)

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 中所有符號(hào)組成的符號(hào)串B( ) 文法 G 的字母表 V 的閉包 V* 中的所有符號(hào)串C( ) 由文法的開始符號(hào)推出的所有終極符串D. ( ) 由文法的開始符號(hào)推出的所有符號(hào)串9 文法分為四種類型，即0型、1型、2型、3型。其中3型文法是_。A. ( ) 短語文法 B( ) 正則文法

5、C( ) 上下文有關(guān)文法 D( ) 上下文無關(guān)文法10 一個(gè)上下文無關(guān)文法 G 包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組 _。A( ) 句子 B( ) 句型C( ) 單詞 D( ) 產(chǎn)生式三、填空題(每空1分，共10分)1編譯程序的工作過程一般可以劃分為詞法分析,語法分析,語義分析,中間代碼生成,代碼優(yōu)化等幾個(gè)基本階段,同時(shí)還會(huì)伴有_表格處理_和 _出錯(cuò)處理_。 2若源程序是用高級(jí)語言編寫的,_目標(biāo)程序_是機(jī)器語言程序或匯編程序,則其翻譯程序稱為 _編譯程序_ 。3編譯方式與解釋方式的根本區(qū)別在于_是否生成目標(biāo)代碼_。4對(duì)編譯程序而言,輸入數(shù)據(jù)是_源程序_

6、, 輸出結(jié)果是_目標(biāo)程序_。5產(chǎn)生式是用于定義_語法成分_的一種書寫規(guī)則。 6語法分析最常用的兩類方法是_自上而下_和_自下而上_分析法。 四、簡(jiǎn)答題（20分）1. 什么是句子？ 什么是語言 ? 答：(1)設(shè)G是一個(gè)給定的文法，S是文法的開始符號(hào)，如果S x(其中xVT*),則稱x是文法的一個(gè)句子。 (2)設(shè)GS是給定文法，則由文法G所定義的語言L(G)可描述為： L(G)xS x,xVT* 。參考答案：(每個(gè)2分，共4分)答：(1)設(shè)G是一個(gè)給定的文法，S是文法的開始符號(hào)，如果S x(其中xVT*),則稱x是文法的一個(gè)句子。 (2)設(shè)GS是給定文法，則由文法G所定義的語言L(G)可描述為：

7、L(G)xS x,xVT* 。 2. 寫一文法，使其語言是偶正整數(shù)的集合,要求： (1)允許0打頭；(2) 不允許0打頭。解：(1)GS=(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 3. 已知文法 GE 為： ET|E+T|E-T TF|T*F|T/F F （ E ） |i

8、 該文法的開始符號(hào)（識(shí)別符號(hào)）是什么？ 請(qǐng)給出該文法的終結(jié)符號(hào)集合 VT 和非終結(jié)符號(hào)集合 VN 。 找出句型 T+T*F+i 的所有短語、簡(jiǎn)單短語和句柄。解： 該文法的開始符號(hào)（識(shí)別符號(hào)）是E。 該文法的終結(jié)符號(hào)集合VT=+、-、*、/、（、）、i。 非終結(jié)符號(hào)集合VN=E、T、F。 句型T+T*F+I的短語為i、T*F、第一個(gè)T、T+T*F+i; 簡(jiǎn)單短語為i、T*F、第一個(gè)T;句柄為第一個(gè)T。4. 構(gòu)造正規(guī)式相應(yīng)的 NFA : 1(0|1)*101 解1(0|1)*101對(duì)應(yīng)的NFA為 5. 寫出表達(dá)式(ab*c)/(ab)d的逆波蘭表示和三元式序列。逆波蘭表示： abc*ab/d 三元

9、式序列： (*，b，c) (，a，) (，a，b) (/，) (，d)五.計(jì)算題（10分）構(gòu)造下述文法 GS 的自動(dòng)機(jī)： S-A0 A-A0|S1|0 該自動(dòng)機(jī)是確定的嗎？若不確定，則對(duì)它確定化。解：由于該文法的產(chǎn)生式S-A0，A-A0|S1中沒有字符集VT的輸入，所以不是確定的自動(dòng)機(jī)。 要將其他確定化，必須先用代入法得到它對(duì)應(yīng)的正規(guī)式。把S?A0代入產(chǎn)生式A?S1有：A=A0|A01|0=A(0|01)|0=0(0|01)*。 代入S-A0有該文法的正規(guī)式：0(0|01)*0，所以，改寫該文法為確定的自動(dòng)機(jī)為： 由于狀態(tài)A有3次輸入0的重復(fù)輸入，所以上圖只是NFA，下面將它確定化： 下表由子

10、集法將NFA轉(zhuǎn)換為DFA: 由上表可知DFA為：編譯原理模擬試題二一、是非題（請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃，錯(cuò)誤的劃）（每個(gè)2分，共20分）1“ 用高級(jí)語言書寫的源程序都必須通過編譯,產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行 ”這種說法。( )2若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。( )3一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。 ()4在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。 ( )5僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無用的。 ( )6削減運(yùn)算強(qiáng)度破壞了臨時(shí)變量在一基本塊內(nèi)僅被定義一次的特性。 ( )7在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達(dá)式外提和削減運(yùn)算強(qiáng)度。 ( )8算符優(yōu)先關(guān)系

11、表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。 ()9數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。 ()10編譯程序與具體的機(jī)器有關(guān),與具體的語言無關(guān)。 ( )二、選擇題(請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾，多劃按錯(cuò)論)(每個(gè)4分，共40分)1 通常一個(gè)編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括_。A( ) 模擬執(zhí)行器B( ) 解釋器 C( ) 表格處理和出錯(cuò)處理 D( ) 符號(hào)執(zhí)行器2 文法 GN= （ b ， N ， B ， N ， NbbB ， BbN ），該文法所描述的語言是 A( ) L(GN)=bii0 B( ) L(GN)=b2ii0 C

12、( ) L(GN)=b2i+1i0 D( ) L(GN)=b2i+1i13 一個(gè)句型中的最左_稱為該句型的句柄。A( ) 短語 B( ) 簡(jiǎn)單短語 C( ) 素短語 D( ) 終結(jié)符號(hào) 4 設(shè) G 是一個(gè)給定的文法， S 是文法的開始符號(hào)，如果 S-x( 其中 xV*), 則稱 x 是文法 G 的一個(gè)_。A( ) 候選式 B( ) 句型 C( ) 單詞 D( ) 產(chǎn)生式 5 文法 GE ： ETE T TFT F Fa （ E ） 該文法句型 E F (E T) 的簡(jiǎn)單短語是下列符號(hào)串中的_。 （ E T ） E T F F (E T) A( ) 和 B( ) 和 C( ) 和 D( ) 6

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

14、型_的 DFA 狀態(tài)。 A.( )句柄 B.( ) 前綴 C.( )活前綴 D.( ) LR(0) 項(xiàng)目 三、填空題(每空1分，共10分)1設(shè)G是一個(gè)給定的文法，S是文法的開始符號(hào)，如果S-x( 其中 xVT*), 則稱 x是文法的一個(gè)_句子_。 2遞歸下降法不允許任一非終極符是直接_左_遞歸的。3自頂向下的語法分析方法的基本思想是：從文法的_開始符號(hào)_開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行_直接推導(dǎo)_，試圖推導(dǎo)出文法的_句子_，使之與給定的輸入串_匹配_。 4自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進(jìn)行_直接歸約_ ，力求歸約到文法

15、的_開始符號(hào)_。 5常用的參數(shù)傳遞方式有_傳地址_，傳值和傳名。 6在使用高級(jí)語言編程時(shí),首先可通過編譯程序發(fā)現(xiàn)源程序的全部_語法_錯(cuò)誤和語義部分錯(cuò)誤。四、簡(jiǎn)答題（20分）1. 已知文法 GS 為： SdAB AaA|a BBb| GS 產(chǎn)生的語言是什么？ 答：GS產(chǎn)生的語言是L(GS)=danbmn1,m0。2. 簡(jiǎn)述 DFA 與 NFA 有何區(qū)別 ? 答：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)。3. 構(gòu)造正規(guī)

16、式相應(yīng)的 DFA : 1(1010 * | 1(010) * 1) * 0。解：1(1010 * | 1(010) * 1) * 0對(duì)應(yīng)的NFA為：4. 已知文法G(S) Sa|(T) TT，S|S 寫出句子(a，a)，a)的規(guī)范歸約過程及每一步的句柄。解：句型歸約規(guī)則句柄 (a，a)，a)Saa (S，a)，a)TSS (T，a)，a)Saa (T，S)，a)TT，S T，S (S)，a) TSS (T)，a) SS(T) (T) (S，a) TSS (T，a) Saa (T，S) TT，S T，S (T) S(T)(T) S5. 何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級(jí)優(yōu)化？1)優(yōu)化：對(duì)程

17、序進(jìn)行各種等價(jià)變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代碼。 (2) 三種級(jí)別：局部?jī)?yōu)化、循環(huán)優(yōu)化、全局優(yōu)化。五.計(jì)算題（10分） 對(duì)下面的文法 G ： E-TE E-+E| T-FT T -T| F- PF F- *F| P-(E)|a|b| (1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的 FIRST 集和 FOLLOW 集。 (4分) (2) 證明這個(gè)方法是 LL(1) 的。(4分) (3) 構(gòu)造它的預(yù)測(cè)分析表。(2分) 解：（1）計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST集和FOLLOW集。 FIRST集合有： FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,

18、; FIRST(E)=+, FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,; FIRST(T)=FIRST(T)=(,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)FOLLOW(E)=+,),#;/不包含 FOLLOW(T)=FOLLOW(T)=FIRST(E)FOLLOW(E)=+,),#; FOLLOW(F)=FIRST(T)FOLLOW(

19、T)=(,a,b,+,),#;/不包含 FOLLOW(F)=FOLLOW(F)=FIRST(T)FOLLOW(T)=(,a,b,+,),#; FOLLOW(P)=FIRST(F)FOLLOW(F)=*,(,a,b,+,),#;/不包含 (2)證明這個(gè)方法是LL(1)的。 各產(chǎn)生式的SELECT集合有： SELECT(E-TE)=FIRST(T)=(,a,b,; SELECT(E-+E)=+; SELECT(E-)=FOLLOW(E/)=),# SELECT(T-FT)=FIRST(F)=(,a,b,; SELECT(T-T)=FIRST(T)=(,a,b,; SELECT(T-)=FOLLOW

20、(T/)=+,),#; SELECT(F-PF)=FIRST(P)=(,a,b,; SELECT(F-*F)=*; SELECT(F-)=FOLLOW(F)=(,a,b,+,),#; SELECT(P-(E)=( SELECT(P-a)=a SELECT(P-b)=b SELECT(P-)= 可見，相同左部產(chǎn)生式的SELECT集的交集均為空，所以文法GE是LL(1)文法。 (3)構(gòu)造它的預(yù)測(cè)分析表。 文法GE的預(yù)測(cè)分析表如下： 編譯原理模擬試題三一、是非題（請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃，錯(cuò)誤的劃）（每個(gè)2分，共20分）1對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動(dòng)態(tài)貯存分配策略。()2甲機(jī)上的某編譯程

21、序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。( )3遞歸下降分析法是自頂向上分析方法。( )4產(chǎn)生式是用于定義詞法成分 的一種書寫規(guī)則。 ()5LR 法是自頂向下語法分析方法。 ( )6在 SLR （ 1 ）分析法的名稱中，S的含義是簡(jiǎn)單的。()7綜合屬性是用于 “ 自上而下 ” 傳遞信息。( )8符號(hào)表中的信息欄中登記了每個(gè)名字的 屬性和特征等有關(guān)信息 ，如類型、種屬、所占單元大小、地址等等。 ()9程序語言的語言處理程序是一種應(yīng)用軟件。 ()10解釋程序適用于 COBOL 和 FORTRAN 語言。 ()二、選擇題(請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾，多劃按

22、錯(cuò)論)(每個(gè)4分，共40分)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( ) 都不對(duì)5 _和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的。A(

23、) 語法分析B( ) 中間代碼生成 C( ) 詞法分析 D( ) 目標(biāo)代碼生成 6_是兩類程序語言處理程序。 A( ) 高級(jí)語言程序和低級(jí)語言程序 B( ) 解釋程序和編譯程序 C( ) 編譯程序和操作系統(tǒng) D( ) 系統(tǒng)程序和應(yīng)用程序 7 數(shù)組的內(nèi)情向量中肯定不含有數(shù)組的_的信息。A. ( ) 維數(shù) B( ) 類型 C( ) 維上下界 D( ) 各維的界差 8. 一個(gè)上下文無關(guān)文法 G 包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組 _。 A( ) 句子 B( ) 句型C( ) 單詞 D( ) 產(chǎn)生式9 文法分為四種類型，即0型、1型、2型、3型。其中2型文法

24、是_。A. ( ) 短語文法 B( ) 正則文法 C( ) 上下文有關(guān)文法D( ) 上下文無關(guān)文法10文法 G 所描述的語言是_的集合。 A. ( ) 文法 G 的字母表 V 中所有符號(hào)組成的符號(hào)串B( ) 文法 G 的字母表 V 的閉包 V* 中的所有符號(hào)串C( ) 由文法的開始符號(hào)推出的所有終極符串D. ( ) 由文法的開始符號(hào)推出的所有符號(hào)串三、填空題(每空1分，共10分)1一個(gè)句型中的最左簡(jiǎn)單短語稱為該句型的_句柄_。 2對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱為 _語義規(guī)則_ 。3一個(gè)典型的編譯程序中，不僅包括_詞法分析_、_語法分析_、_中間代碼生成_、代碼優(yōu)化、目標(biāo)代碼

25、生成等五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。4 從功能上說，程序語言的語句大體可分為_執(zhí)行性_語句和_說明性_語句兩大類。5 掃描器的任務(wù)是從_源程序_中識(shí)別出一個(gè)個(gè)_單詞符號(hào)_。 6 產(chǎn)生式是用于定義_語法范疇_的一種書寫規(guī)則。 四、簡(jiǎn)答題（20分）1. 寫一個(gè)文法，使其語言是奇數(shù)集，且每個(gè)奇數(shù)不以0開頭。解：文法G(N)： NAB|B AAC|D B1|3|5|7|9 DB|2|4|6|8 C0|D2. 設(shè)文法G(S)： S(L)|a S|a LL，S|S (1) 消除左遞歸和回溯；(2) 計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW。解：(1) S(L)|aS SS| LSL LSL| (

26、2) FIRST)S)(，aFOLLOW(S)#，) FIRST(S)，a,FOLLOW(S)#，) FIRST(L)(，aFOLLOW(L) ) FIRST(L)，F(xiàn)OLLOW(L )3. 已知文法G(E) ET|ET TF|T *F F(E)|i (1)給出句型(T *Fi)的最右推導(dǎo)； (2)給出句型(T *Fi)的短語、素短語。解：(1) 最右推導(dǎo)： E-T-F-(E)-(ET)-(EF)-(Ei) -(Ti)-(T*Fi) (2) 短語：(T*Fi)，T*Fi，T*F，i 素短語：T*F,i 4. Whilea0 b0do Begin X：X1； if a0 then a：a1 el

27、se b：b1 End； 翻譯成四元式序列。解： (1) (j，a，0，5) (2) (j，3) (3) (j，b，0，5) (4) (j，15) (5) (，1，T1) (6) (：，T1，) (7) (j，a，0，9) (8) (j，12) (9) (，a，1，T2) (10) (：，T2，a) (11) (j，1) (12) (，b，1， T3) (13) (：，T3，b) (14) (j，1) (15)五.計(jì)算題（10分）已知 NFA= （ x,y,z,0,1,M,x,z ），其中：M(x,0)=z,M(y,0)=x,y,M(z,0)=x,z,M(x,1)=x, M(y,1)= ,M(

28、z,1)=y, 構(gòu)造相應(yīng)的DFA并最小化。 解：根據(jù)題意有NFA圖: 下表由子集法將NFA轉(zhuǎn)換為DFA： 下面將該DFA最小化： (1) 首先將它的狀態(tài)集分成兩個(gè)子集：P1=A,D,E,P2=B,C,F (2) 區(qū)分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等價(jià)。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等價(jià)（見下步），從而B與C，F(xiàn)可以區(qū)分。有P21=C,F,P22=B。 (3) 區(qū)分P1:由于A，E輸入0到終態(tài)，而D輸入0不到終態(tài)，所以D與A，E可以區(qū)分，有P11=A,E,P12=D。 (4) 由于F

29、(A,0)=B,F(E,0)=F,而B，F(xiàn)不等價(jià)，所以A，E可以區(qū)分。 (5) 綜上所述，DFA可以區(qū)分為P=A，B，D，E，C，F(xiàn)。所以最小化的DFA如下： 編譯原理模擬試題四一、是非題（請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃，錯(cuò)誤的劃）（每個(gè)2分，共20分）1一個(gè) LL(l)文法一定是無二義的。 ( )2正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。 ( )3一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。 ()4目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問題。 ( )5逆波蘭法表示的表達(dá)式亦稱前綴式 。 ( )6如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是二

30、義的。 ( )7LR 法是自頂向下語法分析方法。 ( )8數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。( )9算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。 ()10對(duì)于數(shù)據(jù)空間的存貯分配， FORTRAN 采用動(dòng)態(tài)貯存分配策略。 ()二、選擇題(請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾，多劃按錯(cuò)論)(每個(gè)4分，共40分)1詞法分析器用于識(shí)別_。 A( ) 字符串 B( )語句 C( )單詞 D( )標(biāo)識(shí)符2文法分為四種類型，即0型、1型、2型、3型。其中0型文法是_。A. ( ) 短語文法 B( ) 正則文法 C( ) 上下文有關(guān)文法 D( ) 上下文無關(guān)文法3一個(gè)上下文無關(guān)文法 G 包括四個(gè)組成

31、部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組 _。 A( ) 句子 B( ) 句型 C( ) 單詞 D( ) 產(chǎn)生式4_是一種典型的解釋型語言。 A( ) BASIC B( ) C C( ) FORTRAN D( ) PASCAL5與編譯系統(tǒng)相比，解釋系統(tǒng)_。A( ) 比較簡(jiǎn)單 , 可移植性好 , 執(zhí)行速度快 B( ) 比較復(fù)雜 , 可移植性好 , 執(zhí)行速度快 C( ) 比較簡(jiǎn)單 , 可移植性差 , 執(zhí)行速度慢 D( ) 比較簡(jiǎn)單 , 可移植性好 , 執(zhí)行速度慢 6用高級(jí)語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫_。 A( ) 源程序B( ) 目標(biāo)程序C( ) 連接程序 D( )

32、 解釋程序7詞法分析器用于識(shí)別_。 A. ( ) 字符串 B( ) 語句 C( ) 單詞 D( ) 標(biāo)識(shí)符 8編寫一個(gè)計(jì)算機(jī)高級(jí)語言的源程序后 , 到正式上機(jī)運(yùn)行之前，一般要經(jīng)過_這幾步: (1) 編輯 (2) 編譯 (3) 連接 (4) 運(yùn)行 A. ( ) (1)(2)(3)(4) B( ) (1)(2)(3) C( ) (1)(3)D( ) (1)(4)9把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由_完成的。A( ) 編譯器 B( ) 匯編器 C( ) 解釋器 D( ) 預(yù)處理器10文法 G 所描述的語言是_的集合。 A. ( ) 文法 G 的字母表 V 中所有符號(hào)組成的符號(hào)串B(

33、) 文法 G 的字母表 V 的閉包 V* 中的所有符號(hào)串C( ) 由文法的開始符號(hào)推出的所有終極符串D. ( ) 由文法的開始符號(hào)推出的所有符號(hào)串三、填空題(每空1分，共10分)1語法分析是依據(jù)語言的_語法_規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語言的_語義_規(guī)進(jìn)行的。2語法分析器的輸入是_單詞符號(hào)串_，其輸出是_語法單位_。3一個(gè)名字的屬性包括_類型_和_作用域_。4產(chǎn)生式是用于定義_語法成分_的一種書寫規(guī)則。5逆波蘭式 ab+c+ d*e- 所表達(dá)的表達(dá)式為_(a+b+c)*d-e_ 。 6語法分析最常用的兩類方法是_自上而下_和_自下而上_分析法。 四、簡(jiǎn)答題（20分）1. 寫出下列表達(dá)式的三地

34、址形式的中間表示。(1) 5+6 *(a + b); (2)for j:=1 to 10 do aj + j:=0。答： (1)100: t1:=a+b 101: t2:=6*t1 102: t3:=5+t2 (2)100: j:=1 101: if j10 goto NEXT 102: i:=j+j 103: ai:=02. 設(shè)基本塊p由如下語句構(gòu)成： T 0 : =3.14; T 1 :=2*T 0 ; T 2 :=R+r; A:=T l *T 2 ； B:=A; T 3 :=2*T 0 ; T 4 :=R+r; T 5 :=T 3 *T 4 ; T 6 :=R-r ； B:=T 5 *T

35、 6 ；試給出基本塊p的 DAG 。解：基本塊p的DAG圖:3. 寫出表達(dá)式(a+b)/(a-b-(a+b*c)的三元序列及四元序列。解：（1）三元式： （，a，b） （，a，b） （/，） （*，b，c） （，a，） （，） （2）四元式： （，a，b，T1） （，a，b，T2） （/，T1，T2，T3） （*，b，c，T4） （，a，T4，T5） （，T3，T5，T6）4. 寫一個(gè)文法使其語言為偶數(shù)集，且每個(gè)偶數(shù)不以0開頭。 解：文法G（S）： SAB|B|A0 AAD|C B2|4|6|8 C1|3|5|7|9|B D0|C5. 設(shè)文法 G （ S ）： SS aF|aF| aF F*a

36、F|*a （1）消除左遞歸和回溯；（2）構(gòu)造相應(yīng)的 FIRST 和 Follow 集合。1） S-aFS|aFS S-aFS| F-*aF F-F| （2） FIRST（S）a，+ FOLLOW（S） FIRST（S）+， FOLLOW（S） FIRST（F）* FOLLoW（F）（+， FIRST（F）*， FOLLOW（+，五.計(jì)算題（10分）已知文法為： S-a|(T) T-T,S|S 構(gòu)造它的 LR(0)分析表。 解：加入非終結(jié)符S，方法的增廣文法為： S-S S-a S- S-(T) T-T,S T-S 下面構(gòu)造它的LR(0)項(xiàng)目集規(guī)范族為： 從上表可看出,不存在移進(jìn)-歸約沖突以及歸

37、約歸約沖突，該文法是LR(0)文法。 從而有下面的LR(0)分析表： 編譯原理模擬試題五一、是非題（請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃，錯(cuò)誤的劃）（每個(gè)2分，共20分）1編譯程序是對(duì)高級(jí)語言程序的解釋執(zhí)行。( )2一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。()3一個(gè)算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對(duì)應(yīng)。 ( )4語法分析時(shí)必須先消除文法中的左遞歸 。 ()5LR分析法在自左至右掃描輸入串時(shí)就能發(fā)現(xiàn)錯(cuò)誤，但不能準(zhǔn)確地指出出錯(cuò)地點(diǎn)。 ()6逆波蘭表示法表示表達(dá)式時(shí)無須使用括號(hào)。 ( )7靜態(tài)數(shù)組的存儲(chǔ)空間可以在編譯時(shí)確定。 ()8進(jìn)行代碼優(yōu)化時(shí)應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對(duì)提高目標(biāo)代碼的效率將起更大作

38、用。 ()9兩個(gè)正規(guī)集相等的必要條件是他們對(duì)應(yīng)的正規(guī)式等價(jià)。 ( )10一個(gè)語義子程序描述了一個(gè)文法所對(duì)應(yīng)的翻譯工作。 ()二、選擇題(請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾，多劃按錯(cuò)論)(每個(gè)4分，共40分)1詞法分析器的輸出結(jié)果是_。A( ) 單詞的種別編碼 B( ) 單詞在符號(hào)表中的位置 C( ) 單詞的種別編碼和自身值 D( ) 單詞自身值2 正規(guī)式 M 1 和 M 2 等價(jià)是指_。 A( ) M1和M2的狀態(tài)數(shù)相等 B( ) M1和M2的有向邊條數(shù)相等C( ) M1和M2所識(shí)別的語言集相等 D( ) M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等 3 文法G：SxSx|y所識(shí)別的語言是_。A

39、( ) xyx B( ) (xyx)* C( ) xnyxn(n0) D( ) x*yx* 4如果文法G是無二義的，則它的任何句子_。A( )最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹必定相同 B( ) 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹可能不同 C( ) 最左推導(dǎo)和最右推導(dǎo)必定相同 D( )可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語法樹相同 5構(gòu)造編譯程序應(yīng)掌握_。A( )源程序B( ) 目標(biāo)語言 C( ) 編譯方法 D( ) 以上三項(xiàng)都是 6四元式之間的聯(lián)系是通過_實(shí)現(xiàn)的。 A( ) 指示器 B( ) 臨時(shí)變量 C( ) 符號(hào)表 D( ) 程序變量 7表達(dá)式(AB)(CD)的逆波蘭表示為_。A. ( )

40、ABCD B( ) ABCD C( ) ABCD D( ) ABCD 8. 優(yōu)化可生成_的目標(biāo)代碼。A( ) 運(yùn)行時(shí)間較短 B( ) 占用存儲(chǔ)空間較小C( ) 運(yùn)行時(shí)間短但占用內(nèi)存空間大 D( ) 運(yùn)行時(shí)間短且占用存儲(chǔ)空間小9下列_優(yōu)化方法不是針對(duì)循環(huán)優(yōu)化進(jìn)行的。A. ( ) 強(qiáng)度削弱 B( ) 刪除歸納變量 C( ) 刪除多余運(yùn)算 D( ) 代碼外提10編譯程序使用_區(qū)別標(biāo)識(shí)符的作用域。 A. ( ) 說明標(biāo)識(shí)符的過程或函數(shù)名B( ) 說明標(biāo)識(shí)符的過程或函數(shù)的靜態(tài)層次C( ) 說明標(biāo)識(shí)符的過程或函數(shù)的動(dòng)態(tài)層次 D. ( ) 標(biāo)識(shí)符的行號(hào)三、填空題(每空1分，共10分)1計(jì)算機(jī)執(zhí)行用高級(jí)語言編

41、寫的程序主要有兩種途徑：_解釋_和_編譯_。 2掃描器是_詞法分析器_，它接受輸入的_源程序_，對(duì)源程序進(jìn)行_詞法分析_并識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是單詞符號(hào)，供語法分析器使用。3自上而下分析法采用_移進(jìn)_、歸約、錯(cuò)誤處理、_接受_等四種操作。4一個(gè)LR分析器包括兩部分：一個(gè)總控程序和_一張分析表_。5后綴式abc-/所代表的表達(dá)式是_a/(b-c)_。 6局部?jī)?yōu)化是在_基本塊_范圍內(nèi)進(jìn)行的一種優(yōu)化。四、簡(jiǎn)答題（20分）1. 簡(jiǎn)要說明語義分析的基本功能。答：語義分析的基本功能包括: 確定類型、類型檢查、語義處理和某些靜態(tài)語義檢 查。2. 考慮文法 GS: S (T) | a+S | a

42、T T,S | S 消除文法的左遞歸及提取公共左因子。解：消除文法GS的左遞歸： S(T) | a+S | a TST T,ST| 提取公共左因子： S(T) | aS S+S | TST T,ST| 3. 試為表達(dá)式 w+(a+b)*(c+d/(e-10)+8) 寫出相應(yīng)的逆波蘭表示。解： w a b + c d e 10 - / + 8 + * +4. 按照三種基本控制結(jié)構(gòu)文法將下面的語句翻譯成四元式序列：while (AC BD) if (A 1) C=C+1;else while (A D)A=A+2;。解：該語句的四元式序列如下(其中E1、E2和E3分別對(duì)應(yīng)ACBD、A1和AD，并且

43、關(guān)系運(yùn)算符優(yōu)先級(jí)高)： 100 (j,A,C,102) 101 (j,_,_,113) 102 (jaAd|aAb| 判斷該文法是否是 SLR(1) 文法，若是構(gòu)造相應(yīng)分析表，并對(duì)輸入串 ab# 給出分析過程。解：增加一個(gè)非終結(jié)符S/后，產(chǎn)生原文法的增廣文法有： S-A A-aAd|aAb| 下面構(gòu)造它的LR(0)項(xiàng)目集規(guī)范族為： 從上表可看出,狀態(tài)I0和I2存在移進(jìn)-歸約沖突，該文法不是LR(0)文法。對(duì)于I0來說有：FOLLOW(A)a=b,d,#a=，所以在I0狀態(tài)下面臨輸入符號(hào)為a時(shí)移進(jìn)，為b,d,#時(shí)歸約，為其他時(shí)報(bào)錯(cuò)。對(duì)于I2來說有也有與I0完全相同的結(jié)論。這就是說，以上的移進(jìn)-歸

44、約沖突是可以解決的，因此該文法是SLR(1)文法。 其SLR(1)分析表為： 對(duì)輸入串a(chǎn)b#給出分析過程為： 編譯原理模擬試題六一、是非題（請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃，錯(cuò)誤的劃）（每個(gè)2分，共20分）1設(shè)r和s分別是正規(guī)式，則有L(r|s)=L(r)L(s)。()2確定的自動(dòng)機(jī)以及不確定的自動(dòng)機(jī)都能正確地識(shí)別正規(guī)集。()3詞法分析作為單獨(dú)的一遍來處理較好。 ( )4構(gòu)造LR分析器的任務(wù)就是產(chǎn)生LR分析表。 ()5規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。 ( )6同心集的合并有可能產(chǎn)生新的“移進(jìn)”/“歸約”沖突。 ( )7LR分析技術(shù)無法適用二義文法。 ( )8樹形表示和四元式不便于優(yōu)化，而三元式和間接三元式則便于優(yōu)化。 ()9程序中的表達(dá)式語句在語義翻譯時(shí)不需要回填技術(shù)。 ()10對(duì)中間代碼的優(yōu)化依賴于具體的計(jì)算機(jī)。 ( )二、選擇題(請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾，多劃按錯(cuò)論)(每個(gè)