【正文】 即 若項目 [A→ α j為在文法中對產(chǎn)生式 A→ α 的編號。, (0) S? →S (1) S→aAd (2) S→bAc (3) S→aec (4) S→bed (5) A→e 這樣 LR(1)方法構(gòu)造的項目集規(guī)范族在項目集 I5和 I7中的移進 歸約沖突，由于歸約項目的搜索符集合與移進項目的待移進符號不相交，所以在 I5中，當(dāng)面臨輸入符為 d時歸約，為 c時移進，而在 I7中則當(dāng)面臨輸入符為 c時歸約，為 d時移進，沖突已全部可以解決，因此該文法為 LR(1)文法。c, A→e, I2： S→aS,] 為初態(tài)集的初始項目，然后對其求閉包和轉(zhuǎn)換函數(shù)，直到項目集不再增大。 (2) 轉(zhuǎn)換函數(shù)的構(gòu)造 LR(1)轉(zhuǎn)換函數(shù)的構(gòu)造與 LR(0)的相似， GO(I,X)＝ CLOSURE(J) 其中 I是 LR(1)的項目集， X是文法符號： J={任何形如 [A→ α X號才行。 當(dāng)分析經(jīng)過若干步后在項目集 J中含有項目 [B→ γ R R R S??S? bAc? bec (0) S? →S (1) S→aAd (2) S→bAc (3) S→aec (4) S→bed (5) A→e R R S? ?S?bed 這兩個最右推導(dǎo)，包含了活前綴為 b的所有句型，因此FOLLOW(A)中的 c只能跟在句型 bAc中 A的后面，這樣在 I7中當(dāng)面臨輸入符為 c時才能歸約，根據(jù)項目集的構(gòu)造原理有： 若 [A→ α c 因 A→ec I7： S→be 構(gòu)造 SLR(1)分析表 對于上述三個沖突項目等均可用 SLR(1)方法解決沖突。 FOLLOW(S39。] : (0) S39。 → Ii ,則置 ACTION[i,]=acc。 一般地，對于 LR(0)規(guī)范族的一個項目集 I可能含有多個移進項目和多個歸約項目，我們可假設(shè)項目集 I中有 m個移進項目： A1→?1. b1?1, A2→ ?2. b2?2, …, A m→ ?m. bm?m。 4）若 ACTION[i,a]=空白，轉(zhuǎn) 出錯處理 。→S .屬于 Ii ,則置 ACTION[i,]=acc。 如果一個文法 G滿足上述條件，也就是它的每個 LR(0)項目集 中都不含有沖突的項目，則稱 G為 LR(0)文法。： (0)S39。]的 LR(0)項目集規(guī)范族，并記為 C=(I0, I1,…, I 10) 于是，我們所要構(gòu)成的識別文法 G[S39。 I4 =GO(I0,a)=closure({A→a . Ab,B→a . Bd}) G39。設(shè)此狀態(tài)為 Ii ，顯然 Ii中必含有全部形如 K→?A .?的項目，我們將這樣的項目稱為 K→? .A?的 后繼項目 。→.S, S→.A, S→.B, A→.aAb, A→.c, B→.aBd, B→.d I0 : S39。換言之，也就是我們正期待將要掃描的輸入串正好就是能由 S39。 下面以上例中的文法為例來 說明構(gòu)造 DFA的方法。： (0)S39。 LR(0)項目的分類： 例：考慮文法 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 解：求該文法的項目集規(guī)范族 C： 為了方便起見，我們在上述文法中引起一個新的開始符號 S39。 我們把右部某位置上標(biāo)有圓點的產(chǎn)生式稱為相應(yīng)文法的一個 LR(0)項目。 第一種情況表明： 此時某一產(chǎn)生式 A→β的右部 β已出現(xiàn)在符號 棧頂，因此此時相應(yīng)的分析動作應(yīng)當(dāng)是用此產(chǎn)生式進行歸約。 由此可形式地定義活前綴如下： 定義 ：若 S39。實際上，它們恰好是符號棧棧頂形成句柄時符號棧中的內(nèi)容。對接受狀態(tài)，分析棧的格局為： ↓ S0 Sα Z ↑ ↑ 例： 有文法 G[S]:1： S→aAcBe 2： A→b 3： A→Ab 4： B→d 其 ACTION表和 GOTO表為： 考察對輸入串 abbcde 的分析過程。故將當(dāng)前的輸入符號和表元素 Sm+1分別壓入棧中，有 （ 2） ACTION[Sm, ai]= Rj (歸約） 表明此時應(yīng)按文法的第 j個產(chǎn)生式 A→ Xmk+1Xmk+2 … Xm 進行歸約。但 SLR分析表的功能太弱，而且對某些文法可能根本就構(gòu)造不出相應(yīng)的 SLR分析表。 輸入串 … ai … a1 Sp→ X1 S1 S0 ┋ ┋ ┋ ┋ Xm Sm 總 控 程 序 輸出 ACTION 表 GOTO 表 其中 S棧為狀態(tài)棧 X棧為符號棧 棧 產(chǎn)生式 表 圖 LR分析器的邏輯結(jié)構(gòu) 即一個 LR(k)分析器主要由：總控程序，分析棧（狀態(tài)棧和符號棧）輸入隊列和分析表組成。第七章 LR 分析法 1965年， LR(K)文法及 LR(K)分析技術(shù)。一般來說所有 LR分析器的總控程序基本上是大同小異。 第三種稱為向前 LR（即 LALR）分析表構(gòu)造法。即棧頂符號串 Xmk+1Xmk+2 … Xm已成為當(dā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 的語法樹 對輸入串 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分析過程中的性質(zhì)與特點： ? 棧中的文法符號串并上剩余的輸入串構(gòu)成一個右句型（規(guī)范句型） ? 當(dāng)該右句型的句柄出現(xiàn)在棧頂時，歸約，否則，移進 ? 棧中的文法符號串是當(dāng)前句型的前綴，該前綴不包含句型句柄后面的符號，稱之為 活前綴（ Viable Prefixes） LR(0) 分析表的構(gòu)造 為了給出構(gòu)造 LR(0)分析表的算法，引出一些術(shù)語： 規(guī)范句型的活前綴 前綴： 一個符號串的前綴是指該串的任意首部（包括 ?）。 S→aAcBe[1] A→b[2] A→Ab[3] B→d[4] 這是因為一旦句型的句柄在符號棧頂形成，將會立即被歸約 之故。 * ?A? ???是 文法 G中的一個規(guī)范推導(dǎo)， 如果符號串 ?是 ??的前綴，則稱 ?是 G的一個活前綴。 第二種情況表明： 形如 A→?1?2的產(chǎn)生式的 右部子串已在符號棧棧頂，如 ?1， 正期待著從余留的輸入串中看到能由 β推出的 符號串，即期待 ?2 進棧以便能進行歸約。特別地，對形如 A→? 的產(chǎn)生式，相應(yīng)的 LR(0)項目表示為 A→.。, 且將 S39。→S (1)S→ A (2)S→ B (3)A→ aAb (4)A→ c (5)B→ aBd (6)B→ d 如前所述，由于不同的項目反映了分析過程中棧頂?shù)牟煌闆r， 因此，我們可根據(jù)它們不同的作用，將一個文法的全部 LR(0)項目 進行分類： ? 移進項目： A → α G39。推導(dǎo)出的任何終結(jié)符串?！?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。對于每一個文法符號 A，如果存在這樣的后繼項目，則可能不只一個，設(shè)其組成集合 J，則 J中的每個項目都是項目集 Ii的基本項目，因此，按照與上面構(gòu)造項目集 I0相類試的討論，我們有： Ii =closure(J) 為了指明 Ii是“ I0關(guān)于文法符號 A的后繼狀態(tài)”這一事實，我們可定義一個狀態(tài)轉(zhuǎn)移函數(shù)： GO(I0,A)=closure(J) = Ii 其中， I是當(dāng)前狀態(tài)， A為文法符號， J是 I中所有形如 K→?.A? 的項目之后繼項目 K→?A.?所組成的集合，而 closure(J)就是項目集 I（即狀態(tài) I)關(guān)于符號 A的后繼項目集（即后繼狀態(tài)）。： (0)S39。]的全部活前綴的 DFA為 M=(C,V,GO, I0,Z) 其中 C— M的狀態(tài)集，即文法 G[S39?！鶶 (1)S→ A (2)S→ B (3)A→ aAb (4)A→ c (5)B→ aBd (6)B→ d 圖 文法 G[S39。 顯然，只有當(dāng)一個文法是 LR(0)文法時，才能對它構(gòu)造不含沖 突動作的 LR(0)分析表來。 (4)在分析表中 ,凡不能按上述規(guī)則填入信息的元素 ,均置為“出錯”。 SLR(1)分析 因大多數(shù)程序設(shè)計語言的文法不能滿足 LR(0)文法的條件，即使是描述一個變量這樣簡單的文法也不是 LR(0)文法。同時含 有 n個歸約項目： B1→?1. , B2→ ?2. ,…, B n→ ?n. ,只要集合 {b1, b2,… bm}和 FOLLOW(B1),FO