成都理工大學(xué)20122013軟件代碼開發(fā)技術(shù)(編譯原理)考試試卷(最終修改版)

1、成都理工大學(xué)2012-2013學(xué)年第一學(xué)期軟件代碼開發(fā)技術(shù)考試試卷一， 填空題（每題2分，共30分）1. 源程序的動態(tài)錯誤是源程序中的邏輯錯誤，它們發(fā)生在程序運行的時候，也被成為 動態(tài)語義錯誤。2. 設(shè)計一個編譯器，除了具有中間代碼生成、代碼生成和出錯處理功能之外，還應(yīng)具有哪些功能：它們分別為_詞法分析、語法分析、語義分析、中間代碼優(yōu)化、符號表管理_ 3. 設(shè)=0,1上的正規(guī)集S由倒數(shù)第二個字符為0的所有字符串組成，則該正規(guī)集對應(yīng)的正規(guī)式表示為 (0|1)* 0(0|1) 4. 假設(shè)G是一個文法，S是文法的開始符號，如果S =>x,則稱x是該文法的一個句型 5. 中間代碼生成器對語法樹進

2、行遍歷，生成可順序執(zhí)行的中間的代碼序列，最常用的中間代碼形式是 四元式6. 最右推導(dǎo)也成為 規(guī)范 推導(dǎo)，推導(dǎo)出的句型稱為 右 句型。7. LR(k)文法所識別的語言稱為LR(k)語言，其中L表示 從左到右掃描輸入序列，R表示 逆序的最右推導(dǎo)，k表示 確定下一動作向前看的終結(jié)符個數(shù) 8. 將棧頂?shù)姆柡臀姆óa(chǎn)生式的右部符號串進行比較，若相等，則用左部符號去替換棧頂符號串，這種操作稱為 規(guī)約9. 自上而下語法分析方法遇到的主要問題是 回溯 和無限循環(huán)（死循環(huán)）10. 正規(guī)文法，正規(guī)表達式和有限自動機三者在某種意義下是 等價的 11. 若為文法G構(gòu)造的預(yù)測分析表中不含多重定義的條目，則稱G為 回溯文

3、法。12. 文法符號的屬性有兩種，一種稱為 綜合屬性，另一種稱為幾成屬性。13. 一個句型中的最左 直接短語 稱為該句型的句柄。14. 如果一個問發(fā)的同一個句子存在兩棵分析樹，則該文法是 二義性的15. 不管任何類型的文法都包括四個組成部分，它們分別是 非終結(jié)符、終結(jié)符、產(chǎn)生式、開始符號二、判斷題（每題1分，共10分）1，確定的和不確定的有限自動機都能識別正規(guī)集。（）2，有些語言能被確定的有限自動機識別，但不能用正規(guī)表達式表示。（×）3，設(shè)L = a, b, c , M = b, c, d , LM = b , c.（×）4，在預(yù)測分析器的轉(zhuǎn)換圖中，其箭弧上的標識必須是終結(jié)

4、符。（×）5，一個項目集中既可以有移進項目，又有可規(guī)約項目，使得分析無法進行，這種沖突稱為移進/規(guī)約沖突。（）6，在使用自上而下分析法時，文法應(yīng)該沒有左遞歸。（）7，正規(guī)集都可以由一個狀態(tài)數(shù)最少的DFA識別，這個DFA是唯一的。（）8，二義文法是SLR(l)文法。（×）9，正規(guī)表達式的運算操作不具有優(yōu)先級運算。（×）10，文法G的產(chǎn)生式為 S ->（L）| aL-> L，S | S是一個直接左遞歸文法。（）三、選擇題（每題1分，共10分）1，文法G所描述的語言是 D 的集合。A文法G的字匯表V中所有符號組成的符號串B文法G的字匯表V的閉包V*中的所有符

5、號串C由文法的開始符號推出的所有符號串D由文法的開始符號推出的所有終結(jié)符號串2，一個語言的文法是 B 。A唯一的B. 不唯一的 C. 個數(shù)有限的3，若一個文法是遞歸的，則它所產(chǎn)生的句子個數(shù) A 。A. 必定是無窮的B. 是有限個的C. 根據(jù)具體情況而定4，文法的二義性和語言的二義性是兩個 A 的概念。A. 不同B. 相同C. 無法判斷D. 等價5，巴克斯范式（BNF）是一種廣泛采用的 C 的工具。A. 描述規(guī)則B. 描述語言C. 描述文法D. 描述句子6， B 是兩類程序語言處理程序。A. 高級語言程序和低級語言程序B. 解釋程序和編譯程序C. 編譯程序和操作系統(tǒng)D. 系統(tǒng)程序和應(yīng)用程序7，喬

