上海大學(xué)編譯原理試卷秋B_7271

1、優(yōu)秀學(xué)習(xí)資料歡迎下載一、選擇題（本題共 22 分，每小題 2 分）將一個或多個正確答案的編號填入每題題干中的橫線上。錯選、多選、少選均不得分。1.詞法分析階段的任務(wù)是_ B_.A. 識別表達(dá)式B. 識別單詞C. 識別語句D. 識別程序2.設(shè) A 是字母表，則 A *= _BCD_.A. A1 A2 A nB. A 0 A 1 A 2 A nC. A +D. A0A+3. 設(shè)文法 GA 的規(guī)則為： A A1 | A0 | Aa | Ac | a | b | c, 則下列符號串 _ BCD _是該文法的句子 .A.ab0B.a0c01C.aaaD.bc104.如果在推導(dǎo)過程中的任何一步都是對 中的

2、最右非終結(jié)符進(jìn)行替換， 則稱這種推導(dǎo)為_BD _.A.直接推導(dǎo)B.最右推導(dǎo)C.最左推導(dǎo)D. 規(guī)范推導(dǎo)5. 程序設(shè)計語言的單詞符號一般可分為5 種，它們是ACD_ _及運算符和界符 .A.常數(shù)B.表達(dá)式C. 基本字D.標(biāo)識符6. 正規(guī)式 (a | b)(a | b | 0| 1 )* 對應(yīng)的文法為C_ _.A.S aA | bAB.S aA | bAA 0A | 1A | A aA | bA | 0A | 1AC.S aA | bAD.S AA aA | bA | 0A | 1A | A A | bA |0A | 1A | 7. 通常程序設(shè)計語言的單詞符號都能用AC_描述.A.正規(guī)文法B.上下文

3、無關(guān)文法C.正規(guī)式D. 上下文有關(guān)文法8. 如果文法 G 中沒有形如 A BC的規(guī)則， 其中 A,B,C 是非終結(jié)符， 則文法 G 是 D _ _.A.算法優(yōu)先文法B.LL(1) 文法C.LR(0) 文法D.算法文法9. 文法 GE:E E+T|TT T*F|FF (E) | a則句型 T + T * F + aA.aB.的素短語是 T * FABC.T_.D.T+T*F10. LR(0) 分析器的核心部分是一張分析表，它包括兩部分，分別是A.LL(1) 分析表B.分析動作表C.狀態(tài)轉(zhuǎn)換表BC_ _.D.移進(jìn)分析表優(yōu)秀學(xué)習(xí)資料歡迎下載11. LR(0) 項目集規(guī)范族的項目類型可分為ABCD_

4、_.A.移進(jìn)項目B.歸約項目C.待約項目D.接受項目二、是非判斷題（本題共10 分，每小題1 分）正確的在題后的括號內(nèi)填T，錯誤的填F1.在形式語言中， 最右推導(dǎo)的逆過程也稱為規(guī)范過程。（ T ）2.每個直接短語都是某規(guī)則的右部。（ T ）3.任何正規(guī)文法都是上下文無關(guān)文法。（ T ）4.一張狀態(tài)轉(zhuǎn)換圖包含有限個狀態(tài)，其中一個被認(rèn)為是初態(tài)，最多有一個終態(tài)。（ F ）5.無左遞歸的文法是 LL(1) 文法。（ F ）6.LR 分析法是一種規(guī)范歸約分析法。（ T ）7.文法符號的屬性有兩種， 即繼承屬性和綜合屬性。（ T ）8.緊跟在條件轉(zhuǎn)移語句后的語句是基本塊的入口語句。（ T ）9. PL0

5、程序具有分程序結(jié)構(gòu)、過程可嵌套且支持遞歸調(diào)用。（ T ）10. 符號表可以輔助上下文語義正確性檢查。（ T ）三、（本題滿分10 分）為正規(guī)式 (a|b)* a(a|b)構(gòu)造一個確定的有窮自動機(jī)DFA 。（1）構(gòu)造 NFA 如圖 2.1 所示：（ 4 分）aSABaaCZbb圖 2.1 NFA N（ 2） NFA 確定化為 DFA 的過程如下表所示： （ 4 分）表 2：NFA 確定為 DFA 的過程（并換名）IIaIb S, A, B A, B, C A, B A, B, C A, B, C, Z A, B, Z A, B A, B, C A, B A, B, C, Z A, B, C, Z

