answer.西北工業(yè)大學(xué)考試題紙B卷-編譯原理20120619.final

誠信保證本人知曉我?？紙?chǎng)規(guī)則和違紀(jì)處分條例的有關(guān)規(guī)定，保證遵守考場(chǎng)規(guī)則，誠實(shí)做人。 本人簽字：編號(hào)：西北工業(yè)大學(xué)考試試題（ B卷）2011－2012學(xué)年第 二學(xué)期開課學(xué)院考試日期

計(jì)算機(jī)學(xué)院

課程編譯原理考試時(shí)間2小時(shí)

學(xué)時(shí)64考試形式（閉）卷題 一

二

三 四

五 六 七

八 九

十

總分號(hào)得分考生班級(jí) 學(xué) 號(hào) 姓 名一、選擇題（每小題 2分，共10分）1）對(duì)文法S→，B→b，A→，以下哪些結(jié)論是正確的（B）。①該語言可以用正規(guī)式(a**)描述②該文法對(duì)應(yīng)的語言可由圖靈機(jī)識(shí)別③不是該文法的有效句型④是語言的句子A、②④ B. ①②④ C.①③D. ①③④（2）語法分析的任務(wù)是：①分析單詞的構(gòu)成 ②分析單詞流如何構(gòu)成語句； ③分析語句如何構(gòu)成程序；④分析程序的結(jié)構(gòu) （A）A、②③④ B 、①②③④ C 、②③ D 、①④3）給定數(shù)組A[1..10，1..20，1..30]，假定數(shù)組是按行存放的，且首地址為0（按字編址），則A[3，4，5]的地址為（A）A.1294

B.1043

C.1925

D.832（4）以下哪個(gè)結(jié)論是正確的（ C）。①常量傳播可能產(chǎn)生無用變量 ②與的等價(jià)的最小在同構(gòu)意義下唯一③可以用表示 ④中的垃圾收集屬于棧式存儲(chǔ)管理機(jī)制A、①② B 、②④ C、①②③ D 、②③注：1.命題紙上一般不留答題位置，試題請(qǐng)用小四、宋體打印且不出框。命題教師和審題教師姓名應(yīng)在試卷存檔時(shí)填寫。共3頁 第1頁西北工業(yè)大學(xué)命題專用紙（5）對(duì)文法G[S]：文法S→，A→b，A→，B→，哪個(gè)結(jié)論是正確的（①該文法是正規(guī)文法 ②該文法定義的語言無限③中的句柄是 ④該文法不能用(1)方法分析A、① B 、③ C 、②③④ D 、②④二、判斷題（每小題 2分，共10分）

D）（1）已知屬性翻譯文法：S→{("1");}S→y{("2");}W→{("3");}若輸入串為

""，則分析過程將輸出

23131

(

)（2）文法

E→

|

，T→T*，F(xiàn)→i

可用識(shí)別

(

)（3）使用分析法進(jìn)行分析的前提條件是文法不含左遞歸產(chǎn)生式（ ）（4）對(duì)于文法S→，[1]項(xiàng)目[S→b·]對(duì)于活前綴有效（）（5）存在遞歸調(diào)用的語言不能采用靜態(tài)存儲(chǔ)管理方式分配存儲(chǔ)空間（ ）三、（17分）對(duì)于以下狀態(tài)矩陣a b0 1 21 3 42 1 23 44 3其中初始狀態(tài)為狀態(tài)0，終止?fàn)顟B(tài)為狀態(tài)3、4（1）畫出相應(yīng)的狀態(tài)轉(zhuǎn)換圖（4分）（2）對(duì)所得進(jìn)行最小化（6分）（3）求解最小化對(duì)應(yīng)的正規(guī)表達(dá)式（ 5分）四、（8分）用長(zhǎng)度不超過4的某個(gè)句型的兩個(gè)不同最左推導(dǎo)來說明下面的文法是二義的，并畫出相應(yīng)的語法樹。S→A→五、（12分）給定文法：S→，A→，B→（1）給出該文法的每個(gè)候選式的集及每個(gè)非終結(jié)符的集（4分）()={}(b)=()=(c)={c}( )={ }（2）判斷該文法是否為(1)文法,若是，請(qǐng)給出該文法的（1）分析表，若不是，請(qǐng)給出理由。（4分）答案：是，表略（3）給出識(shí)別的分析過程（4分）教 務(wù) 處 印 制共3頁 第2頁六、（18分，每小題6分）對(duì)于文法 S→，X→，X→b，Y→c，Y→（1）構(gòu)造（1）狀態(tài)機(jī)；（2）構(gòu)造該文法的(1)分析表并判斷該文法是否為 (1)文法；（3）給出用（1）分析表對(duì)輸入串進(jìn)行分析的步驟。七、（10分）以下二小題任選一題作答（1）給出語句 b<a a>b 的逆波蘭表示；2）語言中的語句的形式為SE，其含義是重復(fù)地執(zhí)行S，直到布爾表達(dá)式E的值為真時(shí)，退出循環(huán)。請(qǐng)給出此結(jié)構(gòu)的屬性翻譯文法八、（15分）（1）考慮下面的三地址語句序列：L0:i0L1:i1i>mL2nn<<1n<kL1L2:k1k<=0L3L0L3:L4L4:8分）將代碼分成基本塊，并給出控制流圖。如有不可達(dá)代碼則刪除（（2）用圖對(duì)下面的程序進(jìn)行