【試卷B】10級編譯原理.doc

《【試卷B】10級編譯原理.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、貴州大學(xué)計算機(jī)科學(xué)與信息學(xué)院2012-2013學(xué)年第二學(xué)期考試試卷B《編譯原理》注意事項(xiàng)：1.請考生按要求在試卷裝訂線內(nèi)填寫姓名、學(xué)號和年級專業(yè)。2.請仔細(xì)閱讀各種題目的回答要求，在規(guī)定的位置填寫答案。3.不要在試卷上亂寫亂畫，不要在裝訂線內(nèi)填寫無關(guān)的內(nèi)容。4.滿分100分，考試時間為120分鐘。題號一二三四總分統(tǒng)分人得分得分評分人一、填空題(每空1分,共20分)1.將源程序完整地轉(zhuǎn)換成機(jī)器語言程序或匯編語言程序，然后再處理、執(zhí)行的翻譯程序是編譯程序。2.編譯程序的整個過程從邏輯上依次分為詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成等幾個階段。另外還有兩個重要工作是表格

2、管理和出錯處理。3.句子abab的前綴有。4.集合{xnyn

3、n≥0}可以用產(chǎn)生式實(shí)現(xiàn)。5.有窮自動機(jī)接受的語言是語言。6.構(gòu)造LR(0)項(xiàng)目集規(guī)范族的項(xiàng)目類型分為四種：形如S'→α.的稱為接受項(xiàng)目、形如A→α.aβ的稱為項(xiàng)目、形如的稱為待約項(xiàng)目、形如A→αBβ.的稱為項(xiàng)目。1.語法分析方法分為自頂向下與自底向上兩類，自頂向下的分析方法主要有遞歸子程序分析法和；而自底向上的分析方法主要有算符優(yōu)先分析方法和。2.活前綴是指。3.運(yùn)行時的存儲管理方案主要分為兩大類，即方案和方案。4.LR(0)文法中，不會出現(xiàn)沖突和沖突。5.常用的參數(shù)傳遞方式有，，傳值結(jié)果，傳名等。得分評分人一、單選題(每題2分

4、,共20分)1.下面不屬于正規(guī)文法的是（）。A.S?0

5、1

6、00

7、11B.S?0

8、1

9、0A

10、1B，A?0，B?1C.A?aS

11、Sb

12、a

13、bD.S?0

14、0S2.一個句型中稱為句柄的是該句型的最左（）。A．非終結(jié)符號B．短語C．句子D．直接短語3.Chomsky定義的四種形式語言文法中，上下文有關(guān)文法是(　　)。　　A.0型文法　B.1型文法　　C.2型文法　D.3型文法4.詞法分析的任務(wù)是(　　)。A．識別單詞B．分析句子的含義C．識別句子D．生成目標(biāo)代碼5.常用的中間代碼形式不含(　　)。A．三元式B．四元式C．逆波蘭式D．語法樹6.經(jīng)過編譯所得到的目標(biāo)程序是(　　)?！　.三元式序列　　

15、B.四元式序列　　C.間接三元式　D.機(jī)器語言程序或匯編語言程序1.中間代碼生成所依據(jù)的是（）。A.詞法規(guī)則B.語法規(guī)則C.語義規(guī)則D.產(chǎn)生式規(guī)則2.后綴式ab+cd+/可用表達(dá)式（）來表示。A.a+b/c+dB.(a+b)/(c+d)C.a+b/(c+d)D.a+b+c/d3.程序所需的數(shù)據(jù)空間在程序運(yùn)行前就可確定，稱為（）管理技術(shù)。A.動態(tài)存儲B.棧式存儲C.靜態(tài)存儲D.堆式存儲。4.文法G：S→xSx

16、y所識別的語言是（）。A．xyxB．(xyx)*C．xnyxn(n≥0)D.x*yx*得分評分人一、應(yīng)用題(每題8分,共32分)1.文法G的產(chǎn)生式如下：S→(L)

17、aL→L,S

18、S①有如

19、下語法制導(dǎo)定義，畫出輸入為((a),a)時的語法分析樹，判斷其輸出結(jié)果。產(chǎn)生式語義規(guī)則S→(L)S.h:=L.h+1S→aS.h:=0L→L1,SL.h:=L1.h+S.hL→SL.h:=S.hS’→Sprint(S.h)輸入為((a),a)時的語法分析樹：輸入為((a),a)時的輸出結(jié)果：①有如下翻譯模式，判斷輸入為((a),a)時的輸出結(jié)果，并簡述該翻譯模式功能。S’→{S.d:=0;}SS→({L.d:=S.d+1;}L)S→a{print(S.d)}L→{L1.d:=L.d}L1,{S.d:=L.d}SL→{S.d:=L.d}S輸入為((a),a)時的輸出結(jié)果：翻譯模式功能：1.已知

20、文法G：E→T

21、E+TT→F

22、T*FF→(E)

23、i，要求：①給出句型(T*F+i)的最右推導(dǎo)。②畫出句型(T*F+i)的語法樹。③列出句型(T*F+i)的所有短語、簡單短語和句柄。短語：簡單短語：句柄：1.給出表達(dá)式a:=b*(-c)+b/(-d)的逆波蘭式、三元式和四元式。逆波蘭式：三元式：四元式：2.給定正規(guī)式R=(01

24、10)(01

25、10)*，要求：①構(gòu)造對應(yīng)的正規(guī)文法G，使得L(G)=L(R)。②請構(gòu)造該文法的狀態(tài)轉(zhuǎn)換圖。①判斷這是一個NFA還是DFA。得分評分人一、綜合分析題（每題14分，共28分）1.對文法G(S)：S→aSb

26、PP→bPc

27、bQcQ→Qa

28、a①消除該文法的左遞歸

29、和提取左公因子。②針對改造后的文法，構(gòu)造各非終結(jié)符的FIRST和FOLLOW集合。③構(gòu)造該文法的LL(1)分析表，并判斷該文法是否是LL(1)的。2.給定文法G[A]：A→aAd

30、aAb

31、ε，要求：①構(gòu)造拓廣文法，畫出識別該拓廣文法的所有規(guī)范句型活前綴的DFA。拓廣文法為：識別該拓廣文法的所有規(guī)范句型活前綴的DFA如下，請將其補(bǔ)充完整：I0:A’→.AAI1:A’→A.aI2:AI4:.I5:dI3:ba①求