第4章語法分析(4)

1、1第四章第四章 語法分析語法分析(4)4.7 LR(1)、LALR24.6.5 可行前綴（可行前綴（viable prefix）q 對于一個文法G，構(gòu)造一個LR（0）自動機，它能識別所有可能出現(xiàn)在分析棧中的文法符號串，棧中的文法符號串一定是某個右句型的前綴。q 不是右句型的所有前綴都會出現(xiàn)在棧中。xSrm*id*)(id*EFErmrm例如：前綴(E)*不會出現(xiàn)在棧中。3q 可以出現(xiàn)在移進歸約分析器棧中的右句型的前綴稱為可行前綴。q 定義：一個可行前綴是一個右句型的前綴，并且不含右句柄一個可行前綴是一個右句型的前綴，并且不含右句柄之后的任何符號之后的任何符號。例如：對于右句型(E)*id,(

2、(、(E、(E)是可行前綴， (E)*不是可行前綴q 可行前綴后加上終結(jié)符可以得到右句型。q 只有輸入串中已分析過的那部分能歸約成可行前綴，就沒有語法錯誤。q 事實上，LR（0）自動機是一個識別可行前綴的識別可行前綴的DFADFA。產(chǎn)生式： F (E) | id4識別識別G的所有可行前綴的的所有可行前綴的NFAqNFA的狀態(tài)是一個LR(0)項目。q從每個形如B X的狀態(tài)出發(fā)畫一條標記為X的弧到狀態(tài)BX ，q從每個形如B A的狀態(tài)出發(fā)畫一條標記為的弧到所有形如A 的狀態(tài)。q這個NFA通過子集構(gòu)造法得到的DFA和前面構(gòu)造的LR(0)自動機是相同的。5例：例：p153 描述文法的可行前綴描述文法的可

3、行前綴S SS SS+| SS* | a文法的項目有：1. S S 2. S S3. S SS+4. S SS+ 5. S SS +6. S SS+ 7. S SS*8. S SS*9. S SS*10. S SS*11 S a12. S a6startS123 7 S4S511 S8S12 識別可行前綴的識別可行前綴的NFA +69*10 aS SS SS+| SS* | a一個項目對應(yīng)NFA的一個狀態(tài) 1. S S 2. S S3. S SS+4. S SS+ 5. S SS +6. S SS+ 7. S SS*8. S SS*9. S SS*10. S SS*11 S a12. S a7

4、S.SS.SS+S.SS*S.a I0startSa識別可行前綴的識別可行前綴的DFASS .SS. S+SS. S*S.SS+S.SS*S.a I1Sa . I2SSS . +SSS . * SS. S+SS. S*S.SS+S.SS*S.a I3SaSSS +. I4SaSSS *. I5+*8有效項目有效項目q 如果存在一個最右推導(dǎo)S Aw 12w， 則稱項項A A 1 1 2 2 對可行前綴有效的對可行前綴有效的。q 若項目A1 B2 對可行前綴1 是有效的，且 B 是產(chǎn)生式，則項目項目 B B 對可行前綴對可行前綴1 1 也是有效的也是有效的。據(jù)假設(shè)，存在一個最右推導(dǎo)S *Aw 1B

5、2w設(shè)2w * xw， 則對任何B 有最右推導(dǎo)S *Aw 1 B 2w 1 Bxw 1 xw所以 B . 對可行前綴 1 也是有效的。*兩個條件：兩個條件： 1是可行前綴，是可行前綴， 1 1是是1 的后綴的后綴9q一個項目可能對好幾個可行前綴都是有效的。qE E+T對 和和( (這兩個可行前綴都有效 E+T ，E E (，1都為空) ( E+T)， E E (E) ( =“(”，1為空)qDFA讀入 和和( (后到達不同的狀態(tài)，那么項目E E+T就出現(xiàn)在不同的項目集中S Aw 1 B 2w 1 Bxw 1 xw*10有效項目集和項目集規(guī)范族有效項目集和項目集規(guī)范族q 文法G的某個可行前綴的所

6、有有效項目組成的集合，稱為可行前綴的LR(0)有效項目集。例如：I0，I1，I2都是有效項目集。q 文法G的所有有效項目集組成的集合，稱為G的LR(0)項目集規(guī)范族。例如：I0，I1，I211I0I1I6I9E+T*to I7Fto I3(to I4idto I5I2I7I10T*F(to I4idto I5I3FI4I8I11(E)+to I6Tto I2Fto I3I5idid(圖4.36 識別可行前綴的 DFA124.6.4 構(gòu)造SLR分析表q 算法算法 4.32 構(gòu)造SLR分析表輸入：一個拓廣文法G輸出：G 的SLR分析表的函數(shù)action和goto方法：1. 構(gòu)造G 的LR(0)項目

7、集規(guī)范族C = I0, I2, , In。2. 對于狀態(tài)Ii的分析動作如下： (a) 若A . aB Ii且 goto (Ii ,a)= Ij actioni, a = “shift j” (b) 若A . Ii, 對于所有a FOLLOW(A) actioni, a = “reduce A” , A S (c) 若SS. Ii, actioni, $= “accept”3. 若goto(Ii, A) = Ij, AVN , 則 gotoi,A = j4. 分析表其余位置為error13例例4.34 每個每個SLR(1)文法都不是二義的，但是，文法都不是二義的，但是，有許多非二義的文法不是有許

8、多非二義的文法不是SLR(1)。 q 例如，下面的產(chǎn)生式文法S L=RS RL *RL idR L14拓廣文法拓廣文法G 的的LR(0)項目集規(guī)范族為：項目集規(guī)范族為：I0:S SS L=RS RL *RL idR LI3:SR I4:L* RR L L *RL idI5:Lid I6:SL= RR LL *RL idI7:L*R I8:RL I9:SL=R I1:SS I2:SL =RRL 15idS SS L=RS RL *RL idR LL id S L =RR L S S I0I1I2I3S R I4L * RR LL idL * RI5SL*idRS L= RR LL *RL idI

9、6=RS L=R R L LLI7idI3*L *R RI8I916第一個項目使得 action2, = 為shift 第二個項目使得 action2, = 為reduce，因為 = Follow(R)。S L = R * R = R但是，不存在以R=開始的右句型，只有* R = 開始的右句型。SLR(1)文法的描述能力有限文法的描述能力有限S SS L=RS RL *RL idR LS L =RR L I0I2L174.7 構(gòu)造規(guī)范的構(gòu)造規(guī)范的LR分析表分析表q 例 I2有兩個項目SL =R和RL q 當(dāng)下一個輸入為=時用RL 歸約，但是文法沒有以R=開始的右句型，只有以*R=開始的右句型，

10、可見，僅僅知道可行前綴L，不應(yīng)當(dāng)進行歸約。q 擴充項目的定義！產(chǎn)生式文法S L=RS RL *RL idR L18action goto 狀 態(tài) id + * ( ) $ E T F 0 1 2 3 4 5 6 7 8 9 10 11 s5 s4 s6 acc r2 s7 r2 r2 r4 r4 r4 r4 s5 s4 r6 r6 r6 r6 s5 s4 s5 s4 s6 s11 r1 s7 r1 r1 r3 r3 r3 r3 r5 r5 r5 r5 1 2 3 8 2 3 9 3 10 圖圖4.31 表達式文法的表達式文法的LR(0)分析表分析表r2r2r4r4r6r6r1r1r3r3r5r

11、5LR(0)和和SLR的區(qū)別：減少了一些不該規(guī)約的動作的區(qū)別：減少了一些不該規(guī)約的動作I2: E T. ，T T.*F19FOLLOW(E)=$, +,)文法文法4.34的的SLR分析表分析表action goto 狀 態(tài) id + * ( ) $ E T F 0 1 2 3 4 5 6 7 8 9 10 11 s5 s4 s6 acc r2 s7 r2 r2 r4 r4 r4 r4 s5 s4 r6 r6 r6 r6 s5 s4 s5 s4 s6 s11 r1 s7 r1 r1 r3 r3 r3 r3 r5 r5 r5 r5 1 2 3 8 2 3 9 3 10 I2: E T. ，T T.

12、*F20LR(1)項目q 重新定義項目，讓它帶上搜索符(向前看符號)，成為如下形式q LR(1)項目項目: 由由LR(0)項目項目和一個和一個lookahead符號符號組成組成 A. , a q 對于項目 A, a ，搜索符a表示只有當(dāng)下一個輸入符號是a時，才能進行歸約。 這樣的a的集合一定是FOLLOW(A)的一個子集，可能是真子集。SLR中，中，A. 可以看成可以看成 A. , Follow(A)21qLR(1)項目A, a對可行前綴有效，如果存在著推導(dǎo)S *rm Aw rm w，其中： = ，且1. a是w的第一個符號，或者w為且a是$。22例4.37考慮文法：S BBB aB | ba

13、aaBabaaBabaBabBabBaBBBSrmrmrmrmrmrm從最右推導(dǎo)S *rm aaBab rm aaaBab看出：Ba B, a對可行前綴 = aaa是有效的；從最右推導(dǎo)S *rm BaB rm BaaB看出：Ba B, $對可行前綴 = Baa是有效的。這個文法生成的語言是什么？a*ba*bB=aB=aaB=aaaB=aaabLR(1)項目A, a對可行前綴有效，如果存在著推導(dǎo)S *rm Aw rm w，其中： = ，且1.a是w的第一個符號，或者w為且a是$。23構(gòu)造有效的LR(1)項目集q 考慮對可行前綴有效的項目A B, a，必定存在最右推導(dǎo)S *rm Aax rm Ba

14、x，其中 = 。q 假設(shè)ax能推出by，那么， B , b對有效，b是從 能推出的第一個終結(jié)符，或當(dāng) 可空時，b就是a。bFIRST(ax)= FIRST(a) 。LR(1)項目A, a對可行前綴有效，如果存在著推導(dǎo)S *rm Aw rm w，其中： = ，且1.a是w的第一個符號，或者w為且a是$。證明：S *rm Aax rm Bax rm Bby rm by 24算法4.38 LR(1)項目集的構(gòu)造輸入：拓廣文法G。輸出： LR(1)項目集規(guī)范族，是對G 的一個或多個可行前綴有效的項目集。方法：如圖4-40所示。25function closure(I) repeat for ( I中的

15、每個項目 A B, a ) for ( G中的每個產(chǎn)生式 B ) for ( FIRST(a)中的每個終結(jié)符號b ) 將 B. , b加入到集合 I中中 until 不能在I中加入更多的項 return IFig4.40 LR(1) 項目集的構(gòu)造項目集的構(gòu)造 for G 26function goto(I, X)Begin J= ； for (I中的每個項目 A X, a )將項目 A X , a 加入到集合J中 return closure(J)end27procedure items(G )begin C = closure(S S, $); repeat for ( C中的每個項目集 I

16、 )for( 每個文法符號X ) if( goto(I, X) 非空且不在C中 ) 將goto(I, X) 加入到C中； until 不再有新的項集加入到 C 中end28計算S.S,$的閉包I0：S.S, $ S.CC, $ First( $)=$ C.cC, c/d First(C$)=c,d C.d, c/d for ( FIRST( a)中的每個終結(jié)符號中的每個終結(jié)符號b ) 將將 B. , b加入到集合加入到集合 I中中構(gòu)造文法S S S C CC c C | d的LR(1) 分析表。C.cC, c/d是C.cC , c 和 C.cC , d的縮寫項目 A B, a 搜索符29SC.

17、C,$C.cC,$C.d,$ I2CS .S,$S.CC,$C.cC,c/dC.d,c/d I0S S.,$ I1SCc.C, c/dC.cC, c/dC.d, c/d I3cCd.,c/d I4dSCC.,$ I5CCc.C,$C.cC,$C.d,$ I6CcC.,$ I9CcCd.,$ I7dcCcC.,c/d I8Ccdd新增很多狀態(tài)。30算法算法4.40 規(guī)范規(guī)范LR(1)語法分析表的構(gòu)造語法分析表的構(gòu)造輸入：拓廣文法G。輸出：文法G的規(guī)范LR語法分析表函數(shù)action和goto。方法：1. 構(gòu)造G 的LR(1)項目集規(guī)范族C=I0, I1, , In。2. 從Ii構(gòu)造分析器的狀態(tài)i，

18、狀態(tài)i的action函數(shù)確定如下： 若A a, b在Ii中，且goto(Ii, a) = Ij，則置actioni, a為“shift j”； 若A , a在Ii中，且A S，則置actioni, a為“reduce j”，j是產(chǎn)生式A 的序號；若SS, $在Ii中，則置actioni, $為“accept”。31算法算法4.40 規(guī)范規(guī)范LR(1)語法分析表的構(gòu)造語法分析表的構(gòu)造3. 狀態(tài)i的goto函數(shù)確定如下：若goto(Ii, A) = Ij，則gotoi, A = j4. 用上面規(guī)則未能定義的所有條目都置為error。5. 語法分析器的初始狀態(tài)是包含SS, $的項目集對應(yīng)的狀態(tài)。32

19、圖圖4-42 LR(1)分析表分析表33q 每個SLR(1)文法都是LR(1)文法。q 有的文法是LR(1)但不是SLR(1)的。q LR(1)語法分析器的狀態(tài)數(shù)目比SLR(1)分析器的狀態(tài)數(shù)目多。S L = RS R L * RL id R L I0 : S S， $S L = R, $S R, $L * * R, =/$L id, =/$ R L, $I2 : S L = R, $R L , $L 構(gòu)造文法的構(gòu)造文法的LR(1)分析表分析表不存在移進不存在移進歸約沖突歸約沖突S L = R, Follow(S)R L , Follow(R) 在SLR中，F(xiàn)ollow(R)=,$35I0S

20、S， $S L = R, $S R, $L * R, =/$L id, =/$ R L, $I6S L = R, $R L, $L * R, $L id, $=I7L *R , =/$R I8R L , =/$L * S I1 SS., $ I2S L = R, $R L , $L I3S R , $R I4L * R, =/$R L, =/$L * R, =/$L id, =/$* I5L id , =/$id id I9S L= R, $R L I10R L , $I12L id , $id I11L * R, $R L, $L * R, $L id, $* * I13L *R , $R

21、id L 36BabSS S, $ I1S BB, $B aB, $B b, $ I2BB aB, b/aB aB, b/aB b, b/a I3Bb, b/a I4baaS BB, $ I5B aB, $B aB, $B b, $ I6B aB, $ I9B b, $ I7B aB, b/a I8BaBbb例例4.37文法的文法的LR(1)項目集轉(zhuǎn)移圖項目集轉(zhuǎn)移圖S S, $ I0S BB, $B aB, b/aB b, b/a引入引入LALR(1)37BabSS S, $ I1S BB, $B aB, $B b, $ I2BB aB, b/aB aB, b/aB b, b/a I3Bb,

22、b/a I4baaS BB, $ I5B aB, $B aB, $B b, $ I6B aB, $ I9B b, $ I7B aB, b/a I8BaBbb合并同心項合并同心項S S, $ I0S BB, $B aB, b/aB b, b/a38abbSS S, $ I1S BB, $B aB, $B b, $ I2BB aB, b/a/$B aB, b/a/$B b, b/a/$ I3Bb, b/a/$ I4baaS BB, $ I5B aB, b/a/$ I8BB合并同心項合并同心項S S, $ I0S BB, $B aB, b/aB b, b/a394.7.4 構(gòu)造構(gòu)造LALR語法分析表

23、語法分析表q LR(k)方法分析能力很強，但是耗費大量存儲空間。在實際應(yīng)用中，還須簡化。q 觀察圖4.41可知:從自動機狀態(tài)等價的角度來看，圖中彩色相同的狀態(tài)是等價的。這些等價狀態(tài)的特點是，它們的LR(0)有效項目集相同。由于判斷是否等價只須比較狀態(tài)的輸出弧，因而LR(0)有效項目集相同的狀態(tài)必定等價。40q 對于初始狀態(tài)I0，其中的有效項目均可從項目S.S, $推導(dǎo)出來；q 對于非初始狀態(tài)I2, I3, I6，則其中“點在最左端點在最左端”的項目均可由“點不在最左端點不在最左端”的項目推導(dǎo)出來。因此在實際存儲狀態(tài)時，可以只存儲“點不在最左端點不在最左端”的項目。41引入引入“同心項同心項”和

24、和 “核核”的概念：的概念：q 同心項同心項：如果兩個LR(1)項目集去掉搜索符之后是相同的，則稱這兩個項目集具有相同的核心(core)。q 內(nèi)核項目內(nèi)核項目： 對于初始狀態(tài)I0 ，有效項目S.S, $稱為I0的內(nèi)核項目；而對于非初始狀態(tài)，則其中 “點不在最左端”的有效項目稱為它的內(nèi)核項目(kernel)。42LALR分析法的基本思想q 在LR(1)項目集規(guī)范族中，合并同心項以減少狀態(tài)的數(shù)目。q 在存儲LR(1)有效項目集時，僅存儲其中的內(nèi)核。q 注意，由于同心項的合并，使項目的搜索符與可行前綴的對應(yīng)關(guān)系不唯一，降低了分析器的識別能力，參見以下兩例。43Cc.C, c/d/$C.cC, c/d

25、/$C.d, c/d/$ I36I0Cc+ | c+CcC.,c/d/$ I89C可行前綴Cc+與搜索符$對應(yīng)，而可行前綴c+與搜索符c和d對應(yīng)。當(dāng)合并后的自動機識別出可行前綴CcC時，若當(dāng)前的輸入符號是c或d，LR(1)分析器馬上就能發(fā)現(xiàn)出錯，而LALR分析器此時則不行，必須先歸約，得到可行前綴CC后才能發(fā)現(xiàn)出錯。圖圖4.41合并合并I3和和I6，I8和和I9得到的部分狀態(tài)圖得到的部分狀態(tài)圖44SC.C,$C.cC,$C.d,$ I2CS .S,$S.CC,$C.cC,c/dC.d,c/d I0S S.,$ I1SCc.C, c/dC.cC, c/dC.d, c/d I3cCd.,c/d I

26、4dSCC.,$ I5CCc.C,$C.cC,$C.d,$ I6CcC.,$ I9CcCd.,$ I7dcCcC.,c/d I8Ccdd新增很多狀態(tài)。LR（1）45LALR(1)S .S,$S.CC,$C.cC, c/dC.d, c/d I0S S., $ I1SSC.C, $C.cC, $C.d, $ I2CCc.C, c/d/$C.cC, c/d/$C.d, c/d/$ I36c Cd., c/d/$ I47dSCC., $ I5CcCcC.,c/d/$ I89Ccdd46合并同心項目集可能會引起沖突合并同心項目集可能會引起沖突q 同心集的合并不會引起新的移進歸約沖突 假設(shè)合并之后有兩個項

27、目A, a和 Ba, b（存在移進歸約沖突），那么，在合并之前一定有某個集合同時有A, a 和Ba, c（合并之前已經(jīng)存在移進歸約沖突）q 同心集的合并有可能產(chǎn)生新的歸約歸約沖突47考慮文法考慮文法S SS aAd | bBd | aBe | bAeA cB c該文法的語言為acd, bcd, ace, bce，是LR(1)文法。例例4.4248S.S , $S .aAd , $S .bBd , $S .aBe , $S .bAe , $ S S. , $S a.Ad , $S a.Be , $A .c , dB .c , eaSS b.Bd , $S b.Ae , $A .c , eB .c

28、 , d bA S aA.d , $BS aB.e , $cA c. , dB c. , eA c. , eB c. , dcI1I0I2I3I4I5I6S bB.d , $I7BS bA.e, $I8AI9 S aAd. , $I10deI11SaBe., $eI13SbAe., $eI12S bBd., $49S.S , $S .aAd , $S .bBd , $S .aBe , $S .bAe , $ S S. , $S a.Ad , $S a.Be , $A .c , dB .c , eaSS b.Bd , $S b.Ae , $A .c , eB .c , d bA S aA.d ,

29、 $BS aB.e , $ccI1I0I2I3I4I5S bB.d , $I7BS bA.e, $I8A S aAd. , $I10deI11SaBe., $eI13SbAe., $eI12S bBd., $合并同心項合并同心項I69A c. , d/eB c. , d/e50構(gòu)造構(gòu)造G的的LR(1)項目集規(guī)范族項目集規(guī)范族I0: S.S , $ S .aAd , $ S .bBd , $ S .aBe , $ S .bAe , $I1:(I0, S) S S. , $I2:(I0, a) S a.Ad , $ S a.Be , $ A .c , d B .c , eI3:(I0 , b) S

30、 b.Bd , $ S b.Ae , $ A .c , e B .c , d I4:(I2 , A) S aA.d , $I5:(I2 , B) S aB.e , $I6:(I2 , c) A c. , d B c. , eI7:(I3 , B) S bB.d , $I8:(I3 , A) S bA.e , $ I9:(I3 , c) A c. , e B c. , dI10:(I4 , d) S aAd. , $I11:(I4 , e) S aBe. , $I12:(I7 , d) S bBd. , $I13:(I8 , e) S bAe. , $51合并同心項合并同心項I0: S.S ,

31、$ S .aAd , $ S .bBd , $ S .aBe , $ S .bAe , $I1:(I0, S) S S. , $I2:(I0, a) S a.Ad , $ S a.Be , $ A .c , d B .c , eI3:(I0 , b) S b.Bd , $ S b.Ae , $ A .c , e B .c , d I4:(I2 , A) S aA.d , $I5:(I2 , B) S aB.e , $I6:(I2 , c) (I3 , c) A c. , d/e B c. , e/dI7:(I3 , B) S bB.d , $I8:(I3 , A) S bA.e , $ I10

32、:(I4 , d) S aAd. , $I11:(I4 , e) S aBe. , $I12:(I7 , d) S bBd. , $I13:(I8 , e) S bAe. , $52合并同心項合并同心項q 若將同心項I6和I9合并，則得到項目集 I69: Ac. d/e Bc. d/eq 該項目集含“歸約-歸約”沖突。q 因此，文法G是LR(1)文法，但不是LALR文法。53構(gòu)造構(gòu)造LALR分析表的兩種算法分析表的兩種算法q 從LR(1)到LALR簡單、耗空間、耗時間q 直接構(gòu)造LALR復(fù)雜54LALR(1)分析表的原理性構(gòu)造方法分析表的原理性構(gòu)造方法q 構(gòu)造LR(1)項目集族，如果它不存在沖

33、突, 就把同心集合并在一起。若合并后不存在歸約-歸約沖突，則按這個項目集族構(gòu)造文法LALR(1)分析表。q 如果分析表中沒有動作沖突，則文法是LALR(1)文法。55算法算法4.43 LALR分析表的構(gòu)造分析表的構(gòu)造輸入：拓廣文法G輸出：G的LALR(1)分析表方法：1. 構(gòu)造文法的LR(1)項目集族C=I0, I1, , In；2.合并C中的同心集，得到C=J0, J1, , Jm；3. 從C出發(fā)，按LR(1)構(gòu)造action算法（算法4.40）構(gòu)造action表；4. 構(gòu)造goto表：若goto(Ik, X) = Jj，則 gotok,X = j；5. 分析表其余位置為error。56算法

34、算法4.40 規(guī)范規(guī)范LR(1)語法分析表的構(gòu)造語法分析表的構(gòu)造輸入：拓廣文法G。輸出：文法G的規(guī)范LR語法分析表函數(shù)action和goto。方法：1. 構(gòu)造G 的LR(1)項目集規(guī)范族C=I0, I1, , In。2. 從Ii構(gòu)造分析器的狀態(tài)i，狀態(tài)i的action函數(shù)確定如下： 若A a, b在Ii中，且goto(Ii, a) = Ij，則置actioni, a為“shift j”； 若A , a在Ii中，且A S，則置actioni, a為“reduce j”，j是產(chǎn)生式A 的序號；若SS, $在Ii中，則置actioni, $為“accept”。57圖圖4-42 LR(1)分析表分析表

35、58例例4.44 文法文法(4. 16)的的LALR(1)分析表分析表合并同心項：I36: C cC, c/d/$ C cC, c/d/$ C d, c/d/$I47: C d, c/d/$I89: C cC, c/d/$89598960LR(1)和和LALR(1)分析上的差別分析上的差別q 輸入：ccd$q LR: 0 c 3 c 3 d 4 報錯q LALR: 0 c 36 c 36 d 47 0 c 36 c 36 C 89 0 c 36 C 89 0 C 2 推遲報錯文法文法S SS CCC cCC d語言：c*dc*d61幾種幾種LR方法比較方法比較q 不同點主要在歸約動作的選擇：L

36、R(0) 分析考慮所有終結(jié)符SLR(1) 分析考慮FOLLOW 集LR(1) 分析考慮 LR(1)項目中的搜索符LALR分析考慮的是LR(1)項目合并之后的搜索符q 注意，LALR項目的搜索符一般是與該項目相關(guān)的非終結(jié)符號的Follow集的子集，這正是LALR分析法比SLR分析法強的原因62q 一個可行前綴可能有多個有效項目?？赡艽嬖趧幼鳑_突q 一個可行前綴的有效項目集就是從這個DFA的初態(tài)出發(fā)，沿著標記為的路徑到達的那個項目集（狀態(tài)） 。63串E + T *是可行前綴，讀完它后，DFA處于狀態(tài)I7I7: TT *F, F ( E ), F id E E E E E E E+T E+T E+T

37、 E+T * F E+T * F E+T * F E+T * id E+T * (E ) E+T* id E+T * F * id例例4.35644.7.5 LALR分析表的有效構(gòu)造方法分析表的有效構(gòu)造方法q 算法4.43在構(gòu)造LALR分析表時，耗費的存儲空間與LR(1)算法完全相同，代價還是太大。65q 可以從兩個方面改進：存儲有效項目集時，只存儲它們的核心項目，每當(dāng)需要完整的有效項目集時，再根據(jù)核心項目來計算。根據(jù)LR(0)項直接生成LALR(1)項目集規(guī)范族的核心項目，這是有效構(gòu)造方法的關(guān)鍵。只需要利用項目集的核心項目就能計算其動作。66利用項目集的核就能計算其動作利用項目集的核就能計算

38、其動作q 思想：利用項目集的內(nèi)核項目構(gòu)造action表q 歸約動作A 且且 ，則該歸約項目必在內(nèi)核項目中；用A 歸約，此時歸約項目A 不在內(nèi)核項目中，當(dāng)且僅當(dāng)存在內(nèi)核項目B C , b且C*A ，輸入a為FIRST( b)，才能用A 歸約?？梢允孪扔嬎愠鏊蟹螩*A 的非終結(jié)符A。67利用項目集的核就能計算其動作利用項目集的核就能計算其動作q 移進動作若存在內(nèi)核項目B a , b，顯然動作是將a移進；若存在內(nèi)核項目B C , b，且C*ax，且推導(dǎo)的最后一步不是用產(chǎn)生式，則可以將a移進?？梢允孪扔嬎愠鏊蟹螩*ax的終結(jié)符a。68利用項目集的核計算利用項目集的核計算goto轉(zhuǎn)換轉(zhuǎn)換q 利用

39、項目集的內(nèi)核項目構(gòu)造goto轉(zhuǎn)換若 B X , b是I中內(nèi)核項目，顯然B X , b在goto(I, X)的內(nèi)核項目中。若 B C , b是I中內(nèi)核項目，且有C*A ，那么， A X , a在goto(I, X)的內(nèi)核項目中，其中a是FIRST(b)?？梢允孪扔嬎愠鏊蟹螩*A 的非終結(jié)符。69例例4.45 構(gòu)造文法構(gòu)造文法LR(0)項目集的內(nèi)核項目集的內(nèi)核I0: S .S I1: S S. I2: S L.=R R L. I3: S R. I4: L *.R I5: L id. I6: S L=.R I7: L *R. I8: R L. I9: S L=R. 70S S I0RS R I3

40、SL =RR L LI2SS SI1L * R*I4Lid idI5=S L= RI6RL * R I7RL LI8*idRS L= R I9L*id71“自生的自生的”和和“傳播的傳播的”搜索符搜索符q 下面考慮如何為核項目配上搜索符。q 為LR(0)核項目B 添加搜索符b：存在包含內(nèi)核項A , a項目集I ，有g(shù)oto(I, X) = J。計算GOTO(CLOSURE(A , a), X)得到的結(jié)果中包含B , b，則則搜索符b為“自生的自生的” (spontaneously)。A C , aIB X , b JXqC * B， bFirst(a)72SA C B aaaBaCAaSrmrmrmrm* 73“自生的自生的”和和“傳播的傳播的”搜索符搜索符q 下面考慮如何為核項目配上搜索符。q 為LR(0)核項目B 添加搜索符b：存在包含內(nèi)核項A , a項目集I ，有g(shù)oto(I, X) = J。計算GOTO(CLOSURE(A , a), X)得到的結(jié)果中包含B , b，則則