【文章內(nèi)容簡介】 b 和 A→.c 和B→.aBb, B→.d 加入 I0中。 G39。： (0)S39。→S (1)S→ A (2)S→ B (3)A→ aAb (4)A→ c (5)B→ aBd (6)B→ d 由于最后加入 I0的項目在圓點之后已都是終結(jié)符了，故I0已經(jīng)“ 封閉 ”，宣告項目集 I0構(gòu)造結(jié)束。 這樣，表示初態(tài)的項目集 I0將由如下項目組成： I0 : S39?！?S, S→.A, S→.B, A→.aAb, A→.c, B→.aBd, B→.d I0 : S39?！?S, S→.A, S→.B, A→.aAb, A→.c, B→.aBd, B→.d 我們將 LR(0)項目 S‘→.S稱為 項目集 I0的基本項目 ，上述從S’→.S出發(fā)構(gòu)造項目集 I0的過程，可用一個對其基本項目集 {S39。 →.S}的閉包運算，即 closure({S39。→.S})來表示。 一般地，設 I為項目集， I的閉包 closure(I)的定義為： Closure(I)=I∪ {A→.??A→?∈ G∧ K→ ? .A?∈ closure(I)∧ ?∈ V*∧ ?∈ V*} 故構(gòu)造 closure(I)的算法為： 1） I中的每一個項目都屬于 closure(I)。 2）若形如 K→?.A?的項目屬于 I，且 A→?是文法的一個產(chǎn)生式， 則關于產(chǎn)生式 A的任何形如 A→.?的項目也應加到 closure(I)中 （若它們不在 closure(I)中）； 3）重復上述過程，直至不再有新的項目加入到 closure(I)中為 止。 有了初態(tài)項目集 I0之后，我們來說明如何確定從 I0可能轉(zhuǎn)移到的下一狀態(tài)。設 A為一文法符號 (A∈ V)，若 I0中有圓點位于 A左邊的項目 K→? .A?(其中 ?可能為 ?)，則當分析器從輸入串識別出 (即移進或歸約出 )文法符號 A后，分析器將進入它的下一狀態(tài)。設此狀態(tài)為 Ii ，顯然 Ii中必含有全部形如 K→?A .?的項目，我們將這樣的項目稱為 K→? .A?的 后繼項目 。對于每一個文法符號 A，如果存在這樣的后繼項目，則可能不只一個，設其組成集合 J，則 J中的每個項目都是項目集 Ii的基本項目，因此，按照與上面構(gòu)造項目集 I0相類試的討論，我們有： Ii =closure(J) 為了指明 Ii是“ I0關于文法符號 A的后繼狀態(tài)”這一事實，我們可定義一個狀態(tài)轉(zhuǎn)移函數(shù)： GO(I0,A)=closure(J) = Ii 其中， I是當前狀態(tài)， A為文法符號， J是 I中所有形如 K→?.A? 的項目之后繼項目 K→?A.?所組成的集合，而 closure(J)就是項目集 I（即狀態(tài) I)關于符號 A的后繼項目集（即后繼狀態(tài)）。 狀態(tài)轉(zhuǎn)移函數(shù)： GO(I0,A)=closure(J) = Ii 其中， I是當前狀態(tài)， A為文法符號， J是 I中所有形如 K→?.A? 的項目之后繼項目 K→?A.?所組成的集合，而 closure(J)就是項目 集 I（即狀態(tài) I)關于符號 A的后繼項目集（即后繼狀態(tài)）。 即： GO(I,A)=closure({所有形如 [K→?A .?]的項目 ?[K→? .A?]∈ I}) 對于上例，我們有： I1 =GO(I0,S)=closure({S39。→S.}) I1 : S39。→S . 。 I2 =GO(I0,A)=closure({S→A.}) I2 :S→A . 。 I3 =GO(I0,B)=closure({S→B.}) I3 : S→B . 。 I4 =GO(I0,a)=closure({A→a . Ab,B→a . Bd}) G39。： (0)S39?！鶶 (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. 此時，我們求出了 I0的全部后繼項目集 I1, I2,I3,I4,I5,I6,而 I1, I2,I3, I5,I6均無后繼項目集，僅 I4有后繼項目集： 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 這些項目集均不產(chǎn)生新的項目集。另外還有 : G39。： (0)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.} 此時 I8 ， I10也已無后繼項目集，故我們已求出文法 G[S39。]的全部 項目集 I0～ I10 。 通常我們將這些項目集的全體稱為文法 G[S39。]的 LR(0)項目集規(guī)范族，并記為 C=(I0, I1,…, I 10) 于是，我們所要構(gòu)成的識別文法 G[S39。]的全部活前綴的 DFA為 M=(C,V,GO, I0,Z) 其中 C— M的狀態(tài)集，即文法 G[S39。]的 LR(0)項目集規(guī)范族 , C=(I0, I1,…, I10)。 V— M的字母表，即 V={S39。,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ī)范族中所有含有歸約項目的 那些項目集。 DFA: I0 : S39。→.S S→.A S→.B A→.aAb A→.c B→.aBd B→.d I1 :S39?！鶶. 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。： (0)S39?！鶶 (1)S→ A (2)S→ B (3)A→ aAb (4)A→ c (5)B→ aBd (6)B→ d 圖 文法 G[S39。]項目集規(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。： (0)S39?！鶶 (1)S→ A (2)S→ B (3)A→ aAb (4)A→ c (5)B→ aBd (6)B→ d a 圖 識別文法 G[S‘]活前綴的 DFA LR(0)分析表的構(gòu)造 對于一個文法 G的拓廣文法 G39。，當識別它的全部活前綴的 DFA 作出之后，我們可以據(jù)此構(gòu)造相應的 LR(0)分析表了。 然而，要注意的是，用前述方法所構(gòu)造的每一個 LR(0)項目集 實質(zhì)上表征了在分析過程中可能出現(xiàn)的一種分析狀態(tài)；再根據(jù)前 面對 LR(0)項目的分類，項目集中的每一個項目又與某一種分析 動作相關聯(lián)，因此，就要求每一個項目集中的的諸項目應當是相 容的。所謂相容，是指在一個項目集中不出現(xiàn)下列的情況： （ 1）移進項目和歸約項目并存，即存在移進 — 歸約沖突； （ 2）多個歸約項目并存，即存在歸約 — 歸約沖突。 如果一個文法 G滿足上述條件，也就是它的每個 LR(0)項目集 中都不含有沖突的項目，則稱 G為 LR(0)文法。 顯然，只有當一個文法是 LR(0)文法時，才能對它構(gòu)造不含沖 突動作的 LR(0)分析表來。 為了方便起見，我們用整數(shù) 0， 1， 2， … 表示狀態(tài) I0 , I1, I2, …。 分析表的內(nèi)容由兩部分組成，一部分為動作 (ACTION)表，它表示當前狀態(tài)下所面臨的輸入符號應做的動作是移進、歸約、接受或出錯。另一部分為狀態(tài)轉(zhuǎn)移（ GOTO)表，它表示在當前狀態(tài)下面臨文法符號時應轉(zhuǎn)向的下一個狀態(tài)，相當于識別活前綴的有限自動機 DFA的狀態(tài)轉(zhuǎn)換矩陣。分析表的行標為狀態(tài)號，動作表的列標為只包含終結(jié)符和“ ”；狀態(tài)轉(zhuǎn)移表的列標為 非終結(jié)符 ，而將其有關終結(jié)符的各列并入到 ACTION表的各列中去，也就是把當前狀態(tài)下面臨終結(jié)符應作的動作和狀態(tài)轉(zhuǎn)移用同一數(shù)組元素表示 ，以便節(jié)省存儲空間。 構(gòu)造 LR(0)分析表的算法為： (1)對于每一項目集 Ii中形如 A→?.X?的項目，且有 GO(Ii,X)=Ij, 若 X為一終結(jié)符號 a 時，則置 ACTION[i,a]=Sj。 若 X為一非終結(jié)符號時，則僅置 GOTO[i,X]=j (2)若 Ii中有歸約項目 A→?. ,設 A→?為文法第 j個產(chǎn)生式，則對 文法的任何終結(jié)符和“ ”（均記為 a）置 ACTION[i,a]=Rj (3)若接受項目 S39。→S .屬于 Ii ,則置 ACTION[i,]=acc。 (4)在分析表中 ,凡不能按上述規(guī)則填入信息的元素 ,均置為“出錯”。 如上例可構(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)對于每一項目集 Ii中形如 A→?.X?的項目，且有 GO(Ii,X)=Ij, 若 X為一終結(jié)符號 a 時，則置 ACTION[i,a]=Sj。 若 X為一非終結(jié)符號時，則僅置 GOTO[i,X]=j (2)若 Ii中有歸約項目 A→?. ,設 A→?為文法第