編譯原理532-lr(0)項(xiàng)目集族和lr(0)分析表的構(gòu)造(編輯修改稿)
2024-11-13 02:27 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 分類 ? 移進(jìn)項(xiàng)目 : A→ α aβ ? 分析時(shí)把 a移進(jìn)符號(hào)棧 ? 待約項(xiàng)目 : A→ α Bβ ? 用產(chǎn)生式 A的右部歸約時(shí) ,首先要將 B的產(chǎn)生式右部歸約為 B, 對(duì) A的右部才能繼續(xù)進(jìn)行分析 ? 歸約項(xiàng)目 : A→ α ? 表明一個(gè)產(chǎn)生式的右部已分析完，句柄已形成可以歸約 ? 接受項(xiàng)目 : S39?！鶶 ? 表明已分析成功 三、 LR(0)項(xiàng)目集規(guī)范族的構(gòu)造 構(gòu)造識(shí)別文法活前綴 DFA的三種方法 * ，然后由此正規(guī)表達(dá)式構(gòu)造 NFA, 再確定化為 DFA。 ，按一定規(guī)則構(gòu)造識(shí)別活前綴的 NFA, 再確定化為 DFA。 ，直接求出 LR(0)項(xiàng)目集規(guī)范族，再由轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關(guān)系得到識(shí)別活前綴的 DFA。 I的閉包函數(shù) CLOSURE(I) GO(I, X) LR(0)項(xiàng)目集規(guī)范族 ? 原文法 G的開(kāi)始符號(hào)為 S, 在 G中加 S39?！鶶 后得新的文法 G39。， 則稱 G?為原文法 G的拓廣文法。 ? 使文法的開(kāi)始符號(hào)不出現(xiàn)在任何產(chǎn)生式右部，當(dāng)棧頂出現(xiàn) S′, 則分析完成 。 ? 注 :即使原開(kāi)始符號(hào) S不出現(xiàn)在任何產(chǎn)生式右部 ,為了統(tǒng)一起見(jiàn)也要增加該產(chǎn)生式。 I的閉包函數(shù) CLOSURE(I) a) I 的項(xiàng)目均在 CLOSURE(I) 中。 b) 若 A→α Bβ屬于 CLOSURE(I), 則每一形如 B→ γ的項(xiàng)目也屬于 CLOSURE(I) c) 重復(fù) b)直到 CLOSURE(I)不再擴(kuò)大。 NFA : 狀態(tài)集合 I的 ε閉包 εclosure(I) ε A→α Bβ B→ γ 補(bǔ)充例 I＝ { S39。→ E } CLOSURE(I) = { S39?！?E, E→ aA, E→ bB } 1． S39?！?E 2． S39。→E 3． E→ aA 4． E→a A 5． E→aA 6． A→ cA 7． A→c A 8． A→cA 9． A→ d 10. A→d 11. E→ bB 12. E→b B 13. E→bB 14. B→ cB 15. B→c B 16. B→cB 17. B→ d 18. B→d 1 3 11 GO(I, X) GO(I, X) = CLOSURE(J) , X∈ (VN∪ VT) , J = {A→α Xβ| A→α Xβ∈ I } X A→α Xβ A→α Xβ 若狀態(tài) I識(shí)別活前綴 γ ,則狀態(tài) J識(shí)別活
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1