《編譯原理》模擬試題

1、編譯原理期末模擬試題及答案一、是非題（請在括號內(nèi)，正確的劃，錯誤的劃）（每個2分，共20分）1對于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動態(tài)貯存分配策略。()2甲機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系統(tǒng)功能完全相同。( )3遞歸下降分析法是自頂向上分析方法。( )4產(chǎn)生式是用于定義詞法成分 的一種書寫規(guī)則。 ()5LR 法是自頂向下語法分析方法。 ( )6在 SLR （ 1 ）分析法的名稱中，S的含義是簡單的。()7綜合屬性是用于 “ 自上而下 ” 傳遞信息。( )8符號表中的信息欄中登記了每個名字的 屬性和特征等有關(guān)信息 ，如類型、種屬、所占單元大小、地址等等。 (

2、)9程序語言的語言處理程序是一種應(yīng)用軟件。 ()10解釋程序適用于 COBOL 和 FORTRAN 語言。 ()二、選擇題(請在前括號內(nèi)選擇最確切的一項作為答案劃一個勾，多劃按錯論)(每個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ī)

3、文法 4 一個文法所描述的語言是_。A( ) 唯一的 B( ) 不唯一的 C( ) 可能唯一，好可能不唯一 D( ) 都不對5 _和代碼優(yōu)化部分不是每個編譯程序都必需的。A( ) 語法分析B( ) 中間代碼生成 C( ) 詞法分析 D( ) 目標(biāo)代碼生成 6_是兩類程序語言處理程序。 A( ) 高級語言程序和低級語言程序 B( ) 解釋程序和編譯程序 C( ) 編譯程序和操作系統(tǒng) D( ) 系統(tǒng)程序和應(yīng)用程序 7 數(shù)組的內(nèi)情向量中肯定不含有數(shù)組的_的信息。A. ( ) 維數(shù) B( ) 類型 C( ) 維上下界 D( ) 各維的界差 8. 一個上下文無關(guān)文法 G 包括四個組成部分，它們是：一組非

4、終結(jié)符號，一組終結(jié)符號，一個開始符號，以及一組 _。 A( ) 句子 B( ) 句型C( ) 單詞 D( ) 產(chǎn)生式9 文法分為四種類型，即0型、1型、2型、3型。其中2型文法是_。A. ( ) 短語文法 B( ) 正則文法 C( ) 上下文有關(guān)文法D( ) 上下文無關(guān)文法10文法 G 所描述的語言是_的集合。 A. ( ) 文法 G 的字母表 V 中所有符號組成的符號串B( ) 文法 G 的字母表 V 的閉包 V* 中的所有符號串C( ) 由文法的開始符號推出的所有終極符串D. ( ) 由文法的開始符號推出的所有符號串三、填空題(每空1分，共10分)1一個句型中的最左簡單短語稱為該句型的_句

5、柄_。 2對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為 _語義規(guī)則_ 。3一個典型的編譯程序中，不僅包括_詞法分析_、_語法分析_、_中間代碼生成_、代碼優(yōu)化、目標(biāo)代碼生成等五個部分，還應(yīng)包括表格處理和出錯處理。4 從功能上說，程序語言的語句大體可分為_執(zhí)行性_語句和_說明性_語句兩大類。5 掃描器的任務(wù)是從_源程序_中識別出一個個_單詞符號_。 6 產(chǎn)生式是用于定義_語法范疇_的一種書寫規(guī)則。 四、簡答題（20分）1. 寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以0開頭。解：文法G(N)： NAB|B AAC|D B1|3|5|7|9 DB|2|4|6|8 C0|D2. 設(shè)文法G(S

6、)： S(L)|a S|a LL，S|S (1) 消除左遞歸和回溯；(2) 計算每個非終結(jié)符的FIRST和FOLLOW。解：(1) S(L)|aS SS| LSL LSL| (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)-

7、(T*Fi) (2) 短語：(T*Fi)，T*Fi，T*F，i 素短語：T*F,i 4. Whilea0 b0do Begin X：X1； if a0 then a：a1 else 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)五.計算題

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