編譯原理課后答案

1、第二章高級語言及其語法描述1 + 1*24令+、*和f代表加，乘和乘幕，按如下的非標(biāo)準(zhǔn)優(yōu)先級和結(jié)合性質(zhì)的約定，計算 T 2*1 f 2 的值：(1) 優(yōu)先順序(從高至低)為 +, *和f,同級優(yōu)先采用左結(jié)合。(2) 優(yōu)先順序?yàn)閒, +, *，同級優(yōu)先采用右結(jié)合。解：(1) 1 + 1*2 f 2*1 f 2=2*2 f 1*1 f 2=4 f 1 f 2=4 f 2=16(2) 1 + 1*2 f 2*1 f 2=1 + 1*2*1=2*2*1=2*2=46. 令文法G6為N tD|NDDt 0|1|2|3|4|5|6|7|8|9(1) G6的語言L (G6)是什么？(2) 給出句子0127、

2、34和568的最左推導(dǎo)和最右推導(dǎo)。解：(1) L ( G6) =a|a 刀 +,刀= 0,1,2,3,4,5,6,7,8,9(2) N = ND= NDD= NDDD= DDDD= 0DD 01DD= 012D = 0127N=ND=N7 = ND7= N27= ND27=N127 = D127 = 0127N=ND=DD=3D = 34N=ND=N4 = D4 = 34N=ND=NDD= DDD= 5DD=56D = 568N = ND= N8 = ND8= N68 = D68 = 5687 寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以0開頭。解：At SN, S t + |-| 刀,N t

3、 D|MDDT 1|3|5|7|9, Mt MB|1|2|3|4|5|6|7|8|9 B t 0|1|2|3|4|5|6|7|8|98. 文法：E t T E +T|E TTt F T* F|T/ FF (E)|i最左推導(dǎo)：E= E T= T T= F T = i T = i T * F = i F * F = i i * F = i i * iE = T= T* F = F * F = i * F 二 i *( E)二 i *( E T)二 i *( T T)二 i *( F T)= i *( i T)二 i *( i F)二 i *( i i)最右推導(dǎo):E 二 E T= E T* F =

4、E T* i = E F* i= E i *i= T i* i= F i *i= i i*iE= T F*T= F* F= F*( E)二 F *( E T)二 F *( E F)= F *( E i)= F*( T i)二 F*( F i)二 F*( i i)二 i*( i i)語法樹. /*15T T * Fii+i+ii-i-iii+i*i*/9. 證明下面的文法是二義的:St iSeS|iS|l解：因?yàn)閕iiiei有兩種最左推導(dǎo)，所以此文法是二義的。10把下面文法改寫為無二義的：St SS|(S)|() 解：St ST|T, T t (S)|()11.給出下面語言的相應(yīng)文法L1 =an

5、bnci |n 1,i 0L2=ai bncn|n 1,i 0L3=anbnambm|n,m 0L4=1 n0m1 m0n|n,m 0解:(1) 4 AB|AAtaAb|abBtc|cB(2) S t AB|BA t a|aABt bBc|bcS t AB|A|B| 刀At aAb|abBt aBb|abSt 1S0|0A1 at 0A1|01第三章 詞法分析7. 構(gòu)造下列正規(guī)式的相應(yīng)的 DFA1(0|1)*1011(1010*|1(010)*1)*00*10*10*10* (00|11)*(01|10)(00|11)*(01|10)(00|11)*)*解答：(1)1(0|1)*101I0I1

6、X A,B,C B,C B,C B,CB,C,DB,C,EB,C,D,y B,C,E B,CB,C,EA,B,C B,C,D B,C,D B,C,D B,C,D,y B,C,D(2) 1(1010*|1(010)*1)*0XA,B,CA,B,CyD,H,I,LyD,H,I,LE,JB,CE,JB,C,F,G,KB,CyD,H,I,LB,C,F,G,KB,C,G,I,L,yD,H,I,LB,C,G,I,L,yB,C,G,J,yB,C,D,H,I,L B,C,G,J,yB,C,G, yD,H,I,LD,H,I,K,LE,I,J,LB,CE,J,yB,C,F,G,K E,I,J,LJB,C,F,G,