6、姆斯基把文法分為四種類型：0型、1型、2型和3型，其中2型文法指的是 C 。A短語文法B.上下文有關(guān)文法C. 上下文無關(guān)文法D. 正規(guī)文法8，語法分析常用的方法是 A 。A. 自頂向下、自底向上B. 自頂向下、自底向上、自左向右C. 自頂向下、自底向上、自左向右、自右向左D. 自左向右、自右向左9.編譯程序中的語法分析器接受以 C 為單位的輸入，并產(chǎn)生以有關(guān)信息供以后各階段使用。A. 表達式B. 產(chǎn)生式 C. 單詞D. 語句10.LR語法分析棧中存放的狀態(tài)是識別 B 的DFA狀態(tài)。A. 前綴B. 可規(guī)約前綴C. 項目D. 句柄四，綜合題（5小題，共50分）1， 設(shè)文法G具有下列產(chǎn)生式：E -&

7、gt; E Or T | TT -> T and F | FF -> not F | (E) | true | false請指出文法G的終結(jié)符號、非終結(jié)符號和開始符號。（4分）解答：終結(jié)符：or,and,not,(,),true,false 非終結(jié)符：E,T,F 開始符號：E2， 根據(jù)1中文法G寫出句子 not(true and false) 的規(guī)范推導(dǎo)并確定句柄。（6分）解答：規(guī)范推導(dǎo)為：E =>T =>F =>not F =>not (E) =>not (T) =>not (T and F) =>not (T and false) =&

8、gt;not (F and false) =>not (true and false)由分析樹：可知句柄為：true3， 有NFA定義如下：N = （S=0,1，=a,b,s0 = 0，F(xiàn) = 0，MOVE = move(0,a) = 0，move(0,a) = 1，move(1,a) = 0）(1) 畫出N的狀態(tài)轉(zhuǎn)換圖（4分）解答：aa,ba10(2) 構(gòu)造N的最小DFA D（7分）解答：確定DFA_閉包（0）= 0*A_閉包（smove(0,a)） = 0,1*B_閉包（smove(0，b)） = 1*C_閉包（smove(0，1,a)）= 0,1B_閉包（smove(0，1,b)）

9、= 1C_閉包（smove(1,a)）= 0A_閉包（smove(1,b)）=DFA為：AAABCAACabba = A，B,Cmove(A,a)= Bmove(A,b)=cmove(B,a)= Bmove(B,b)= c故A,B不可分，將A為A,B編號0，C編號1,為c代表最小DFA為aba10(3) 給出串a(chǎn)aba,baa的識別過程（4分）解答： a a b a0 0 0 1 0 b a a 0 1 0 0 識別aaba:識別baa:4， 設(shè)文法G具有下列產(chǎn)生式：E -> E + T | TT -> T * F | FF > id | (E)(1) 消除文法的直接左遞歸：

10、（4分）解答：消除左遞歸后的文法為：E ->T EE->+T E/T ->F TT ->*F T/F ->id/(E)(2) 求消除左遞歸后文法的FIRST和FOLLOW函數(shù)：（6分）解答：First(F) = id,(First(T) = *,First(T) = id,(First(E) = +，F(xiàn)irst(E) = First(T) = First(F) =id,(Follow(E) = #,)Follow(E) = Follow(E) =#,)Follow(T) =+,#,)Follow(T) = Follow(T) =+,#,)Follow(F) = *

11、,+,#(3) 構(gòu)造其預(yù)測分析表。（4分）解答：first(TE) = id，(first(+TE) = +,first(FT) = id，(first(*FT) = *,(first(id) = idfirst(E) = （*+）（id#ETETEE+TETFTFTT*FTF(E)id5，已知文法G3: S -> EE -> aA | bBA -> cA | dB -> cB | d(1) 寫出句型bccB的所有短語、直接短語和句柄。（4分）解答：S=>E =>bB =>bcB =>bccB短語： bccB(SE) ccB(B1)cB(B2)直

12、接短語：cB(B2)句柄：cB(B2)(2) 列出4個項目集I1、I2、I3、I4（如下圖），請將這4個項目集補充完整。（7分）I1: S ->.EE->.aAE->.bBI2:E->a.AA->.cAA->dI3:E.I4:E->b.BB->.cBB->.daEb附加資料：編譯：高級語言可以直接轉(zhuǎn)換成機器語言，也可以翻譯成匯編語言，這兩個過程稱為編譯。解釋器與編譯器的主要區(qū)別：運行目標程序的控制權(quán)在解釋器而不在目標程序。解釋器優(yōu)點：（1）其具有較好的動態(tài)特性。（2）具有較好的可移植性。缺點：在時間和空間上的損失較大，運行效率低。文法的分類：文法產(chǎn)生式語言自動機0型文法（短語）->0型語言（短語結(jié)構(gòu)語言，遞歸可枚舉集）圖靈機1型文法（CSG）限制11型語言（CSL）線性界線自動機2型文法（CFG）限制22型語言（CFL）下推自動機3型文法（正規(guī)）限制33型語言（正規(guī)語言，正規(guī)集）有限自動機LR(1)與L