資源描述：
《上海大學編譯原理試卷秋b》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、一、選擇題（本題共22分，每小題2分）將一個或多個正確答案的編號填入每題題干中的橫線上。錯選、多選、少選均不得分。1.詞法分析階段的任務(wù)是__B___.A.識別表達式B.識別單詞C.識別語句D.識別程序2.設(shè)A是字母表，則A*=__BCD___.A.A1∪A2∪…∪An∪…B.A0∪A1∪A2∪…∪An∪…C.{ε}∪A+D.A0∪A+3.設(shè)文法G[A]的規(guī)則為：A→A1
2、A0
3、Aa
4、Ac
5、a
6、b
7、c,則下列符號串__BCD__是該文法的句子.A.ab0B.a0c01C.aaaD.bc104..如果在推導過程中的任何一步αTβ都是對
8、α中的最右非終結(jié)符進行替換，則稱這種推導為__BD___.A.直接推導B.最右推導C.最左推導D.規(guī)范推導5.程序設(shè)計語言的單詞符號一般可分為5種，它們是ACD__及運算符和界符.A.常數(shù)B.表達式C.基本字D.標識符6.正規(guī)式(a
9、b)(a
10、b
11、0
12、1)*對應(yīng)的文法為C__.A.S→aA
13、bAB.S→aA
14、bAA→0A
15、1A
16、εA→aA
17、bA
18、0A
19、1AC.S→aA
20、bAD.S→AA→aA
21、bA
22、0A
23、1A
24、εA→A
25、bA
26、0A
27、1A
28、ε7.通常程序設(shè)計語言的單詞符號都能用AC__描述.A.正規(guī)文法B.上下文無關(guān)文法C.正規(guī)式D.
29、上下文有關(guān)文法8.如果文法G中沒有形如A→…BC…的規(guī)則，其中A,B,C是非終結(jié)符，則文法G是D__.A.算法優(yōu)先文法B.LL(1)文法C.LR(0)文法D.算法文法9.文法G[E]:E→E+T
30、TT→T*F
31、FF→(E)
32、a則句型T+T*F+a的素短語是AB_.A.aB.T*FC.TD.T+T*F10.LR(0)分析器的核心部分是一張分析表，它包括兩部分，分別是BC__.A.LL(1)分析表B.分析動作表C.狀態(tài)轉(zhuǎn)換表D.移進分析表11.LR(0)項目集規(guī)范族的項目類型可分為ABCD__.A.移進項目B.歸約項目C.待約項目D.接
33、受項目二、是非判斷題（本題共10分，每小題1分）正確的在題后的括號內(nèi)填T，錯誤的填F1.在形式語言中，最右推導的逆過程也稱為規(guī)范過程。（T）2.每個直接短語都是某規(guī)則的右部。（T）3.任何正規(guī)文法都是上下文無關(guān)文法。（T）4.一張狀態(tài)轉(zhuǎn)換圖包含有限個狀態(tài)，其中一個被認為是初態(tài)，最多有一個終態(tài)。（F）5.無左遞歸的文法是LL(1)文法。（F）6.LR分析法是一種規(guī)范歸約分析法。（T）7.文法符號的屬性有兩種，即繼承屬性和綜合屬性。（T）8.緊跟在條件轉(zhuǎn)移語句后的語句是基本塊的入口語句。（T）9.PL0程序具有分程序結(jié)構(gòu)、過程可嵌套且支
34、持遞歸調(diào)用。（T）10.符號表可以輔助上下文語義正確性檢查。（T）三、（本題滿分10分）為正規(guī)式構(gòu)造一個確定的有窮自動機DFA。（1）構(gòu)造NFA如圖2.1所示：（4分）（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]⑤[A,B,Z]⑤[A,B,Z]②[A,B,C]③[A,B]（3）相應(yīng)的DFA狀態(tài)土如圖2.
35、2所示：（2分）四、（本題滿分18分）對文法G[S]S→(L)
36、aL→L,S
37、S（1）給出句子(a,((a,a),(a,a)))的一個最右推導（4分）；（2）對文法G，消除左遞歸，使之成為LL(1)文法，并加以驗證（6分）。（3）構(gòu)造這個LL(1)文法的預(yù)測分析表（4分）。（4）用預(yù)測分析器給出輸入串(a,(a,a))＃的分析過程，并說明該串是否是G的句子（4分）?！窘獯稹浚?）最右推導為：（4分）（2）將所給文法消除左遞歸得G’：（6分）①求出能推出ε的非終結(jié)符SLL′否否是②求First集FIRST(S)={(,a}FIRST(
38、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(S→a)={a}Select(S→(L))∩Select(S→a)=?Select(L→SL′)={(,a}Select(L′→,SL′)={,}Select(L′→ε)=FO
39、LLOW(L′)={)}Select(L′→,SL′)∩Select(L′→ε)=?所以，該文法是LL(1)文法。（1）構(gòu)造預(yù)測分析表’：（4分）a(),#S→a→(L)L→SL′→SL′L′→ε→,SL′（2）對符號串(a,(a,a
