編譯試卷2013-2014及答案

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

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

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

4、析中，如果使用的是規(guī)范歸約技術，則每次被歸約的子串都是：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) 項目為 AaB.c ，其中a、cVT，A、BVN，該項目是：A歸約項目； B接收

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

6、在下面的算符優(yōu)先關系表中標記為“？”的欄目內(nèi)填寫出正確的優(yōu)先關系（ 或 =）： （共計10分)ab01c#a？b？ ？0c ？# ？ ？b ？ ？0= ？ ？ ？c ？ ？#=注 每空1分。2.（小計10分)【解】(1). 計算First集和Follow集 注 First 集 和 Follow集2分 First(A1A0)=1; First(B0B1)=0; Follow(S)=#; Follow(A)=1，0; Follow(B)=1，0;(2). 計算各產(chǎn)生式的SELECT集：注 SELECT集2分SELECT(SA1A0)=1 ； SELECT(SB0B1)=0SELECT(A)=1，0

7、 ； 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 注 計算出了LR（0）項目集規(guī)范簇2分； 判斷了交集不為空2分用Follow集不能解決其沖突，所以該文法不是SLR(1)文法。注 給出了不是SLR（1）文法的結(jié)論1分。總注 以上為寫出步驟給分，

8、若以上步驟不全，但最終證明了：是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的形式寫出了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 （2） 識別該文法活前綴的DFA如下圖所示： 共5分（3） 該文法的LR(0)分析表如下： 共5分 狀態(tài)Action表Goto