7、K JKII0I1Kl,LI,LJB,C8. 給出下面正規(guī)表達(dá)式(1)以 01 結(jié)尾的二進(jìn)制數(shù)串(2)能被 5 整除的十進(jìn)制整數(shù)(3) 包含奇數(shù)個 1 或者奇數(shù)個 0 的二進(jìn)制數(shù)串(4) 英文字母組成的所有符號串，要求符號串中的字母按照字典序排列。(7)不包含子串a(chǎn)bb的由a和b組成的符號串的全體。解答：( 1)( 0|1 ) *01(2) (1|2| |9)01|2|9) *(0|5)|0|5(3) 0*1(0*10*10*)*(4) A* B* Z*(7) b *(a|ab) *9. 對下面的情況給出DFA以及正規(guī)表達(dá)式。(1) 0，1上的含有子串 010的所有串。(2) 0，1上不含子串

8、 010的所有串。解答：(1)(0|1 ) *010(0|1 ) *(2) 1*(0|1*|1)*1* 12將圖3.8的(a)和(b)分別確定化和最少化。解： 1 確定化a b00,1 10,10,1 110 _令 A= 0B= 0， 1C= 1則狀態(tài)轉(zhuǎn)換圖為：2 最少化首先，所有狀態(tài)可分為 終態(tài)集 A B 非終態(tài)集 CA=A B其次，考察A B,由于A B由a到B，由b到C，所以不可分，令 則最少化后的狀態(tài)轉(zhuǎn)換圖為：14構(gòu)造一個DFA它接受E= 0,1 上所有滿足下列條件的字符串，每個1都有0直接跟在右邊。解：1正規(guī)式為：（0|10 ）*2 由正規(guī)式轉(zhuǎn)化為 NFA：3 由 NFA到 DFA0

9、 1XXbbX_令 A=X B=b 則狀態(tài)轉(zhuǎn)換圖為：4 最少化終態(tài)集 A 非終態(tài)集 B顯然不可再劃分，則最簡的DFA即為:15 給定右線性文法 G：SABC求出一個與t0S|1S|1A|0B t1C|1 t0C|0 t0C|1C|1|0G等價的左線性文法。解： 1 由右線性文法構(gòu)造 NFA：2 從NFA中構(gòu)造左線性文法:FtA1|B0|C0|C1At S1|1Bt S0|0CtC0|C1|A1|B0StS0|S1|1|0第四章 語法分析自上而下分析1. 考慮下面文法 G1:St a| A |(T)T,S|S(1) 消去G1的左遞歸，然后對每個非終結(jié)符寫出不帶回溯的遞歸子程序。(2) 經(jīng)過改寫的

10、文法是否是 LL( 1 )的？給出它的預(yù)測分析表。 解答：(1)消去G1的左遞歸：St a| A |(T)T t STT t ,ST| 遞歸子程序：PROCEDURE S;IF sym= a THEN ADVANCEELSE IF sym= A THEN ADVANCEELSE IF sym= ( THENBEGINADVANCET;IF sym= ) THEN ADVANCE ELSE ERRORENDELSE ERROR;PROCEDURE T;BEGINS;TEND;PROCEDURE S;IF sym= , THENBEGINADVANCES;TEND;2)是 LL( 1)文法。FIR

