上海大學(xué)編譯原理試卷(共6頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上一、單項(xiàng)選擇題。1設(shè)x是符號(hào)串，則符號(hào)串的冪運(yùn)算x0 = _ C_ _. A. 1 B. x C. D. Æ2字母表中的因素可以是 _ D_ _. A. 字母 B. 字母、數(shù)字 C. 數(shù)字 D. 字母、數(shù)字和其它符號(hào)3設(shè)文法GS = (S, B, b, S bB | b, B bS, S), 則該文法所描述的語言是 C _ _.A. L(GS) = bn | n 0 B. L(GS) = b2n | n 0C. L(GS) = b2n+1 | n 0 D. L(GS) = b2n+1 | n 14一個(gè)句型最左邊的 C _ _稱為該句型的句柄.A. 短語 B.

2、 素短語 C. 直接短語 D. 規(guī)范短語5語法分析方法中，遞歸下降分析法屬于 B _ _.A. 自左至右 B. 自上而下 C. 自下而上 D. 自右至左6通常程序設(shè)計(jì)語言的詞法規(guī)則可用正規(guī)式描述，詞法分析器可用 B _ _描述.A. 語法樹 B. 有窮自動(dòng)機(jī) C. 棧 D. 堆7自下而上語法分析的原理是 B _ _.A. “移進(jìn)推導(dǎo)法” B. “移進(jìn)歸約法” C. “最左推導(dǎo)法” D. “推導(dǎo)歸約法”8算法優(yōu)先文法從左向右掃描輸入串，當(dāng)棧頂出現(xiàn) D _時(shí)進(jìn)行歸約.A. 素短語 B. 直接短語 C. 句柄 D. 最左素短語9LR語法分析棧中存放的狀態(tài)是識(shí)別文法規(guī)范句型 B _ _的DFA狀態(tài).A

3、. 前綴 B. 活前綴 C. 項(xiàng)目 D. 句柄10中綴表達(dá)式-a + b * (-c + d )的逆波蘭式是 A _ _.A. abcd+*+ B. abcd+*+ C. abcd+*+ D. abcd+*+二、是非判斷題正確的在題后的括號(hào)內(nèi)填T，錯(cuò)誤的填F1. 描述一個(gè)語言的文法是惟一的。 （ F ）2. 用二義性文法定義的語言也是二義的。 （ F ）3. 若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn)為兩者是等價(jià)的。 （ T ）4. 有窮自動(dòng)機(jī)的初態(tài)和終態(tài)是可區(qū)別的。 （ T ）5. 算法優(yōu)先分析方法屬于自上而下的分析方法。 （ F ）6. SLR(1)文法是二義性文法。 （ F ）7. 轉(zhuǎn)移語句是

4、基本塊的入口語句。 （ F ）8. 堆式存儲(chǔ)分配屬于靜態(tài)存儲(chǔ)分配。 （ F ）9. 跟蹤嵌套過程語言的每個(gè)外層過程的最新活動(dòng)過程的記錄，常用的辦法有在過程活動(dòng)記錄中增設(shè)存取鏈，或者建立一張嵌套層次顯示表Display表。 （ T ）10. 符號(hào)表可以輔助語法錯(cuò)誤檢查。 （ T ）三、（本題滿分10分）構(gòu)造正規(guī)式1(0|1)*101相應(yīng)的DFA.解：NFA如下：（4分，每錯(cuò)1處扣1分，扣完4分為止）確定化（4分，每錯(cuò)1處扣1分，扣完4分為止）I (標(biāo)記)I0I1X 0A 1A 1 A 1A,B 2A,B 2A,C 3A,B 2A,C 3A 1A,B,Y 4A,B,Y 4A,C 3A,B 2I0

