[理學]第四章2自下而上語法分析-展示頁
2024-10-25 22:57本頁面
【正文】 約的過程和 LR分析過程中的實現(xiàn) 5. 掌握 LR語法分析的實現(xiàn)過程 回顧 : 歸約和推導的概念 例 S ? aABe A ? Abc | b B ? d 用歸約的方法對句子 abbcde進行語法分析 。 例 S ? aABe A ? Abc | b B ? d abbcde 例 S ? aABe A ? Abc | b B ? d abbcde aAbcde aAbcde 例 S ? aABe A ? Abc | b B ? d abbcde aAbcde aAde 例 S ? aABe A ? Abc | b B ? d abbcde aAbcde aAde aABe 例 S ? aABe A ? Abc | b B ? d abbcde aAbcde aAde aABe S 例 S ? aABe A ? Abc | b B ? d abbcde aAbcde aAde aABe S S ?rm aABe ?rm aAde ?rm aAbcde ?rm abbcde 自下而上的語法分析的一般過程 ? 實現(xiàn)思想 – 從輸入符號串開始 ， 從左到右進行掃描 ， 將輸入符號逐個移入一個棧中 ， 邊移入邊分析 ， 一旦棧頂符號串形成某個產生式的右部時 ， 就用該產生式的左部非終結符代替 ， 稱為 歸約 。 – 從 語法樹的角度 看：從語法樹的 樹葉 開始 ， 逐步向上歸約 構造分析樹 ， 直到形成根結點 。 ? 最左推導 (Leftmost Derive) – 每次推導都替換當前句型的最左邊的非終結符。 ? 最右推導 (Rightmost Derive) – 每次推導都替換當前句型的最右邊的非終結符。 例： 設有文法 G[S]： (1) S ? aABe (2) A ? b (3) A ? Abc (4) B ? d 使用最右推導： 因為 S aABe aAde aAbcde abbcde，所以 abbcde是文法 G的句子。 a b a A a b A a c b A a A a d A a B A a e B A a S 1 移進a 2 移進b 3 歸約2 4 移進b 5 移進c 6 歸約3 7 移進d 8 歸約4 9 移進e 10 歸約1 ―移進 歸約”分析法中棧的使用 ? 移進 歸約分析器使用了一個符號棧和一個輸入緩沖區(qū) ? 句型表示 a1 a2 a3 …… … X1 X2 X3 ―移進 歸約” 分析程序 輸出 棧(存放句型前綴) 輸入串 符號棧內容 + 輸入緩沖區(qū)內容 ＝ 當前句型 一般形式： 符號棧的內容 剩余輸入串 初態(tài)： 輸入串 終態(tài)： S ? 分析器結構 ? 3. 過程描述： do{ do { 將輸入串最左邊的符號移入棧內 。 ? 注意： 該過程并未涉及如何在棧里找可歸約串。 分析器的四種動作 ? 1) 移進 ： 讀入下一個輸入符號并把它下推進棧。 ? 3) 接受 ： 當棧底只有 “ ‖和開始符號，而輸入也已經到達右端標志符號 “ ‖時，識別出符號串是句子，執(zhí)行該動作，表示分析成功，是歸約的一種特殊情況。 ? 注意：決定移進和歸約的依據是什么？ 棧頂是否出現(xiàn)了可歸約的符號串。 – 一旦發(fā)現(xiàn) 可歸約串 (某個產生式的右端 )就立即 歸約 。 – 若最終能歸約成文法的開始符號，則分析成功（ 接受 ）；否則 出錯 。 ? 關鍵是 如何識別可歸約的符號串 ？ 語法分析中問題的提出： ① 在構造語法樹的過程中 ， 何時歸約 ？ 當可歸約串出現(xiàn)在棧頂時就進行歸約 。 規(guī)范歸約：使用 句柄 來定義可歸約串 算符優(yōu)先：使用 最左素短語 來定義可歸約串 ? 自下而上語法分析主要有以下三種方法： ① 簡單優(yōu)先分析法 (規(guī)范歸
教學課件相關推薦
鄂ICP備17016276號-1