編譯原理期末復習題

1、3.2 是非判斷，對下面的陳述，正確的在陳述后的括號內(nèi)寫T，否則寫F。(1)有窮自動機接受的語言是正則語言。（）(2)若r1和r2是上的正規(guī)式，則r1|r2也是。（）(3)設M是一個NFA，并且L(M)x,y,z，則M的狀態(tài)數(shù)至少為4個。（） (4)令a,b，則上所有以b為首的字構(gòu)成的正規(guī)集的正規(guī)式為b*(a|b)*。（）(5)對任何一個NFA M，都存在一個DFA M'，使得L(M')=L(M)。（）(6)對一個右線性文法G，必存在一個左線性文法G'，使得L(G)=L(G')，反之亦然。（）答案(1)  T   

2、; (2)  T   (3)  F(4)  F    (5)  T    (6) T3.3 描述下列各正規(guī)表達式所表示的語言。(1) 0(0|1)*0(2) (|0)1*)*(3) (0|1)*0(0|1)(0|1)(4) 0*10*10*10*(5) (00|11)*(01|10)(00|11)*(01|10)(00|11)*)*答案(1) 以0開頭并且以0結(jié)尾的，由0和1組成的符號串

3、。(2) |0,1*(3) 由0和1組成的符號串，且從右邊開始數(shù)第3位為0。(4) 含3個1的由0和1組成的符號串。  |0,1+，且中含有3個1 (5) |0,1*,中0和1為偶數(shù)3.4 對于下列語言分別寫出它們的正規(guī)表達式。 (1) 英文字母組成的所有符號串，要求符號串中順序包含五個元音。(2) 英文字母組成的所有符號串，要求符號串中的字母依照詞典順序排列。 (3) =0,1上的含偶數(shù)個1的所有串。(4) =0,1上的含奇數(shù)個1的所有串。(5) 具有偶數(shù)個0和奇數(shù)個1的有0和1組成

