【正文】 bw的活前綴（記作 g),a∈First( w),則 LR(1)項目（ A a?b,a)對于活前綴 g是有效的，如果 a∈First （ w),即使 a∈Follow(A), 項目（ A a?b,a)也是無效的。 ●注： 1）規(guī)范 LR分析法僅考慮有效的 LR(1)項目，在LR(1)項目中有效的項目并不多。 2）對于多數(shù)程序設(shè)計語言，向前展望一個符號就是足以決定歸約與否，所以只研究 LR(1). 第六章 LR分析法及分析程序自動構(gòu)造（ 97） ? 例：對非 SLR文法的例子。有如下文法： ’ S aAd bAc aec bed e ● 按照求 LR(0)項目集規(guī)范族的算法，求得 G(S)文法得項目集族，其中某狀態(tài)中發(fā)生移進(jìn) 歸約沖突： Ix:S ae?c A e? 由于規(guī)范推導(dǎo)為： S’ S aAd aed S’ S aec 第六章 LR分析法及分析程序自動構(gòu)造（ 98） ?這兩個最右推導(dǎo)中已包含了活前綴為 ae的所有句型，可見 “ aAc”決不會是規(guī)范句型，即：歸約成非終結(jié)符 “ A”之后。其后決不會跟“ c”. ?故：雖然 Follow(A)={c,d},但是（ A e?,c)對活前綴 ae是無效的，僅（ A e?,d)是有效的。 第六章 LR分析法及分析程序自動構(gòu)造（ 99） 規(guī)范 LR分析表的構(gòu)造 ? 二、構(gòu)造 LR(1)項目集規(guī)范族的算法 函數(shù) CLOSURE(I)—I的項目集 (1)I的任何項目都屬于 CLOSURE(I)。 (2)若項目 (A a?Bb,a)屬于 CLOSURE(I),B g是一個產(chǎn)生式，那么對于 FIRST(ba)中的每個終結(jié)符 b，如果 (B ?g,b)原來不在 CLOSURE(I)中，則把它加進(jìn)去； (3)重復(fù)步驟 (2)直到 CLOSURE(I)不再擴大為止。 注：因為 (A a?Bb,a)屬于 CLOSURE(I),那么 (B ?g,b)當(dāng)然也屬于 CLOSURE(I),其中 b必定是跟在B后面的終結(jié)符，即 b∈First( ba).若 b=e,則 b=a 第六章 LR分析法及分析程序自動構(gòu)造（ 100） 規(guī)范 LR分析表的構(gòu)造 ?二、構(gòu)造 LR(1)的項目集規(guī)范族的算法 GO函數(shù) ●令 I是一個項目集， X是文法符號，函數(shù)GO(I,X)定義為 GO(I,X)=CLOSURE(J) 其中 J={任何形如（ A aX?b,a)的項目∣(A a?Xb,a)∈ I} ●注：在執(zhí)行轉(zhuǎn)換函數(shù) GO時，搜索符并不改變。 第六章 LR分析法及分析程序自動構(gòu)造（ 101） 規(guī)范 LR分析表的構(gòu)造 ? 構(gòu)造拓廣文法的 LR(1)項目集族 C的算法 PROC ITEMSETLR1 { C={CLOSURE ({(S’ ?S,)})}。 DO { FOR C中的每個項目集 I和 G’的每個文法符號 X IF GO(I,X)非空且不屬于 C 把 GO(I,X)加入 C中； }WHILE C 依然擴大； 第六章 LR分析法及分析程序自動構(gòu)造（ 102） ? 例：有如下文法： ● ’ S L=R R *R i L ●按照求 LR(1)項目集規(guī)范族的算法 ,求 G(S)文法的項目集族 ●解 :求初態(tài)項目集 I0:從（ S’ ?S ,)項目開始求閉包 得： 第六章 LR分析法及分析程序自動構(gòu)造（ 103） I0初態(tài) S’ ?S, S’ ?L=R, S ?R, L ?*R,= L ?i,= R ?L, L ?*R, L ?i, I0初態(tài) S’ ?S, S’ ?L=R, S ?R, L ?*R,=| L ?i,=| R ?L, 縮寫為 ?接著利用 GO函數(shù)，對該項目集內(nèi)得各項目求后繼項目集，然后再對新求的項目集重復(fù)上面的過程，直到項目集不再增加為止。 第六章 LR分析法及分析程序自動構(gòu)造（ 104） 5:L i?,=| 0 S’ ?S, S’ ?L=R, S ?R, L ?*R,=| L ?i,=| R ?L, 3:S R?, 4: L *?R,=| R ?L, L ?i, =| L ?i, =| 6:S L=?R, R ?L, L ?*R,=| L ?i, =| 8:R L?, 7:L *R?, =| 2:S’ L?=R, R L?, 1:S’ S ?, 9:S L=R?, = i S * * i R i * L L R R 第六章 LR分析法及分析程序自動構(gòu)造（ 91） L I10 I12 規(guī)范 LR分析表的構(gòu)造 ? 三、構(gòu)造 LR(1)分析表的算法 ?設(shè) C={I0,I1,… ..In},以各項目集 Ik(k=0,1,… ..n)的下標(biāo) k為分析表中的狀態(tài)，并以包含（ S’ ?S,)的項目的狀態(tài)為分析表初態(tài)。按下列步驟填寫 ACTION表和 GOTO表： 1）若項目（ A a?ab,b)屬于 Ik，且 GO(Ik,a)=Ij,a為終結(jié)符，則置 ACTION[k,a]=Sj。即：移進(jìn) a,并轉(zhuǎn)向 Ij狀態(tài)。 2）若項目（ A a?,a) ∈I k,則置 ACTION[k,a]=rj。其中 j為產(chǎn)生式 A a的編號，即根據(jù) j號產(chǎn)生式 A a進(jìn)行歸約 第六章 LR分析法及分析程序自動構(gòu)造（ 105） 規(guī)范 LR分析表的構(gòu)造 ?三、構(gòu)造 LR(1)分析表的算法 3）若項目（ S’ S?,)屬于 IK,則置ACTION[k,]=acc。 4)若 GO(Ik,A)=Ij,A是非終結(jié)符，則置GOTO[K,A]=j。 5)分析表中凡不能用步驟 1至 4填入信息的空白項，均置上 “ 出錯標(biāo)志 ” 。 ?例如：根據(jù)前面例子中的 LR(1)項目集族構(gòu)造的規(guī)范 LR(1)分析表如下： 第六章 LR分析法及分析程序自動構(gòu)造（ 106） 狀態(tài) ACTION GOTO = i * S L R 0 S5 S4 1 2 3 1 acc 2 S6 r6 3 r3 4 S5 S4 8 7 5 r5 r5 6 S10 S12 11 9 7 r4 r4 8 r6 r6 9 r2 10 r5 11 r6 12 S10 S12 11 13 第六章 LR分析法及分析程序自動構(gòu)造（ 107） 5:L i?,=| 0 S’ ?S, S’ ?L=R, S ?R, L ?*R,=| L ?i,=| R ?L, 3:S R?, 4: L *?R,=| R ?L, L ?i, =| L ?i, =| 6:S L=?R, R ?L, L ?*R,=| L ?i, =| 8:R L?, 7:L *R?, =| 2:S’ L?=R, R L?, 1:S’ S ?, 9:S L=R?, = i S * * i R i * L L R R 第六章 LR分析法及分析程序自動構(gòu)造（ 91） L I10 I12 規(guī)范 LR分析表的構(gòu)造 ? 四、 LR(1)文法 ? 定義：若文法 G’按構(gòu)造 LR(1)分析表算法構(gòu)造出來的分析表不包含多重定義項，則該文法 G’是 LR(1)文法 ? 注： 1）每個 SLR文法都是 LR(1)文法 2）一個 SLR文法的規(guī)范 LR分析表比其 SLR分析表含有更多的狀態(tài)。在嚴(yán)重的情況下，狀態(tài)數(shù)可能成 n倍增長，因此需要簡化。 第六章 LR分析法及分析程序自動構(gòu)造（ 108） 狀態(tài) ACTION GOTO = i * S L R 0 S5 S4 1 2 3 1 acc 2 S6 r6 3 r3 4 S5 S4 8 7 5 r5 r5 6 S10 S12 11 9 7 r4 r4 8 r6 r6 9 r2 10 r5 11 r6 12 S10 S12 11 13 第六章 LR分析法及分析程序自動構(gòu)造（ 109） 規(guī)范 LR分析表的構(gòu)造 ? 一、基本思想 ? LALR分析法是一種簡化的、具有預(yù)測能里能力（ LookAhead)的 LR(1)分析方法。是在 LR(1)文法的基礎(chǔ)上構(gòu)造出來的。構(gòu)造方法的基本思想是合并同心。 ? 同心 若文法 G’的 LR(1)的兩個項目集 Ii和 IJ在去掉各項目中搜索符之后是相同的，則稱這兩項目集為同心。 第六章 LR分析法及分析程序自動構(gòu)造（ 110） 規(guī)范 LR分析表的構(gòu)造 ? 構(gòu)造 LALR分析表的基本思想 合并同心，可得到一個與 LR(0)狀態(tài)數(shù)相同的項目集族。在合并同心的同時，以某種方式合并 LR(1)分析表中的 ACTION表和 GOTO表的對應(yīng)項，從而可以在 LR(1)分析表的基礎(chǔ)上構(gòu)造一個尺寸與 LR(0)分析表相同的分析表，若此表不含多重定義項，它就是 LALR分析表。 注： 僅當(dāng)文法是 LR(1)時，才有可能構(gòu)造 LALR分析表。 LALR分析法的分析能力比 LR(1)弱，比 SLR強。 LALR分析表的尺寸比 SLR分析表相同。 第六章 LR分析法及分析程序自動構(gòu)造（ 111） LALR分析表的構(gòu)造 ? 二、合并同心 合并 ACTION和 GOTO表的對應(yīng)項。 合并 GOTO表 ●方法：根據(jù) GO函數(shù)的定義： GO(I,X)=CLOSURE(J),其中：J={任何形如（ A aX?b,a)的項目 )(A a?Xb,a∈I} 進(jìn)行。 ●例如：設(shè) Im和 In同心，則： (A a?Xb,a)∈I m GO(Im,X) (A aXb,a) (A a?Xb,b)∈I n GO(In,X) (A aXb,b) 注：根據(jù) GO函數(shù)定義，轉(zhuǎn)向后，搜索符不變，即與搜索符無關(guān)，故合并之后不出現(xiàn)轉(zhuǎn)向沖突，轉(zhuǎn)向之后仍然同心 第六章 LR分析法及分析程序自動構(gòu)造（ 112） LALR分析表的構(gòu)造 ? 二、合并同心 合并 ACTION表 ?(1)出錯與出錯合并：結(jié)果仍為出錯，無沖突； ?(2)移進(jìn)與移進(jìn)合并； ?(3)出錯與移進(jìn)合并：不會出現(xiàn)此情況，因為出錯項目與移進(jìn)項目不同心； ?(4)移進(jìn)與歸約合并：不會出現(xiàn)此情況； ?(5)歸約與出錯合并：規(guī)定它做歸約； 注：由此可見， LALR與 LR(1)相比，放松了報錯條件。但由于移進(jìn)能力沒有減弱，所以在下一個符號進(jìn)棧之前總能報錯，故它對錯誤的定向能力沒減弱。 第六章 LR分析法及分析程序自動構(gòu)造（ 113） LALR分析表的構(gòu)造 ? 二、合并同心 ? 合并 ACTION表 ?(6)歸約與歸約合并：分兩種情況討論： A)按同一產(chǎn)生式歸約，無沖突； B)按不同產(chǎn)生式歸約，將造成沖突，因此 LALR的能力弱于 LR(1). ?綜上所述，可得：只要合并同心之后，不存在按不同產(chǎn)生式的歸約 歸約沖突，由 LR(1)項目集族總能構(gòu)造出 LALR分析表。 第六章 LR分析法及分析程序自動構(gòu)造（ 114） ? 例如，文法： (0)S’ S (1)S aAd|bBd|aBe|bAe (2)A c (3)B c 此文法是 LR(1)文法，其項目集族不存在沖突性動作，但在合并時，將 LR(1)中的兩個同心項目 {(A c?,d)(B c?,e)},{(A c?,e),(B c?,d)}進(jìn)行合并，得： {(A c?,d|e)(B c?,e|d)}. 當(dāng)面臨 d或 e這兩個搜索時，不知該用哪個產(chǎn)生式進(jìn)行歸約，出現(xiàn)了歸約 —歸約沖突