第4章語法分析(4)

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

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

3、行前綴S SS SS+| SS* | a文法的項(xiàng)目有：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一個項(xiàng)目對應(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有效項(xiàng)目有效項(xiàng)目q 如果存在一個最右推導(dǎo)S Aw 12w， 則稱項(xiàng)項(xiàng)A A 1 1 2 2 對可行前綴有效的對可行前綴有效的。q 若項(xiàng)目A1 B2 對可行前綴1 是有效的，且 B 是產(chǎn)生式，則項(xiàng)目項(xiàng)目 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一個項(xiàng)目可能對好幾個可行前綴都是有效的。qE E+T對 和和( (這兩個可行前綴都有效 E+T ，E E (，1都為空) ( E+T)， E E (E) ( =“(”，1為空)qDFA讀入 和和( (后到達(dá)不同的狀態(tài)，那么項(xiàng)目E E+T就出現(xiàn)在不同的項(xiàng)目集中S Aw 1 B 2w 1 Bxw 1 xw*10有效項(xiàng)目集和項(xiàng)目集規(guī)范族有效項(xiàng)目集和項(xiàng)目集規(guī)范族q 文法G的某個可行前綴的所

6、有有效項(xiàng)目組成的集合，稱為可行前綴的LR(0)有效項(xiàng)目集。例如：I0，I1，I2都是有效項(xiàng)目集。q 文法G的所有有效項(xiàng)目集組成的集合，稱為G的LR(0)項(xiàng)目集規(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)項(xiàng)目

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)項(xiàng)目集規(guī)范族為：項(xiàng)目集規(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第一個項(xiàng)目使得 action2, = 為shift 第二個項(xiàng)目使得 action2, = 為reduce，因?yàn)?= 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有兩個項(xiàng)目SL =R和RL q 當(dāng)下一個輸入為=時用RL 歸約，但是文法沒有以R=開始的右句型，只有以*R=開始的右句型，

10、可見，僅僅知道可行前綴L，不應(yīng)當(dāng)進(jìn)行歸約。q 擴(kuò)充項(xiàng)目的定義！產(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 表達(dá)式文法的表達(dá)式文法的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)項(xiàng)目q 重新定義項(xiàng)目，讓它帶上搜索符(向前看符號)，成為如下形式q LR(1)項(xiàng)目項(xiàng)目: 由由LR(0)項(xiàng)目項(xiàng)目和一個和一個lookahead符號符號組成組成 A. , a q 對于項(xiàng)目 A, a ，搜索符a表示只有當(dāng)下一個輸入符號是a時，才能進(jìn)行歸約。 這樣的a的集合一定是FOLLOW(A)的一個子集，可能是真子集。SLR中，中，A. 可以看成可以看成 A. , Follow(A)21qLR(1)項(xiàng)目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)項(xiàng)目A, a對可行前綴有效，如果存在著推導(dǎo)S *rm Aw rm w，其中： = ，且1.a是w的第一個符號，或者w為且a是$。23構(gòu)造有效的LR(1)項(xiàng)目集q 考慮對可行前綴有效的項(xiàng)目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)項(xiàng)目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)項(xiàng)目集的構(gòu)造輸入：拓廣文法G。輸出： LR(1)項(xiàng)目集規(guī)范族，是對G 的一個或多個可行前綴有效的項(xiàng)目集。方法：如圖4-40所示。25function closure(I) repeat for ( I中的

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

16、 )for( 每個文法符號X ) if( goto(I, X) 非空且不在C中 ) 將goto(I, X) 加入到C中； until 不再有新的項(xiàng)集加入到 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的縮寫項(xiàng)目 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)項(xiàng)目集規(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, $的項(xiàng)目集對應(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)分析表分析表不存在移進(jìn)不存在移進(jìn)歸約沖突歸約沖突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)項(xiàng)目集轉(zhuǎn)移圖項(xiàng)目集轉(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合并同心項(xiàng)合并同心項(xiàng)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合并同心項(xiàng)合并同心項(xiàng)S S, $ I0S BB, $B aB, b/aB b, b/a394.7.4 構(gòu)造構(gòu)造LALR語法分析表

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

24、和 “核核”的概念：的概念：q 同心項(xiàng)同心項(xiàng)：如果兩個LR(1)項(xiàng)目集去掉搜索符之后是相同的，則稱這兩個項(xiàng)目集具有相同的核心(core)。q 內(nèi)核項(xiàng)目內(nèi)核項(xiàng)目： 對于初始狀態(tài)I0 ，有效項(xiàng)目S.S, $稱為I0的內(nèi)核項(xiàng)目；而對于非初始狀態(tài)，則其中 “點(diǎn)不在最左端”的有效項(xiàng)目稱為它的內(nèi)核項(xiàng)目(kernel)。42LALR分析法的基本思想q 在LR(1)項(xiàng)目集規(guī)范族中，合并同心項(xiàng)以減少狀態(tài)的數(shù)目。q 在存儲LR(1)有效項(xiàng)目集時，僅存儲其中的內(nèi)核。q 注意，由于同心項(xiàng)的合并，使項(xiàng)目的搜索符與可行前綴的對應(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)合并后的自動機(jī)識別出可行前綴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合并同心項(xiàng)目集可能會引起沖突合并同心項(xiàng)目集可能會引起沖突q 同心集的合并不會引起新的移進(jìn)歸約沖突 假設(shè)合并之后有兩個項(xiàng)

27、目A, a和 Ba, b（存在移進(jìn)歸約沖突），那么，在合并之前一定有某個集合同時有A, a 和Ba, c（合并之前已經(jīng)存在移進(jìn)歸約沖突）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., $合并同心項(xiàng)合并同心項(xiàng)I69A c. , d/eB c. , d/e50構(gòu)造構(gòu)造G的的LR(1)項(xiàng)目集規(guī)范族項(xiàng)目集規(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合并同心項(xiàng)合并同心項(xiàng)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合并同心項(xiàng)合并同心項(xiàng)q 若將同心項(xiàng)I6和I9合并，則得到項(xiàng)目集 I69: Ac. d/e Bc. d/eq 該項(xiàng)目集含“歸約-歸約”沖突。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)項(xiàng)目集族，如果它不存在沖

33、突, 就把同心集合并在一起。若合并后不存在歸約-歸約沖突，則按這個項(xiàng)目集族構(gòu)造文法LALR(1)分析表。q 如果分析表中沒有動作沖突，則文法是LALR(1)文法。55算法算法4.43 LALR分析表的構(gòu)造分析表的構(gòu)造輸入：拓廣文法G輸出：G的LALR(1)分析表方法：1. 構(gòu)造文法的LR(1)項(xiàng)目集族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)項(xiàng)目集規(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)分析表分析表合并同心項(xiàng)：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 不同點(diǎn)主要在歸約動作的選擇：L

36、R(0) 分析考慮所有終結(jié)符SLR(1) 分析考慮FOLLOW 集LR(1) 分析考慮 LR(1)項(xiàng)目中的搜索符LALR分析考慮的是LR(1)項(xiàng)目合并之后的搜索符q 注意，LALR項(xiàng)目的搜索符一般是與該項(xiàng)目相關(guān)的非終結(jié)符號的Follow集的子集，這正是LALR分析法比SLR分析法強(qiáng)的原因62q 一個可行前綴可能有多個有效項(xiàng)目?？赡艽嬖趧幼鳑_突q 一個可行前綴的有效項(xiàng)目集就是從這個DFA的初態(tài)出發(fā)，沿著標(biāo)記為的路徑到達(dá)的那個項(xiàng)目集（狀態(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分析表時，耗費(fèi)的存儲空間與LR(1)算法完全相同，代價還是太大。65q 可以從兩個方面改進(jìn)：存儲有效項(xiàng)目集時，只存儲它們的核心項(xiàng)目，每當(dāng)需要完整的有效項(xiàng)目集時，再根據(jù)核心項(xiàng)目來計算。根據(jù)LR(0)項(xiàng)直接生成LALR(1)項(xiàng)目集規(guī)范族的核心項(xiàng)目，這是有效構(gòu)造方法的關(guān)鍵。只需要利用項(xiàng)目集的核心項(xiàng)目就能計算其動作。66利用項(xiàng)目集的核就能計算其動作利用項(xiàng)目集的核就能計算

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

39、項(xiàng)目集的內(nèi)核項(xiàng)目構(gòu)造goto轉(zhuǎn)換若 B X , b是I中內(nèi)核項(xiàng)目，顯然B X , b在goto(I, X)的內(nèi)核項(xiàng)目中。若 B C , b是I中內(nèi)核項(xiàng)目，且有C*A ，那么， A X , a在goto(I, X)的內(nèi)核項(xiàng)目中，其中a是FIRST(b)。可以事先計算出所有符合C*A 的非終結(jié)符。69例例4.45 構(gòu)造文法構(gòu)造文法LR(0)項(xiàng)目集的內(nèi)核項(xiàng)目集的內(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 下面考慮如何為核項(xiàng)目配上搜索符。q 為LR(0)核項(xiàng)目B 添加搜索符b：存在包含內(nèi)核項(xiàng)A , a項(xiàng)目集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 下面考慮如何為核項(xiàng)目配上搜索符。q 為LR(0)核項(xiàng)目B 添加搜索符b：存在包含內(nèi)核項(xiàng)A , a項(xiàng)目集I ，有g(shù)oto(I, X) = J。計算GOTO(CLOSURE(A , a), X)得到的結(jié)果中包含B , b，則則