4、的符號串的全體。(6) 不包含子串011的由0和1組成的符號串的全體。(7) 由0和1組成的符號串,把它看成二進制數(shù)，能被3整除的符號串的全體。答案(1) 令Letter表示除這五個元音外的其它字母。   (letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter)*(2) A*B*.Z*(3) (0|10*1)*(4) (0|10*1)*1(5) 分析設S是符合要求的串，|S|=2k+1 (k0）。則 SS10|S21，|S1|=2k (

5、k>0），|S2|=2k (k0）。且S1是0,1上的串，含有奇數(shù)個0和奇數(shù)個1。 S2是0,1上的串，含有偶數(shù)個0和偶數(shù)個1。考慮有一個自動機M1接受S1，那么自動機M1如下：和L(M1)等價的正規(guī)表達式，即S1為：(00|11)|(01|10)(00|11)*(01|10)*(01|10)(00|11)*類似的考慮有一個自動機M2接受S2，那么自動機M2如下：和L(M2)等價的正規(guī)表達式，即S2為：(00|11)|(01|10)(00|11)*(01|10)*因此，S為：(00|11)|(01|10)(00|11)*(01|10)*(01|10)(00|11)*0|(00|

6、11)|(01|10)(00|11)*(01|10)*1(6)1*|1*0(0|10)*(1|)(7)接受w的自動機如下：對應的正規(guī)表達式：(1(01*0)1|0)*3.6 給出接受下列在字母表0,1上的語言的DFA。(1) 所有以00結(jié)束的符號串的集合。(2) 所有具有3個0的符號串的集合。答案(a) DFA M=(0，1，q0，q1，q2，q0，q2，)其中定義如下:（q0，0）=q1     （q0，1）=q0（q1，0）=q2     （q1，1）=q0（q2，0）=

7、q2     （q2，1）=q0(b)正則表達式: 1*01*01*01* DFA M=(0，1，q0，q1，q2，q3，q0，q3，)其中定義如下:（q0，0）=q1     （q0，1）=q0（q1，0）=q2     （q1，1）=q1（q2，0）=q3     （q2，1）=q2（q3，1）=q3     3.7構(gòu)造等價于下列正規(guī)表達式的有限自動機。(1)10|（0|11）0*1

8、(2)(0|1)*|(11)*答案(1) DFA M=(0，1，q0，q1，q2，q3，q0，q3，)其中定義如下:(2) （q0，0）=q1     （q0，1）=q2(3) （q1，0）=q1     （q1，1）=q3(4) （q2，0）=q3     （q2，1）=q1(5) (6) (2) DFA M=(0，1，q0，q0，q0，)(7) 其中定義如下:(8) （q0，0）=q0     （q0，1）=q0

9、(9)3.8 給定右線性文法G：S->0S|1S|1A|0BA->1C|1B->0C|0C->0C|1C|0|1試求一個于G等價的左線性文法G'3.9 試對于下列正規(guī)表達式使用證明定理3。5的構(gòu)造算法構(gòu)造非確定的有限自動機。請給出每個自動機在處理輸入符號串a(chǎn)babbab的過程中的動作序列。(1) (a|b)*(2) (a*|b*)*(3) (|a)b*)* 3.10 轉(zhuǎn)換練習3.9中的每個 NFA 為 DFA 。并給出每個DFA在處理輸入符號串a(chǎn)babbab的過程中的動作序列。3.11 試把練習3.10中得到的DFA的狀態(tài)給以最小化。答案(1),(2),(3)的

10、DFA M相同，化簡結(jié)果為：(4)3.12 我們可以證明兩個正規(guī)表達式是等價的，如果它們的最小狀態(tài)DFA是相同的（除了狀態(tài)的名字以外）。利用這一結(jié)論，請說明下列正規(guī)表達式都是等價的。(1) (a|b)*(2) (a*|b*)*(3) (|a)b*)*答案根據(jù)3.11的結(jié)果知這幾個正規(guī)表達式是等價的。3.13 對于下列正規(guī)表達式構(gòu)造最小狀態(tài)的DFA。(1) (a|b)*a(a|b)(2) (a)b)*a(a|b)(a|b)5對如下文法：GS ：S à a b S | a a B | a d B à b b B | b 分別給出句子abaabbb和ad的句柄 句子ad的語法分析

11、樹為：S a d句子abaabbb的語法分析樹為:SabSaaB b b B b所以句子abaabbb的句柄是b；句子ad的句柄是ad .二、（10分）說明如下文法是否是LL（1）文法，若不是，將其轉(zhuǎn)換為LL（1）文法。最后給出該文法的LL（1）分析表。 GA：A à B e B à B b | a 文法中有左遞歸，不是LL(1)文法。 轉(zhuǎn)換為 G ： Aà B e Bà a B Bàb B | Predict(Aà B e) = a Predict(Bà a B) = a Predict(Bàb B) = b P

12、redict(Bà ) = e LL(1)分析表: a b e A à B e B à a B B à b Bà 4. 給出識別正則表達式(（a|bc）*d)+的NFA 。 5已知文法GS：S S；GG G G(T) HH a (S)T T+S S找出句型：a(T+S)；H；(S)的短語、簡單短語和句柄。 短語: a, T+S, a(T+S) , H , a(T+S);H , (S) 簡單短語：a , T+S , H , (S) 句柄是 a . 6已知文法GS為：SAB | bC Ab | BaD | CAD | b DaS | c 對其每一個

13、非終級符求First集和Follow集。 First (S) = b , a , First (A) = b , First (B) = a , First (C) = b , a , c First (D) = a , c Follow (S) = # Follow (A) = a , c , # Follow (B) = # Follow (C) = # Follow (D) = # 二、（10分）設有文法GA: A ® iB*e B ® SB|e S ® eC|.i C ® eC|e判定該文法是否為LL(1)文法？若是則給出它的LL(1)分析表，否

14、則說明理由。 先計算各個產(chǎn)生式的Predict集： Predict (A-> iB*e)= i ; Predict (B-> SB) = , . Predict (B->e ) = * Predict (S->eC) = Predict (S->. i) = . Predict (C-> eC) = e Predict (C->e ) = 因為Predict集沒有沖突，所以是LL(1)文法。 LL(1)分析表如下： i * e . A-> iB*e -> e B ->S B ->S B S ->e C ->. i C

15、 ->eC -> e1、證明下面文法是LL(1)的但不是SLR(1)文法SAaAb|BbBa A B解：對于產(chǎn)生式SAaAb|BbBa 來說FIRST(AaAb)FIRST(BbBa)=ab=而A，BVN僅有一條候選式。因此，這個文法是LL(1)的。 下面構(gòu)造這個文法的識別活前綴的DFA。系 專業(yè) 班級 學號 姓名 密封線I0 = S'·S, S·AaAb, S·BbBa, A·, B· I1 = S'S·I2 = SA·aAbI3 = SB·bBaI4 = SAa·Ab, A

16、·I5 = SBb·Ba, B·I6 = SAaA·bI7 = SBbB·aI8 = SAaAb·I9 = SBbBa·由于FOLLOW(A)=FOLLOW(B)=a, b因此項目集I0中存在歸約歸約沖突。在I0狀態(tài)下，當輸入符號是a或是b時，不知用A還是B進行歸約。故此文法不是SLR(1)的。但是，此文法是LR(1)的。 五、已知文法GS，其產(chǎn)生式如下： S(L)|a L L，S|S 從GS中消除左遞歸，并為之構(gòu)造一個非遞歸預測分析器LL(1)分析表。請說明在句子(a，(a，a)上的分析器的動作。（20分）解：將所給文法消

17、除左遞歸得G'： S (L)|a L SL' L' ，SL' | 實現(xiàn)預測分析器的不含遞歸調(diào)用的一種有效方法是使用一張分析表和一個棧進行聯(lián)合控制，下面構(gòu)造預測分析表：根據(jù)文法G'有FIRST(s) = ( , a )FOLLOW(S) = , ', ' , $ FIRST(L) = ( , a )FOLLOW(L) = FIRST(L) = ', ' FOLLOW(L) = 按以上結(jié)果，構(gòu)造預測分析表M如下： 文法G是LL(1)的，因為它的LL(1)分析表不含多重定義入口。 預測分析器對輸入符號串(a, (a, a)做出的

18、分析動作如下： 例5.3的文法G3S 為：SaASdAbASA不難看出由定義5.3可得：SELECT(SaA)=aSELECT(Sd)=dSELECT(AbAS)=bSELECT(A)=a,d,# 所以 SELECT(SaA)SELECT(Sd)=ad= SELECT(AbAS)SELECT(A)=ba,d,# =由定義5.4知例5.3文法是LL(1)文法，所以可用確定的自頂向下分析。而對例5.5 文法G5S為：SaASSbAbAA則 SELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=a,b所以 SELECT(SaAS)SELECT(Sb)=ab

19、= SELECT(AbA)SELECT(A)=ba,b因此，例5.5文法不是LL(1)文法，因而也就不可能用確定的自頂向下表達式文法為：EE+T|TTT*F|FFi|(E)構(gòu)造步驟：(1) 判斷文法是否為LL(1)文法4.5 已知文法GS，其產(chǎn)生式如下： S(L)|a L L，S|S 從GS中消除左遞歸，并為之構(gòu)造一個非遞歸預測分析器LL(1)分析表。請說明在句子(a，(a，a)上的分析器的動作。解：將所給文法消除左遞歸得G'：        S (L)|a    &

20、#160;   L SL'         L' ，SL' | 實現(xiàn)預測分析器的不含遞歸調(diào)用的一種有效方法是使用一張分析表和一個棧進行聯(lián)合控制，下面構(gòu)造預測分析表：根據(jù)文法G'有FIRST(s) = ( , a )FOLLOW(S) = ) , ', ' , $ FIRST(L) = ( , a )FOLLOW(L) = ) FIRST(L) = ', ' FOLLOW(L) = ) 按以上結(jié)果，構(gòu)造預測分析表M如下：文法

21、G是LL(1)的，因為它的LL(1)分析表不含多重定義入口。預測分析器對輸入符號串(a, (a, a)做出的分析動作如下：4.6 對于練習4.1的文法，構(gòu)造它的LL(1)分析表。解：從練習4.1得到文法的產(chǎn)生式如下：        R R '|' T | T        T TF | F        F F* | C  

22、0;      C (R)| a | b 消除上面文法中的左遞歸R TR' R' '|' TR' | T FT' T' FT' | F CF' F *F' | C (R) | a | b計算FIRST()和FOLLOW(A)構(gòu)造LL(1)分析表。4.9 對于文法GS，其產(chǎn)生式如下S(L)|a (4.22) LL,S|S (1)給出句子(a，(a，a)，(a，a)的一個最右推導，并指出右句型的句柄。 (2)按照(a)的最右推導，說明移進-歸約分析器的工作步驟

23、。解：(1)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

24、,(a,a),(a,a)右句型的句柄為每個右句型中用下劃線標識出的部分。(2) 對于(a)的最右推導，移進規(guī)約分析器的工作步驟如下：4.11 下列文法是否為SLR(1)文法？若是，請構(gòu)造相應的分析表。若不是，請說明理由。(a)SSab|bR RS|a解：該文法的拓廣文法G'為 (0) S' S(1) S Sab(2) S bR(3) R S(4) R a其LR(0)項目集規(guī)范族和goto函數(shù)(識別活前綴的DFA)如下:I0 = S'·S, S·Sab, S·bRI1 = S'S·, SS·abI2 = Sb

25、83;R, R·S, R·a, S·Sab, S·bRI3 = SSa·b I4 = SbR·I5 = RS·, SS·ab I6 = Ra· I7 = SSab·求FOLLOW集：    FOLLOW(S')=    FOLLOW(R)=FOLLOW(S)=a,在I5中，出現(xiàn)移進歸約沖突，且FOLLOW(R)a=a因此，此文法不是SLR(1)文法。b)SaSAB|BA AaA|B Bb 解：該文法的拓廣文法

26、G'為 (0) S' S(1) S aSAB(2) S BA(3) A aA(4) A B(5) B b其LR(0)項目集規(guī)范族和goto函數(shù)(識別活前綴的DFA)如下:I0 = S'·S, S·aSAB, S·BA, B·b I1 = S'S· I2 = Bb· I3 = Sa·SAB, S·aSAB, S·BA, B·b I4 = SB·A, A·aA, A·B, B·bI5 = SaS·AB, A·

27、aA, A·B, B·b I6 = SaSA·B, B·b I7 = Aa·A, A·aA, A·B, B·b I8 = AB· I9 = SBA· I10 = SaSAB·I11 = AaA·求FOLLOW集：    FOLLOW(S')=    FOLLOW(S)=a,b,    FOLLOW(A)=a,b,   &

28、#160;FOLLOW(B)=a,b,4.12 證明下面文法是SLR(1)文法，并構(gòu)造其SLR分析表。EE+T|T TTF|F FF*|a|b解：該文法的拓廣文法G'為 (0) E' E(1) E E+T(2) E T(3) T TF(4) T F(5) F F*(6) F a(7) F b其LR(0)項目集規(guī)范族和goto函數(shù)(識別活前綴的DFA)如下:I0 = E'·E, E·E+T, E·T, T·TF, T·F, F·F*,      

29、0; F·a, F·b I1 = E'E·, EE·+TI2 = ET·, TT·F, F·F*, F·a, F·bI3 = TF·, FF·* I4 = Fa· I5 = Fb· I6 = EE+·T, T·TF, T·F, F·F*, F·a, F·b I7 = TTF·, FF·* I8 = FF*·I9 = EE+T·, TT·F,

30、 F·F*, F·a, F·b求FOLLOW集：    FOLLOW(E)=,     FOLLOW(T)=, , a, bFOLLOW(F)=, , a, b, *構(gòu)造的SLR分析表如下： 顯然，此分析表無多重定義入口，所以此文法是SLR文法。4.13 下面文法屬于哪類LR文法？試構(gòu)造其分析表。S(SR|a R,SR|)解：該文法的拓廣文法G'為 (0) S' S(1) S (SR(2) S a(3) R ,SR(4) R )構(gòu)造其LR(0)項目集規(guī)范族和goto函數(shù)

31、(識別活前綴的DFA)如下:I0 = S'·S, S·(SR, S·aI1 = S'S· I2 = S(·SR, S·(SR, S·a I3 = Sa· I4 = S(S·R, R·,SR, R·)I5 = S(SR· I6 = R)· I7 = R,·SR, S·(SR, S·a I8 = R,S·R, R·,SR, R·) I9 = R,SR·每個LR(0)項目集中沒有沖突。因

32、此，此文法是LR(0)文法。其分析表如下：4.14 設文法G為 SA ABA|BaB|b (1)證明它是LR(1)文法。 (2)構(gòu)造它的LR(1)分析表。 (3)給出輸入符號串a(chǎn)bab的分析過程。解：(1) 構(gòu)造其拓廣文法G'的產(chǎn)生式為 (0) S' S(1) S A(2) A BA(3) A (4) B aB(5) B b構(gòu)造其LR(0)項目集規(guī)范族和goto函數(shù)(識別活前綴的DFA)如下:I0 = S'·S, $, S·A, $, A·BA, $, A·, $,     

33、60;   B·aB, a/b/$, B·b, a/b/$ I1 = S'S·, $ I2 = SA·, $I3 = AB·A, $, A·BA, $, A·, $,        B·aB, a/b/$, B·b, a/b/$I4 = Bb·, a/b/$I5 = Ba·B, a/b/$, B·aB, a/b/$,    B·b

34、, a/b/$I6 = ABA·, $ I7 = BaB·, a/b/$該文法的LR(1)項目集規(guī)范族中沒有沖突，所以該文法是LR(1)文法。(2)構(gòu)造LR(1)分析表如下：以上分析表無多的定義入口，所以該文法為LR(1)文法。(3)對于輸入串a(chǎn)bab，其分析過程如下： 4.15 為下面的文法構(gòu)造LALR(1)分析表SE EE+T|T T(E)|a解：其拓廣文法G'： (0) S' S(1) S E(2) E E+T(3) E T(4) T (E)(5) T a構(gòu)造其LR(1)項目集規(guī)范族和goto函數(shù)(識別活前綴的DFA)如下: I0 = S·S

35、, $, S·E, $, E·E+T, $/+, E·T, $/+, T·(E), $/+, T·a, $/+ I1 = SS·, $ I2 = SE·, $, EE·+T, $/+ I3 = ET·, $/+I4 = T(·E), $/+, E·E+T, )/+, E·T, )/+,  T·(E), )/+, T·a, )/+ I5 = Ta·, $/+ I6 = EE+·T, $/+, T·(E), $

36、/+, T·a, $/+I7 = T(E·), $/+, EE·+T, )/+ I8 = ET·, )/+I9 = T(·E), )/+, E·E+T, )/+, E·T, )/+, T·(E), )/+, T·a, )/+I10 = Ta·, )/+ I11 = EE+T·, $/+ I12 = T(E)·, $/+I13 = EE+·T, )/+, T·(E), )/+, T·a, )/+ I14 = T(E·), )/+, EE&