11、ST(S)= a, A ,( FIRST(T)= a, A ,( FIRST(T )= , FOLLOW(S)= #, , , s , ) FOLLOW(T)= ) FOLLOW(T )= ) 預(yù)測分析表如下：a5A()#SSt aStASt (T)TSTTt stTt stTTt ,STTt 2. 文法：E TEE E | ；T FTT T | ；F PFF ”一； *F | ；P (E)| a |b|A(1)FIRST(E)=(,a,b,AFIRST(E)=+, FIRST(T)=(,a,b,AFIRST(T)=(,a,b,A, FIRST(F)=(,a,b,AFIRST(F)=*, FI

12、RST(P)=(,a,b,AFOLLOW(E)=#,)FOLLOW(E)=#,)FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=(,a,b,A,+,),#FOLLOW(F)=(,a,b,A,+,),#FOLLOW(P)=*,(,a,b,A,+,),#考慮下列產(chǎn)生式：E ，E| ；T TpF *F pP (E)|A|a|bFIRST(+E) A FIRST( )=+ n = $FIRST(+E) A FOLLOW(E)=+ A #,)=$FIRST(T) A FIRST( )=(,a,b,A A = $FIRST(T) A FOLLOW(T)=(,a,b,A A

13、+,),#=$FIRST(*F) A FIRST( )=* A = $FIRST(*F) A FOLLOW(F)=* A (,a,b,A,+,),#=$FIRST(E) n FIRST(a) n FIRST(b) n FIRST(A)= $ 所以,該文法式LL(1)文法.+*()abA#EEt TEEt TEEt TEEt TEEE J+ EE J名E J sTTt FTt FTt FTt FTTTJ gTJ TT J eTJ TTJ TTJ TTJ sFFt PFhFt PLFt PF，F(xiàn)t PFhFF J JFt*FF J eF T EF J FJeF J名F J sPPt (E)Pt a

14、Pt bPt aprocedure E;beginif sym=( or sym=a or sym=b or sym= athe n beg in T; E endelse errorendprocedure E;beginif sym=+the n beg in adva nee; E endelse if sym) and sym# then errorendprocedure T;beginif sym=( or sym=a or sym=b or sym= athe n beg in F; T endelse errorendprocedure T;beginif sym=( or s

15、ym=a or sym=b or sym= athe n Telse if sym=* then errorendprocedure F;beginif sym=( or sym=a or sym=b or sym= athe n beg in P; F endelse errorendprocedure F;beginif sym=*then begin advance; F end end procedure P;beginif sym=a or sym=b or sym=Athen advanceelse if sym=( thenbegin advance; E; if sym=) t

16、hen advance else errorendelse errorend;3. 下面文法那些是 LL (1)文法？(1) S tAbc A t a| e B 宀 b| &沒有左遞歸且 FIRST 候選集不沖突且FIRST(A) n FOLLOW(A)= a, e n b =FIRST(B) n FOLLOW(B)= b, e n c =所以該文法為 LL( 1 )文法2)S tAb A ta|B| e B tb| eFIRST(B) = b, e n FIRST( e ) = e 工所以該文法不是 LL( 1 )文法(3)S tABBA A ta | e B tb|e沒有左遞歸且 FIRS

17、T 候選集不沖突FIRST(A) n FOLLOW(A)= a, e n b,#= FIRST(B) n FOLLOW(B)= b, e n b,a,#工所以該文法不是 LL( 1 )文法(4) S taSe|B BtbBe |C C tcCe|d沒有左遞歸且 FIRST 候選集不沖突所以該文法為 LL( 1 )文法4. Expr t_ExprExpr t (Expr)| Var ExprTailExprTail t _ Expr| &Var t id VarTailVarTail t (Expr)| &(1) 構(gòu)造LL (1)分析表的分析過程(2) 給出對句子id_d(id)& FIRST(

18、Var)=id解答：(1) FIRST(Expr)=_ , ( , id FIRST(ExprTail)=_ , FIRST(VarTail)= ( , FOLLOW(Expr)=# , ) FOLLOW(ExprTail) =# , ) FOLLOW(Var) =_ , # , ) FOLLOW(VarTail) =_ , # , ) 預(yù)測分析表如下:一id()#ExprExpr t _ExprExpr t Var ExprTailExprt(Expr)ExprTailExprTail t_ ExprExprTail t &ExprTail t &VarVar t idVarTailVarT

19、ailVarTail t VarTail t(Expr)VarTail t 對句子id_ _(id)的分析過程:步驟符號棧輸入串所用產(chǎn)生式0# Exprid_ _id(id)#1# ExprTail Varid_ _id(id)#Expr tVar ExprTail2# ExprTail VarTail idid_ _id(id)# Var t id VarTail3# ExprTail VarTail_ _id(id)#4# ExprTail_ _id(id)#VarTail t 5# Expr_d(id)#ExprTailt _ Expr6# Expr_id(id)#7# Expr_id(

20、id)#Expr t _Expr8# Exprid(id)#9# ExprTail Varid(id)#Expr t Var ExprTail10# ExprTail VarTail idid(id)#Vart id VarTail11# ExprTail VarTail(id)#12# ExprTail )Expr(id)#VarTail t (Expr)13# ExprTail )Expr(id)#14# ExprTail ) )Expr(id)#Expr t (Expr)15# ExprTail ) )Exprid)#16# ExprTail )ExprTail Varid)#Expr

21、t Var ExprTail17# ExprTail )ExprTail VarTail idid)#Var t id VarTail18# ExprTail )ExprTail VarTail)#19# ExprTail )ExprTail)#VarTail t 20# ExprTail )#ExprTailT 21# ExprTail )#22# ExprTail#ExprTail t &23# #分析成功第五章1. E= E T二 E T* F短語：E+T*F, T*F,直接短語：T*F句柄:T*F2 (1) (a, ( a, a )的最左推導(dǎo)：S = ( T ) =( T,S ) =

22、( S,S ) =(a,S ) =( a,( T ) = (a,( T,S ) ) = ( a,(S,S ) ) = ( a,( a ,S ) ) = ( a,( a ,a )最右推導(dǎo)：S = ( T ) =( T,S ) = ( T, (T) ) =( T, (T, S) ) =( T, (T, a) ) =( T,(S, a) ) = ( T,(S, a ) ) = ( T,( a ,a ) ) = (S,( a ,a ) ) = ( a,( a ,a ) )(a, a)f,(a),a)的最左推導(dǎo)：S = ( T ) =( T,S ) = ( S,S ) =( ( T ) ,S )=( T

23、,S ),S ) = ( T,S，S ),S ) =( S,S，S ),S ) =( ( T ),S ，S ),S ) =( ( T,S ),S ， S ),S ) =( ( S,S ),S，S ),S ) =( ( a, S ),S，S ),S ) =( ( a, a ),S，S ),S )=(a ,a ),A , S ),S ) =( ( a ,a ),A, a ),S ) =( ( a ,a ),A, a ),a )最右推導(dǎo)： S = ( T ) =( T,S ) =( T, a ) =( S ,a ) =( (T) , a ) =( (T, S) , a )=( (T, ( T ) ,

24、 a ) =( (T, ( a ) , a ) =( (T, S, ( a ) , a ) =( (T, A, ( a ) ,a ) =( (S, A, ( a ) , a ) =( (T), A, ( a ) , a ) =( (T,S), A, ( a ) , a )=( (T ,a), A, ( a ) , a ) =( (S ,a), A, ( a ) , a ) =( (a ,a), A, ( a ) , a )(2) (a, a),A,(a),a)的規(guī)范規(guī)約及每一步的句柄為(a, a),A,(a),a)a( (S ,a), A, ( a ) , a )S( (T ,a), A, (

25、 a ) , a )a( (T,S), A, ( a ) , a )T,S( (T), A, ( a ) , a )(T)( (S, A, ( a ) , a )S( (T, A, ( a ) , a )A( (T, S, ( a ) , a )T,S( (T, ( a ) , a )a(T,(S),a)S( (T, ( T ) , a )(T)( (T, S) , a )T,S( (T) , a )(T)( S ,a )S( T, a )a( T,S )T,S( T )(T)S步驟符號棧輸入串動作0#(a, a),A,(a),a)#預(yù)備1#(a, a),A,(a),a)#進(jìn)2#(a, a),

26、A,(a),a)#進(jìn)3#(a, a),A,(a),a)#進(jìn)4#(a, a),A,(a),a)#進(jìn)5#(S, a),A,(a),a)#規(guī) 約 St a6#(T, a),A,(a),a)#規(guī) 約 TT S7#(a),A,(a),a)#進(jìn)8#(a),A,(a),a)#進(jìn)9#(T,S),A,(a),a)#規(guī)約S t a10#(T),A,(a),a)#規(guī)約Ttt,s11#(T),A,(a),a)#進(jìn)12#(S,A,(a),a)#規(guī)約St (T)13#(T,A,(a),a)#規(guī)約TS14#(T,A,(a),a)#進(jìn)15#(T,A,(a),a)#進(jìn)16#(T,S,(a),a)#規(guī)約ST A17#(T,(a)

27、,a)#規(guī)約TtT,S18#(T,(a),a)#進(jìn)19#(T,(a),a)#進(jìn)20#(T,(a),a)#進(jìn)21#(T,(S),a)#規(guī)約St a22#(T,(T),a)#規(guī)約Tt S23#(T,(T),a)#進(jìn)24#(T,S),a)#規(guī)約St (T)25#(T),a)#規(guī)約TtT,S26#(T),a)#進(jìn)27#(S,a)#規(guī)約St (T)28#(Ta)#規(guī)約Tt S29#(T,a)#進(jìn)30#(T, a)#進(jìn)31#(T, S)#規(guī)約St a32#(T)#規(guī)約Tt T,S33#(T)#進(jìn)34#S#規(guī)約St (T)35#S#接受語法樹：(14 TT )1517(T其中的編號指示的結(jié)點(diǎn)為每一步規(guī)約所形

28、成的語法樹的根結(jié)點(diǎn)。3 (1) FIRSTVT(S)=a,(FIRSTVT(T)=,aA(LASTVT(S)=a,A,)LASTVT(T)=,a,A,)aA()5aA(=G6是算符文法，并且是算符優(yōu)先文法(3)優(yōu)先函數(shù)aA()5f44244g55523也可以最后指定f (#) ,g (#)的值。I oS , S AS , S b , A tSA , A a(4)算符優(yōu)先分析過程。步驟符號棧輸入串動作0#(a,(a ,a)#預(yù)備1#(a,(a ,a)#進(jìn)2#(a,(a ,a)#進(jìn)3#(S,(a ,a)#規(guī)約St a4#(S,(a ,a)#進(jìn)5#(S,(a ,a)#進(jìn)6#(S,(a,a)#進(jìn)7#(

29、S,(S,a)#規(guī)約St a8#(S,(S,a)#進(jìn)9#(S,(S,a)#進(jìn)10#(S,(S,S)#規(guī)約St a11#(S,(T)#規(guī)約Ttt,s12#(S,(T)#進(jìn)13#(S,S)#規(guī)約St (T)14#(T)#規(guī)約TtT,S15#(T)#進(jìn)16#S#規(guī)約St (T)17#S#接受5.拓廣的文法為：St s , S t AS, S t b ,A tSA, A t a,(1)所有的LR(O)項目0. S S 1. S S 2. S AS 3. S A S4. S AS 5. Sr b6. b 7. A - SA8. A S A9. A SA 10. A a 11. A a(2) LR(0)項

30、目集規(guī)范族：I o S I 1 St S , St A S , S t b , A t s A, A t a , A SAA I2St a- S, , S t. AS , S t-b , At SA , A t aa I3At a b I4St b 1 S I5At s - A, A t SA , A t a,S t AS , S t bA I6At SA- , S t a- S , S tAS , St b , A t SA , A t a,a (I 3)b (I 4)I 2 S I 7 St AS , A t S A, A t SA , A t a, S t AS, S t b,A( I

31、2)所以該沖突可以消除I 6 中存在移進(jìn)規(guī)約沖突：Atsa- , St - b , At - a 但是 FOLLOW(A并b, a 所以該沖突不可以消除。I 7 中存在移進(jìn)規(guī)約沖突：St AS- , At - a , St - b 但是 FOLLOW(S 并a , b ,# 所以該沖突不可以消除。所以該文法不是 SLR文法。St S-, Aa , Sb 但是 FOLLOW(S) = #a (I3)b (I4)5 S (I5)A(I6) a (I3)b (I4)6 S (I7)A(I2 ) a (I3)b (I4)7 S (I5)A(I6) a (I3)b (I4)(3) I 1 中存在移進(jìn)規(guī)約

32、沖突(4)Io S S, # , S 亠 AS, # , S b , #, SA,a/b ,a ,a/bIo S I i S S- ,# , SS,a/b , S b ,a/b , A S- A, a /b , A t a - , a/b , Asa, a/bA Ia/b 2 StA- S, # , St- AS , #, S t- b , #, A t- SA ,a/b , A t- aa I3 : A ta- ,a/b,b I4 Stb- ,#I 1 S I5 AtS- A, a/b , At- SA , a/b , At- a , a/b , St- AS , a/b , S t- b,

33、 a/b A I6 AtSA- ,a/b , St A- S , a/b , St- AS , a/b , St- b , a/b ,A t- SA , a/b , At- a, a/b a (I3)b I7 S tb- , a/b I 2 S I8 StAS- ,# , AtS- A, a/b , At- SA ,a/b , At- a, a/b , SaS, a/b, S t- b, a/bA I 9 s tA- S , #/a/b, S t- as , #/a/b , S t- b ,#/ a/b , A t- SA ,a/b , A t- a, a/b a (I 3 )b I 1o S

34、 tb- , #/a/b I 5 S (I 5) A (I 6) a (I 3) b (I7)I 6 S I 11 : StAS- , a/b , A tS- A, a/b , A t- SA , a/b , A t- a, a/b ,A I 12 : StA- S , a/b , St- AS , a/b , St- b, a/b, At- SA, a/b ,A t- a, a/b 41b (I7)S( I5 )A( I 6)a(I 3)b( I 7)S I13 :St AS-,#/a/b , At s-A, a/b ,A t SA , a/b , ASAS ,a/b , Sb , a/b

35、A (I9 )a (I3 )b (I10 )S( I5)A( I 6)a(I 3)b( I 7)S( I11 )A( I 12)a( I3)b( I7)S( I5)A( I6 )a( I3)b( I7)I 11, I1 13 1中存在移進(jìn)規(guī)約沖突，所以該文法不是LR(1)的和 LALR 的。a (I 3)89I11I12I13I6,IIa, a/b ,(附上網(wǎng)絡(luò)版的答案)(2)sAab0,2,5,7,101,2,5,7,8,102,3,5,7,101161,2,5,7,8,102,5,7,8,102,3,5,7,9,10116確定化:2,3,5,7,102,4,5,7,8,102,3,5,7,

36、101162,5,7,8,102,5,7,8,102,3,5,7,9,101162,3,5,7,9,102,4,5,7,8,102,3,5,7,101162,4,5,7,8,102,5,7,8,102,3,5,7,9,10116110000600003St SS-At s A At SA At a St AS St biiSa AAsbSasASaT TA A6: A y SA -Sa sSasSba SAa a0:S SS ASaSr bA、SAA aSSA AAASbSSaA s s ASSaAs1: A = a2: S bdfa構(gòu)造LR（O）項目集規(guī)范族也可以用GO函數(shù)來計算得到。所得到

37、的項目集規(guī)范族與上圖中的項目集一樣：|0 = S = S， AS， Sr b， Ar SA， A a G0（| 0，a）=Ara=I1G0（| o，b）=Sb=I2G0（| 0，S）=S S ,ArSA， A SA，Aa，S“ AS，S； b= 13G0（| 0，A）=Sr A S，SAS， Sr b，ArSA，A* a =14G0（| 3，a）=A a= I1GO（13，b）=Srb= I2GO（I 3，S）=A_. S A，S AS，S b，A SA，A 、a = I5GO（13，A）=A SA，S A S，S AS，Sr b，A SA，A a=I6GO（14，a）=A a= I1GO（1

38、4，b）=Sb= I2GO（I 4，S）=S； ASA S A，S AS，Sr b，A)SA，A a=I7GO（l4，A）=SAS，S AS，S b， A SA，A)a = I4GO（15，a）=A a= I1GO（15，b）=Sb= I2GO（I 5，S）=A； S A，S AS，S b，A SA，A 、a = I5GO（l5，A）=Ar SA，S A S，S AS，Sb，A SA，A a=IeGO（16，a）=A a= I1GO（16，b）=S rb= I2GO（I6，S）=S AS，A 、SA，S AS，Sr b，A SA，A a=I7GO（l6，A）=S AS，Sr AS，S b， A

39、 SA，A a = I4GO（I 7，a）=A a= I1GO（I 7，b）=S rb= I2GO（I 7， S）=A S A，S AS，S b，A SA，A；a= I5GO（l7，A）=A； SA，S A S，S AS，Sr b，A；SA，A；a=I 6項目集規(guī)范族為C=I1，1I2，I3，14，I 5，I6，I7不是SLR文法狀態(tài)3, 6, 7有移進(jìn)歸約沖突狀態(tài) 3: FOLLOW)=#不包含 a,b狀態(tài)6: FOLLOW(S)=#,a,b包含a,b,;移進(jìn)歸約沖突無法消解狀態(tài)7： FOLLOW(A)=a,b包含a,b ;移進(jìn)歸約沖突消解所以不是SLR文法。(4)構(gòu)造例如LR(1)項目集規(guī)

40、范族見下圖：對于狀態(tài)5，因?yàn)榘椖緼AS a/b，所以遇到搜索符號a或b時，應(yīng)該用A AS 歸約。又因?yàn)闋顟B(tài) 5包含項目Aa a/b，所以遇到搜索符號 a時，應(yīng)該移進(jìn)。因此 存在“移進(jìn)-歸約”矛盾，所以這個文法不是LR(1)文法。S8. FIRST (AaAb) = a , FIRST( BbBa) = b ,FIRST(AaAb) n FIRST( BbBa)= 且不含左遞歸，所以該文法是 LL(1)的。拓廣文法為 S t S ,S tAaAb , S 宀BbBa , A e ,B t e .LR(0)項目為:1. S TS ,2. S tS-, 3. St- AaAb , 4. St a

41、 - aAb5. S t Aa. Ab , 6. StAaA - b , 7. StAaAb - , 8. St- BbBa ,9. S tb bBa , 10. STBb - Ba , 11. St BbB - a , 12. StBbBa-,13. A t,14. B tLR(0)項目集規(guī)范族為：I 0 : : S T S , S T AaAb , At- , St - BbBa , BT-11 : S ts 12 : S t a aAb13 : St b bBa14 : S t Aa Ab , A t15 : St Bb Ba , B t 16 : S t AaA b17 : St BbB a18 : S tAaAb-19 : St BbBa 10中存在規(guī)約規(guī)約沖突，而FOLLOW( A)=a ,b FOLLOW( B)=a ,b,消除不了，所以該文法不是 SLR的是LR(1)的。第八早P164 - 5(1)E E1 + T if (E1.type = in t) a nd (type = int ) then E.type := int else E.type := realE TE.type:=T.type num.num T.type := real num T.type := intP164 7