【正文】 第六章 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)}進行合并，得： {(A c?,d|e)(B c?,e|d)}. 當面臨 d或 e這兩個搜索時，不知該用哪個產(chǎn)生式進行歸約，出現(xiàn)了歸約 —歸約沖突 。但由于移進能力沒有減弱，所以在下一個符號進棧之前總能報錯，故它對錯誤的定向能力沒減弱。 合并 GOTO表 ●方法：根據(jù) GO函數(shù)的定義： GO(I,X)=CLOSURE(J),其中：J={任何形如（ A aX?b,a)的項目 )(A a?Xb,a∈I} 進行。 LALR分析表的尺寸比 SLR分析表相同。 注： 僅當文法是 LR(1)時，才有可能構(gòu)造 LALR分析表。 第六章 LR分析法及分析程序自動構(gòu)造（ 110） 規(guī)范 LR分析表的構(gòu)造 ? 構(gòu)造 LALR分析表的基本思想 合并同心，可得到一個與 LR(0)狀態(tài)數(shù)相同的項目集族。構(gòu)造方法的基本思想是合并同心。 第六章 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)分析方法。 ?例如：根據(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)。 4)若 GO(Ik,A)=Ij,A是非終結(jié)符，則置GOTO[K,A]=j。 2）若項目（ A a?,a) ∈I k,則置 ACTION[k,a]=rj。按下列步驟填寫 ACTION表和 GOTO表： 1）若項目（ A a?ab,b)屬于 Ik，且 GO(Ik,a)=Ij,a為終結(jié)符，則置 ACTION[k,a]=Sj。 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ù)上面的過程，直到項目集不再增加為止。 注：因為 (A a?Bb,a)屬于 CLOSURE(I),那么 (B ?g,b)當然也屬于 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)造（ 99） 規(guī)范 LR分析表的構(gòu)造 ? 二、構(gòu)造 LR(1)項目集規(guī)范族的算法 函數(shù) CLOSURE(I)—I的項目集 (1)I的任何項目都屬于 CLOSURE(I)。有如下文法： ’ S aAd bAc aec bed e ● 按照求 LR(0)項目集規(guī)范族的算法，求得 G(S)文法得項目集族，其中某狀態(tài)中發(fā)生移進 歸約沖突： 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”之后。 ●注： 1）規(guī)范 LR分析法僅考慮有效的 LR(1)項目，在LR(1)項目中有效的項目并不多。 ?2）（ A a?b,a)的含義：預(yù)期當棧頂句柄 ab形成后，在讀頭下讀到 a，此時 a在棧內(nèi)， b還未入棧，那它展望了句柄后的一個符號。 第六章 LR分析法及分析程序自動構(gòu)造（ 85） ?例如：試構(gòu)造表達式文法 G(E)的 SLR分析表 ?’ E E+T ? T T*F ? F 5. F (E) ? i ? 解 :按照求 LR(0)項目集規(guī)范族的算法 ,求得 G(E)文法得項目集族如下圖 : SLR分析表的構(gòu)造 二、構(gòu)造 SLR分析表的算法 第六章 LR分析法及分析程序自動構(gòu)造（ 86） I5:F i? I0:S’ ?E E ?E+T E ?T T ?T*F T ?F F ?(E) F ?i I2:E T? T T?*F I1:S’ E? E E?+T I4:F’ (?E) E ?E+T E ?T T ?T*F T ?F F ?(E) F ?i I3:T F? I6:E E+?T T ?T*F T ?F F ?(E) F ?i I10:T T?F I7:T T*?F F ?(E) F ?i I9:E E+T? T T?*F I8:F (E?) E E?+T I11:F (E)? i i ( F T I2 ( I4 T T E ) E F * F i ( I5 I3 I5 i + ( 第六章 LR分析法及分析程序自動構(gòu)造（ 87） F * SLR分析表的構(gòu)造 二、構(gòu)造 SLR分析表的算法 構(gòu)造 SLR分析表時要注意項目集族中 I1,I2,I9 三個項目集 ,其中含有沖突 : I1:S’ E? I2:E T? I9:E E+T? E E?+T T T?*F T T?*F 根據(jù)原來的文法分別求 S’ ,E的 Follow集 ,按 SLR方法進行分析 ,得 第六章 LR分析法及分析程序自動構(gòu)造（ 88） 狀態(tài) ACTION GOTO i + * ( ) E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 S7 r1 r1 10 r3 r3 r3 r3 第六章 LR分析法及分析程序自動構(gòu)造（ 89） ?例：一個非 SLR文法的例子 ,有如下文法 : ?’ S L=R ? R *R ? i 6. R L ? 按照求 LR(0)項目集規(guī)范族的算法 ,求得 G(S)文法得項目集族如下圖 : SLR分析表的構(gòu)造 二、構(gòu)造 SLR分析表的算法 第六章 LR分析法及分析程序自動構(gòu)造（ 90） 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 狀態(tài) ACTION GOTO = i * S L R 0 S5 S4 1 2 3 1 acc 2 S6/ r6 r6 3 r3 4 S5 S4 8 7 5 r5 r5 6 S5 S4 8 9 7 r4 r4 8 r6 r6 9 r2 第六章 LR分析法及分析程序自動構(gòu)造（ 69） ? 一 在構(gòu)造 SLR分析表的方法中 ,若項目集 Ik中含有 A a?,那么在狀態(tài) K時 ,只要面臨輸入符號a∈FOLLOW(A), 就確定采