第6章自底向上優(yōu)先分析法(已修改)
2025-08-01 06:29 本頁面
【正文】 編譯原理 第 6章 自底向上優(yōu)先分析法 自底向上優(yōu)先分析概述 簡單優(yōu)先分析 算符優(yōu)先分析 返回目錄 編譯原理 自底向上分析方法 自底向上分析方法，也稱 移進(jìn) 歸約 分析法。 實(shí)現(xiàn)思想： ?對輸入符號串自左向右進(jìn)行掃描，并 將輸入符逐個(gè)移入一個(gè)后進(jìn)先出棧中 ，邊移入邊分析， 一旦棧頂符號串形成某個(gè)句型的句柄時(shí)，（該句型對應(yīng)某產(chǎn)生式的右部）， 就用 該產(chǎn)生式的 左部 非終結(jié)符 代替 相應(yīng)右部的文法符號串，這稱為 歸約 。 ?重復(fù)這一過程直到歸約到棧中只剩文法的開始符號時(shí)則為分析成功 ，也就確認(rèn)輸入串是文法的句子 。 S 10） aAcBe 歸約 (S→ aAcBe) 文法 G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d a b b c d e 步驟 符號棧 輸入符號串 動(dòng)作 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 接受 分析符號串 abbcde是否為 G[S]的句子？ 對輸入串 abbcde的移進(jìn) 規(guī)約分析過程 S ? aAcBe ? aAcde ? aAbcde ? abbcde 編譯原理 算法應(yīng)考慮的問題 算法是否能夠終止？ 算法是否快速？ 算法是否能夠處理所有的情況？ 在每一步中如何選擇子串進(jìn)行歸約？ 編譯原理 ?自下而上語法分析的策略：移進(jìn) 規(guī)約分析。 ?移進(jìn) 就是將一個(gè)終結(jié)符推進(jìn)棧。 ?歸約 就是將 0個(gè)或多個(gè)符號從棧中彈出，根據(jù)產(chǎn)生式將一個(gè)非終結(jié)符壓入棧。 ?移進(jìn) 歸約過程是自頂向下最右推導(dǎo)的逆過程（規(guī)范歸約）。 編譯原理 ? 簡單優(yōu)先分析法 對一個(gè)文法按一定原則求出該文法所有符號（終結(jié)符和非終結(jié)符）之間的優(yōu)先關(guān)系，按照這種關(guān)系確定歸約過程中的句柄，它的歸約實(shí)際上是一種規(guī)范歸約。 ? 算符優(yōu)先分析法 只規(guī)定算符（終結(jié)符）之間的優(yōu)先關(guān)系。找到句柄就歸約，不是規(guī)范歸約。 優(yōu)先分析法 編譯原理 簡單優(yōu)先分析法 按照文法符號（包括終結(jié)符和非終結(jié)符）
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1