《編譯原理5.1-自下而上分析基本問題.ppt》由會員分享，可在線閱讀，更多相關《編譯原理5.1-自下而上分析基本問題.ppt（21頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、第五章 語法分析 自下而上分析 Bottom-up Parsing 自下而上語法分析 優(yōu)先分析法 簡單優(yōu)先分析法 * 算符優(yōu)先分析法 LR分析法 YACC 第五章 語法分析 5.1 自下而上分析基本問題 5.2 算符優(yōu)先分析 5.3 LR分析 5.4 YACC 5.1 自下而上分析基本問題 5.1.1 歸約 5.1.2 規(guī)范歸約簡述 5.1.3 符號棧的使用和語法樹的表示 1. 自下而上分析過程 2. 自下而上分析面臨的問題 1. 自下而上分析過程 - 補充例 GS: ScAd Aab Aa 識別輸入串
2、 cabd 是否該文法的句子 S c A d a b 自下而上分析過程中的每一步，都是從當前串 中選擇一個子串，將它歸約到某個非終結(jié)符號 , 該子串稱為 “ 可歸約串 ” GS: ScAd Aab Aa c d a b A S S c A d a b 2. 自下而上分析面臨的問題 當串中的某部分和某個產(chǎn)生式右部匹配時 , 該不該歸約 ? 如何確定 可歸約串 ? a不是 可歸約串 ,ab是 可歸約串 可歸約串 最左素短語 句柄 算符優(yōu)先分析 規(guī)范規(guī)約 如何精確定義 “ 可歸約串 ” ? 本章核心 1. 采用哪一種自下而上分析方法
3、? 2. 如何定義可歸約串 ? 3. 如果在當前符號串中確定可歸約串 ? 5.1.1 歸約 G: (1) SaAcBe (2) Ab (3) AAb (4) Bd 識別輸入串 abbcde# 是否該文法的句子 a b b c d e A A B S 例 : p83 a b b c d e A A B S G: (1) SaAcBe (2) Ab (3) AAb (4) Bd 輸入串 abbcde# 可行的實現(xiàn)方案 : 邊掃描 , 邊歸約 最左歸約 (規(guī)范歸約 ) 復習最左推導、最右推導、最左歸約、 最右歸約、規(guī)范推導、規(guī)范歸約的概念 a
4、G: (1) SaAcBe (2) Ab (3) AAb (4) Bd 輸入串 abbcde# b a A b c 何時移進 ,何時歸約 ?歸約誰 ? 如何確定 可歸約串 ? a a A a A a A c a A d c a A B c a A B e S 動 作 移 進 移 進 歸 約 移 進 歸 約 移 進 歸 約 歸 約 移 進 移 進 a b (2) b (3) c d (4) e (1) 圖 5.1 符號棧的變遷 移進 -歸約分析 用棧實現(xiàn)規(guī)范歸約 棧頂出現(xiàn)可歸約串即可歸約 5.1.2 規(guī)范歸約簡述 1. 短語、直接短語、
5、句柄 的定義 2. 從句型的語法樹上找出句型的短語、 直接短語、句柄 3. 規(guī)范歸約與句柄的關系 精確定義規(guī)范歸約過程中的可歸約串 短語（ Phrase） S A, 且 A , 則稱 是 句型 相對于 非終結(jié)符 A 的短語 直接短語 (簡單短語 , Simple phrase) S A, 且 A , 則稱 是 句型 相對于 規(guī)則 A 的直接短語 * + * 句柄 (Handle) 一個句型的 最左直接短語 稱為該句型的句柄 . 1. 定義 找出句型 i1*i2+i3 的所有 短語 , 直接短語 , 句柄 . G: ET | E+T TF
6、| T*F F(E) | i T F E E + T * F T F i1 i2 i3 短語 : i1, i2, i3, i1*i2, i1*i2+i3 直接短語 : i1, i2, i3, 句柄 : i1 一棵子樹的所有末端結(jié)點自 左至右排列起來就形成一個 相對子樹根的短語 . 2. 從語法樹中 p85 例 5.1 p85 例 5.2 找出句型 E+T*F+i 的所有 短語 , 直接短語 , 句柄 G: ET | E+T TF | T*F F(E) | i 短語 : E+T*F+i E+T*F, i , T*F 直接短語 : T*F, i 句柄 : T*F
7、E E + T F i E + T T * F G: (1) SaAcBe (2) Ab (3) AAb (4) Bd a b b c d e A A B S 例 : p83 a b a A b c a a A a A a A c a A d c a A B c a A B e S 移 進 移 進 歸 約 移 進 歸 約 移 進 歸 約 歸 約 移 進 移 進 a b (2) b (3) c d (4) e (1) 圖 5.1 符號棧的變遷 規(guī)范歸約過程中的 可歸約串是句柄 3. 規(guī)范歸約與句柄的關系 規(guī)范歸約精確定義 P86 假定
8、 是文法 G的一個句子 , 如果序列 : n, n-1, , 0 滿足如下條件 , 則 n, n-1, , 0 是一個規(guī)范歸約 : (1) n = 是給定的句子 (2) 0 = S 是文法的開始符號 (3) 對任何 i, 0
9、 a b a A b c a a A a A a A c a A d c a A B c a A B e S 移 進 移 進 歸 約 移 進 歸 約 移 進 歸 約 歸 約 移 進 移 進 a b (2) b (3) c d (4) e (1) a b a A b c a a A a A a A c a A d c a A B c a A B e S 移進 移進 歸約 移進 歸約 移進 歸約 歸約 移進 移進 a b (2) b (3 ) c d (4) e (1 ) 移進 -歸約分析 用棧實現(xiàn)規(guī)范歸約 GS: ScAd Aab Aa S c A d a b 分析過程詳見黑板 移進 -歸約分析器 :符號棧 + 輸入緩沖區(qū) 分析器的動作 :移進 ,歸約 ,接受 ,出錯 步驟 符號棧 輸入串 動作 課后練習 : p88 例 5.3 對 i1*i2+i3的移進 -歸約分析 P89 語法樹的表示 - 穿線表 *
編譯原理5.1-自下而上分析基本問題.ppt
