【正文】 LR分析 自下而上語法 分析算法之 ： ； :； ： ? 復(fù)習(xí)：移進(jìn) 歸約分析 ： ； :； ： 文法 G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d a b b c d e 步驟 符號棧 輸入符號串 動作 1） abbcde 移進(jìn) 2） a bbcde 移進(jìn) A 3） ab bcde 歸約 (A→ b) 4） aA bcde 移進(jìn) A 5） aAb cde 歸約 (A→ Ab) 6） aA cde 移進(jìn) 7） aAc de 移進(jìn) B 8） aAcd e 歸約 (B→ d) 9） aAcB e 移進(jìn) 11） S 接受 S 10） aAcBe 歸約 (S→ aAcBe) 分析符號串 abbcde是否 G[S]的句子 對輸入串 abbcde的移進(jìn) 規(guī)約分析過程 S ? aAcBe ? aAcde ? aAbcde ? abbcde ? 在步驟 3中，用 A→ b歸約 ? 在步驟 5中，用 A→ Ab歸約 ? 問題：何時移進(jìn)？何時歸約？用哪個產(chǎn)生式歸約？ 3） ab bcde 歸約 (A→ b) 5） aAb cde 歸約 (A→ Ab) 4） aA bcde 移進(jìn) 6） aA cde 移進(jìn) 分析：已分析過的部分在棧中的 前綴 不同，而且移進(jìn)和歸約后棧中的狀態(tài)會發(fā)生變化 我們引入一個新的 狀態(tài)棧 來表示符號棧中的符號目前狀態(tài) 用 LR分析表 來表示不同狀態(tài)下對于各輸入符號應(yīng)采取的動作 步驟 符號棧 輸入符號串 動作 1） abbcde 移進(jìn) 0 S2 2） a bbcde 移進(jìn) 02 S4 4） aA bcde 移進(jìn) 023 S6 6） aA cde 移進(jìn) 023 S5 7） aAc de 移進(jìn) 0235 S8 9） aAcB e 移進(jìn) 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 ACT ION GOTOa c e b d S A B0 S211 acc2 S433 S5S64 r2r2r2r2r2r25 76 r3r3r3r3r3r378 r4r4r4r4r4r49 r1r1r1r1r1r1狀態(tài)棧 ACTION GOTO 文法 G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d Si:移進(jìn)，并將狀態(tài) i進(jìn)棧 ri:用第 i個產(chǎn)生式歸約，同時狀態(tài)棧與符號棧退出相應(yīng)個符號，根據(jù) GOTO表將相應(yīng)狀態(tài)入棧 步驟 符號棧 輸入符號串 動作 1） abbcde 移進(jìn) 0 S2 2） a bbcde 移進(jìn) 02 S4 4） aA bcde 移進(jìn) 023 S6 6） aA cde 移進(jìn) 023 S5 7） aAc de 移進(jìn) 0235 S8 9） aAcB e 移進(jìn) 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 ACT ION GOTOa c e b d S A B0 S211 acc2 S433 S5S64 r2r2r2r2r2r25 76 r3r3r3r3r3r378 r4r4r4r4r4r49 r1r1r1r1r1r1狀態(tài)棧 ACTION GOTO 文法 G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d Si:移進(jìn)，并將狀態(tài) i進(jìn)棧 ri:用第 i個產(chǎn)生式歸約，同時狀態(tài)棧與符號棧退出相應(yīng)個符號，根據(jù) GOTO表將相應(yīng)狀態(tài)入棧 問題 ： ? 對于一個文法，狀態(tài)集是如何確定的？ ? LR分析表是如何得到的？ 可歸前綴與活前綴 文法 G[S]： (1) S → aAcBe[1] (2) A → b[2] (3) A → Ab[3] (4) B → d[4] S ?aAcBe[1] ?aAcd[4]e[1] ?aAb[3]cd[4]e[1] ?ab[2]b[3]cd[4]e[1] 每次歸約句型的前部分 依次為： ab[2] aAb[3] aAcd[4] aAcBe[1] 規(guī)范句型的這種前部分符號串稱為 可歸前綴 我們把形成可歸前綴之前包括可歸前綴在內(nèi)的所有規(guī)范句型的前綴都稱為 活前綴 ?,a,ab ? ,a,aA,aAb ? ,a,aA,aAc,aAcd ? ,a,aA,aAc,aAcB,aAcBe 活前綴（ Viable Prefixes） ? viable:adj – capable of growing and developing~ seed – capable of being put into practice : workable ? 定義： – S’ ?A? ???是文法 G中的一個規(guī)范推導(dǎo)，如果符號串是的前綴，則稱是 G的一個 活前綴 。 R?*R?? LR分析需要構(gòu)造識別 活前綴 的 有窮自動機(jī) –我們可以文法的終結(jié)符和非終結(jié)符都看成有窮自動機(jī)的輸入符號，每次把一個符號進(jìn)?？闯梢炎R別過了該符號，同時狀態(tài)進(jìn)行轉(zhuǎn)換，當(dāng)識別到可歸前綴時，相當(dāng)于在棧中形成句柄，認(rèn)為達(dá)到了識別句柄的終態(tài)。 步驟 符號棧 輸入符號串 動作 1） abbcde 移進(jìn) 0 S2 2） a bbcde 移進(jìn) 02 S4 4） aA bcde 移進(jìn) 023 S6 6） aA cde 移進(jìn) 023 S5 7） aAc de 移進(jìn) 0235 S8 9） aAcB e 移進(jìn) 02357 S9 11） S 接受 01 acc 對輸入串 abbcde的 LR分析過程 3） ab bcde 歸約 (A→ b) 024 r2 3 5） aAb cde 歸約 (A