【正文】 A→?1 .?2 。 我們把右部某位置上標(biāo)有圓點(diǎn)的產(chǎn)生式稱為相應(yīng)文法的一個(gè) LR(0)項(xiàng)目。 顯然不同的 LR(0)項(xiàng)目，反映了分析過(guò)程中符號(hào)棧頂?shù)牟煌闆r。 [0] S→.aAcBe [1] S→ [2] S→ [3] S→ [4] S→ [5] S→aAcBe. 例如：產(chǎn)生式 S→aAcBe對(duì)應(yīng)有六個(gè)項(xiàng)目。概括地說(shuō)，圓點(diǎn)左邊的子串表示在分析過(guò)程的某一時(shí)刻用該產(chǎn)生式歸約時(shí)句柄中已識(shí)別過(guò)的部分，圓點(diǎn)右邊的子串表示待識(shí)別的部分。 LR(0)項(xiàng)目的分類： 例：考慮文法 G[S]=({S,A,B}, {a,b,c,d},P,S),構(gòu)造其分析表： 其中 P: (1)S→ A (2)S→ B (3)A→ aAb (4)A→ c (5)B→ aBd (6)B→ d 解：求該文法的項(xiàng)目集規(guī)范族 C： 為了方便起見(jiàn)，我們?cè)谏鲜鑫姆ㄖ幸鹨粋€(gè)新的開(kāi)始符號(hào) S39。 →S作為第 0個(gè)產(chǎn)生式添加到文法 G中，從而得到了所謂 G的拓廣文法 G39。)=L(G)，則對(duì)于文法 G39。 →.S 2) S39。： (0)S39。 aβ ? 待約項(xiàng)目： A → α ? 接受項(xiàng)目： S’ → S 在作出文法的全部 LR(0)項(xiàng)目之后，現(xiàn)在將用它們來(lái)構(gòu)造識(shí)別 全部活前綴的 DFA。 下面以上例中的文法為例來(lái) 說(shuō)明構(gòu)造 DFA的方法。： (0)S39?；蛘叻催^(guò)來(lái)說(shuō)，我們所期待的是，從使用產(chǎn)生式 S39。因此，我們應(yīng)將項(xiàng)目 S39。換言之，也就是我們正期待將要掃描的輸入串正好就是能由 S39。 然而，我們不能從輸入串中直接讀出非終結(jié)符號(hào) S，因此我們也應(yīng)將項(xiàng)目S→.A 和 S→.B 加入 I0中。 G39?！鶶 (1)S→ A (2)S→ B (3)A→ aAb (4)A→ c (5)B→ aBd (6)B→ d 由于最后加入 I0的項(xiàng)目在圓點(diǎn)之后已都是終結(jié)符了，故I0已經(jīng)“ 封閉 ”，宣告項(xiàng)目集 I0構(gòu)造結(jié)束?！?S, S→.A, S→.B, A→.aAb, A→.c, B→.aBd, B→.d I0 : S39。 →.S}的閉包運(yùn)算，即 closure({S39。 一般地，設(shè) I為項(xiàng)目集， I的閉包 closure(I)的定義為： Closure(I)=I∪ {A→.??A→?∈ G∧ K→ ? .A?∈ closure(I)∧ ?∈ V*∧ ?∈ V*} 故構(gòu)造 closure(I)的算法為： 1） I中的每一個(gè)項(xiàng)目都屬于 closure(I)。 有了初態(tài)項(xiàng)目集 I0之后，我們來(lái)說(shuō)明如何確定從 I0可能轉(zhuǎn)移到的下一狀態(tài)。設(shè)此狀態(tài)為 Ii ，顯然 Ii中必含有全部形如 K→?A .?的項(xiàng)目，我們將這樣的項(xiàng)目稱為 K→? .A?的 后繼項(xiàng)目 。 狀態(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)）。→S.}) I1 : S39。 I2 =GO(I0,A)=closure({S→A.}) I2 :S→A . 。 I4 =GO(I0,a)=closure({A→a . Ab,B→a . Bd}) G39?！鶶 (1)S→ A (2)S→ B (3)A→ aAb (4)A→ c (5)B→ aBd (6)B→ d I4 : A→ B→ A→.aAb B→.aBd A→.c B→.d I5=GO(I0,c)=closure({A→c.}) I5 : A→c. I6=GO(I0,d)=closure({B→d.}) I6 :B→d. 此時(shí)，我們求出了 I0的全部后繼項(xiàng)目集 I1, I2,I3,I4,I5,I6,而 I1, I2,I3, I5,I6均無(wú)后繼項(xiàng)目集，僅 I4有后繼項(xiàng)目集： I7 =GO(I4,A)=closure({A→})={A→} I9 =GO(I4,B)=closure({B→})={B→} 此外，還有： GO(I4,a)=closure({A→, B→})= I4 GO(I4,c)=closure({A→c.})= I5 GO(I4,d)=closure({B→d.})= I6 這些項(xiàng)目集均不產(chǎn)生新的項(xiàng)目集。： (0)S39。]的全部 項(xiàng)目集 I0～ I10 。]的 LR(0)項(xiàng)目集規(guī)范族，并記為 C=(I0, I1,…, I 10) 于是，我們所要構(gòu)成的識(shí)別文法 G[S39。]的 LR(0)項(xiàng)目集規(guī)范族 , C=(I0, I1,…, I10)。,S,A,B,a,b,c,d}； GO— M的映射函數(shù)，即上面定義的狀態(tài)轉(zhuǎn)移函數(shù) GO； I0— M的唯一初態(tài)； Z— M的終態(tài)集， Z?C，為規(guī)范族中所有含有歸約項(xiàng)目的 那些項(xiàng)目集?！?S S→.A S→.B A→.aAb A→.c B→.aBd B→.d I1 :S39。： (0)S39。]項(xiàng)目集規(guī)范族 DFA: 即： ? I0 I1 I2 I3 I4 I5 I6 I7 I9 I8 I10 S A B a c d c d A B b d G39?！鶶 (1)S→ A (2)S→ B (3)A→ aAb (4)A→ c (5)B→ aBd (6)B→ d a 圖 識(shí)別文法 G[S‘]活前綴的 DFA LR(0)分析表的構(gòu)造 對(duì)于一個(gè)文法 G的拓廣文法 G39。 然而，要注意的是，用前述方法所構(gòu)造的每一個(gè) LR(0)項(xiàng)目集 實(shí)質(zhì)上表征了在分析過(guò)程中可能出現(xiàn)的一種分析狀態(tài)；再根據(jù)前 面對(duì) LR(0)項(xiàng)目的分類，項(xiàng)目集中的每一個(gè)項(xiàng)目又與某一種分析 動(dòng)作相關(guān)聯(lián)，因此，就要求每一個(gè)項(xiàng)目集中的的諸項(xiàng)目應(yīng)當(dāng)是相 容的。 如果一個(gè)文法 G滿足上述條件，也就是它的每個(gè) LR(0)項(xiàng)目集 中都不含有沖突的項(xiàng)目，則稱 G為 LR(0)文法。 為了方便起見(jiàn)，我們用整數(shù) 0， 1， 2， … 表示狀態(tài) I0 , I1, I2, …。另一部分為狀態(tài)轉(zhuǎn)移（ GOTO)表，它表示在當(dāng)前狀態(tài)下面臨文法符號(hào)時(shí)應(yīng)轉(zhuǎn)向的下一個(gè)狀態(tài)，相當(dāng)于識(shí)別活前綴的有限自動(dòng)機(jī) DFA的狀態(tài)轉(zhuǎn)換矩陣。 構(gòu)造 LR(0)分析表的算法為： (1)對(duì)于每一項(xiàng)目集 Ii中形如 A→?.X?的項(xiàng)目，且有 GO(Ii,X)=Ij, 若 X為一終結(jié)符號(hào) a 時(shí)，則置 ACTION[i,a]=Sj?！鶶 .屬于 Ii ,則置 ACTION[i,]=acc。 如上例可構(gòu)造分析表為： ACTION GOTO a b c d S A B 0 S4 S5 S6 1 2 3 1 Acc 2 R1 R1 R1 R1 R1 3 R2 R2 R2 R2 R2 4 S4 S5 S6 7 9 5 R4 R4 R4 R4 R4 6 R6 R6 R6 R6 R6 7 S8 8 R3 R3 R3 R3 R3 9 S10 10 R5 R5 R5 R5 R5 構(gòu)造 LR(0)分析表的算法為： (1)對(duì)于每一項(xiàng)目集 Ii中形如 A→?.X?的項(xiàng)目，且有 GO(Ii,X)=Ij, 若 X為一終結(jié)符號(hào) a 時(shí)，則置 ACTION[i,a]=Sj。具體為： 1）若 ACTION[i,a]=Sj, a∈ VT,則把 a移進(jìn) 符號(hào)棧， j移進(jìn) 狀態(tài)棧。并將 兩個(gè)棧的指針減去 K(其中 K為第 j 個(gè)產(chǎn)生式右部的串長(zhǎng)度 ），并 把產(chǎn)生式的左部符號(hào) A壓入符號(hào)棧，同時(shí)用符號(hào)對(duì)（ Sik,A)去查 GOTO表（其中 Sik為狀態(tài)棧當(dāng)前棧頂元素，若 GOTO[Sik,A]=j, 則 j壓入狀態(tài)棧， 使得兩個(gè)棧內(nèi)的元素一樣多 。 4）若 ACTION[i,a]=空白，轉(zhuǎn) 出錯(cuò)處理 。因此下面將介紹對(duì) LR(0)規(guī)范族中有沖突的項(xiàng)目集（狀態(tài)）用向前查 看一個(gè)（輸入）符號(hào)的辦法進(jìn)行處理，以解決沖突。 假定有一個(gè) LR(0)規(guī)范族中含有如下項(xiàng)目集 (狀態(tài) )I: I={X→?.b?,A→?., B→?.}其中 ?,?,?,?為符號(hào)串， b∈ VT, 顯然 I中含有移進(jìn) — 歸約和歸約 — 歸約沖突。 2）若 a ∈ FOLLOW(A),則用產(chǎn)生式 A→?歸約。 一般地，對(duì)于 LR(0)規(guī)范族的一個(gè)項(xiàng)目集 I可能含有多個(gè)移進(jìn)項(xiàng)目和多個(gè)歸約項(xiàng)目，我們可假設(shè)項(xiàng)目集 I中有 m個(gè)移進(jìn)項(xiàng)目： A1→?1. b1?1, A2→ ?2. b2?2, …, A m→ ?m. bm?m。 2）若 a∈ FOLLOW(Bi),i=1,…,n, 則用 Bi→ ?i進(jìn)行歸約。 所以，我們只須把構(gòu)造 LR(0)分析表算法中的規(guī)則 (2)，即： (2)若 Ii中有歸約項(xiàng)目 A→?. ,設(shè) A→?為文法第 j個(gè)產(chǎn)生式，則對(duì) 文法的任何終結(jié)符和“ ”（均記為 a）置 ACTION[i,a]=Rj 。 若 X為一非終結(jié)符號(hào)時(shí)，則僅置 GOTO[i,X]=j； (239。 → Ii ,則置 ACTION[i,]=acc。 （ 239。 其余的規(guī)則不變，就得到了構(gòu)造 SLR(1)分析表的算法。 G[E]: E→E+T?T T→T*F?F F→(E) ? i 解： 拓廣文法 為 G39。] : (0) S39。的全部活前綴的 DFA（即 LR(0)的項(xiàng)目集規(guī)范簇）： I0: S39?！鶨. E→E.+T GO(I1,+)=I6 I2: E→T. T→T.*F GO(I2,*)=I7 I3: T→F. I4: F→(.E) GO(I4,E)=I8 E→.E+T GO(I4,E)=I8 E→.T GO(I4,T)=I2 T→.T*F GO(I4,T)=I2 T→.F GO(I4,F)=I3 F→.(E) GO(I4,( )=I4 F→.i GO(I4,i)=I5 I5: F→i. I6: E→E+.T GO(I6,T)=I9 T→.T*F GO(I6,T)=I9 T→.F