【正文】 根據(jù)上述規(guī)則，我們對 LR(1)項目集族構(gòu)造其相應(yīng)的 LR(1)分析表如表 。,a] 屬于 Ik，則置 ACTION[k,a]= rj。 LR(1)分析表的構(gòu)造除 (2) 外，其余同 LR(0)或 SLR(1)。 (5) 凡不能用規(guī)則 (1)~(4)填入分析表中的元素，均置“報錯標(biāo)志”。 (4) 若 GO(Ik， A)＝ Ij，其中 A∈V N，則置 GOTO[k,A]＝ j。 (3) 若項目 [S?→S,a] 屬于 Ik，則置 ACTION[k,a]= rj 其中a∈V T， rj 的含義為把當(dāng)前棧頂符號串 α 歸約為 A(即用產(chǎn)生式 A→ α 歸約 )。其 Sj的含義是把輸入符號 a和狀態(tài) j分別移入文法符號棧和狀態(tài)棧。 C＝ {I0,I1,?,I n}，其中 Ik的 k為分析器的狀態(tài)，則動作 ACTION表和狀態(tài)轉(zhuǎn)換 GOTO表構(gòu)造方法如下： (1) 若項目 [A→ α LR(1)分析表的構(gòu)造 由于一個 LR(1)項目可以看成兩個部分組成，一部分和 LR(0)項目相同部分我們稱它為心，另一部分為向前搜索符集合，因而 LR(1)分析表的構(gòu)造與 LR(0)分析表的構(gòu)造大部分相同，僅對歸約項目的歸約動作取決于該歸約項目的向前搜索符集，只有當(dāng)面臨輸入符屬于向前搜索符的集合，才做歸約動作，其它情況均出錯。, I11： S→bed, I9： S→aecd, A→e,d I6： S→bAd, I5： S→aeed, A→e,d I3： S→bAd, S→abed, I1： S′→SbAc, S→S, S→ 也就是對狀態(tài) I經(jīng)過符號 X后轉(zhuǎn)向狀態(tài) J，求出 J的基本項目后，對基本項目求閉包即為 CLOSURE(J)。 對文法 G′ 的 LR(1)項目集族的構(gòu)造仍以 [S′→ γ ， b加到 J中 until 再沒有項目加到 J中 return J }； 對項目 [A→ α B β ,a]和產(chǎn)生式 B→ γ ； α ， β ， γ ∈V *； b ∈FIRST( β a), 若 B→ β ,a]的項目 |A→ α c) 重復(fù) b)直到 CLOSURE(I)不再增大為止。B β ,a]屬于 CLOSURE(I)， B→ γ 是文法中的產(chǎn)生式， β ∈V *， b∈FIRST( β a)，則 [B→具體構(gòu)造步驟如下： (1) 構(gòu)造 LR(1)項目集的閉包函數(shù)。因此對初始項目[S′→39。39。如讓 S′→]需要用產(chǎn)生式 B→ γ 歸約，這時向前查看的符號集合是FIRST(β )，而 FIRST(β )? FOLLOW（ B）。 γ ]。如在項目集 I中有項目： [A→ α 不妨考慮，把 FIRST(β )作為用產(chǎn)生式 B→ γ 歸約的搜索符，稱為 向前搜索符 ，作為歸約時查看的符號集合，用以代替 SLR(1)分析中的 FOLLOW集，把此搜索符號的集合也放在相應(yīng)項目的后面，這種處理方法即為 LR(1)方法。B β ]∈ 項目集 I， 則 [B→d 而 A→e再看在 I7中。回顧 LR分析過程，若輸入符號串是所給文法的句子，那么分析過程的任何時刻在文法符號棧中的符號和剩余的輸入串符號合起來總是構(gòu)成該文法的規(guī)范句型。 R R R S? ?S?aAd?aed R R S? ?S?aec (0) S? →S (1) S→aAd (2) S→bAc (3) S→aec (4) S→bed (5) A→e 這兩個最右推導(dǎo)已包括了活前綴為 a的所有句型，因此，不難看出對活前綴 ae來說，當(dāng)面臨輸入符號為 c時應(yīng)移進(jìn)，面臨 d時應(yīng)用產(chǎn)生式A→e歸約。 現(xiàn)在我們再看圖 I5， I7項目集中的移進(jìn) 歸約沖突，不能用 SLR(1)方法解決的原因如下： I5： S→ae 由于用 SLR(1)方法解決動作沖突時，對于歸約項目A→ α 而歸約項目左部非終結(jié)符的 FOLLOW(A)={c,d} 在 I5中， FOLLOW(A)∩{c}={c,d}∩{c}≠ Φ 在 I7中， FOLLOW(A) ∩nhcuj7d3={c,d}∩nhcuj7d3≠ Φ 因此 I5， I7中沖突不能用 SLR(1)方法解決。d A→e I5： S→aeS 作為初態(tài)集的項目，然后用閉包函數(shù)和轉(zhuǎn)換函數(shù)構(gòu)造識別文法 G′ 的識別活前綴的有限自動機(jī)DFA如圖 。 例 :有下列文法 G′, 構(gòu)造構(gòu)造識別文法 G′ 的識別活前綴的有限自動機(jī)。因此該 文法是 SLR(1)文法。 對于 I9,與 I2類似，當(dāng)面臨輸入符號為“ +”，“）”或“ ”時，則用產(chǎn)生式 E→E+T歸約；當(dāng)面臨輸入符號為“ *”時，則移進(jìn)，其余情況報錯。 對于 I2,因 FOLLOW(E)={+,),}∩{*}=φ ,因此當(dāng)面臨輸入符號為“ +”，“ ）”或“ ”號時，則用產(chǎn)生式 E→T歸約。)={).而 S39。)= {} FOLLOW(E)= {+， )， } FOLLOW(T)= {+， *， )， } FOLLOW(F)= {+， *， )， } 現(xiàn)在分別考慮上述三個沖突項目中的沖突是否能用 SLR(1)方法解決。存在移進(jìn) — 歸約沖突，因而該文法不屬于 LR(0)文法，故不能構(gòu)造 LR(0)分析表?！?E E→.E+T E→.T T→.T*F T→.F F→.(E) F→.i I2: E→T. T→T.*F I5: F→i. I1: S39?！?E GO(I0,E)=I1 E→.E+T GO(I0,E)=I1 E→.T GO(I0,T)=I2 T→.T*F GO(I0,T)=I2 T→.F GO(I0,F)=I3 F→.(E) GO(I0,( )=I4 F→.i GO(I0,i )=I5 I1: S39?！鶨 (1) E→E+T (2) E→T (3) T→T*F (4) T→F (5) F→(E) (6) F→i 再求識別 G39。[S39。 例如： 有算術(shù)表達(dá)式文法 G[E],構(gòu)造其 LR(0)項目規(guī)范簇和 SLR(1)分析表。）若歸約項目 A→?.屬于 Ii,設(shè) A→?為文法第 j個行產(chǎn)生式，則對任何屬于 FOLLOW(A)的輸入符號 a,置 ACTION[i,a]=Rj 。 (4) 在分析表 ,凡不能按上述規(guī)則填入信息的元素 ,均置為“出錯”。)若歸約項目 A→?.屬于 Ii,設(shè) A→?為文法第 j個行產(chǎn)生式，則 對任何屬于 FOLLOW(A)的輸入符號 a,置 ACTION[i,a]=Rj； (3)若接受項目 S39。 修改為 ： 即： (1)對于每一項目集 Ii中形如 ，且有 GO(Ii,X)=Ij, 若 X為一終結(jié)符號 a時，則置 ACTION[I,a]=Sj。 3）此外，則報錯。同時含 有 n個歸約項目： B1→?1. , B2→ ?2. ,…, B n→ ?n. ,只要集合 {b1, b2,… bm}和 FOLLOW(B1),FOLLOW(B2),…,FOLLOW(B n) 兩兩交集都為空，則我們?nèi)钥捎蒙鲜鰵w則來解決沖突： 1）若 a∈ {b1, b2,…, bm},則移進(jìn)。 3）若 a ∈ FOLLOW(B),則用產(chǎn)生式 B→?歸約。那么只要在所有 含有 A或 B的句型中，直接跟在 A或 B后面的可能終結(jié)符集合 FOLLOW(A)和 FOLLOW(B)互不相交，且都不包含 b,即只要滿足： FOLLOW(A)∩FOLLOW(B)=φ FOLLOW(A)∩=φ FOLLOW(B)∩=φ 即： FOLLOW(A)∩FOLLOW(B)∩ =φ 那么，當(dāng)在狀態(tài) I面臨某輸入符號為 a時，則動作可由下述規(guī)定決策： 1）若 a = b,則移進(jìn)。這種分析方法 因為只對有沖突的狀態(tài)才向前查看一個符號，以確定做什么動作 ，故稱這種分析方法為簡單的 LR(1)分析法，用 SLR(1)表示。 SLR(1)分析 因大多數(shù)程序設(shè)計語言的文法不能滿足 LR(0)文法的條件，即使是描述一個變量這樣簡單的文法也不是 LR(0)文法。 3）若 ACTION[i,a]=Acc,（此時 a應(yīng)為“ ”號），則表明 分析成功 ， 結(jié)束分析。 2）若 ACTION[i,a]=Rj， a∈ VT或 ，則用第 j個產(chǎn)生式 歸約 。 若 X為一非終結(jié)符號時，則僅置 GOTO[i,X]=j (2)若 Ii中有歸約項目 A→?. ,設(shè) A→?為文法第 j個產(chǎn)生式，則對 文法的任何終結(jié)符和“ ”（均記為 a）置 ACTION[i,a]=Rj LR(0)分析器的工作過程 對于一個文法構(gòu)造了它的 LR(0)分析表就可以在 LR分析器的總 控程序控制下對輸入串進(jìn)行分析，即 根據(jù)輸入串當(dāng)前符號 a和分析 棧棧頂狀態(tài) i查找分析表應(yīng)采取的動作 ，對狀態(tài)棧和符號棧進(jìn)行相 應(yīng)的操作即 移進(jìn)、歸約、接受或報錯 。 (4)在分析表中 ,凡不能按上述規(guī)則填入信息的元素 ,均置為“出錯”。 若 X為一非終結(jié)符號時，則僅置 GOTO[i,X]=j (2)若 Ii中有歸約項目 A→?. ,設(shè) A→?為文法第 j個產(chǎn)生式，則對 文法的任何終結(jié)符和“ ”（均記為 a）置 ACTION[i,a]=Rj (3)若接受項目 S39。分析表的行標(biāo)為狀態(tài)號，動作表的列標(biāo)為只包含終結(jié)符和“ ”；狀態(tài)轉(zhuǎn)移表的列標(biāo)為 非終結(jié)符 ，而將其有關(guān)終結(jié)符的各列并入到 ACTION表的各列中去，也就是把當(dāng)前狀態(tài)下面臨終結(jié)符應(yīng)作的動作和狀態(tài)轉(zhuǎn)移用同一數(shù)組元素表示 ，以便節(jié)省存儲空間。 分析表的內(nèi)容由兩部分組成，一部分為動作 (ACTION)表，它表示當(dāng)前狀態(tài)下所面臨的輸入符號應(yīng)做的動作是移進(jìn)、歸約、接受或出錯。 顯然，只有當(dāng)一個文法是 LR(0)文法時，才能對它構(gòu)造不含沖 突動作的 LR(0)分析表來。所謂相容，是指在一個項目集中不出現(xiàn)下列的情況： （ 1）移進(jìn)項目和歸約項目并存，即存在移進(jìn) — 歸約沖突； （ 2）多個歸約項目并存，即存在歸約 — 歸約沖突。當(dāng)識別它的全部活前綴的 DFA 作出之后，我們可以據(jù)此構(gòu)造相應(yīng)的 LR(0)分析表了。： (0)S39?！鶶 (1)S→ A (2)S→ B (3)A→ aAb (4)A→ c (5)B→ aBd (6)B→ d 圖 文法 G[S39。→S. I2 :S→A. I3 :S→B. I4 :A→ A→ A→.aAb A→.c B→.aBd B→.d I8 :A → aAb. I7 :A → I9 :B → I10 :B → aBd. I5 :A→c. I6 :B→d. A B d b c d d a c S A B a G39。 DFA: I0 : S39。 V— M的字母表，即 V={S39。]的全部活前綴的 DFA為 M=(C,V,GO, I0,Z) 其中 C— M的狀態(tài)集，即文法 G[S39。 通常我們將這些項目集的全體稱為文法 G[S39。→S (1)S→ A (2)S→ B (3)A→ aAb (4)A→ c (5)B→ aBd (6)B→ d I8 =GO(I7,b)=closure({A→aAb.})={A→aAb.} I10 =GO(I9,b)=closure({B→aBd.})={B→aBd.} 此時 I8 ， I10也已無后繼項目集，故我們已求出文法 G[S39。另外還有 : G39。： (0)S39。 I3 =GO(I0,B)=closure({S→B.}) I3 : S→B . ?！鶶 . 。 即： GO(I,A)=closure({所有形如 [K→?A .?]的項目 ?[K→? .A?]∈ I}) 對于上例，我們有： I1 =GO(I0,S)=closure({S39。對于每一個文法符號 A，如果存在這樣的后繼項目，則可能不只一個，設(shè)其組成集合 J，則 J中的每