編譯原理習題解答

1、第二章：習題2-4 Table表var x,y;procedure p; var a; procedure q; var b; begin b:=10; end; procedure s; var c,d; procedure r; var e,f; begin call q; end; begin call r; end; begin call s; end;begin call p;end根據(jù)：Page289，變量table:array0.txmax of record 結構體以及block函數(shù)得到下表，而表中各部分的含義，見教材Page18,Page19NameKinkVal /Leve

2、lAdrSizexvariable030yvariable040pprocedur010avariable130qprocedur134sprocedur170cvariable230dvariable240rprocedur200第三章 文法和語言5. 寫一文法，使其語言是偶正整數(shù)的集合要求：(1) 允許0打頭(2) 不允許0打頭解：(1) GS=(S,P,D,N,0,1,2,9,P,S)P:SàPD|DP->NP|NDà0|2|4|6|8N->0|1|2|3|4|5|6|7|8|9(2) GS=(S,P,R,D,N,Q ,0,1,2,9,P,S)P:S

3、24;PD|P0|DP->NR|NR->QR|QDà2|4|6|8N->1|2|3|4|5|6|7|8|9Q->0|1|2|3|4|5|6|7|8|96. 已知文法G：<表達式>:=<項>|<表達式>+<項>|<表達式>-<項><項>:=<因子>|<項>*<因子>|<項>/<因子><因子>:=(<表達式>)|i。試給出下述表達式的推導及語法樹。(1)i; (2)(i)(3)i*i;(4)i*i+

4、i; (5)i+(i+i);(6)i+i*i。解：(1) v=<表達式>=><項>=><因子>=>i=w(2) v=<表達式>=><項>=><因子>=>(<表達式>)=>(<項>)=>(<因子>)=>(i)=w(3) v=<表達式>=><項>=><項>*<因子>=><因子>*<因子>=>i*i=w(4) v=<表達式>=>

5、<表達式>+<項>=><項>+<項>=><項>*<因子>+<項>=><因子>*<因子>+<因子>=>i*i+i=w(5) v=<表達式>=><表達式>+<項>=><項>+<項>=><因子>+<因子>=>i+(<表達式>)=> i+(<表達式>+<項>)=>i+(<項>+<項>

6、)=> i+(<因子>+<因子>)=>i+(i+i)=w(6) v=<表達式>=><表達式>+<項>=><項>+<項>=><因子>+<項>=>i+<項>=>i+<項>*<因子>=> i+<因子>*<因子>=> i+i*i=w語法樹見下圖:7. 為句子i+i*i構造兩棵語法樹，從而證明下述文法G<表達式>是二義的。<表達式><項><因子

7、>i<表達式><項><因子>( <表達式> )<項><因子>i<表達式><項><項> * <因子><因子>ii<表達式><表達式> + <項><項><項> * <因子><因子>ii<因子>i<表達式><表達式> + <項><項><因子>i<因子>( <表達式> )<表達式&g

8、t; + <項><項><因子>i<因子>i<表達式><表達式> + <項><項><因子>i<項> * <因子><因子>ii(1)i(2)(i)(3)i*i(4) i*i+i(5) i+(i+i)(6) i+i*i<表達式>:=i|(<表達式>)|<表達式><運算符><表達式><運算符>:=+|-|*|/解：為句子i+i*i構造的兩棵語法樹如下：<表達式><表達式&

9、gt; + <表達式>i<表達式> * <表達式>ii<表達式><表達式> * <表達式><表達式> + <表達式>iii所以，該文法是二義的。8. 習題1中的文法GS是二義的嗎？為什么？答：是二義的。因為對于句子abc可以有兩種不同的生成樹，即：S=>Ac=>abc和S=>aB=>abc11. 令文法GE為：EàT|E+T|E-TTàF|T*F|T/FFà(E)|i證明E+T*F是它的一個句型，指出這個句型的所有短語、直接短語和句柄。解：可為E

