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

1、一、選擇題（本題共22分，每小題2分）將一個(gè)或多個(gè)正確答案的編號(hào)填入每題題干中的橫線上。錯(cuò)選、多選、少選均不得分。1. 詞法分析階段的任務(wù)是_ B_ _.A. 識(shí)別表達(dá)式 B. 識(shí)別單詞 C. 識(shí)別語(yǔ)句D. 識(shí)別程序2. 設(shè)A是字母表，則A* = _BCD _ _. A. A1A2An B. A0A1A2An C. A+ D. A0A+3. 設(shè)文法GA的規(guī)則為：AA1 | A0 | Aa | Ac | a | b | c, 則下列符號(hào)串_ BCD_是該文法的句子. A. ab0 B. a0c01 C. aaa D. bc104.如果在推導(dǎo)過(guò)程中的任何一步 Þ 都是對(duì)中的最右非終結(jié)符進(jìn)

2、行替換，則稱這種推導(dǎo)為_(kāi) BD_ _. A. 直接推導(dǎo) B. 最右推導(dǎo) C. 最左推導(dǎo) D. 規(guī)范推導(dǎo)5. 程序設(shè)計(jì)語(yǔ)言的單詞符號(hào)一般可分為5種，它們是 ACD _ _及運(yùn)算符和界符.A. 常數(shù) B. 表達(dá)式 C. 基本字 D. 標(biāo)識(shí)符6. 正規(guī)式(a | b)(a | b | 0 | 1 )*對(duì)應(yīng)的文法為 C _ _.A. S aA | bA B. S aA | bAA 0A | 1A | A aA | bA | 0A | 1A C. S aA | bA D. S AA aA | bA | 0A | 1A | A A | bA |0A | 1A | 7. 通常程序設(shè)計(jì)語(yǔ)言的單詞符號(hào)都能用 A

3、C _ _描述.A. 正規(guī)文法 B. 上下文無(wú)關(guān)文法 C. 正規(guī)式 D. 上下文有關(guān)文法8. 如果文法G中沒(méi)有形如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 + a 的素短語(yǔ)是 AB _.A. a B. T * F C. T D. T + T * F10. LR(0)分析器的核心部分是一張分析表，它包括兩部分，分別是 BC _ _.A. LL(1)分析表 B. 分析動(dòng)作表 C. 狀態(tài)轉(zhuǎn)換表

4、D. 移進(jìn)分析表11. LR(0)項(xiàng)目集規(guī)范族的項(xiàng)目類型可分為 ABCD _ _.A. 移進(jìn)項(xiàng)目 B. 歸約項(xiàng)目 C. 待約項(xiàng)目 D. 接受項(xiàng)目二、是非判斷題（本題共10分，每小題1分）正確的在題后的括號(hào)內(nèi)填T，錯(cuò)誤的填F1. 在形式語(yǔ)言中，最右推導(dǎo)的逆過(guò)程也稱為規(guī)范過(guò)程。 （ T ）2. 每個(gè)直接短語(yǔ)都是某規(guī)則的右部。 （ T ）3. 任何正規(guī)文法都是上下文無(wú)關(guān)文法。 （ T ）4. 一張狀態(tài)轉(zhuǎn)換圖包含有限個(gè)狀態(tài)，其中一個(gè)被認(rèn)為是初態(tài)，最多有一個(gè)終態(tài)。 （ F ）5. 無(wú)左遞歸的文法是LL(1)文法。 （ F ）6. LR分析法是一種規(guī)范歸約分析法。 （ T ）7. 文法符號(hào)的屬性有兩種，即

5、繼承屬性和綜合屬性。 （ T ）8. 緊跟在條件轉(zhuǎn)移語(yǔ)句后的語(yǔ)句是基本塊的入口語(yǔ)句。 （ T ）9. PL0程序具有分程序結(jié)構(gòu)、過(guò)程可嵌套且支持遞歸調(diào)用。 （ T ）10. 符號(hào)表可以輔助上下文語(yǔ)義正確性檢查。 （ T ）三、（本題滿分10分）為正規(guī)式構(gòu)造一個(gè)確定的有窮自動(dòng)機(jī)DFA。（1）構(gòu)造NFA如圖2.1所示：（4分）（2）NFA確定化為DFA的過(guò)程如下表所示：（4分）表2：NFA確定為DFA的過(guò)程（并換名）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,

