【正文】 LLOW(B2),…,FOLLOW(B n) 兩兩交集都為空，則我們?nèi)钥捎蒙鲜鰵w則來(lái)解決沖突： 1）若 a∈ {b1, b2,…, bm},則移進(jìn)。 (4) 在分析表 ,凡不能按上述規(guī)則填入信息的元素 ,均置為“出錯(cuò)”。→E (1) E→E+T (2) E→T (3) T→T*F (4) T→F (5) F→(E) (6) F→i 再求識(shí)別 G39。)= {} FOLLOW(E)= {+， )， } FOLLOW(T)= {+， *， )， } FOLLOW(F)= {+， *， )， } 現(xiàn)在分別考慮上述三個(gè)沖突項(xiàng)目中的沖突是否能用 SLR(1)方法解決。因此該 文法是 SLR(1)文法。d A→e R R R S? ?S?aAd?aed R R S? ?S?aec (0) S? →S (1) S→aAd (2) S→bAc (3) S→aec (4) S→bed (5) A→e 這兩個(gè)最右推導(dǎo)已包括了活前綴為 a的所有句型，因此，不難看出對(duì)活前綴 ae來(lái)說(shuō)，當(dāng)面臨輸入符號(hào)為 c時(shí)應(yīng)移進(jìn)，面臨 d時(shí)應(yīng)用產(chǎn)生式A→e歸約。B β ]∈ 項(xiàng)目集 I， 則 [B→]需要用產(chǎn)生式 B→ γ 歸約，這時(shí)向前查看的符號(hào)集合是FIRST(β )，而 FIRST(β )? FOLLOW（ B）。因此對(duì)初始項(xiàng)目[S′→ β ,a]的項(xiàng)目 |A→ α 也就是對(duì)狀態(tài) I經(jīng)過(guò)符號(hào) X后轉(zhuǎn)向狀態(tài) J，求出 J的基本項(xiàng)目后，對(duì)基本項(xiàng)目求閉包即為 CLOSURE(J)。Ad, S→a,d I6： S→bA LR(1)分析表的構(gòu)造 由于一個(gè) LR(1)項(xiàng)目可以看成兩個(gè)部分組成，一部分和 LR(0)項(xiàng)目相同部分我們稱它為心，另一部分為向前搜索符集合，因而 LR(1)分析表的構(gòu)造與 LR(0)分析表的構(gòu)造大部分相同，僅對(duì)歸約項(xiàng)目的歸約動(dòng)作取決于該歸約項(xiàng)目的向前搜索符集，只有當(dāng)面臨輸入符屬于向前搜索符的集合，才做歸約動(dòng)作，其它情況均出錯(cuò)。 (3) 若項(xiàng)目 [S?→S,a] 屬于 Ik，則置 ACTION[k,a]= rj。 LR(1)分析表的構(gòu)造除 (2) 外，其余同 LR(0)或 SLR(1)。,a] 屬于 Ik，則置 ACTION[k,a]= rj 其中a∈V T， rj 的含義為把當(dāng)前棧頂符號(hào)串 α 歸約為 A(即用產(chǎn)生式 A→ α 歸約 )。, I11： S→bedd, I5： S→aebed, I1： S′→S 對(duì)文法 G′ 的 LR(1)項(xiàng)目集族的構(gòu)造仍以 [S′→ c) 重復(fù) b)直到 CLOSURE(I)不再增大為止。39。 γ ]。d 而 A→e 現(xiàn)在我們?cè)倏磮D I5， I7項(xiàng)目集中的移進(jìn) 歸約沖突，不能用 SLR(1)方法解決的原因如下： I5： S→ae I5： S→ae 對(duì)于 I9,與 I2類似，當(dāng)面臨輸入符號(hào)為“ +”，“）”或“ ”時(shí)，則用產(chǎn)生式 E→E+T歸約；當(dāng)面臨輸入符號(hào)為“ *”時(shí)，則移進(jìn)，其余情況報(bào)錯(cuò)。存在移進(jìn) — 歸約沖突，因而該文法不屬于 LR(0)文法，故不能構(gòu)造 LR(0)分析表。[S39。)若歸約項(xiàng)目 A→?.屬于 Ii,設(shè) A→?為文法第 j個(gè)行產(chǎn)生式，則 對(duì)任何屬于 FOLLOW(A)的輸入符號(hào) a,置 ACTION[i,a]=Rj； (3)若接受項(xiàng)目 S39。 3）若 a ∈ FOLLOW(B),則用產(chǎn)生式 B→?歸約。 3）若 ACTION[i,a]=Acc,（此時(shí) a應(yīng)為“ ”號(hào)），則表明 分析成功 ， 結(jié)束分析。 若 X為一非終結(jié)符號(hào)時(shí)，則僅置 GOTO[i,X]=j (2)若 Ii中有歸約項(xiàng)目 A→?. ,設(shè) A→?為文法第 j個(gè)產(chǎn)生式，則對(duì) 文法的任何終結(jié)符和“ ”（均記為 a）置 ACTION[i,a]=Rj (3)若接受項(xiàng)目 S39。所謂相容，是指在一個(gè)項(xiàng)目集中不出現(xiàn)下列的情況： （ 1）移進(jìn)項(xiàng)目和歸約項(xiàng)目并存，即存在移進(jìn) — 歸約沖突； （ 2）多個(gè)歸約項(xiàng)目并存，即存在歸約 — 歸約沖突?！鶶. I2 :S→A. I3 :S→B. I4 :A→ A→ A→.aAb A→.c B→.aBd B→.d I8 :A → aAb. I7 :A → I9 :B → I10 :B → aBd. I5 :A→c. I6 :B→d. A B d b c d d a c S A B a G39。 通常我們將這些項(xiàng)目集的全體稱為文法 G[S39。 I3 =GO(I0,B)=closure({S→B.}) I3 : S→B . 。設(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)。 這樣，表示初態(tài)的項(xiàng)目集 I0將由如下項(xiàng)目組成： I0 : S39?！?S 列入項(xiàng)目集 I0之中。這種 DFA中的中每一個(gè)狀態(tài)由若干個(gè) LR(0) 項(xiàng)目所組成的集合（稱為項(xiàng)目集）來(lái)表示。 → 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)目將是構(gòu)造識(shí)別它的所有活前綴的有窮自動(dòng)機(jī)的基礎(chǔ)。 A→.? 。 （ 3） 活前綴中全然不包含句柄的任何符號(hào)。 活前綴定義： 在前面例中對(duì)輸入串 abbcde的歸約分析過(guò)程中，在規(guī)范歸約 過(guò)程中的任何時(shí)候只要已分析過(guò)的部分即在符號(hào)棧中的符號(hào)串均 為規(guī)范句型的活前綴，它表明輸入串的已被分析過(guò)的部分是該文 法某規(guī)范句型的一個(gè)正確部分。 如上例中每次歸約前句型的前面部分為： ab[2] aAb[3] aAcd[4] aAcBe[1] 我們把規(guī)范句型的這種前端部分的串稱為可歸前綴。 3. 重復(fù)上述第 2步的工作，直到分析棧頂出現(xiàn)“接受狀態(tài)”或“出錯(cuò)狀態(tài)“為止。 表中每一表元素所規(guī)定的動(dòng)作僅能是下列四種動(dòng)作之一： S0S1 S2 … Sm Sm+1 ai+1 ai+2 … an X1 X2 … X m ai ↑ ↑ ↓ ，分析棧及余留的輸入串為如下格局： ↓ S0S1… Sm ai ai+1… an X1… X m ↑ ↑ （ 1） ACTION[Sm, ai]= Sm+1 （移進(jìn)） 表明句柄尚未在棧頂形成，此時(shí)正期待移進(jìn)輸入符號(hào)以便形成 句柄。這是一種比較容易實(shí)現(xiàn)的方法。 2） 要移進(jìn)時(shí)，即把 Xn+1進(jìn)棧，并讀下一符號(hào)： X1X2…Xi…XnXn+1 Xn+2…Xn+k… 在棧中 當(dāng)前掃描符 棧頂 LR分析概論 一 .LR分析器的邏輯結(jié)構(gòu)及工作過(guò)程 從邏輯上來(lái)說(shuō)，一個(gè) LR分析器如圖 所示。 LR(K)分析是指自左向右掃描和自底向上的語(yǔ)法分析，且 在分析的每一步，只須根據(jù)分析棧中當(dāng)前已移進(jìn)和歸約出的 全部文法符號(hào)，并至多再向前查看 K個(gè)輸入符號(hào)，就能確定 相當(dāng)于某一產(chǎn)生式右部符號(hào)的句柄是否已在分析棧的頂部形 成。只有分析表各不相同。這種方法構(gòu)造的分析表功能介于規(guī)范 LR分析表 SLR分析表之間。所謂按第 j個(gè)產(chǎn)生式歸約，就是將分析棧中從頂向下的 k個(gè)符 號(hào)退棧，然后將文法符號(hào) A壓入符號(hào)棧中。 例如 abc的前綴有： ?,a,ab,abc abcd的前綴有：?,a,ab,abc,abcd 由此可知，對(duì)于符號(hào)串 ? 而言，其前綴的數(shù)量為 ???+1。所以我們將把規(guī)范句型具有上述性質(zhì)（即不含句柄之后的 任何符號(hào)）的前綴稱之為 可歸前綴 。 其中 S39。故此時(shí)分析動(dòng)作是“移進(jìn)”當(dāng)前輸入符號(hào)。 顯然不同的 LR(0)項(xiàng)目，反映了分析過(guò)程中符號(hào)棧頂?shù)牟煌闆r。 →S作為第 0個(gè)產(chǎn)生式添加到文法 G中，從而得到了所謂 G的拓廣文法 G39。 aβ ? 待約項(xiàng)目： A → α： (0)S39。 然而，我們不能從輸入串中直接讀出非終結(jié)符號(hào) S，因此我們也應(yīng)將項(xiàng)目S→.A 和 S→.B 加入 I0中。 →.S}的閉包運(yùn)算，即 closure({S39。 狀態(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)）?！鶶 (1)S→ A (2)S→ B (3)A→ aAb (4)A→ c (5)B→ aBd (6)B→ d I4 : A→ B→ A→.aAb B→.aBd A→.c B→.d I5=GO(I0,c)=closure({A→c.}) I5 : A→c. I6=GO(I0,d)=closure({B→d.}) I6 :B→d. 此時(shí)，我們求出了 I0的全部后繼項(xiàng)目集 I1, I2,I3,I4,I5,I6,而 I1, I2,I3, I5,I6均無(wú)后繼項(xiàng)目集，僅 I4有后繼項(xiàng)目集： I7 =GO(I4,A)=closure({A→})={A→} I9 =GO(I4,B)=closure({B→})={B→} 此外，還有： GO(I4,a)=closure({A→, B→})= I4 GO(I4,c)=closure({A→c.})= I5 GO(I4,d)=closure({B→d.})= I6 這些項(xiàng)目集均不產(chǎn)生新的項(xiàng)目集。]的 LR(0)項(xiàng)目集規(guī)范族 , C=(I0, I1,…, I10)。]項(xiàng)目集規(guī)范族 DFA: 即： ? I0 I1 I2 I3 I4 I5 I6 I7 I9 I8 I10 S A B a c d c d A B b d G39。 為了方便起見(jiàn)，我們用整數(shù) 0， 1， 2， … 表示狀態(tài) I0 , I1, I2, …。 如上例可構(gòu)造分析表為： ACTION GOTO a b c d S A B 0 S4 S5 S6 1 2 3 1 Acc 2 R1 R1 R1 R1 R1 3 R2 R2 R2 R2 R2 4 S4 S5 S6 7 9 5 R4 R4 R4 R4 R4 6 R6 R6 R6