10、+T*F構造一棵語法樹（見下圖），所以它是句型。EE + TT * F從語法樹中容易看出，E+T*F的短語有：T*F是句型E+T*F的相對于T的短語，也是相對于規(guī)則TàT*F的直接短語。E+T*F是句型E+T*F的相對于E的短語。句型E+T*F的句柄（最左直接短語）是T*F。12. 下述文法GE生成的語言是什么？給出該文法的一個句子，該句子至少含五個終結符，構造該句子的語法樹。證明：<E><T><F><MOP><POP>是G<E>的句型，并指出該句型的所有短語、直接短語和句柄。<E>à<

11、;E><T><POP>|<T><T>à<T><F><MOP>|<F><F>àa|b|c<POP>à+|-<MOP>à*|/解：(1)計算文法GE的語言：由于L(T)=(a|b|c)(a|b|c)(*|/)n|n>=0所以L(E)=L(T)(L(T)(+|-)n|n>=0(2)該文法的一個句子是aab*+,它的語法樹是：<E><E> <T> <POP><T

12、> <F> <MOP><T><F>a<F>ab*+(3) 證明：<E><T><F><MOP><POP>是G<E>的句型，并指出該句型的所有短語、直接短語和句柄。由于下面的語法樹可以生成<E><T><F><MOP><POP>，所以它是G<E>的句型。<E><E> <T> <POP><T> <F> <MOP>

13、由于<E> => <E><T><POP>,且<T> => <T><F><MOP>,所以<T><F><MOP>是句型<E><T><F><MOP><POP>相對于<T>的短語，也是相對于規(guī)則<T> à <T><F><MOP>的直接短語。由于<E> => <E> 且<E> => &l

14、t;E><T><F><MOP><POP>,所以<E><T><F><MOP><POP>是句型<E><T><F><MOP><POP>相對于<E>的短語。顯然，句型<E><T><F><MOP><POP>的句柄是<T><F><MOP>。14. 給出生成下述語言的上下文無關文法：（1）anbnambm|n,m>=0（2）

15、1n0m1m0n|n,m>=0（3）WaWt|W屬于0|a*,W表示W(wǎng)t的逆解：（1）所求文法為GS=(S,A,a,b,P,S),其中P為：SàAAAàaAb|（2）所求文法為GS=(S,A,0,1,P,S),其中P為：Sà1S0|AAà0A1|（3）W屬于0|a*是指W可以的取值為,0,a,00,a0,aa0,00aa,a0a0,如果W=aa0a00,則Wt=00a0aa。所求文法為GS=(S,P,Q,0,a,P,S),其中P為：Sà0S0|aSa|a15. 語言WaW和anbmcndm是上下文無關的嗎？能看出它們反映程序設計語言的什么

16、特性嗎？答：生成語言WaW的文法非常簡單，如GS: SàWaWWàaW|bW|可見GS是上下文無關的。生成語言anbmcndm的文法非常復雜，用上下文無關文法不可能辦到，只能用上下文有關文法。這是因為要在ancn的中間插入bm而同時要在其后面插入dm。即a,c相關聯(lián)，b,d相關聯(lián)。這說明對語言的限定越多（特別是語言中的符號前后關聯(lián)越多），生成它的文法越復雜，甚至于很難找到一個上下文法無關文法。16給出生成下述語言的三型文法：(1)an|n>=0(2)anbm|n,m>=1(3)anbmck|n,m,k>=0解：(1) 生成的3型文法是：GS：Sà

17、aS|(2) 生成的2型文法是：GS: SàABAàaA|aBàbB|b生成的3型文法是：GS：SàaPPàaP|bDDàbD|(3) 生成的2型文法是：GS: SàABCAàaA|BàbB|C->cC|生成的3型方法是：GS：AàaA|bB|cC|BàbB|cC|CàcC|第四章 詞法分析1構造下列正規(guī)式相應的DFA：(1) 1(0|1)* 101(2) 1(1010* | 1(010)* 1)* 0(3) a(a|b)*|ab*a)* b(4) b(ab)* | b