37、#183;+T, )/+I15 = EE+T·, )/+ I16 = T(E)·, )/+合并同心的LR(1)項目集，得到LALR的項目集和轉(zhuǎn)移函數(shù)如下： I0 = S·S, $, S·E, $, E·E+T, $/+, E·T, $/+, T··(E), $/+, T·a, $/+I1 = SS·, $ I2 = SE·, $, EE·+T, $/+ I3,8 = ET·, $/+/)I4,9 = T(·E), $/+/), E·E+T, )/

38、+, E·T, )/+,  T·(E), )/+, T·a, )/+I5,10 = Ta·, $/+/) I6,13 = EE+·T, $/+/), T·(E), $/+/), T·a, $/+/)I7,14 = T(E·), $/+/), EE·+T, )/+ I11,15 = EE+T·, $/+/) I12,16 = T(E) ·, $/+/)LALR分析表如下：br> 4.16 考慮文法GS，其產(chǎn)生式如下SAS | b ASA | a(1)構(gòu)造文法GS的LR(0

39、)項目集規(guī)范族及相應的DFA。(2)如果把每一個LR(0)項目看成一個狀態(tài)，并從每一個形如B·X的狀態(tài)出發(fā)畫一條標識為X的箭弧到狀態(tài)BX·,而且從每一個形如B·A的狀態(tài)出發(fā)畫標記為的箭弧到所有形如A·的狀態(tài)。這樣就得到了一個NFA。說明這個NFA與(a)的DFA是等價的。(3)構(gòu)造文法的SLR分析表。(4)對于輸入串bab，給出SLR分析器所作出的動作。(5)構(gòu)造文法的LR(1)分析表和LALR分析表。解：(1)其拓廣文法G'： (0) S' S(1) S AS(2) S b(3) A SA(4) A a構(gòu)造其LR(0)項目集規(guī)范族和go

