[教育學]第7章lr分析法-資料下載頁

　　

【正文】 3 3 03 F +i*i R4 2 4 02 T +i*i R2 1 5 01 E +i*i S6 6 016 E+ i*i S5 7 0165 E+i *i R6 3 8 0163 E+T *i R4 9 9 0169 E+T *i S7 10 01697 E+T* i S5 11 016975 E+T*i R6 10 12 0169710 E+T*F R3 9 13 0169 E+T R1 1 14 01 E acc 本 章 作 業 ? P165：題 1，題 2(1) LR(1) 分析 本節介紹比 SLR(1)功能更強的 LR(1)分析法。 例 :有下列文法 G′, 構造構造識別文法 G′ 的識別活前綴的有限自動機。 (0) S′→S (1) S→aAd (2) S→bAc (3) S→aec (4) S→bed (5) A→e 我們首先用 S′→S 作為初態集的項目，然后用閉包函數和轉換函數構造識別文法 G′ 的識別活前綴的有限自動機DFA如圖 。 圖 LR(0)識別 G′的活前綴的 DFA 如圖 ，可以發現在項目集 I5和 I7中存在移進和歸約沖突。 I5： S→aec I7： S→bed A→e A→e 而歸約項目左部非終結符的 FOLLOW(A)={c,d} 在 I5中， FOLLOW(A)∩{c}={c,d}∩{c}≠ Φ 在 I7中， FOLLOW(A) ∩mrtlaohc6vc={c,d}∩mrtlaohc6vc≠ Φ 因此 I5， I7中沖突不能用 SLR(1)方法解決。只能考慮用下面將要介紹的 LR(1)方法解決。 由于用 SLR(1)方法解決動作沖突時，對于歸約項目A→ α ，只要當前面臨輸入符為 a∈FOLLOW(A) 時，就確定采用產生式 A→ α 進行歸約，但是如果棧中的符號串為 βα，歸約后變為 β A，再移進當前符 a，則棧里變為 β Aa，而實際上 β Aa未必為文法規范句型的活前綴。 現在我們再看圖 I5， I7項目集中的移進 歸約沖突，不能用 SLR(1)方法解決的原因如下： I5： S→aec 因 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 這兩個最右推導已包括了活前綴為 a的所有句型，因此，不難看出對活前綴 ae來說，當面臨輸入符號為 c時應移進，面臨 d時應用產生式A→e歸約。因為 R R S? ?S≠aAc 這說明從 S′ 出發不能用最右推導（規范推導）推出 aAc句型，所以 aAc不是該文法的規范句型。回顧 LR分析過程，若輸入符號串是所給文法的句子，那么分析過程的任何時刻在文法符號棧中的符號和剩余的輸入串符號合起來總是構成該文法的規范句型。 這也說明了并不是 FOLLOW(A)的每個元素在含 A的所有句型中在 A的后面都會出現，例中d只在規范句型 aAd中 A的后面出現，因此面臨輸入符為 d才應歸約。再看在 I7中。 I7： S→bed 而 A→e 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 這兩個最右推導，包含了活前綴為 b的所有句型，因此FOLLOW(A)中的 c只能跟在句型 bAc中 A的后面，這樣在 I7中當面臨輸入符為 c時才能歸約，根據項目集的構造原理有： 若 [A→ α B β ]∈ 項目集 I， 則 [B→ γ ](B→ γ 為一產生式 )也包含在 I中。 不妨考慮，把 FIRST(β )作為用產生式 B→ γ 歸約的搜索符，稱為 向前搜索符 ，作為歸約時查看的符號集合，用以代替 SLR(1)分析中的 FOLLOW集，把此搜索符號的集合也放在相應項目的后面，這種處理方法即為 LR(1)方法。 其原因是：一個非終結符號的 FOLLOW集合，包含了所有含該非終結符的任一句型中在該非終結符后的向前搜索符集合。如在項目集 I中有項目： [A→ α B β ]， [B→ γ ]。 當分析經過若干步后在項目集 J中含有項目 [B→ γ ]需要用產生式 B→ γ 歸約，這時向前查看的符號集合是FIRST(β )，而 FIRST(β )? FOLLOW（ B）。 LR(1)項目集族的構造 一個 LR(1)項目可以看成兩個部分組成，一部分和 LR(0)項目相同部分我們稱它為 心 ，另一部分為 向前搜索符集合 。如讓 S′→S ， 屬于初始項目集中，把 39。39。號作為向前搜索符，表示活前綴為 γ (若 γ 是有關 S產生式的某一右部 )要歸約成 S時，必須面臨輸入符為 39。39。號才行。因此對初始項目[S′→S ， ]求閉包后再用轉換函數逐步求出整個文法的LR(1)項目集族。具體構造步驟如下： (1) 構造 LR(1)項目集的閉包函數。 a) 項目集 I的任何項目都屬于 CLOSURE(I)； b) 若有項目 [A→ αB β ,a]屬于 CLOSURE(I)， B→ γ 是文法中的產生式， β ∈V *， b∈FIRST( β a)，則 [B→ γ ,b]也屬于 CLOSURE(I)中。 c) 重復 b)直到 CLOSURE(I)不再增大為止。 (2) 轉換函數的構造 LR(1)轉換函數的構造與 LR(0)的相似， GO(I,X)＝ CLOSURE(J) 其中 I是 LR(1)的項目集， X是文法符號： J={任何形如 [A→ α X β ,a]的項目 |A→ α X β ,a]∈I} 現給出直接由產生式構造識別活前綴的 DFA的 LR（ 1）項目集的閉包 CLOSURE的算法： function CLOSURE (I)； /* I是項目集 */ { J:= I； repeat 對 J中的每個項目 [A→ α B β ,a]和產生式 B→ γ ； α ， β ， γ ∈V *； b ∈FIRST( β a), 若 B→ γ ， b不在 J中 Do 將 B→ γ ， b加到 J中 until 再沒有項目加到 J中 return J }； 對項目 [A→ α B β ,a]，計算 B的向前搜索符時，應為FIRST(β a)，這是因為 β ∈V *，即 β 可能為 ε ，而 a是用產生式 A→ α Bβ 歸約時的向前搜索符，而現在 β 為 ε ，就等于用A→ α B歸約，向前搜索符為 a，那么用 A→ α B歸約前，必須先用產生式 B→ γ 歸約成 B，因此， B的向前搜索符時也應為 a。 對文法 G′ 的 LR(1)項目集族的構造仍以 [S′→S,] 為初態集的初始項目，然后對其求閉包和轉換函數，直到項目集不再增大。 也就是對狀態 I經過符號 X后轉向狀態 J，求出 J的基本項目后，對基本項目求閉包即為 CLOSURE(J)。 現在我們可以對上面 SLR(1)方法解決 I5，I7中移進 歸約沖突的文法構造它的 LR(1)項目集規范族如下： I0： S′→S, S→aAd, S→bAc, S→aec, S→bed, I1： S′→S, I2： S→aAd, S→aec, A→e,d I3： S→bAc, S→bed, A→e,c I4： S→aAd, I5： S→aec, A→e,d I6： S→bAc, I7： S→bed, A→e,c I8： S→aAd, I9： S→aec, I10： S→bAc, I11： S→bed, (0) S? →S (1) S→aAd (2) S→bAc (3) S→aec (4) S→bed (5) A→e 這樣 LR(1)方法構造的項目集規范族在項目集 I5和 I7中的移進 歸約沖突，由于歸約項目的搜索符集合與移進項目的待移進符號不相交，所以在 I5中，當面臨輸入符為 d時歸約，為 c時移進，而在 I7中則當面臨輸入符為 c時歸約，為 d時移進，沖突已全部可以解決，因此該文法為 LR(1)文法。 LR(1)分析表的構造 由于一個 LR(1)項目可以看成兩個部分組成，一部分和 LR(0)項目相同部分我們稱它為心，另一部分為向前搜索符集合，因而 LR(1)分析表的構造與 LR(0)分析表的構造大部分相同，僅對歸約項目的歸約動作取決于該歸約項目的向前搜索符集，只有當面臨輸入符屬于向前搜索符的集合，才做歸約動作，其它情況均出錯。具體構造過程如下： 若已構造出某文法的 LR(1)項目集族 C。 C＝ {I0,I1,?,I n}，其中 Ik的 k為分析器的狀態，則動作 ACTION表和狀態轉換 GOTO表構造方法如下： (1) 若項目 [A→ α a β ,b]屬于 Ik，且 GO（ Ik,a） =Ij，其中a∈V T,則置 ACTION[k,a]=Sj。其 Sj的含義是把輸入符號 a和狀態 j分別移入文法符號棧和狀態棧。 (2) 若項目 [A→ α ,a] 屬于 Ik，則置 ACTION[k,a]= rj 其中a∈V T， rj 的含義為把當前棧頂符號串 α 歸約為 A(即用產生式 A→ α 歸約 )。 j為在文法中對產生式 A→ α 的編號。 (3) 若項目 [S?→S ， ]屬于 Ik，則置 ACTION[k， ]＝ acc，表示 接受 。 (4) 若 GO(Ik， A)＝ Ij，其中 A∈V N，則置 GOTO[k,A]＝ j。表示轉入 j狀態，置當前文法符號棧頂為 A，狀態棧頂為 j。 (5) 凡不能用規則 (1)~(4)填入分析表中的元素，均置“報錯標志”。我們用“空白”表示之。 LR(1)分析表的構造除 (2) 外，其余同 LR(0)或 SLR(1)。即 若項目 [A→ α ,a] 屬于 Ik，則置 ACTION[k,a]= rj。也就是歸約時向前查看的符號為向前搜索符。 根據上述規則，我們對 LR(1)項目集族構造其相應的 LR(1)分析表如表 。 狀態 ACTION GOTO a b c d e S A 0 1 2 3 4 5 6 7 8 9 10 11 S2 S3 . . . . . S9 S10 r5 . . . . S8 r5 . S11 . . S5 S7 . acc . . . . . r1 r3 r2 r4 1 . . 4 6