編譯試卷2013-2014及答案

1、承諾：我將嚴(yán)格遵守考場紀(jì)律，知道考試違紀(jì)、作弊的嚴(yán)重性，還知道請他人代考或代他人考者將被開除學(xué)籍和因作弊受到記過及以上處分將不授予學(xué)士學(xué)位，愿承擔(dān)由此引起的一切后果。專業(yè) 班級 學(xué)號 學(xué)生簽名： 華東交通大學(xué)20132014學(xué)年第二學(xué)期考試卷 （A ）卷課程名稱： 編譯原理 課程類別：必、限、任考試方式：閉卷（ ）、開卷(范圍)（ ）：題號一二三四五六七八九十總分累分人簽名題分1020151010101510100得分考生注意事項：1、本試卷共 4 頁，總分100分，考試時間120分鐘。2、考試結(jié)束后，考生不得將試卷、答題紙和草稿紙帶出考場。得分評閱人 一、是非判斷題（對下列各題，請在答題卡上

2、對應(yīng)的小題中，對的打“”，錯的打“×”。）（共10小題，每題1分，共計10分)1 編譯程序不是一種翻譯程序。2 編譯程序和解釋程序都會產(chǎn)生目標(biāo)程序。3 任何一門高級程序設(shè)計語言的語法都可以用一個上下文無關(guān)文法來描述。4 一個上下文無關(guān)語言可以用無數(shù)個上下文無關(guān)文法來描述。5 一個遞歸文法G所描述的語言一定是一個無限集合。6 一個文法是二義性的，其描述的語言不一定是二義性的。7 文法中不含左公共因子只是LL(1)文法的必要條件。8 簡單優(yōu)先分析與算符優(yōu)先分析方法一樣，都不需要比較非終結(jié)符的優(yōu)先級。9 素短語可以看作是包含有終結(jié)符的直接短語。10 正規(guī)文法、DFA和正規(guī)式均可以用于描述高

3、級程序設(shè)計語言的詞法。得分評閱人二、單項選擇填空題（對下列各題，請在答題卡上對應(yīng)的小題中填上你的選項，共10小題，每題2分，共計20分) 1 在編譯程序的八大功能模塊中，下面的哪個模塊是可有可無： A語法分析； B語義分析； C代碼優(yōu)化； D詞法分析 2 在下面的四類文法中，哪類文法的描述能力最弱： A短語文法； B上下文有關(guān)； C上下文無關(guān)； D正規(guī)文法3 在語法分析方法中，遞歸下降分析法屬于下面的哪種分析方法：A自頂向下； B自右向左； C自左向右； D自底向上4 給定文法 GE：EE0E11 ，下面的符號串中，是該文法的句子： A110； B11011011； C100； D110011

4、5 在語法分析中，如果使用的是規(guī)范歸約技術(shù)，則每次被歸約的子串都是：A活前綴； B素短語； C句柄； D句型6 語句x:=（a-b）*c+d/e的等價逆波蘭表達式為：Ax:=ab-c*de/+ ； Bxabcde-*/+:= ； Cxab-c*de/+:= ； Dabc-*de/+x:=7 在下面的四種LR分析方法中，分析能力最強的是：ALR(0)； BLALR(1)； CSLR(1)； DLR(1) 8 LL（1）文法和LR（0）文法都有一個共同的特性：A自右向左； B無二義性； C自頂向下； D自底向上9 一個LR(0) 項目為 A®aB.c ，其中a、cVT，A、BVN，該項目

5、是：A歸約項目； B接收項目； C移進項目； D待約項目10 文法Gs: S ® 1A1 ， A ® 1A0A10，所描述的語言為：A0(0½1)* ； B(1½0)*1 ； C(0½1)*0 ； D1(1½0)*三、給定文法GE：EE+T | T ， TT*F | F ， F(E) | a 中的一個句型：F*a+(E) ，請完成以下工作： （共計15分) 得分評閱人 1. 畫出該句型對應(yīng)的語法樹；（6分)2. 找出該句型中的全部短語；（5分)3. 找出該句型中的句柄和最左素短語。（4分)四、請構(gòu)造出接收正規(guī)式 a(ab | a)*的

6、最小DFA。（共計10分) 得分評閱人 得分評閱人五、給定文法GE：E0B1ab ， BBcEE 請在下面的算符優(yōu)先關(guān)系表中標(biāo)記為“？”的欄目內(nèi)填寫出正確的優(yōu)先關(guān)系（<、> 或 =）： （共計10分)ab01c#a？>b？ ？>0<<< ？ ？1？>c<<< ？#<<<=六、給定文法GE: EA1A0B0B1 ， A ， B得分評閱人 請證明該文法是LL(1)文法，但不是SLR(1)文法。 （共計10分) 得分評閱人七、：給定文法GS 如下所示: S ® cAdA ， A ® aAb 請完成