6、 A, B, Z A, B, Z A, B, C A, B（ 3）相應(yīng)的 DFA 狀態(tài)土如圖2.2 所示：（ 2 分）優(yōu)秀學(xué)習(xí)資料歡迎下載aa2a1abb3bb圖2.2DFA Ma4b5四、（本題滿分18 分）對文法 GSS (L) | aL L,S|S（ 1）給出句子 (a, (a, a), (a, a)的一個最右推導(dǎo)（ 4 分）；（ 2）對文法 G，消除左遞歸，使之成為LL(1) 文法，并加以驗證（6 分）。（ 3）構(gòu)造這個 LL(1) 文法的預(yù)測分析表（4 分）。（ 4）用預(yù)測分析器給出輸入串 (a,(a,a)的分析過程， 并說明該串是否是G 的句子（4分）。【解答】（ 1）最右推導(dǎo)為：

7、 （ 4 分）S(L)(L,S)(L,(L)(L,(L,S)(L,(L,(L)(L,(L,(L,S)(L,(L,(L,a)(L,(L,(S,a) (L,(L,(a,a) (L,(S,(a,a)(L,(L),(a,a)(L,(L,S),(a,a)(L,(L,a),(a,a)(L,(S,a),(a,a)(L,(a,a),(a,a)(S,(a,a),(a,a)(a,(a,a),(a,a)（ 2）將所給文法消除左遞歸得G： （6 分）S(L) | aLSLL,SL |求出能推出 的非終結(jié)符SLL 否否是求 First 集FIRST(S) = ( , aFIRST(L) = ( , a FIRST(L

8、) = , , 優(yōu)秀學(xué)習(xí)資料歡迎下載 求 Follow集FOLLOW(S) = FIRST(L ) FOLLOW(L)FOLLOW(L) = )FOLLOW(L ) = FOLLOW(L)所以有，F(xiàn)OLLOW(S) = = , , )FOLLOW(L) = )FOLLOW(L ) = ) 求 Select 集Select(S(L) ) = (Select(Sa) = aSelect(S(L) ) Select(S a) =Select(LS L ) = ( , a Select(L,S L) = ,Select(L ) = FOLLOW(L) = )Select(L ,S L) Select(

9、L ) =所以，該文法是LL(1) 文法。（ 3）構(gòu)造預(yù)測分析表 ： （4 分）a(),#Sa (L)LSL SL L ,SL（ 4）對符號串 (a,(a,a)的分析過程如下： （ 4 分）步驟分析棧剩余輸入串所用產(chǎn)生式1#S(a,(a,a)S (L)2#)L(a,(a,a)匹配3#)La,(a,a)L SL4#) LSa,(a,a)Sa5#) Laa,(a,a)匹配6#) L,(a,a)L ,SL7#)L S,(a,a)匹配8#)L S(a,a)S (L)9#) L)L(a,a)匹配10#)L )La,a)L SL11#) L) LSa,a)Sa12#) L) Laa,a)匹配13#) L)

10、 L,a)L ,SL14#) L) LS,a)匹配15#)L )LSa)Sa16#) L) Laa)匹配優(yōu)秀學(xué)習(xí)資料歡迎下載17#) L) L)L 18#) L)匹配19#) L)L 20#)匹配21#接受所以符號串 (a,(a,a)是該文法的句子。五、（本題滿分15 分）證明下面文法不是LR(0) 文法，但是SLR(1) 文法。S AA Ab | bBaB aAc | a | aAb【解答】該文發(fā)的拓廣文法如下：（8 分）(0) SS(1) S A(2) A Ab(3) A bBa(4) B aAc(5) B a(6) B aAb構(gòu)造識別該文法活前綴的有限自動機(jī)DFA ：I0 ：SSAA&#

11、183;A Ab·A bBa·aI 3 ： A b Ba·B ·aAc B a·B aAb·S I1：SS ·A I2 ：S A· A A ·bB I 5 ： A bB ·aaI 6 ： B a Ac·B a ·bB a Ab·A Ab·A bBa·b I 4 ：A Ab ·aI 7 ： A bBa ·I 9： B aAc ·cI8 ： B aA ·cAB aA ·bbA A ·bI10

12、 ：B aAb ·A Ab ·優(yōu)秀學(xué)習(xí)資料歡迎下載3 分）I 2， I 6 存在移進(jìn) -歸約沖突。I 10 存在歸約 -歸約沖突。 該文法不是LR(0) 文法。（4 分）對于狀態(tài)I 2：FOLLOW(S) = #。FOLLOW(S) b =，所以此狀態(tài)的沖突可以通過SLR(1) 方法消除。對于狀態(tài)I 6：FOLLOW(B)= a 。 FOLLOW(B) b =，所以此狀態(tài)的沖突也可以通過SLR(1) 方法消除。對于狀態(tài)I 10：FOLLOW(B) = a。 FOLLOW(A) = b,c,#。 FOLLOW(A) FOLLOW(B) =，所以此狀態(tài)的沖突也可以通過SLR(1

13、) 方法消除。 該文法是SLR(1) 文法。六、（本題滿分15 分）已知文法 GS 為：S a | (T)T T,S|S(1) 計算 GS 的 FIRSTVT ， LASTVT.(2)構(gòu)造 GS 的算符優(yōu)先關(guān)系表并說明GS 是否為算符優(yōu)先文法。【解答】(1) （5 分）將文法改寫成 :S#S#S a | (T)S T,S|S用簡單關(guān)系圖方法求非終結(jié)符號的FIRSTVT， LASTVT如下：FIRSTVT(S ) = # FIRSTVT(S) = a, (FIRSTVT(T) = a, (, LASTVT(S ) = # LASTVT(S) = a, )LASTVT(T) = a, ), (2)

14、（8 分）算符優(yōu)先關(guān)系表a(),#a·>· >· >優(yōu)秀學(xué)習(xí)資料歡迎下載·>· >· >(<·<·<·=·<·)·>· >· >,<·<·<··>· >#<·<·<·=·因為該文法的任意兩個終結(jié)符之間最多只有一種優(yōu)先關(guān)系，所以該文法是算符優(yōu)先文法（2分）。七、（本題滿分10 分）將下面語句翻譯成四元式序列（假設(shè)四元式起始標(biāo)號為100）。While A or B<