18、b)* ab解：(1)1(0|1)* 101對應的NFA為01231104110下表由子集法將NFA轉換為DFA：II0 = -closure(MoveTo(I,0)I1 = -closure(MoveTo(I,1)A0B1B1B1C1,2C1,2D1,3C1,2D1,3B1E1,4E1,4B1B1ABCD110E11000,11(2)1(1010* | 1(010)* 1)* 0對應的NFA為02451101010361079810011下表由子集法將NFA轉換為DFA：II0 = -closure(MoveTo(I,0)I1 = -closure(MoveTo(I,1)A0B1,6B1,6

19、C10D2,5,7C10D2,5,7E3,8B1,6E3,8F1,4,6,9F1,4,6,9G1,2,5,6,9,10D2,5,7G1,2,5,6,9,10H1,3,6,9,10I1,2,5,6,7H1,3,6,9,10J1,6,9,10K2,4,5,7I1,2,5,6,7L3,8,10I1,2,5,6,7J1,6,9,10J1,6,9,10D2,5,7K2,4,5,7M2,3,5,8B1,6L3,8,10F1,4,6,9M2,3,5,8N3F1,4,6,9N3O4O4P2,5P2,5N3B1,6AB1C0D1E01F101H0G1I0K1J10L01M0011NOP011001(3)a(a|

20、b)*|ab*a)* b (略)(4)b(ab)* | bb)* ab (略)2已知NFA=（x,y,z,0,1,M,x,z）其中：M(x,0)=z,M(y,0)=x,y,M(z,0)=x,z,M(x,1)=x, M(y,1)=,M(z,1)=y,構造相應的DFA。xy0z010010解：根據(jù)題意有NFA圖如下下表由子集法將NFA轉換為DFA：II0 = -closure(MoveTo(I,0)I1 = -closure(MoveTo(I,1)AxBzAxBzCx,zDyCx,zCx,zEx,yDyEx,yEx,yFx,y,zAxFx,y,zFx,y,zEx,y01100BCEF00DA110

21、1下面將該DFA最小化：(1) 首先將它的狀態(tài)集分成兩個子集：P1=A,D,E,P2=B,C,F(2) 區(qū)分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等價。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等價（見下步），從而B與C，F(xiàn)可以區(qū)分。有P21=C,F,P22=B。(3) 區(qū)分P1:由于A，E輸入0到終態(tài)，而D輸入0不到終態(tài)，所以D與A，E可以區(qū)分，有P11=A,E,P12=D。(4) 由于F(A,0)=B,F(E,0)=F,而B，F(xiàn)不等價，所以A，E可以區(qū)分。(5) 綜上所述，DFA可以區(qū)分為P=A，

22、B，D，E，C，F(xiàn)。所以最小化的DFA如下：11010F0BE10DA03.將圖4.16確定化：S0，1Z1V11U0Q0，1001圖4.16解：下表由子集法將NFA轉換為DFA：II0 = -closure(MoveTo(I,0)I1 = -closure(MoveTo(I,1)ASBQ,VCQ,UBQ,VDV,ZCQ,UCQ,UEVFQ,U,ZDV,ZGZGZEVGZFQ,U,ZDV,ZFQ,U,ZGZGZGZAGDB0，10C110E010F010，14.把圖4.17的(a)和(b)分別確定化和最小化：12435bbbbaaa0abaab01aa,ba(a) (b)解：(a):下表由子集

23、法將NFA轉換為DFA：IIa = -closure(MoveTo(I,a)Ib = -closure(MoveTo(I,b)A0B0,1C1B0,1B0,1C1C1A0可得圖（a1），由于F(A,b)=F(B,b)=C,并且F(A,a)=F(B,a)=B,所以A,B等價，可將DFA最小化，即：刪除B，將原來引向B的引線引向與其等價的狀態(tài)A，有圖(a2)。（DFA的最小化，也可看作將上表中的B全部替換為A，然后刪除B所在的行。）AabCaBbaAbCaa（a1）確定化的DFA （a2）最小化的DFA（b）:該圖已經(jīng)是DFA。下面將該DFA最小化：(6) 首先將它的狀態(tài)集分成兩個子集：P1=0,

24、P2=1,2,3,4,5(7) 區(qū)分P2：由于F(4,a)=0屬于終態(tài)集，而其他狀態(tài)輸入a后都是非終態(tài)集，所以區(qū)分P2如下：P21=4,P22=1,2,3,5。(8) 區(qū)分P22:由于F(1,b)=F(5,b)=4屬于P21,而F(2,b)與F(3,b)不等于4,即不屬于P21，所以區(qū)分P22如下：P221=1,5,P222=2,3。(9) 區(qū)分P221:由于F(1,b)=F(5,b)=4,即F(1,a)=1,F(5,a)=5,所以1,5等價。(10) 區(qū)分P222:由于F(2,a)=1屬于P221，而F(3,a)=3屬于P222,所以2，3可區(qū)分。P222區(qū)分為P22212，P22223。1

25、243bbaa0abaabb(11) 結論：該DFA的狀態(tài)集可分為：P= 0,1,5,2,3,4 ,其中1,5等價。刪去狀態(tài)5，將原來引向5的引線引向與其等價的狀態(tài)1，有圖(b1)。(b1)最小化的DFA5構造一個DFA，它接收=0，1上所有滿足如下條件的字符串：每個1都有0直接跟在右邊。然后再構造該語言的正則文法。解：根據(jù)題意，DFA所對應的正規(guī)式應為：(0|(10)*。所以，接收該串的NFA如下：012100下表由子集法將NFA轉換為DFA：II0 = -closure(MoveTo(I,0)I1 = -closure(MoveTo(I,1)A0B0,2C1B0,2B0,2C1C1B0,2

26、11000BCA顯然，A，B等價，所以將上述DFA最小化后有：0C1A0對應的正規(guī)文法為：GA：Aà1C|0A|Cà0A6設無符號數(shù)的正規(guī)式為：=dd*|dd*.dd*|.dd*|dd*e(s|)dd*|e(s|)dd*|.dd*e(s|)dd*|dd*.dd*e(s|)dd* 化簡,畫出的DFA，其中d=0,1,2,9,s=+,-解：把原正規(guī)式的每2，3項，4，5項，6，7項分別合并后化簡有：=dd*|d*.dd*|d*e(s|)dd*|d*.dd*e(s|)dd*=dd*|d*.dd*|(d*|d*.dd*)e(s|)dd*=(|d*.|(d*|d*.dd*)e(s|)

27、dd*=(|d*.|d*(|.dd*)e(s|)dd*下面構造化簡后的對應的NFA：57ed421.3dd6sdd.0 下表由子集法將NFA轉換為DFA：IId =-closure(MoveTo(I,d)Ie=-closure(MoveTo(I,e)Is=-closure(MoveTo(I,s)I.=-closure(MoveTo(I,.)A0,1,4,6B1,7C5,6D2,6B1,7B1,7D2,6C5,6E7F6D2,6G3,4,7E7E7F6E7G3,4,7G3,4,7C5,6ED.ddCGdBd.AeesFddd7給文法GS：SàaA|bQAàaA|bB|bB&#

28、224;bD|aQQàaQ|bD|bDàbB|aAEàaB|bFFàbD|aE|b構造相應的最小的DFA。解：由于從S出發(fā)任何輸入串都不能到達狀態(tài)E和F，所以，狀態(tài)E，F(xiàn)為多余的狀態(tài)，不予考慮。這樣，可以寫出文法GS對應的NFA：aZSADQBbbbababbbaa下表由子集法將NFA轉換為DFA：IIa = -closure(MoveTo(I,a)Ib = -closure(MoveTo(I,b)1S2A3Q2A2A4B,Z3Q3Q5D,Z4B,Z3Q6D5D,Z2A7B6D2A7B7B3Q6D由上表可知：(1)因為4，5是DFA的終態(tài)，其他是非終態(tài)，

29、可將狀態(tài)集分成兩個子集：P1=1，2，3，6，7，P2=4，5 (2)在P1中因為2,3輸入b后是終態(tài)，而1，6，7輸入b后是非終態(tài)，所以P1可區(qū)分為：P11=1，6，7，P12=2，3 (3)在P11中由于1輸入b后為3，6輸入b后為7，而3，7分屬P11和P12，所以1與6不等價，同理，1與7不等價。所以P11可區(qū)分為：P111=1，P112=6，7(4)查看P112=6，7，由于輸入a后為2，3，所以6，7是否等價由2，3是否等價決定。(5)查看P12=2，3，由于輸入b后為4，5，所以2，3是否等價由4，5是否等價決定。(6)查看P2=4，5 ， 顯然4，5是否等價由2，3與6，7是否

30、同時等價決定。由于有（4）即6，7是否等價由2，3是否等價決定，所以，4，5是否等價由2，3是否等價決定。由于有（5）即2，3是否等價由4，5是否等價決定，所以有4，5等價，2，3等價,進而6，7也等價。(7)刪除上表中的第3，5，7行，并將剩余行中的3，5，7分別改為對應的等價狀態(tài)為2，4，6有下表：IIa Ib 1S2A2A2A2A4B,Z4B,Z2A6D6D2A6D這樣可得最小化的DFA如下：a41b2aaabb6b8給出下述文法所對應的正規(guī)式：Sà0A|1BAà1S|1Bà0S|0解：把后兩個產生式代入第一個產生式有：S=01|01SS=10|10S有:S

31、=01S|10S|01|10=(01|10)S|(01|10)=(01|10)*(01|10)即:(01|10)*(01|10)為所求的正規(guī)式。9將圖4.18的DFA最小化，并用正規(guī)式描述它所識別的語言：a72bcbdb134c6aabbd5b圖 4.18解：(1) 因為6，7是DFA的終態(tài)，其他是非終態(tài)，可將狀態(tài)集分成兩個子集：P1=1，2，3，4，5，P2=6，7。(2) 由于F(6,b)=F(7,b)=6,而6，7又沒有其他輸入，所以6，7等價。(3) 由于F(3,c)=F(4,c)=3,F(3,d)=F(4,d)=5,F(3,b)=6,F(4,b)=7,而6，7等價，所以3,4等價。(

32、4) 由于F(1,b)=F(2,b)=2,F(1,a)=3,F(2,a)=4,而3，4等價，所以1,2等價。(5) 由于狀態(tài)5沒有輸入字符b,所以與1，2，3，4都不等價。(6) 綜上所述，上圖DFA的狀態(tài)可最細分解為：P=1，2，3，4，5，6，7。abb13c6bd5a該DFA用正規(guī)式表示為：b*a(c|da)*bb*10構造下述文法GS的自動機：SàA0AàA0|S1|0該自動機是確定的嗎？若不確定，則對它確定化。該自動機相應的語言是什么？解：由于該文法的產生式SàA0，AàA0|S1中沒有字符集VT的輸入，所以不是確定的自動機。要將其他確定化，必

33、須先用代入法得到它對應的正規(guī)式。把SàA0代入產生式AàS1有：A=A0|A01|0=A(0|01)|0=0(0|01)*。代入SàA0有該文法的正規(guī)式：0(0|01)*0，所以，改寫該文法為確定的自動機為：0WX0Z00Y1由于狀態(tài)A有3次輸入0的重復輸入，所以上圖只是NFA，下面將它確定化：下表由子集法將NFA轉換為DFA：II0 = -closure(MoveTo(I,0)Ib = -closure(MoveTo(I,1)AWBXBXCX,Y,ZCX,Y,ZCX,Y,ZBX100CBA0由上表可知DFA為：第五章 自頂向下語法分析方法1對文法GSSà

34、;a|(T)TàT,S|S(1) 給出(a,(a,a)和(a,a),(a),a)的最左推導。(2) 對文法G，進行改寫，然后對每個非終結符寫出不帶回溯的遞歸子程序。(3) 經(jīng)改寫后的文法是否是LL(1)的？給出它的預測分析表。(4) 給出輸入串(a,a)#的分析過程，并說明該串是否為G的句子。解：(1) (a,(a,a)的最左推導為Sà(T)à(T,S)à(S,S)à(a,(T)à(a,(T,S)à(a,(S,a)à(a,(a,a)(a,a),(a),a)的最左推導為Sà(T)à(T,S)

35、24;(S,a)à(T),a)à(T,S),a)à(T,S,S),a)à(S,(T),a)à(T),(S),a) à(T,S),(a),a)à(S,a),(a),a)à(a,a),(a),a)(2)由于有TàT,S的產生式，所以消除該產生式的左遞歸，增中一個非終結符U有新的文法G/S:Sàa|(T)TàSUUà，SU|分析子程序的構造方法對滿足條件的文法按如下方法構造相應的語法分析子程序。(1) 對于每個非終結號U，編寫一個相應的子程序P(U)；(2) 對于規(guī)則U:=x1|x

36、2|.|xn,有一個關于U的子程序P(U),P(U)按如下方法構造：IF CH IN FIRST(x1) THEN P(x1)ELSE IF CH IN FIRST(x2) THEN P(x2)ELSE .IF CH IN FIRST(xn) THEN P(xn)ELSE ERROR其中，CH存放當前的輸入符號，是一個全程變量；ERROR是一段處理出錯信息的程序；P(xj)為相應的子程序。(3) 對于符號串x=y1y2.yn;p(x)的含義為：BEGIN P(y1);P(y2);.P(yn);END如果yi是非終結符，則P(yi)代表調用處理yi的子程序；如果yi是終結符，則P(yi)為形如下

37、述語句的一段子程序IF CH=yi THEN READ(CH) ELSE ERROR即如果當前文法中的符號與輸入符號匹配，則繼續(xù)讀入下一個待輸入符號到CH中，否則表明出錯。(4) 如果文法中有空規(guī)則U:=EPSILON,則算法中的語句IF CH IN FIRST(xn) THEN P(xn)ELSE ERROR改寫為：IF CH IN FIRST(xn) THEN P(xn)ELSE IF CH IN FOLLOW(U) THEN RETURN ERROR(5) 要分析一個OrgStr,應在該串的后面加上一個串括號'#',并從子程序P(S)(S為文法的開始符號)開始，如果中途沒

38、有產生錯誤，并且最后CH='#',則說明OrgStr串合法，否則該串不合法。對每個非終結符寫出不帶回溯的遞歸子程序如下：char CH;/存放當前的輸入符號void P_S()/非終結符S的子程序if(CH=a) READ(CH);/產生式Sàaelse if(CH=) READ(CH);/產生式Sàelse if(CH=()/產生式Sà(T)READ(CH);P_T();IF (CH=) THEN READ(CH) else ERRORelse ERR;void P_T()/非終結符S的子程序if(IsIn(CH,FIRST_SU) /FIRST

39、_SU為TàSU的右部的FIRST集合P_S();P_U();void P_U()/非終結符U的子程序if(CH=,)/產生式Uà，SUREAD(CH);P_S();P_U();else/產生式Uàif(IsIn(CH,FOLLOW_U) /FOLLOW_U為U的FOLLOW集合return ;else ERR;(3)判斷文法G/S是否為LL(1)文法。各非終結符的FIRST集合如下：FIRST(S)=a,（FIRST(T)=FIRST(S)=a,（FIRST(U)=，,各非終結符的FOLLOW集合如下：FOLLOW(S)=# FIRST(U) FOLLOW(T)

40、 FOLLOW(U)=#,，,)FOLLOW(T)=)FOLLOW(U)=FOLLOW(T)=)每個產生式的SELECT集合如下：SELECT(Sàa)=aSELECT(Sà)=SELECT(Sà(T)=(SELECT(TàSU)=FIRST(S)=a,（SELECT(Uà，SU)=，SELECT(Uà)=FOLLOW(U)=)可見，相同左部產生式的SELECT集的交集均為空，所以文法G/S是LL(1)文法。文法G/S的預測分析表如下：a()，#Sàaàà(T)TàSUàSUà

41、;SUUàà，SU(5) 給出輸入串(a,a)#的分析過程步驟分析棧剩余輸入串所用產生式123456789101112#S#)T(#)T#)US#)Ua#)U#)US,#)US#)Ua#)U#)#(a,a)#(a,a)#a,a)#a,a)#a,a)#,a)#,a)#a)#a)#)#)#Sà(T)( 匹配TàSUSàaa匹配Uà，SU,匹配Sàaa匹配Uà)匹配接受2對下面的文法G：EàTE/E/à+E|TàFT/T/àT|FàPF/F/à*F/|P

42、4;(E)|a|b|(1) 計算這個文法的每個非終結符的FIRST集和FOLLOW集。(2) 證明這個方法是LL(1)的。(3) 構造它的預測分析表。(4) 構造它的遞歸下降分析程序。解：（1）計算這個文法的每個非終結符的FIRST集和FOLLOW集。FIRST集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,;FIRST(E/)=+,FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,;FIRST(T/)=FIRST(T)=(,a,b,;FIRST(F)=FIRST(P)=(,a,b,;FIRST(F/)=FIRST(P)=*,;FIR

43、ST(P)=(,a,b,;FOLLOW集合有：FOLLOW(E)=),#;FOLLOW(E/)=FOLLOW(E)=),#;FOLLOW(T)=FIRST(E/)FOLLOW(E)=+,),#;/不包含F(xiàn)OLLOW(T/)=FOLLOW(T)=FIRST(E/)FOLLOW(E)=+,),#;FOLLOW(F)=FIRST(T/)FOLLOW(T)=(,a,b,+,),#;/不包含F(xiàn)OLLOW(F/)=FOLLOW(F)=FIRST(T/)FOLLOW(T)=(,a,b,+,),#;FOLLOW(P)=FIRST(F/)FOLLOW(F)=*,(,a,b,+,),#;/不包含(2)證明這個方法

44、是LL(1)的。各產生式的SELECT集合有：SELECT(EàTE/)=FIRST(T)=(,a,b,;SELECT(E/à+E)=+;SELECT(E/à)=FOLLOW(E/)=),#SELECT(TàFT/)=FIRST(F)=(,a,b,;SELECT(T/àT)=FIRST(T)=(,a,b,;SELECT(T/à)=FOLLOW(T/)=+,),#;SELECT(FàPF/)=FIRST(P)=(,a,b,;SELECT(F/à*F/)=*;SELECT(F/à)=FOLLOW(F/)=(,

45、a,b,+,),#;SELECT(Pà(E)=(SELECT(Pàa)=aSELECT(Pàb)=bSELECT(Pà)=可見，相同左部產生式的SELECT集的交集均為空，所以文法GE是LL(1)文法。(3)構造它的預測分析表。文法GE的預測分析表如下：+*()ab#EàTE/àTE/àTE/àTE/E/à+EààTàFT/àFT/àFT/àFT/T/ààTààTàTàTàF&

46、#224;PF/àPF/àPF/àPF/F/àà*F/ààààààPà(E)àaàbà(4)構造它的遞歸下降分析程序。對每個非終結符寫出不帶回溯的遞歸子程序如下：char CH;/存放當前的輸入符號void P_E()/非終結符E的子程序if(IsIn(CH,FIRST_TEP) /FIRST_TEP為TàTE/ 的右部的FIRST集合，產生式EàTE/P_T();P_EP();else ERR;void P_EP()/非終結

47、符E/的子程序if(CH=+) /產生式E/à+EREAD(CH);P_E();else/產生式E/àif(IsIn(CH,FOLLOW_EP) /FOLLOW_EP為E/的FOLLOW集合return ;else ERR;void P_T()/非終結符T的子程序if(IsIn(CH,FIRST_FTP) /FIRST_TEP為TàFT/ 的右部的FIRST集合，產生式TàFT/P_F();P_TP();else ERR;void P_TP()/非終結符T/的子程序if(IsIn(CH,FIRST_T) /FIRST_T為產生式T/àT 的右部

48、的FIRST集合，產生式T/àTP_T();else/產生式T/àif(IsIn(CH,FOLLOW_TP) /FOLLOW_TP為T/的FOLLOW集合return ;else ERR;void P_F()/非終結符F的子程序if(IsIn(CH,FIRST_PFP) /FIRST_PFP為FàPF/ 的右部的FIRST集合，產生式FàPF/ P_P();P_FP();else ERR;void P_FP()/非終結符F/的子程序if(CH=*) /產生式F/à*F/READ(CH);P_FP();else/產生式F/àif(IsI

49、n(CH,FOLLOW_FP) /FOLLOW_FP為F/的FOLLOW集合return ;else ERR;void P_P()/非終結符P的子程序if(CH=()READ(CH);P_E();if(CH=) READCH(CH);elseERR;else if(CH=a) READ(CH);else if(CH=b) READ(CH);else if(CH=) READ(CH);else ERR;3已知文法GS：SàMH|aHàLSo|KàdML|LàeHfMàK|bLM判斷G是否是LL（1）文法，如果是，構造LL（1）分析表。解：首先求各

50、非終結符的FIRST集合：FIRST(S)=aFIRST(M)FIRST(H)=ab,d,e,=a,b,d,e,;FIRST(H)=FIRST(L)=e,;FIRST(K)=d,;FIRST(L)=e;FIRST(M)=FIRST(K)b=b,d,;然后求非終結符的FOLLOW集合：FOLLOW(S)=o,#FOLLOW(H)=FOLLOW(S)f=f,o,#FOLLOW(K)=FOLLOW(M)=FIRST(H)FOLLOW(S)=e,o,#;/不包含F(xiàn)OLLOW(L)=FIRST(S)oFOLLOW(K)FIRST(M)FOLLOW(M)=a,b,d,e,o,#FOLLOW(M)=a,b,

51、d,e,o,#;/不包含F(xiàn)OLLOW(M)=FIRST(L)FIRST(H)FOLLOW(S)=e,o,#/不包含最后求各產生式的SELECT集合：SELECT(SàMH)=(FIRST(MH)-)FOLLOW(S)=b,d,eo,#=b,d,e,o,#;SELECT(Sàa)=aSELECT(HàLSo)=eSELECT(Hà)=FOLLOW(H)=f,o,#SELECT(KàdML)=dSELECT(Kà)=FOLLOW(K)=e,o,#SELECT(LàeHf)=eSELECT(MàK)=(FIRST(K)-)FOLLOW(M)=d,e,o,#SELECT(MàbLM)=b可見，相同左部產生式的SELECT集的交集均為空，所以文法GS是LL(1)文法。文法GE的預測分析表如下：aodefb#SàaàMHàMHàMHàMHàMHHààLSoààKààdMLààLàeHfMàKàKàKàbLM