40、to函數(shù)(識別活前綴的DFA)如下:I0 = S'·S, S·AS, S·b, A·SA, A·a I1 = S'S·, AS·A, A·SA, A·a, S·AS, S·b I2 = SA·S, S·AS, S·b, A·SA, A·a I3 = A a· I4 = Sb·I5 = ASA·, SA·S, S·AS, S·b, A·SA, A

41、3;a I6 = AS·A, A·SA, A·a, S·AS, S·bI7 = SAS·, AS·A, A·SA, A·a, S·AS, S·b(2) 文法GS的LR(0)項目如下： (0) S' ·S(1) S' S·(2) S ·AS(3) S A·S(4) S AS·(5) S ·b(6) S b·(7) A ·SA(8) A S·A(9) A SA·(10)A &

42、#183;a(11)A a·對上面的NFA通過求-cloasure確定化，得到與(1)相同的識別文法GS活前綴的DFA。因此，此NFA與(1)的DFA等價。(3) 求FOLLOW集：FOLLOW(S) = a, b,     FOLLOW(A) = a, b GS的SLR分析表：(4) 注：GS的SLR分析表中有移進歸約沖突，因此它不是一個SLR文法。其實，GS是一個二義性文法，對于句子abab有下面兩棵不同的分析樹。因此，GS不是任何LR文法。(5) 文法GS的LR(1)項目集規(guī)范族及轉(zhuǎn)移函數(shù)為：I0 = S'·S, $,

43、S·AS, $/a, S·b, $/a, A·SA, a/b, A·a, a/bI1 = S'S·, $, AS·A, a/b, A·SA,a/b, A·a, a/b, S·AS, a/b, S·b, a/bI2 = SA·S, $/a/b, S·AS, $/a/b, S·b, $/a/b, A·SA, a/b, A·a, a/b,I3 = Aa·, a/b I4 = Sb·, a/b/$I5 = AS·A,

44、 a/b, A·SA, a/b, A·a, a/b, S·AS, a/b, S·b, a/b6 = ASA·, a/b, SA·S, a/b, S·AS, a/b, S·b, a/b, A·SA, a/b, A·a, a/bI7 = SAS·, a/b/$, AS·A, a/b, A·SA, a/b, A·a, a/b, S·AS, a/b, S·b, a/bI8 = SA·S, a/b, S·AS, a/b, S·b, a/b, A·SA, a/b, a·a, a/bI9 = SAS·, a/b/$, AS·A, a/b, A·SA, a/b, A·a, a/b, S·AS, a/b, S·b, a/b, I10 = Sb·, a/b合并同心項目集(I2和I8，I7和I9，I4和I10)：I0 =