自底向上分析把一個(gè)輸入符號串逐步歸約到文法的開始符(已修改)
2025-08-02 08:47 本頁面
【正文】 自底向上分析 把一個(gè)輸入符號串逐步歸約到文法的開始符號。 這種方法的大致過程是，用一個(gè)棧，把輸入符號一個(gè)一個(gè)地移進(jìn)到棧里，當(dāng)棧頂形成某個(gè)產(chǎn)生式的右部（ 句柄） 時(shí)，把棧頂?shù)倪@一部分替換成 (歸約為 )它的左部符號。稱作 “移進(jìn) — 歸約”分析。 規(guī)范歸約 句柄 “移進(jìn) — 歸約”分析的 棧實(shí)現(xiàn) 規(guī)范歸約 歸約 G=(VT,VN,S,P),α, β ∈ (VT∪ VN)*,A→β ∈ P, αAw ?αβw 。 歸約的過程是，已知 αβw和產(chǎn)生式 A→β ， 用產(chǎn)生式 A→β 左部 A替換 αβw中的 β，得到符號串 αAw。 從輸入符號串出發(fā) ，每次從被歸約的句型中找到一個(gè)產(chǎn)生式的右部 ，用其左部替換之，得到新的句型 ，直至歸約到文法的開始符號。 因?yàn)閺淖笾劣易x入輸入符號串，自然在被歸約的句型中找最左邊的某個(gè)產(chǎn)生式的右部（句柄）進(jìn)行歸約。 例 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 S S?aABe ? aAde ? aAbcde? abbcde a b b c d e ?abbcde A ?aAbcde A ?aAde B S ?aABe S S A ? ? w ?Aw? ? ?w 已知 ? ?w， 分 析已識別出 ?，產(chǎn)生式 A? ? 的右部 ?， 再看待輸入串 w的最左邊符號，用 A替 換 ?得到 ?Aw； 自上而下分析是 從w A?， 看 FIRST(?), w A? ? w ? ? 定義 假定 ?是文法 G的一個(gè)句子。稱右句型序列 ?n , ?n1,… , ? 1, ? 0 是 ?的一個(gè) 規(guī)范歸約 ，如果序列滿足 1. ? n= ? ， ? 0=S； 2.?i(0 ≤ i n）， ?i ?i+1 規(guī)范歸約是關(guān)于 ?的一個(gè)最右推導(dǎo)的逆過程。 如果文法 G是無二義的，那么，規(guī)范推導(dǎo) (最右推導(dǎo) )的逆過程必是規(guī)范歸約 (最左歸約 )。 ? βw 表示一個(gè)規(guī)范句型 , ?是在 β歸約之前進(jìn)行的規(guī)范歸約得到的結(jié)果 , ? ?(VT?VN)* , w ? VT*。 句柄的“最左”特征使得在移進(jìn) 歸約方法中，它處于符號棧的棧頂。 ? rm 二義性文法存在規(guī)范歸約不唯一的句子。例如， 文法 G[E]: E→ E＋ E ? E*E ?(E) ? id 句子 id＋ id*id有二個(gè)不同的最右推導(dǎo) : E?E+E
物理相關(guān)推薦
鄂ICP備17016276號-1