7、以下工作： （共計15分) 1. 構(gòu)造出該文法的LR(0)項目集規(guī)范族； （5分)2. 畫出識別該文法活前綴的DFA； （5分)（注： DFA的狀態(tài)用LR(0)項目集的編號表示，比如 I0，I1）3. 構(gòu)造出該文法的LR(0)分析表。 （5分)八、結(jié)合本學(xué)期對編譯原理課程內(nèi)容的學(xué)習(xí)，請用最簡潔的語言回答下面二個問題： （共計10分)得分評閱人 1. 至少列舉出本課程中十個大知識點； （5分)2. 談?wù)剬W(xué)完本課程后，對你從事應(yīng)用軟件開發(fā)有何啟發(fā)？ （5分)承諾：我將嚴(yán)格遵守考場紀(jì)律，知道考試違紀(jì)、作弊的嚴(yán)重性，還知道請他人代考或代他人考者將被開除學(xué)籍和因作弊受到記過及以上處分將不授予學(xué)士學(xué)位，愿

8、承擔(dān)由此引起的一切后果。專業(yè)： 班級: 學(xué)號： 學(xué)生簽名： 承諾：我將嚴(yán)格遵守考場紀(jì)律，知道考試違紀(jì)、作弊的嚴(yán)重性，還知道請他人代考或代他人考者將被開除學(xué)籍和因作弊受到記過及以上處分將不授予學(xué)士學(xué)位，愿承擔(dān)由此引起的一切后果。專業(yè)： 班級: 學(xué)號： 學(xué)生簽名： 華東交通大學(xué)20132014學(xué)年第二學(xué)期試卷(A)答題紙得分評閱人 一、是非判斷題（對，錯×，每小題1分；共10分）12345678910××××得分評閱人 二、單項選擇填空題（每小題2分； 共計20分) 12345678910CDABCCDBCD得分評閱人 三、基礎(chǔ)應(yīng)用題 （共2小題，

9、共計25分）1.（第(1)問6分、第(2)問5分、第(3)問4分； 小計15分)【解】 （1） 該句型對應(yīng)的語法樹如下圖所示： 注 6分 （2） 該句型中的全部短語有： 注 5分 F ； a ； F*a ； (E) ； F*a+(E) （3）該句型中的句柄為 ： F 注 2分 該句型中的最左素短語為：a 注 2分2. （小計10分)【解】（1）接收該正規(guī)式的 NFA 如下圖所示： 注 畫出了NFA ，可以給步驟分5分（2）確定化后，得等價的 DFA 如下圖所示：注 畫出了DFA ，可以給步驟分3分（3）該自動機已經(jīng)是最小的 DFA 注 注明了此為最小的DFA，可以給步驟分2分總注 此僅為參考答

10、案，NFA有多種等價的答案！ 此DFA唯一！得分評閱人 四、語法分析應(yīng)用題 （共3小題，共計35分）1.（共計10分)【解】ab01c#a> ？> ？>b> ？> ？>0<<<= ？< ？1> ？> ？>c<<<> ？> ？#<<<=注 每空1分。2.（小計10分)【解】(1). 計算First集和Follow集 注 First 集 和 Follow集2分 First(A1A0)=1; First(B0B1)=0; Follow(S)=#; Follow(A)=1，0;

11、 Follow(B)=1，0;(2). 計算各產(chǎn)生式的SELECT集：注 SELECT集2分SELECT(SA1A0)=1 ； SELECT(SB0B1)=0SELECT(A)=1，0 ； SELECT(B)=1，0(3). 因為，SELECT(SA1A0) SELECT(SB0B1) = ，所以該文法是LL(1)文法；注 計算了交集且給出了是LL（1）文法的結(jié)論1分(4). 因為該文法的LR(0)項目集規(guī)范族中有一個項目集I0，存在“歸約-歸約”沖突， I0 = S.S, S.A1A0， S.B0B1 ， A. ， B. 而， Follow(A) Follow(B) = 1, 0 注 計算出

12、了LR（0）項目集規(guī)范簇2分； 判斷了交集不為空2分用Follow集不能解決其沖突，所以該文法不是SLR(1)文法。注 給出了不是SLR（1）文法的結(jié)論1分?？傋?以上為寫出步驟給分，若以上步驟不全，但最終證明了：是LL(1)文法，給5分； 證明了不是SLR(1)文法，給5分3.（第（1）小題5分、第（2）小題5分、第（3）小題5分； 小計15分)【解】（1） 構(gòu)造出該文法的LR(0)項目集規(guī)范族如下： 共5分對該文法拓廣，得其拓廣文法GS：注 文法拓廣給2分 (0) SS (1) ScA (2) SdA (3) AaA (4) Ab注 如下計算出LR(0)項目集規(guī)范族；或用DFA的形式寫出了

13、LR(0)項目集規(guī)范族，可給3分I0 = S.S ， S.cA ， S.dA I1 = GOTO(I0，S) = SS. I2 = GOTO(I0，c) = Sc.A ， A.aA ， A.b I3 = GOTO(I0，d) = Sd.A ， A.aA ， A.b I4 = GOTO(I2，A) = ScA. I5 = GOTO(I2，a) = Aa.A ， A.aA ， A.b I6 = GOTO(I2，b) = Ab. I7 = GOTO(I3，A) = SdA. GOTO(I3，a) = I5 ; GOTO(I3，b) = I6I8 = GOTO(I5，A) = AaA. GOTO(I5，a) = I5 ; GOTO(I5，b) = I6