【正文】 3）重復上述過程，直至不再有新的項目加入到 closure(I)中為 止?！?S, S→.A, S→.B, A→.aAb, A→.c, B→.aBd, B→.d 我們將 LR(0)項目 S‘→.S稱為 項目集 I0的基本項目 ，上述從S’→.S出發(fā)構造項目集 I0的過程，可用一個對其基本項目集 {S39。： (0)S39。推導出的任何終結符串?！鶶 開始，能夠逐漸推導出所給定的輸入串。 G39。 圓點的左部表示分析過程中的某時刻用該產生式歸約時句柄已識別過的部分，圓點右部表示待識別部分 構造識別活前綴的 DFA 在 LR方法實際過程中，并不是去直接分析符號棧中的符號 是否已形成句柄，但它給我們一個啟示，我們可以把 終結符和非 終結符 都可看成一個有限自動機的 輸入符號 ，每把一個符號進棧 時看成已識別過該符號，而狀態(tài)進行轉換（到下一狀態(tài)），當識 別到可歸前綴時相當于棧頂已形成了句柄，則認為到達了識別句 柄的 終態(tài) ?！鶶 (1)S→ A (2)S→ B (3)A→ aAb (4)A→ c (5)B→ aBd (6)B→ d 如前所述，由于不同的項目反映了分析過程中棧頂的不同情況， 因此，我們可根據它們不同的作用，將一個文法的全部 LR(0)項目 進行分類： ? 移進項目： A → α其 LR(0) 項目為： 1) S39。, 且將 S39。 [0] S→.aAcBe [1] S→ [2] S→ [3] S→ [4] S→ [5] S→aAcBe. 一個產生式可對應的項目的數量為它的右部符號串長度加 1，值得注意的是對空產生式，即 A→ε僅有項目 A→. 每個項目的含義與圓點的位置有關。特別地，對形如 A→? 的產生式，相應的 LR(0)項目表示為 A→.。 為了刻畫在分析過程中，文法的一個產生式右部符號串有多大 部分已被識別，我們可在該產生式的右部相應位置上加一個圓點 “ .”，來指示位置，標明在“ .”前的部分已被識別。 第二種情況表明： 形如 A→?1?2的產生式的 右部子串已在符號棧棧頂，如 ?1， 正期待著從余留的輸入串中看到能由 β推出的 符號串，即期待 ?2 進棧以便能進行歸約。 ? 只要每一時刻棧中的文法符號串是某規(guī)范句型的活前綴，則說明已分析的部分是正確的 ? 一個文法的規(guī)范句型的所有活前綴構成一個語言，而且是正規(guī)語言，可以用一個 DFA 來識別 ? 例子： 文法 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 ? * ? 每個狀態(tài)都是活前綴的識別態(tài)，雙圈狀態(tài)是可歸前綴（句柄）識別態(tài)，標識了 *的狀態(tài)是句子識別態(tài) 分析句子的過程可以看作在上面這個 DFA 上運行的過程 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）項目 由上述分析和定義可知，活前綴與句柄間的關系不外乎下述 三種情況： （ 1） 活前綴中已含有句柄的全部符號（句柄的最后符號就是 活前綴的最后符號）。 * ?A? ???是 文法 G中的一個規(guī)范推導， 如果符號串 ?是 ??的前綴，則稱 ?是 G的一個活前綴。 活前綴： 可歸前綴的任意首部。 S→aAcBe[1] A→b[2] A→Ab[3] B→d[4] 這是因為一旦句型的句柄在符號棧頂形成，將會立即被歸約 之故。由于 LR方法是自底向上的 分析，故應采用歸約。 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 的語法樹 對輸入串 abbcde 的分析過程為： ACTION GOTO 步驟 狀態(tài)棧 符號棧 輸入流 分析動作 下一狀態(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的分析過程 ? LR分析過程中的性質與特點： ? 棧中的文法符號串并上剩余的輸入串構成一個右句型（規(guī)范句型） ? 當該右句型的句柄出現在棧頂時，歸約，否則，移進 ? 棧中的文法符號串是當前句型的前綴，該前綴不包含句型句柄后面的符號，稱之為 活前綴（ Viable Prefixes） LR(0) 分析表的構造 為了給出構造 LR(0)分析表的算法，引出一些術語： 規(guī)范句型的活前綴 前綴： 一個符號串的前綴是指該串的任意首部（包括 ?）。 表明當前的輸入串中含有錯誤，也應終止當前的分析工作。即棧頂符號串 Xmk+1Xmk+2 … Xm已成為當前句型的句 柄。 二、 LR 分析器的分析過程如下： S0及句子的左界限 分別壓入狀態(tài)棧和符號棧中。 第三種稱為向前 LR（即 LALR）分析表構造法。用此法構造的分析表功能最強而且也適合于很多文法，但實現代價比較高。一般來說所有 LR分析器的總控程序基本上是大同小異。 1） 要歸約時，則根據某產生式 U→XiXi+1…Xn 進行歸約： X1X2…Xi 1UXn+1Xn+2…Xn+k… 例： X1X2…Xi… Xn Xn+1Xn+2…Xn+kXn+k+1… 棧頂 （續(xù)頁） LR(0) 表示在每一步分