【正文】 個(gè)項(xiàng)目都是項(xiàng)目集 Ii的基本項(xiàng)目，因此，按照與上面構(gòu)造項(xiàng)目集 I0相類(lèi)試的討論，我們有： 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)）。設(shè) A為一文法符號(hào) (A∈ V)，若 I0中有圓點(diǎn)位于 A左邊的項(xiàng)目 K→? .A?(其中 ?可能為 ?)，則當(dāng)分析器從輸入串識(shí)別出 (即移進(jìn)或歸約出 )文法符號(hào) A后，分析器將進(jìn)入它的下一狀態(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)中）； 3）重復(fù)上述過(guò)程，直至不再有新的項(xiàng)目加入到 closure(I)中為 止?！?S})來(lái)表示?！?S, S→.A, S→.B, A→.aAb, A→.c, B→.aBd, B→.d 我們將 LR(0)項(xiàng)目 S‘→.S稱(chēng)為 項(xiàng)目集 I0的基本項(xiàng)目 ，上述從S’→.S出發(fā)構(gòu)造項(xiàng)目集 I0的過(guò)程，可用一個(gè)對(duì)其基本項(xiàng)目集 {S39。 這樣，表示初態(tài)的項(xiàng)目集 I0將由如下項(xiàng)目組成： I0 : S39。： (0)S39。由于 A和 B同樣是非終結(jié)符，所以也應(yīng)將 A→.aAb 和 A→.c 和B→.aBb, B→.d 加入 I0中。推導(dǎo)出的任何終結(jié)符串?！?S 列入項(xiàng)目集 I0之中。→S 開(kāi)始，能夠逐漸推導(dǎo)出所給定的輸入串。→S (1)S→ A (2)S→ B (3)A→ aAb (4)A→ c (5)B→ aBd (6)B→ d 首先我們用 I0表示這個(gè) DFA的初態(tài)，它預(yù)示著整個(gè)分析過(guò)程的開(kāi)始，并且期待著將給定的輸入串逐步歸約為文法的開(kāi)始符號(hào) S39。 G39。這種 DFA中的中每一個(gè)狀態(tài)由若干個(gè) LR(0) 項(xiàng)目所組成的集合（稱(chēng)為項(xiàng)目集）來(lái)表示。 圓點(diǎn)的左部表示分析過(guò)程中的某時(shí)刻用該產(chǎn)生式歸約時(shí)句柄已識(shí)別過(guò)的部分，圓點(diǎn)右部表示待識(shí)別部分 構(gòu)造識(shí)別活前綴的 DFA 在 LR方法實(shí)際過(guò)程中，并不是去直接分析符號(hào)棧中的符號(hào) 是否已形成句柄，但它給我們一個(gè)啟示，我們可以把 終結(jié)符和非 終結(jié)符 都可看成一個(gè)有限自動(dòng)機(jī)的 輸入符號(hào) ，每把一個(gè)符號(hào)進(jìn)棧 時(shí)看成已識(shí)別過(guò)該符號(hào)，而狀態(tài)進(jìn)行轉(zhuǎn)換（到下一狀態(tài)），當(dāng)識(shí) 別到可歸前綴時(shí)相當(dāng)于棧頂已形成了句柄，則認(rèn)為到達(dá)了識(shí)別句 柄的 終態(tài) 。 Bβ ? 歸約項(xiàng)目： A → α→S (1)S→ A (2)S→ B (3)A→ aAb (4)A→ c (5)B→ aBd (6)B→ d 如前所述，由于不同的項(xiàng)目反映了分析過(guò)程中棧頂?shù)牟煌闆r， 因此，我們可根據(jù)它們不同的作用，將一個(gè)文法的全部 LR(0)項(xiàng)目 進(jìn)行分類(lèi)： ? 移進(jìn)項(xiàng)目： A → α → S. 3) S→.A 4) S→A . 5) S→.B 6) S→B. 7) A→.aAb 8) A→a .Ab 9) A→aA .b 10) A→aAb . 11) A→.c 12) A→c . 13) B→.aBd 14) B→a .Bd 15) B→aB .d 16) B→aBd . 17)B→.d 18) B→d . G39。其 LR(0) 項(xiàng)目為： 1) S39。顯然 L(G39。, 且將 S39。 文法的全部 LR(0)項(xiàng)目將是構(gòu)造識(shí)別它的所有活前綴的有窮自動(dòng)機(jī)的基礎(chǔ)。 [0] S→.aAcBe [1] S→ [2] S→ [3] S→ [4] S→ [5] S→aAcBe. 一個(gè)產(chǎn)生式可對(duì)應(yīng)的項(xiàng)目的數(shù)量為它的右部符號(hào)串長(zhǎng)度加 1，值得注意的是對(duì)空產(chǎn)生式，即 A→ε僅有項(xiàng)目 A→. 每個(gè)項(xiàng)目的含義與圓點(diǎn)的位置有關(guān)。 例如：產(chǎn)生式 S→aAcBe對(duì)應(yīng)有六個(gè)項(xiàng)目。特別地，對(duì)形如 A→? 的產(chǎn)生式，相應(yīng)的 LR(0)項(xiàng)目表示為 A→.。 A→.? 。 為了刻畫(huà)在分析過(guò)程中，文法的一個(gè)產(chǎn)生式右部符號(hào)串有多大 部分已被識(shí)別，我們可在該產(chǎn)生式的右部相應(yīng)位置上加一個(gè)圓點(diǎn) “ .”，來(lái)指示位置，標(biāo)明在“ .”前的部分已被識(shí)別。 第三種情況則意味著： 期望從余留輸入串中能看到由某產(chǎn)生式 A→?的右部，即 ?所代表的符號(hào)串 (即句柄 ) 。 第二種情況表明： 形如 A→?1?2的產(chǎn)生式的 右部子串已在符號(hào)棧棧頂，如 ?1， 正期待著從余留的輸入串中看到能由 β推出的 符號(hào)串，即期待 ?2 進(jìn)棧以便能進(jìn)行歸約。 （ 3） 活前綴中全然不包含句柄的任何符號(hào)。 ? 只要每一時(shí)刻棧中的文法符號(hào)串是某規(guī)范句型的活前綴，則說(shuō)明已分析的部分是正確的 ? 一個(gè)文法的規(guī)范句型的所有活前綴構(gòu)成一個(gè)語(yǔ)言，而且是正規(guī)語(yǔ)言，可以用一個(gè) DFA 來(lái)識(shí)別 ? 例子： 文法 G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 ? * ? 每個(gè)狀態(tài)都是活前綴的識(shí)別態(tài)，雙圈狀態(tài)是可歸前綴（句柄）識(shí)別態(tài)，標(biāo)識(shí)了 *的狀態(tài)是句子識(shí)別態(tài) 分析句子的過(guò)程可以看作在上面這個(gè) DFA 上運(yùn)行的過(guò)程 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 ? * (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d ? 例子： 步驟 棧 輸入串 ACTION GOTO 1 0 abbcde S2 0 1 4 2 3 5 7 6 9 S a b A b c B e d ? * 8 ? 例子： 步驟 棧 輸入串 ACTION GOTO 1 0 abbcde S2 2 0a2 bbcde S4 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 ? * ? 例子： 步驟 棧 輸入串 ACTION GOTO 1 0 abbcde S2 2 0a2 bbcde S4 3 0a2b4 bcde R2 3 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 ? * ? 例子： 步驟 棧 輸入串 ACTION GOTO 1 0 abbcde S2 2 0a2 bbcde S4 3 0a2b4 bcde R2 3 4 0a2A3 bcde S6 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 ? * ? 例子： 步驟 棧 輸入串 ACTION GOTO 1 0 abbcde S2 2 0a2 bbcde S4 3 0a2b4 bcde R2 3 4 0a2A3 bcde S6 5 0a2A3b6 cde R3 3 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 ? * ? 例子： 步驟 棧 輸入串 ACTION GOTO 3 0a2b4 bcde R2 3 4 0a2A3 bcde S6 5 0a2A3b6 cde R3 3 6 0a2A3 cde S5 * 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 ? ? 例子： 步驟 棧 輸入串 ACTION GOTO 4 0a2A3 bcde S6 5 0a2A3b6 cde R3 3 6 0a2A3 cde S5 7 0a2A3c5 de S8 * 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 ? ? 例子： 步驟 棧 輸入串 ACTION GOTO 5 0a2A3b6 cde R3 3 6 0a2A3 cde S5 7 0a2A3c5 de S8 8 0a2A3c5d8 e R4 7 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 ? * ? 例子： 步驟 棧 輸入串 ACTION GOTO 6 0a2A3 cde S5 7 0a2A3c5 de S8 8 0a2A3c5d8 e R4 7 9 0a2A3c5B7 e S9 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 ? * ? 例子： 步驟 棧 輸入串 ACTION GOTO 7 0a2A3c5 de S8 8 0a2A3c5d8 e R4 7 9 0a2A3c5B7 e S9 10 0a2A3c5B7e9 R1 1 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 ? * ? 例子： 步驟 棧 輸入串 ACTION GOTO 8 0a2A3c5d8 e R4 7 9 0a2A3c5B7 e S9 10 0a2A3c5B7e9 R1 1 11 0S1 Acc 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 ? * LR（ 0）項(xiàng)目 由上述分析和定義可知，活前綴與句柄間的關(guān)系不外乎下述 三種情況： （ 1） 活前綴中已含有句柄的全部符號(hào)（句柄的最后符號(hào)就是 活前綴的最后符號(hào)）。為 文法開(kāi)始符號(hào)。 * ?A? ???是 文法 G中的一個(gè)規(guī)范推導(dǎo)， 如果符號(hào)串 ?是 ??的前綴，則稱(chēng) ?是 G的一個(gè)活前綴。 活前綴定義： 在前面例中對(duì)輸入串 abbcde的歸約分析過(guò)程中，在規(guī)范歸約 過(guò)程中的任何時(shí)候只要已分析過(guò)的部分即在符號(hào)棧中的符號(hào)串均 為規(guī)范句型的活前綴，它表明輸入串的已被分析過(guò)的部分是該文 法某規(guī)范句型的一個(gè)正確部分。 活前綴： 可歸前綴的任意首部。 對(duì)各規(guī)范句型有前綴： ab[2]b[3]cd[4]e[1] ?,a,ab aAb[3]cd[4]e[1] ?,a,aA,aAb aAcd[4]e[1] ?,a,aA,aAc,aAcd aAcBe[1] ?,a,aA,aAc,aAcB,aAcBe 可以發(fā)現(xiàn)前綴 a,ab,aA,aAc是多個(gè)規(guī)范句型的前綴，因此我們可進(jìn) 一步 把形成可歸前綴前和形成可歸前綴時(shí)的所有規(guī)范句型的前綴 都稱(chēng)為 活前綴 。 S→aAcBe[1] A→b[2] A→Ab[3] B→d[4] 這是因?yàn)橐坏┚湫偷木浔诜?hào)棧頂形成，將會(huì)立即被歸約 之故。 如上例中每次歸約前句型的前面部分為： ab[2] aAb[3] aAcd[4] aAcBe[1] 我們把規(guī)范句型的這種前端部分的串稱(chēng)為可歸前綴。由于 LR方法是自底向上的 分析，故應(yīng)采用歸約。 例：有文法 G[S]:S→aAcBe[1] A→b[2] 這里在每條產(chǎn)生式后加上了產(chǎn) A→Ab[3] 生式的