【正文】 ?,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)為 活前綴 。 可歸前綴： 是指規(guī)范句型的一個(gè)前綴，這種前綴包含句柄且不含句柄之后的任何符號(hào)。 活前綴： 可歸前綴的任意首部。特指在分析過(guò)程中對(duì)于在棧頂 形成句柄之前和恰好形成句柄時(shí)，每一步中 符號(hào)棧中的那些符號(hào)組成的符號(hào)串 。 活前綴定義： 在前面例中對(duì)輸入串 abbcde的歸約分析過(guò)程中，在規(guī)范歸約 過(guò)程中的任何時(shí)候只要已分析過(guò)的部分即在符號(hào)棧中的符號(hào)串均 為規(guī)范句型的活前綴，它表明輸入串的已被分析過(guò)的部分是該文 法某規(guī)范句型的一個(gè)正確部分。 由此可形式地定義活前綴如下： 定義 ：若 S39。 * ?A? ???是 文法 G中的一個(gè)規(guī)范推導(dǎo)， 如果符號(hào)串 ?是 ??的前綴，則稱(chēng) ?是 G的一個(gè)活前綴。 其中 S39。為 文法開(kāi)始符號(hào)。 R R LR分析 ? 分析過(guò)程可以看作是識(shí)別文法規(guī)范句型活前綴的過(guò)程。 ? 只要每一時(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)）。 （ 2） 活前綴中只含有句柄的前部分符號(hào)（句柄的最左子串 為活前綴的最右子串）。 （ 3） 活前綴中全然不包含句柄的任何符號(hào)。 第一種情況表明： 此時(shí)某一產(chǎn)生式 A→β的右部 β已出現(xiàn)在符號(hào) 棧頂，因此此時(shí)相應(yīng)的分析動(dòng)作應(yīng)當(dāng)是用此產(chǎn)生式進(jìn)行歸約。 第二種情況表明： 形如 A→?1?2的產(chǎn)生式的 右部子串已在符號(hào)棧棧頂，如 ?1， 正期待著從余留的輸入串中看到能由 β推出的 符號(hào)串，即期待 ?2 進(jìn)棧以便能進(jìn)行歸約。故此時(shí)分析動(dòng)作是“移進(jìn)”當(dāng)前輸入符號(hào)。 第三種情況則意味著： 期望從余留輸入串中能看到由某產(chǎn)生式 A→?的右部，即 ?所代表的符號(hào)串 (即句柄 ) 。所以此時(shí)分析的動(dòng)作也是讀輸入符進(jìn)符號(hào)棧。 為了刻畫(huà)在分析過(guò)程中，文法的一個(gè)產(chǎn)生式右部符號(hào)串有多大 部分已被識(shí)別，我們可在該產(chǎn)生式的右部相應(yīng)位置上加一個(gè)圓點(diǎn) “ .”，來(lái)指示位置，標(biāo)明在“ .”前的部分已被識(shí)別。如上述三種情況，可分別標(biāo)注為： A→β.； A→?1 .?2 。 A→.? 。 我們把右部某位置上標(biāo)有圓點(diǎn)的產(chǎn)生式稱(chēng)為相應(yīng)文法的一個(gè) LR(0)項(xiàng)目。特別地，對(duì)形如 A→? 的產(chǎn)生式，相應(yīng)的 LR(0)項(xiàng)目表示為 A→.。 顯然不同的 LR(0)項(xiàng)目，反映了分析過(guò)程中符號(hào)棧頂?shù)牟煌闆r。 例如：產(chǎn)生式 S→aAcBe對(duì)應(yīng)有六個(gè)項(xiàng)目。 [0] S→.aAcBe [1] S→ [2] S→ [3] S→ [4] S→ [5] S→aAcBe. 例如：產(chǎn)生式 S→aAcBe對(duì)應(yīng)有六個(gè)項(xiàng)目。 [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)。概括地說(shuō)，圓點(diǎn)左邊的子串表示在分析過(guò)程的某一時(shí)刻用該產(chǎn)生式歸約時(shí)句柄中已識(shí)別過(guò)的部分，圓點(diǎn)右邊的子串表示待識(shí)別的部分。 文法的全部 LR(0)項(xiàng)目將是構(gòu)造識(shí)別它的所有活前綴的有窮自動(dòng)機(jī)的基礎(chǔ)。 LR(0)項(xiàng)目的分類(lèi)： 例：考慮文法 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。, 且將 S39。 →S作為第 0個(gè)產(chǎn)生式添加到文法 G中，從而得到了所謂 G的拓廣文法 G39。顯然 L(G39。)=L(G)，則對(duì)于文法 G39。，其 LR(0) 項(xiàng)目為： 1) S39。 →.S 2) S39。 → 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。： (0)S39?！鶶 (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 → α aβ ? 待約項(xiàng)目： A → α Bβ ? 歸約項(xiàng)目： A → α ? 接受項(xiàng)目： S’ → S 圓點(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) 。 在作出文法的全部 LR(0)項(xiàng)目之后，現(xiàn)在將用它們來(lái)構(gòu)造識(shí)別 全部活前綴的 DFA。這種 DFA中的中每一個(gè)狀態(tài)由若干個(gè) LR(0) 項(xiàng)目所組成的集合（稱(chēng)為項(xiàng)目集）來(lái)表示。 下面以上例中的文法為例來(lái) 說(shuō)明構(gòu)造 DFA的方法。 G39。： (0)S39。→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?；蛘叻催^(guò)來(lái)說(shuō)，我們所期待的是，從使用產(chǎn)生式 S39?！鶶 開(kāi)始，能夠逐漸推導(dǎo)出所給定的輸入串。因此，我們應(yīng)將項(xiàng)目 S39?！?S 列入項(xiàng)目集 I0之中。換言之，也就是我們正期待將要掃描的輸入串正好就是能由 S39。推導(dǎo)出的任何終結(jié)符串。 然而，我們不能從輸入串中直接讀出非終結(jié)符號(hào) S，因此我們也應(yīng)將項(xiàng)目S→.A 和 S→.B 加入 I0中。由于 A和 B同樣是非終結(jié)符，所以也應(yīng)將 A→.aA