【正文】 3）重復(fù)上述過(guò)程，直至不再有新的項(xiàng)目加入到 closure(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。： (0)S39。推導(dǎo)出的任何終結(jié)符串。→S 開(kāi)始，能夠逐漸推導(dǎo)出所給定的輸入串。 G39。 圓點(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) ?！鶶 (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 → α其 LR(0) 項(xiàng)目為： 1) S39。, 且將 S39。 [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)。特別地，對(duì)形如 A→? 的產(chǎn)生式，相應(yīng)的 LR(0)項(xiàng)目表示為 A→.。 為了刻畫(huà)在分析過(guò)程中，文法的一個(gè)產(chǎn)生式右部符號(hào)串有多大 部分已被識(shí)別，我們可在該產(chǎn)生式的右部相應(yīng)位置上加一個(gè)圓點(diǎn) “ .”，來(lái)指示位置，標(biāo)明在“ .”前的部分已被識(shí)別。 第二種情況表明： 形如 A→?1?2的產(chǎn)生式的 右部子串已在符號(hào)棧棧頂，如 ?1， 正期待著從余留的輸入串中看到能由 β推出的 符號(hào)串，即期待 ?2 進(jìn)棧以便能進(jìn)行歸約。 ? 只要每一時(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)）。 * ?A? ???是 文法 G中的一個(gè)規(guī)范推導(dǎo)， 如果符號(hào)串 ?是 ??的前綴，則稱(chēng) ?是 G的一個(gè)活前綴。 活前綴： 可歸前綴的任意首部。 S→aAcBe[1] A→b[2] A→Ab[3] B→d[4] 這是因?yàn)橐坏┚湫偷木浔诜?hào)棧頂形成，將會(huì)立即被歸約 之故。由于 LR方法是自底向上的 分析，故應(yīng)采用歸約。 r1 r1 r1 r1 r1 r1 r4 r4 r4 r4 r4 r4 S9 r3 r3 r3 r3 r3 r3 7 S8 r2 r2 r2 r2 r2 r2 S6 S5 3 S4 acc 1 S2 B A S d b e c a GOTO ACTION 0 1 2 3 4 5 6 7 8 9 S a A c B e A b d b 圖 abbcde 的語(yǔ)法樹(shù) 對(duì)輸入串 abbcde 的分析過(guò)程為： ACTION GOTO 步驟 狀態(tài)棧 符號(hào)棧 輸入流 分析動(dòng)作 下一狀態(tài) 1 0 abbcde S2(0,a) 2 02 a bbcde S4(2,b) 3 024 ab bcde r2(4,b) GOTO[2,A]=3 4 023 aA bcde S6(3,b) 6 023 aA cde S5(3,c) 5 0236 aAb cde r3(6,b) GOTO[2,A]=3 7 0235 aAc de S8(5,d) 8 02358 aAcd e r4(8,d) GOTO[5,B]=7 9 02357 aAcB e S9(7,e) 10 023579 aAcBe r1(9,) GOTO[0,S]=1 11 01 S acc(1,) 圖 abbcde的分析過(guò)程 ? LR分析過(guò)程中的性質(zhì)與特點(diǎn)： ? 棧中的文法符號(hào)串并上剩余的輸入串構(gòu)成一個(gè)右句型（規(guī)范句型） ? 當(dāng)該右句型的句柄出現(xiàn)在棧頂時(shí)，歸約，否則，移進(jìn) ? 棧中的文法符號(hào)串是當(dāng)前句型的前綴，該前綴不包含句型句柄后面的符號(hào)，稱(chēng)之為 活前綴（ Viable Prefixes） LR(0) 分析表的構(gòu)造 為了給出構(gòu)造 LR(0)分析表的算法，引出一些術(shù)語(yǔ)： 規(guī)范句型的活前綴 前綴： 一個(gè)符號(hào)串的前綴是指該串的任意首部（包括 ?）。 表明當(dāng)前的輸入串中含有錯(cuò)誤，也應(yīng)終止當(dāng)前的分析工作。即棧頂符號(hào)串 Xmk+1Xmk+2 … Xm已成為當(dāng)前句型的句 柄。 二、 LR 分析器的分析過(guò)程如下： S0及句子的左界限 分別壓入狀態(tài)棧和符號(hào)棧中。 第三種稱(chēng)為向前 LR（即 LALR）分析表構(gòu)造法。用此法構(gòu)造的分析表功能最強(qiáng)而且也適合于很多文法，但實(shí)現(xiàn)代價(jià)比較高。一般來(lái)說(shuō)所有 LR分析器的總控程序基本上是大同小異。 1） 要?dú)w約時(shí)，則根據(jù)某產(chǎn)生式 U→XiXi+1…Xn 進(jìn)行歸約： X1X2…Xi 1UXn+1Xn+2…Xn+k… 例： X1X2…Xi… Xn Xn+1Xn+2…Xn+kXn+k+1… 棧頂 （續(xù)頁(yè)） LR(0) 表示在每一步分