【導讀】自下而上語法分析算法。步驟符號棧輸入符號串動作。3）#abbcde#歸約(A→b). 8）#aAcde#歸約(B→d). 對輸入串a(chǎn)bbcde#的移進-規(guī)約分析過程。約后棧中的狀態(tài)會發(fā)生變化。用LR分析表來表示不同狀態(tài)下對于各輸入符號應采取的動。態(tài)棧與符號棧退出相應個符號，根據(jù)GOTO表將相應狀態(tài)入棧。對于一個文法，狀態(tài)集是如何確定的？可歸前綴與活前綴。我們把形成可歸前綴之前包括可歸前綴在內。的所有規(guī)范句型的前綴都稱為活前綴。LR分析需要構造識別活前綴的有窮自動。–我們可以文法的終結符和非終結符都看成有。柄，認為達到了識別句柄的終態(tài)。

　　

【正文】 E ? .T + E T ? .(E) T ? .int * T T ? .int T ? int * .T T ? .(E) T ? .int * T T ? .int T ? int * T. T ? (E.) T ? (E). E T ( int int * ) E E T int ( ( int T + ( 1 2 3 4 5 6 7 8 9 10 11 的資料庫下載 SLR(1)分析 ? 大多數(shù)適用的程序設計語言的文法不能滿足 LR(0)文法的條件，即其規(guī)范族中會有含有沖突的項目集（狀態(tài)） ? 如果解決這種沖突？ ? 直覺：對于有沖突的狀態(tài)，向前查看 一個 符號，以確定采用的動作 的資料庫下載 文法 G‘： (0) S’ ? S (1) S ? rD (2) D? D,i (3) D ? i 狀態(tài) 核集合 閉包增加項目 項目集I0 S ‘ → ? S S → ? rD S ‘ → ? SS → ? rDI1 S ‘ → S ? S ‘ → S ?I2 S → r ? D D → ? D ,iD → ? iS → r ? DD → ? D ,iD → ? iI3 S → rD ? D → D ? , iS → rD ? D → D ? , iI4 D → i ? D → i ?I5 D → D , ? i D → D , ? iI6 D → D ,i ? D → D ,i ?A C T I O N GOTO狀態(tài)r , i S D0 S 2 11 a c c2 S 4 33 r 1 r 1 ,S 5 r 1 r 14 r 3 r 3 r 3 r 35 S 66 r 2 r 2 r 2 r 2I0: S‘ → ? S S‘ → ?rD I2: S → r?D D → ?D,i D → ? i I3: S → rD ? D → D ?,i I4: D → i ? I5: D → D,?i I1: S‘ → S ? I6: D → D,i ? ? S r i D , i LR(0)分析表 的資料庫下載 I3: S → rD ? D → D ?,i A C T I O N GOTO狀態(tài)r , i S D0 S 2 11 a c c2 S 4 33 r 1 r 1 ,S 5 r 1 r 14 r 3 r 3 r 3 r 35 S 66 r 2 r 2 r 2 r 2向前查看一個符號，看其是否是 S的后跟符號（ FOLLOW(S)） ,若否則移進，是則歸約。 SLR(1)分析表 A C T I O N GOTO狀態(tài)r , i S D0 S211 a c c2 S433 S 5 r 14 r3r3r3r35 S 66 r2r2r2r2的資料庫下載 一個 LR(0)規(guī)范族中含有如下的項目集（狀態(tài)） I I = {X → ? ? b? , A → ? ? , B → ? ? } 若有： FOLLOW(A) ∩FOLLOW(B) = 216。 FOLLOW(A) ∩ = 216。 FOLLOW(B) ∩ = 216。 狀態(tài) I面臨某輸入符號 a 1) 若 a=b，則移進 2) 若 a?FOLLOW(A), 則用產(chǎn)生式 A → ? 進行歸約 3) 若 a?FOLLOW(B), 則用產(chǎn)生式 B → ? 進行歸約 4) 此外，報錯 若一個文法的 LR(0)分析表中所含有的動作沖突都能用上述方法解決，則稱這個文法是 SLR(1)文法 的資料庫下載 “改進的” SLR(1)分析： 對所有非終結符都求出其 FOLLOW集合 ，這樣只有歸約項目僅對面臨輸入符號包含在該歸約項目左部非終結符的FOLLOW集合中，才采取用該產(chǎn)生式歸約的動作。 改進的 SLR(1)分析表的 ACTION表和 GOTO表的 構造步驟 ： a) 若項目 A→ ? ? a?屬于 Ik，且轉換函數(shù) GO(Ik,a)= Ij ，當a為終結符時，則置 ACTION[k,a]為 Sj b) 若項目 A→ ? ?屬于 Ik ，則對 a為任何終結符或‘ ’， 且滿足 a?FOLLOW(A)時 ，置 ACTION[k,a] = rj ， j為產(chǎn)生式在文法 G‘中的編號 c) 若 GO(Ik,A)= Ij ，則置 GOTO[k,A]=j，其中 A為非終結符， j為某一狀態(tài)號 d) 若項目 S‘→ S ?屬于 Ik ，則置 ACTION[k,] = acc e) 其它填上 “報錯標志” 的資料庫下載 ? 仍有許多文法構造的 LR(0)項目集規(guī)范族存在的動作沖突不能用 SLR(1)方法解決 的資料庫下載 LR(1)分析 ? 若項目集 [A→ ??B?]屬于 I時，則 [B→ ??]也屬于 I ? 把 FIRST(?)作為用產(chǎn)生式歸約的搜索符（稱為向前搜索符），作為用產(chǎn)生式 B→ ?歸約時查看的符號集合（用以代替 SLR(1)分析中的FOLLOW集），并把此搜索符號的集合也放在相應項目的后面，這種處理方法即為 LR(1)方法 的資料庫下載 LR(1)項目集族的構造：針對初始項目 S’→ ?S,求閉包后再用轉換函數(shù)逐步求出整個文法的 LR(1)項目集族。 1）構造 LR（ 1）項目集的閉包函數(shù) a)I的項目都在 CLOSURE(I)中 b)若 A→ ? ? B?， a屬于 CLOSURE(I)， B→ ?是文法的產(chǎn)生式， ??V*， b?FIRST(?a),則 B→ ? ?,b也屬于CLOSURE(I) c)重復 b)直到 CLOSURE(I)不再擴大 2)轉換函數(shù)的構造 GOTO（ I， X） = CLOSURE（ J） 其中： I為 LR(1)的項目集 ， X為一文法符號 J={任何形如 A→ ?X ? ?,a的項目 | A→ ? ? X ?,a屬于 I} 的資料庫下載 I0: S’ ? ? S, S ? ? aAd, S ? ? bAc, S ? ? aec, S ? ? bed, 文法 G‘： (0) S’ ? S (1) S ? aAd (2) S ? bAc (3) S ? aec (4) S ? bed (5) A ? e I1: S’ ? S ?, I2: S ? a ?Ad, S ? a ? ec, A ? ? e, d I3: S ? b ? Ac, S ? b ? ed, A ? ? e, c I4: S ? aA ? d, I5: S ? ae ? c, A ? e ?, d I6: S ? bA ? c, I7: S ? be ? d, A ? e ?, c I8: S ? aAd ?, I9: S ? ae c ?, I10: S ? bAc ?, I11: S ? bed ?, 查看 I5 ， I7中的沖突，體會 LR(1)如何解決 的資料庫下載 LR(1)分析表的構造 1) 若項目 [A→ ? ? a?,b]屬于 Ik，且轉換函數(shù) GO(Ik,a)= Ij ，當 a為終結符時，則置 ACTION[k,a]為 Sj 2) 若項目 [A→ ? ? ,a]屬于 Ik ，則對 a為任何終結符或‘ ’， 置 ACTION[k,a] = rj ， j為產(chǎn)生式在文法 G‘中的編號 3) 若 GO(Ik,A)= Ij ，則置 GOTO[k,A]=j，其中 A為非終結符， j為某一狀態(tài)號 4) 若項目 [S‘→ S ? ,]屬于 Ik ，則置 ACTION[k,] = acc 5) 其它填上 “報錯標志” 的資料庫下載 ? LR(1)項目集的構造對某些同心集的分裂可能使狀態(tài)數(shù)目劇烈的增長 的資料庫下載 文法 G‘： (0) S’ ? S (1) B ? aB (2) S ? BB (3) B ? b I0: S’ ? ? S, S ? ? BB, B ? ? aB, a/b B ? ? b, a/b I1: S’ ? S ?, I2: S ? B ? B, B ? ? a B, B ? ? b, I5: S ? B B ?, I6: S ? a ? B, B ? ? aB, B ? ? b, I9: B ? a B ?, I4: B ? b ?, a/b I3: B ? a ? B, a/b B ? ? aB, a/b B ? ? b, a/b I8: B ? a B ?, a/b I7: B ? b ?, S B b b B b b a a a a B B LR(1)項目集和轉換函數(shù) 的資料庫下載 分析可發(fā)現(xiàn) I3和 I6 ， I4和 I7 ， I8和 I9分別為同心集 I3: B ? a ? B, a/b B ? ? aB, a/b B ? ? b, a/b I6: S ? a ? B, B ? ? aB, B ? ? b, I4: B ? b ?, a/b I7: B ? b ?, I8: B ? a B ?, a/b I9: B ? a B ?, I3,6: S ? a ? B, a/b/ B ? ? aB, a/b/ B ? ? b, a/b/ I4,7: B ? b ?, a/b/ I8,9: B ? a B ?, a/b/ 合并為 合并為 合并為 的資料庫下載 LALR(1)分析 ? 對 LR(1)項目集規(guī)范族合并同心集，若合并同心集后不產(chǎn)生新的沖突，則為LALR(1)項目集。 的資料庫下載 合并同心集的幾點說明 ? 同心集合并后心仍相同，只是超前搜索符集合為各同心集超前搜索符的和集 ? 合并同心集后轉換函數(shù)自動合并 ? LR(1)文法合并同心集后也只可能出現(xiàn)歸約 歸約沖突，而沒有移進 歸約沖突 ? 合并同心集后可能會推遲發(fā)現(xiàn)錯誤的時間，但錯誤出現(xiàn)的位置仍是準確的 的資料庫下載 ACTI ON GOTO狀態(tài)a b S B0 S3, 6S4, 71 21 acc2 S3, 6S753 ,6 S3, 6S48,94 ,7 r3r3r35 r18,9 r2r2r2A C T ION G OT O狀態(tài)a b S B0 S3S41 21 a cc2 S6S753 S3S484 r3r35 r16 S6S797 r38 r2r29 r2合并同心集后 的資料庫下載 二義性文法在 LR分析中的應用 ? 對于某些二義文法，可以人為地給出優(yōu)先性和結合性的規(guī)定，從而可以構造出比相應非二義性文法更優(yōu)越的 LR分析器 的資料庫下載 LR(0),SLR(1),LR(1),LR(k),LALR(1) ? LR(0) ? SLR(1): 生成的 LR(0)項目集如有沖突，則根據(jù)非終結符的 FOLLOW集決定 ? LR(1)、 LR(k): 項由 心與向前搜索符組成，搜索符長度為 1或 k ? LALR(1): 對 LR(1)項目集規(guī)范族合并同心集 的資料庫下載 作業(yè) ? p152, 第 6,11,18題