5、= -Closure(move(I, 0)I1 = -Closure(move(I, 1)DFA： （2分，每錯(cuò)1處扣1分，扣完2分為止）四、（本題滿分15分）對(duì)文法GSS a|Ù|(T)T T,S|S 進(jìn)行改寫，消除左遞歸。經(jīng)改寫后的文法是否是LL(1)文法？證明之。【解】（10分，每錯(cuò)1處扣1分，扣完10分為止）改寫文法為：0) S->a 1) S-> 2) S->( T ) 3) T->S T 4) T->, S T 5) T->FIRST(S)=a,(FIRST(T)=a,(FIRST(T)=,FOLLOW(S)= #,)FOLLOW(T)

6、= )FOLLOW(T)= )（5分，每錯(cuò)1處扣1分，扣完5分為止）SELECT(S->a)=aSELECT(S->)=SELECT(S->( T )=( SELECT(S->a)SELECT(S->)SELECT(S->( T ) = fSELECT(T->, S T)=,SELECT(T->)=FOLLOW(T)= ) SELECT(T->, S T)SELECT(T->) = f相同左部符號(hào)產(chǎn)生式的SELECT集的交集為空，從而判斷該文法是LL(1)文法五、（本題滿分5分）已知一個(gè)算符優(yōu)先文法GS的優(yōu)先關(guān)系表如下：算符優(yōu)先關(guān)系表

7、aÙ(),#a·>·>·>Ù·>·>·>(<·<·<·=·<·)·>·>·>,<·<·<··>·>#<·<·<·=·給出輸入串(a, a)#的算符優(yōu)先分析過程，并說明該輸入串是否是該文法的一個(gè)句子。解：（4分，每錯(cuò)一處扣0.

8、5分，扣完4分為止）對(duì)輸入串為(a, a)#的算符優(yōu)先分析過程步驟棧優(yōu)先關(guān)系當(dāng)前符號(hào)剩余輸入串移進(jìn)/歸約1#<·（a,a)#移進(jìn)2#(<·a,a)#移進(jìn)3#(a·>,a)#歸約4#(N<·,a)#移進(jìn)5#(N,<·a)#移進(jìn)6#(N,a·>)#歸約7#(N, N·>)#歸約8#(N=·)#移進(jìn)9#(N）·>#歸約10#N=·#接受輸入串為(a, a)是該文法的一個(gè)句子。（1分）六、下列文法是否為SLR(1)文法？（要求構(gòu)造相應(yīng)的分析表，說明理由）S

9、 à Sab | bRR à S | a解：(a)該文法的拓廣文法G為：（3分） (0) Sà S(1) S à Sab (2) S à bR(3) R à S (4) R à a其LR(0)項(xiàng)目集規(guī)范族如下: （4分，每錯(cuò)一處扣1分，4分扣完為止） I0 : S à S· I3 : S à Sa·b S à ·SabI4 : S à bR· S à ·bRI5 : R à S·S à S

10、3;ab I1 : S à S·I6 : R à a· S à S·ab I2 : S à b·RI7 : S à Sab· R à ·S R à ·a S à ·Sab S à ·bR文法G的識(shí)別活前綴的DFA如下所示：（4分，每錯(cuò)一處扣1分，4分扣完為止）構(gòu)造的SLR分析表如下：（5分，每錯(cuò)一處扣1分，5分扣完為止）狀態(tài) actiongotoab#SR0S211S3acc2S6S2543S74r2r25r3/S3

11、r36r4r47r1r1觀察分析表，對(duì)狀態(tài)5，可歸納又可移進(jìn)，存在重定義的入口，移進(jìn)-歸約沖突。（2分）FOLLOW(S) = FOLLOW(R) = a, #，又FOLLOW(S)a=a。所以，該文法不是SLR(1)文法。（2分）七、（本題滿分10分）將下面語句翻譯成四元式序列（假設(shè)四元式起始標(biāo)號(hào)為100）。if y<0 and x>1 then y:=y+x else y:=y-x.【解】每錯(cuò)一處扣1分，扣完10分為止100 if y<0 goto 102101 goto 107102 if x>1 goto 104103 goto 101104 t:=y+x105 y:=t106 goto 109107 t:=y-x108 y:=t109八、（本題滿分10分）對(duì)于基本塊PS0 := 2S1 := 3 / S0 S2 := T CS3 := T + CR := S0 / S3H := RS4 := 3 / S1 S5 := T + CS6 := S4 / S5