【正文】 s5 ? 7 0235 aAc de s8 ? 8 02358 aAcd e r4 ? 9 02357 aAcB s9 ? 10 023579 aAcBe r1 ? 11 01 S acc ＬＲ分析 ? 特征 : – ． 規(guī)范的 – ． 符號棧中的符號是規(guī)范句型的前綴 ， 且不含句柄以后的任何符號 – ． 分析決策依據(jù) ―― 棧頂狀態(tài)和現(xiàn)行輸入符號 ． ？ 識別規(guī)范句型特定前綴 (就到句柄為止 )的 DFA. ? 四種技術(shù) – LR(0) SLR(1) LR(1) LALR(1) 文法 G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d a b b c d e 步驟 符號棧 輸入符號串 動作 1） abbcde 移進 2） a bbcde 移進 A 3） ab bcde 歸約 (A→ b) 4） aA bcde 移進 A 5） aAb cde 歸約 (A→ Ab) 6） aA cde 移進 7） aAc de 移進 B 8） aAcd e 歸約 (B→ d) 9） aAcB e 移進 11） S 接受 S 10） aAcBe 歸約 符號串 abbcde是否是 G[S]的子 對輸入串 abbcde的移進 規(guī)約分析過程 S ? aAcBe ? aAcde ? aAbcde ? abbcde 步驟 符號棧 輸入符號串 動作 1） abbcde 移進 0 S2 2） a bbcde 移進 02 S4 4） aA bcde 移進 023 S6 6） aA cde 移進 023 S5 7） aAc de 移進 0235 S8 9） aAcB e 移進 02357 S9 11） S 接受 01 acc 對輸入串 abbcde的 LR分析過程 3） ab bcde 歸約 (A→ b) 024 r2 3 5） aAb cde 歸約 (A→ Ab) 0236 r3 3 8） aAcd e 歸約 (B→ d) 02358 r4 7 10） aAcBe 歸約 (S→ aAcBe) 023579 r1 1 ACTI ON GOT Oa c e b d S A B0 S211 a c c2 S433 S5S64 r2r2r2r2r2r25 S876 r3r3r3r3r3r37 S98 r4r4r4r4r4r49 r1r1r1r1r1r1狀態(tài)棧 ACTION GOTO 文法 G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d Si:移進，將狀態(tài) i和 輸入符 進棧 ri:歸約，用第 i個產(chǎn)生式歸約，同時狀態(tài)棧與符號棧退出相應個符號，并把 GOTO表相應狀態(tài)和第 i個產(chǎn)生式的 左部 非終結(jié) 符入棧。 repeat for J 中的每個項目 A ?? .B ? 和產(chǎn)生式 B? ? ， 若 B? .? 不在 J中 do 將 B? .? 加到 J中 until 再沒有項目加到 J中 return J }。 例 ? 文法 G: ? （ 0） S`→E (1) E→aA (2) E→bB ? (3) A→cA (4) A→d (5) B→cB ? (7) B→d ? LR(0) 項目集規(guī)范族（ 識別 G的活前綴的 DFA)： I0: S`→ ． E I1: S`→E ． I2: E→a ． A ? E→ ． aA A→.cA ? E→ ． bB A→ ． d ? ? I3: E→b ． B I4: A→c .A I5: B→ ． cB A→ ． cA B→c ． B B→ ． d A → .d B→ ． cB B→ ． d I6: I7: I8: E→aA ． E→bB ． A→cA ． I9: B→cB ． I10: A→d ． I11: B→cB ． LR(0)分析表的構(gòu)造 假定 C={I0, I1,…… ， In}， 令每個項目集 Ik的下標 k 為分析器的一個狀態(tài) ， 因此 ， G` 的 LR(0)分析表含有狀態(tài) 0， 1， …… ， n。其中 ， 假定 A→ α 為文法 G`的第 j個產(chǎn)生式； ? 若項目 S`→S ． 屬于 Ik, 則置 ACTION[k, ]為 “ 接受 ” ，簡記為 “ acc‖。具有 LR(0)表的文法 G稱為一個 LR（ 0） 文法。 G[S]拓廣 為 : S’ ? S S ?a A c B e A ?b A ?Ab B ?d I0 : S’ ? ? S S ? ? a A c B e I1 : S’ ? S ? I2 : S ? a ? A c B e A ? ? b A ? ? Ab I3 : S ? a A ? c B e A ? A ? b I4 : A ? b ? I5 : S ? a A c ? B e B ? ? d I7 : S ? a A c B ? e I8 : B ? d ? I9 : S ? a A c B e ? I6 : A ? A b ? S a A b b c B e d G[L]= ab+ cde 例 G[S]的 LR(0)分析表 ACTI ON GOT Oa c e b d S A B0 S211 a c c2 S433 S5S64 r2r2r2r2r2r25 S876 r3r3r3r3r3r37 S98 r4r4r4r4r4r49 r1r1r1r1r1r1Step states. Syms. The rest of input action goto 1 0 abbcde s2 2 02 a bbcde s4 3 024 ab bcde r2 3 4 023 aA bcde s6 5 0236 aAb cde r3 3 6 023 aA cde s5 7 0235 aAc de s8 8 02358 aAcd e r4 7 9 02357 aAcB e s9 10 023579 aAcBe r1 1 11 01 S acc 對輸入串 abbcde的分析過程 Step states. Syms. The rest of input action goto 1 0 abbce s2 2 02 a bbce s4 3 024 ab bce r2 3 4 023 aA bce s6 5 0236 aAb ce r3 3 6 023 aA ce s5 7 0235 aAc e 出錯 說明 abbce不是 文法 G[S]的 句子 對輸入串 abbce的分析過程 構(gòu)造識別活前綴的 NFA 文法 G‘： S‘→E E→a