【正文】 法 由于用 SLR(1)方法解決動作沖突時，它僅孤立地 考察對于歸約項目 A→ α? ，只要當前面臨輸入符號 a∈ Follow(A)時，就確定使用規(guī)則 A→ α進行歸約， 而沒有考察符號串 α所在規(guī)范句型的環(huán)境 。 Ii : A→ α? I0 I1 Ii $ δ α aa39。a… I0 I1 Ij $δA aa39。a… SLR（ 1）分析法 因為如果棧里的符號串為 $δα ，歸約后變?yōu)?$δA，當前讀到的輸入符號是 a，若文法中不存在以 δAa為前綴的規(guī)范句型，那么， 這種歸約無效 。 例如，我們考查規(guī)范句型 i＝ i的 SLR(1) 分析過程： I0: S →L=R L →*R L →i R →L S39?！鶶 S→L=R S→R L→*R L→i R→L S I1:S′→S I2: S →L=R R →L L I3: S →R R L →*R L →i R →L L →*R I4: * * i i I5: L →i I6: = * I7: L →*R R i L I8: R →L L R I9: S →L=R LR(0)識別 G’活前綴的 DFA 0. S′→ S 1. S → L=R 2. S → R 3. L →* R 4. L → i 5. R → L SLR（ 1）分析法 狀態(tài)棧 符號棧 輸入串 0 $ i=i$ 05 $i =i$ 02 $L =i$ 03 $R =i$ 不難看出當狀態(tài) 2呈現(xiàn)于棧頂且面臨的輸入符號是＝時， 由于這個文法不含有以R＝為前綴的規(guī)范句型，因此用 R→L 進行的歸約是無效歸約 。 SLR（ 1）分析法 ∵ S?L=R?*R=R 也就是說， 并不是 FOLLOW(R)中的每個元素在含 R的所有句型中在 R的后面都會出現(xiàn) 。解決這一問題的方法是采用LR(1)分析法。 LR（ 1）分析法 在分析過程中，當試圖用某一規(guī)則A→ α歸約棧頂?shù)姆柎?α時不僅應(yīng)該察看棧中符號串 δα，還應(yīng)向前掃視一個輸入符號 a，只有當 δAa的確構(gòu)成文法某一規(guī)范句型的前綴時，才能用此規(guī)則進行歸約。 LR(1)分析法的思想 : LR（ 1）分析法 為此，我們可以考慮在原來 LR(0)項目集中 。增加更多的展望信息，這些展望信息有助于克服動作沖突和排除無效歸約。也就是需要重新定義項目，稱之為LR(1)項目 。 一個 LR(1)項目是一個二元組 [A→ α?β， a] LR（ 1）分析法 當 β＝ ε時，搜索符 a明確指出當[A→ α?β， a]是棧頂狀態(tài)的一個 LR(1)項目時，僅在輸入符號是 a時才能用 A→ α歸約， 而不是對 FOLLOW(A)中的所有符號都用 A→ α歸約 。 當 β≠ε時， 搜索符是無意義的 。 其中 A→ α?β是一個 LR(0)項目，每個a是終結(jié)符，稱為展望符或搜索符。 LR（ 1）分析法 構(gòu)造 LR(1)項目集族的方法和構(gòu)造 LR(0)項目集規(guī)范族的方法基本相同。具體構(gòu)造方法如下： (1) 構(gòu)造 LR(1)項目集 I 的閉包函數(shù) (a) I的任何 LR(1)項目都屬于 CLOSURE(I)。 (b) 若項目 [A?aB ?, a] 屬于 CLOSURE(I), B?r 是文法中的一條規(guī)則 , b?FIRST(?a),則 [B?r, b]也屬于 CLOSURE(I)。 (c) 重復 (b),直到 CLOSURE(I)不再增大為止。 LR（ 1）分析法 對例 2中的文法 G39。, 令 I=[S39?！??S， $]為初態(tài)集的初始項目集 ，對其求閉包： = CLOSURE({[S39?！??S， $]}) CLOSURE(I) = {[S39。→ ?S， $] [S→ ?L=R， $] [S→ ?R， $] [L→ ?*R， =/$] [L→ ?i， =/$] [R→ ?L， $] } = I0 0. S′→S 1. S →L=R 2. S →R 3. L → *R 4. L →i 5. R →L FIRST(βa)=FIRST($)={$} FIRST(βa)=FIRST(=R$)={=} FIRST(βa)=FIRST($)={$} FIRST(βa)=FIRST($)={$} LR（ 1）分析法 (2) 構(gòu)造轉(zhuǎn)換函數(shù) 令 I是一個 LR(1)項目集， X是一個文法符號，函數(shù) GO(I， X)=CLOSURE(J)。 J={[A→ αXβ,a] | [A→ αXβ,a]∈ I} LR（ 1）分析法 GO( I0 ,S) = { [S39?！?S， $] }= I1 GO( I0 ,*) = { [L→ *R ， =/$] [R→ L ， =/$] [L→ *R， =/$] [L→ i ， =/$] } = I4 I0 = {[S39。→ ?S， $] [S→ ?L=R， $] [S→ ?R， $] [L→ ?*R， =/$] [L→ ?i， =/$] [R→ ?L， $] } I0: S I1: S39?！?S?,$ L I2:S→ L?=R,$ R→ L?,$ I3: S→ R?,$ R I4: L→ *?R,=/$ R→ ?L,=/$ L→ ?*R,=/$ L→ ?i,=/$ * I5: L→ i?,=/$ i i S39?！??S,$ S→ ?L=R,$ S→ ?R,$ L→ ?*R,=/$ L→ ?i,=/$ R→ ?L,$ * I6: S→ L=?R,$ L→ ?*R,$ L→ ?i,$ R→ ?L,$ I9:S→ L=R?,$ I11: L→ *?R,$ R→ ?L,$ L→ ?*R,$ L→ ?i,$ I10:R→ L?,$ I12: L→ i?,$ I7: L→ *R?,=/$ I13:L→ *R?,$ I8: R→ L?,=/$ * LR(1)項目集族及轉(zhuǎn)換函數(shù) = R L R L * L i R 0. S′→S 1. S →L=R 2. S →R 3. L → *R 4. L →i 5. R →L i LR（ 1）分析法 分析所有這些項目集 ,可以發(fā)現(xiàn)每個項目集中都不含移進 —歸約沖突 ,或歸約 —歸約沖突。 在項目集 I2中，由于歸約項目 [R?L,$]的搜索符集合 {$}與移進項目 [S?L=R,$]的待移進符號‘＝’號不相交，所以在 I2中，當面臨輸入符為‘ $’時用規(guī)則 R→L 歸約，為‘＝’時則移進， I2中的移進一歸約沖突在 LR(1)分析法中得到了解決。 LR（ 1）分析法 構(gòu)造 LR(1)分析表的方法與構(gòu)造 LR(0)分析表的方法基本相同，僅對歸約項目作如下修改： 若歸約項目 [A?a,a]屬于 Ik，則對搜索符 a置 ACTION[K， a]＝ rj。其中 A→ α為文法的第 j條規(guī)則 。 按上述方法我們對例 2中文法的 LR(1)項目集族構(gòu)造相應(yīng)的 LR(1)分析表如下表所示： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ACTION GOTO i * = $ S L R S5 S4 1 2 3 acc S6 r5 r2 S5 S4 r4 r4 S12 S11 r3 r3 r5 r5 r1 8 7 10 9 r5 S12 S11 10 13 r4 r3 G[S]的 LR(1) 分析表 0. S39。→S 1. S→L=R 2. S→R 3. L→ *R 4. L→i 5. R→L I0: S I1: S39?！?S?,$ L I2:S→ L?=R,$ R→ L?,$ I3: S→ R?,$ R I4: L→ *?R,=/$ R→ ?L,=/$ L→ ?*R,=/$ L→ ?i,=/$ * I5: L→ i?,=/$ i i S39?！??S,$ S→ ?L=R,$ S→ ?R,$ L→ ?*R,=/$ L→ ?i,=/$ R→ ?L,$ * I6: S→ L=?R,$ L→ ?*R,$ L→ ?i,$ R→ ?L,$ I9:S→ L=R?,$ I11: L→ *?R,$ R→ ?L,$ L→ ?*R,$ L→ ?i,$ I10:R→ L?,$ I12: L→ i?,$ I7: L→ *R?,=/$ I13:L→ *R?,$ I8: R→ L?,=/$ * LR(1)項目集族及轉(zhuǎn)換函數(shù) = R L R L * L i R 0. S′→S 1. S →L=R 2. S →R 3. L → *R 4. L →i 5. R →L i LR（ 1）分析法 由上表可以看出，對 LR(1)的歸約項目不存在任何無效歸約。但在多數(shù)情況下同一個文法的 LR(1)項目集的個數(shù)比LR(0)項目集的個數(shù)要多。 這是因為對同一個 LR(0)項目集，由于搜索符不同而對應(yīng)著多個 LR(1)項目集。 LR（ 1）分析法 例 2中的文法 是一個 LR(1)文法，卻不是SLR(1)文法。 然而，當 一個文法是 LR(0)文法，則一定也是一個 SLR(1)文法，也是LR(1)文法。反之則不一定成立 。 如果一個文法的 LR(1)分析表不含多重入口時，或者任何一個 LR(1)項目集中沒有移進一歸約沖突或歸約一歸約沖突， 則稱該文法為 LR(1)文法。 LR（ 1）分析法 例 3 考慮拓廣文法 : 試構(gòu)造它的 LR(1)項目集合的 DFA和LR(1)分析表。 0. S39?！鶶 1. S →(S) 2. S →a LR（ 1）分析法 I0: S39?！鶶, $ S→(S), $ S→a, $ S I1: S39?！鶶, $ I3: S→a, $ a I2: S→(S), $ S→(S), ) S→a, ) S I4: S→(S), $ I6: S→a, ) I5: S→(S), ) S→(S), ) S→a, ) a ( ( a ( ) I7: S→(S),$ S I8: S→(S), ) I9: S→(S),) ) 文法 G[S]項目集合的 DFA 0. S39?！鶶 1. S →(S) 2. S →a LR（ 1）分析法 由該文法的 10個 LR(1)項目集中可以看出，均不存在移進一歸約或歸約一歸約沖突，因此該文法為 LR(1)文法。 實際上，該文法是一個 LR(0)文法，因此該文法也是 SLR(1)文法，也是LR(1)文法。該文法相應(yīng)的 LR(1)分析表如表所示。 LR（ 1）分析法 0 S3 S2 1 1 2 3 4 5 r2 r2 S6 S5 r1 4 6 7 8 9 acc r1 S7 S6 S5 S9 8 狀態(tài) GOTO ACTION a ( ) $ S LR(1) 分析表 0 S′→S 1 S →(S) 2 S →a LR（ 1）分析法 0. S39?！鶶 1. S →(S) 2. S →a I0: S39?！鶶, $ S→(S), $ S→a, $ S I1: S39。→S, $ I3: S→a, $ a I2: S→(S), $