6、Z A, B, Z A, B, Z A, B, C A, B （3）相應(yīng)的DFA狀態(tài)土如圖2.2所示：（2分）四、（本題滿分18分）對(duì)文法GSS (L) | aL L, S | S（1） 給出句子(a, (a, a), (a, a)的一個(gè)最右推導(dǎo)（4分）；（2） 對(duì)文法G，消除左遞歸，使之成為L(zhǎng)L(1)文法，并加以驗(yàn)證（6分）。（3） 構(gòu)造這個(gè)LL(1)文法的預(yù)測(cè)分析表（4分）。（4） 用預(yù)測(cè)分析器給出輸入串(a,(a,a)的分析過(guò)程，并說(shuō)明該串是否是G的句子（4分）?！窘獯稹浚?） 最右推導(dǎo)為：（4分）（2） 將所給文法消除左遞歸得G： （6分） 求出能推出的非終結(jié)符SLL否否是 求Firs

7、t集FIRST(S) = ( , a FIRST(L) = ( , a FIRST(L) = , , 求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(Sa) = ÆSelect(LS L) = ( , a Select(L,S L) = ,Select(L ) = FOLLOW(

8、L) = )Select(L,S L)Select(L ) = Æ所以，該文法是LL(1)文法。（3） 構(gòu)造預(yù)測(cè)分析表： （4分） a(),#Sa(L)LS LS LL,S L（4） 對(duì)符號(hào)串(a,(a,a)的分析過(guò)程如下：（4分）步驟分析棧剩余輸入串所用產(chǎn)生式1#S(a,(a,a)S(L)2#)L(a,(a,a)匹配3#)La,(a,a)LS4#)Sa,(a,a)Sa5#)aa,(a,a)匹配6#),(a,a),S7#)S,(a,a)匹配8#)S(a,a)S(L)9#)L(a,a)匹配10#)La,a)LS11#)Sa,a)Sa12#)aa,a)匹配13#),a),S14#)S,a

9、)匹配15#)Sa)Sa16#)aa)匹配17#)18#)匹配19#)20#)匹配21#接受所以符號(hào)串(a,(a,a)是該文法的句子。五、（本題滿分15分）證明下面文法不是LR(0)文法，但是SLR(1)文法。S AA Ab | bBaB aAc | a | aAb【解答】該文發(fā)的拓廣文法如下： （8分）(0) S´ S(1) S A(2) A Ab(3) A bBa(4) B aAc(5) B a(6) B aAb構(gòu)造識(shí)別該文法活前綴的有限自動(dòng)機(jī)DFA： 3分）I2，I6存在移進(jìn)-歸約沖突。I10存在歸約-歸約沖突。 該文法不是LR(0)文法。（4分）對(duì)于狀態(tài)I2：FOLLOW(S

10、) = #。FOLLOW(S)b = Æ，所以此狀態(tài)的沖突可以通過(guò)SLR(1)方法消除。對(duì)于狀態(tài)I6：FOLLOW(B) = a。FOLLOW(B)b = Æ，所以此狀態(tài)的沖突也可以通過(guò)SLR(1)方法消除。對(duì)于狀態(tài)I10：FOLLOW(B) = a。FOLLOW(A) = b,c,#。FOLLOW(A)FOLLOW(B) = Æ，所以此狀態(tài)的沖突也可以通過(guò)SLR(1)方法消除。 該文法是SLR(1)文法。六、（本題滿分15分）已知文法GS為：S a | Ù | (T)T T, S | S(1) 計(jì)算GS的FIRSTVT，LASTVT.(2) 構(gòu)造GS的

11、算符優(yōu)先關(guān)系表并說(shuō)明GS是否為算符優(yōu)先文法。【解答】 (1) （5分）將文法改寫(xiě)成:S #S#S a |Ù | (T)S T, S | S用簡(jiǎn)單關(guān)系圖方法求非終結(jié)符號(hào)的FIRSTVT，LASTVT如下：FIRSTVT(S) = # FIRSTVT(S) = a, Ù, ( FIRSTVT(T) = a, Ù, (, , LASTVT(S) = # LASTVT(S) = a, Ù, )LASTVT(T) = a, Ù, ), , (2) （8分）算符優(yōu)先關(guān)系表aÙ(),#a·>·>·>&

12、#217;·>·>·>(<·<·<·=·<·)·>·>·>,<·<·<··>·>#<·<·<·=·因?yàn)樵撐姆ǖ娜我鈨蓚€(gè)終結(jié)符之間最多只有一種優(yōu)先關(guān)系，所以該文法是算符優(yōu)先文法（2分）。七、（本題滿分10分）將下面語(yǔ)句翻譯成四元式序列（假設(shè)四元式起始標(biāo)號(hào)為100）。While A or B<D do if (x<6) then x := x-1 else y := x+1【解答】(10分）100 if A goto 104101 goto