自底向上分析把一個(gè)輸入符號(hào)串逐步歸約到文法的開始符-展示頁(yè)
2025-07-30 08:47本頁(yè)面
【正文】 b c d e $ 移進(jìn)( 3 ) $ ab b c d e $ 歸約， A ? b( 4 ) $ aA b c d e $ 移進(jìn)( 5 ) $ a A b c d e $ 歸約， A ? Ab( 6 ) $ aA c d e $ 移進(jìn)( 7 ) $ a A c d e $ 移進(jìn)( 8 ) $ a A c d e$ 歸約， B ? d( 9 ) $ a A c B e$ 移進(jìn)( 1 0 ) $ a A c B e $ 歸約， S ? a A c B e( 1 1 ) $S $ 接受 “移進(jìn) 歸約”分析對(duì)符號(hào)棧的使用有四類操作：移進(jìn)、歸約、接受和出錯(cuò)處理。分析器的初始狀態(tài)為 : 棧 輸入 ＄ w＄ 工作過程：自左至右把串 w 的符號(hào)一一移進(jìn)棧里，一旦棧頂形成句柄時(shí)，就進(jìn)行歸約。 規(guī)范歸約的中心問題是：如何尋找或確定 一 個(gè)句型的句柄 。 ? rm 二義性文法存在規(guī)范歸約不唯一的句子。 ? βw 表示一個(gè)規(guī)范句型 , ?是在 β歸約之前進(jìn)行的規(guī)范歸約得到的結(jié)果 , ? ?(VT?VN)* , w ? VT*。稱右句型序列 ?n , ?n1,… , ? 1, ? 0 是 ?的一個(gè) 規(guī)范歸約 ，如果序列滿足 1. ? n= ? ， ? 0=S； 2.?i(0 ≤ i n）， ?i ?i+1 規(guī)范歸約是關(guān)于 ?的一個(gè)最右推導(dǎo)的逆過程。 因?yàn)閺淖笾劣易x入輸入符號(hào)串，自然在被歸約的句型中找最左邊的某個(gè)產(chǎn)生式的右部（句柄）進(jìn)行歸約。 歸約的過程是，已知 αβw和產(chǎn)生式 A→β ， 用產(chǎn)生式 A→β 左部 A替換 αβw中的 β，得到符號(hào)串 αAw。稱作 “移進(jìn) — 歸約”分析。 自底向上分析 把一個(gè)輸入符號(hào)串逐步歸約到文法的開始符號(hào)。 這種方法的大致過程是，用一個(gè)棧，把輸入符號(hào)一個(gè)一個(gè)地移進(jìn)到棧里，當(dāng)棧頂形成某個(gè)產(chǎn)生式的右部（ 句柄） 時(shí)，把棧頂?shù)倪@一部分替換成 (歸約為 )它的左部符號(hào)。 規(guī)范歸約 句柄 “移進(jìn) — 歸約”分析的 棧實(shí)現(xiàn) 規(guī)范歸約 歸約 G=(VT,VN,S,P),α, β ∈ (VT∪ VN)*,A→β ∈ P, αAw ?αβw 。 從輸入符號(hào)串出發(fā) ，每次從被歸約的句型中找到一個(gè)產(chǎn)生式的右部 ，用其左部替換之，得到新的句型 ，直至歸約到文法的開始符號(hào)。 例 G[S](),其產(chǎn)生式如下： ① S→ aABe ②A→ b ③A→ Abc ④B→ d () 輸入串 abbcde aAbcde aAde aABe S S?aABe ? aAde ? aAbcde? abbcde a b b c d e ?abbcde A ?aAbcde A ?aAde B S ?aABe S 例 G[S](),其產(chǎn)生式如下： ① S→ aABe ②A→ b ③A→ Abc ④B→ d () 輸入串 abbcde aAbcde aAde aABe
物理相關(guān)推薦
鄂ICP備17016276號(hào)-1