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