《編譯原理-劉善梅》第5章語法分析-自下而上分析

《《編譯原理-劉善梅》第5章語法分析-自下而上分析》由會員分享，可在線閱讀，更多相關《《編譯原理-劉善梅》第5章語法分析-自下而上分析（181頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第 五 章 語 法 分 析 自 下 而 上 分 析語 法 分 析 方 法 ：n 自 上 而 下 分 析 法 (Top-down)n 自 下 而 上 分 析 法 (Bottom-up) n基 本 思 想 它 從 文 法 的 開 始 符 號 出 發(fā) ， 反 復 使 用 各 種 產(chǎn) 生式 ， 尋 找 匹 配 的推導。n遞 歸 下 降 分 析 法 對 每 一 語 法 變 量 (非 終 結 符 )構 造 一 個 相 應 的 子程 序 ， 每 個 子 程 序 識 別 一 定 的 語 法 單 位 ， 通 過子 程 序 間 的 相 互 調(diào) 用 實 現(xiàn) 對 輸 入 串 的 識 別 。n預 測 分 析 程 序F非

2、 遞 歸 實 現(xiàn) F優(yōu) 點 ： 直 觀 、 簡 單 和 宜 于 手 工 實 現(xiàn) 。 n基 本 思 想 從 輸 入 串 開 始 ， 逐 步 進 行 “歸約” ， 直 到 文法 的 開 始 符 號 。 即 從 樹 末 端 開 始 ， 構 造 語 法 樹 。所 謂 歸 約 ， 是 指 根 據(jù) 文 法 的 產(chǎn) 生 式 規(guī) 則 ， 把 產(chǎn)生 式 的 右 部 替 換 成 左 部 符 號 。n算 符 優(yōu) 先 分 析 法 按 照 算 符 的 優(yōu) 先 關 系 和 結 合 性 質(zhì) 進 行 語 法 分 析 。適 合 分 析 表 達 式 。nLR分 析 法 規(guī) 范 歸 約 G(E)： E i| E+E | E-E |

3、 E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E E i +* Ei iEE EE 第 五 章 語 法 分 析 自 下 而 上 分 析n 自 下 而 上 分 析 的 基 本 問 題n 算 符 優(yōu) 選 分 析 算 法n LR分 析 法 一 、 自 下 而 上 分 析 的 基 本 問 題n 采 用 “ ” 思 想 進 行 自 下 而 上 分 析 。n基 本 思 想 用 一 個 寄 存 符 號 的 先 進 后 出 ， 把 輸 入 符 號一 個 一 個 地 移 進 到 棧 里 ， 當 棧 頂 形 成 某 個 產(chǎn)生 式 的 候 選 式 時 ， 即 把 棧 頂 的 這

4、一 部 分 替 換成 (歸約為 )該 產(chǎn) 生 式 的 左 部 符 號 。 n 例 ： 設 文 法 G(S)： (1) S aAcBe (2) A b (3) A Ab (4) B d試 對 abbcde進 行 “ 移 進 歸 約 ” 分 析 。a bbcdeb Ab c d abbcdeeB Sca e 步 驟 : 1 2 3 4 5 6 7 8 9 10動 作 : 進 a 進 b 歸 (2) 進 b 歸 (3) 進 c 進 d 歸 (4) 進 e 歸 (1)e d B Bb c c c cb A A A A A A A a a a a a a a a a S b dba c eSA BA自

5、下 而 上 分 析 過 程 ： 邊 輸 入 單 詞 符 號 ， 邊歸 約 。核 心 問 題 ： 識 別 可 歸 約 串 NNP VPSDETThe teacher Vpraised NNPDETthe studentn 定 義 ： 令 G是 一 個 文 法 ， S是 文 法 的 開 始 符 號 ， 假定 是 文 法 G的 一 個 句 型 ， 如 果 有 且 AS * A則 稱 是 句 型 相 對 于 非 終 結 符 A的 短 語 。 特 別 是 ， 如 果 有 A,則 稱 是 句 型 相 對 于 規(guī)則 A 的 直 接 短 語 。 一 個 句 型 的 最 左 直 接 短 語稱 為 該 句 型 的

6、 句 柄 。n 定 義 ： 令 G是 一 個 文 法 ， S是 文 法 的 開 始 符 號 ， 假定 是 文 法 G的 一 個 句 型 ， 如 果 有 且 AS * A則 稱 是 句 型 相 對 于 非 終 結 符 A的 短 語 。 考 慮 文 法 G(E)： E T | E+T T F | T*F F (E) | i和 句 型 i1*i2+i3： E E+T E+F E+i3 T+i3 T*F+i3 T*i2+i3 F*i2+i3 i1*i2+i3 * +E F*i2+i3 F i1 i1*i2+i3 短 語 ： i1E i1 *F+i3 F i2 i1*i2+i3 短 語 ： i2E i1

7、*i2+F F i3 i1*i2+i3 短 語 ： i3E E+ i3 E i1*i2 i1*i2+i3 短 語 ： i1*i2 E E E i1*i2+i3 i1*i2+i3 短 語 ： i1*i2+i3 G(E)： E T | E+T T F | T*F F (E) | i E E+T E+F E+i3 T+i 3 T*F+i3 T*i2+i3 F*i2+i3 i1*i2+i3 考 慮 文 法 G(E)： E T | E+T T F | T*F F (E) | i和 句 型 i1*i2+i3： E E+T E+F E+i3 T+i3 T*F+i3 T*i2+i3 F*i2+i3 i1*i2

8、+i3n 短 語 ： i1， i2， i3， i1*i2， i1*i2+i3n 直 接 短 語 ： i1， i2， i3n 句 柄 ： i 1 n 在 一 個 句 型 對 應 的 語 法樹 中 ：p 以 某 非 終 結 符 為 根 的 兩 代 以上 的 子 樹 的 所 有 末 端 結 點 從左 到 右 排 列 就 是 相 對 于 該 非終 結 符 的 一 個 短 語p 如 果 子 樹 只 有 兩 代 ， 則 該 短語 就 是 直 接 短 語 。E FF T TTi1 +* E Fi3i2 n 可 用 句 柄 來 對 句 子 進 行 歸 約句 型 歸 約 規(guī) 則abbcde (2) A b b

9、dba c eSA BA n 可 用 句 柄 來 對 句 子 進 行 歸 約句 型 歸 約 規(guī) 則abbcde (2) A baAbcde (3) A Ab dba c eSA BA n 可 用 句 柄 來 對 句 子 進 行 歸 約句 型 歸 約 規(guī) 則abbcde (2) A baAbcde (3) A AbaAcde (4) B d da c eSA B n 可 用 句 柄 來 對 句 子 進 行 歸 約句 型 歸 約 規(guī) 則abbcde (2) A baAbcde (3) A AbaAcde (4) B daAcBe (1) S aAcBe S a c eSA B n 定 義 ： 假

10、定 是 文 法 G的 一 個 句 子 ， 我 們稱 序 列 n， n-1， ， 0 是 一 個 規(guī) 范 歸 約 ， 如 果 此 序 列 滿 足 ： 1 n= 為 句 子 2 0為 文 法 的 開 始 符 號 ， 即 0=S 3 對 任 何 i， 0 i n， i-1是 從 i經(jīng) 把 句 柄替 換 成 為 相 應 產(chǎn) 生 式 左 部 符 號 而 得 到 的 。 把 上 例 倒 過 來 寫 ， 則 得 到 ：S aAcBe aAcde aAbcde abbcde 顯 然 這 是 一 個 最 右 推 導 。規(guī) 范 歸 約 是 最 右 推 導 的 逆 過 程最 左 歸 約 規(guī) 范 推 導由 規(guī) 范 推

11、 導 推 出 的 句 型 稱 為 規(guī) 范 句 型 。 b dba c eSA BA dba c eSA BAda c eSA B a c eSA B 符 號 棧 的 使 用n 棧 是 語 法 分 析 的 一 種 基 本 數(shù) 據(jù) 結 構 。 #作 為 棧 底 符號n 自 下 而 上 的 語 法 分 析 器 的 工 作 過 程 是 ： 自 左 至 右 把輸 入 串 的 符 號 一 一 移 進 符 號 棧 里 ， 一 旦 發(fā) 現(xiàn) 棧 頂 出現(xiàn) 可 歸 約 串 就 歸 約 ， 這 種 替 換 可 能 出 現(xiàn) 多 次 ， 直 至棧 頂 不 再 出 現(xiàn) 可 歸 約 串 為 止 。 然 后 繼 續(xù) 移 進

12、符 號 ，重 復 整 個 過 程 ， 直 至 棧 里 只 含 有 #和 文 法 開 始 符 號 、且 輸 入 串 全 被 吸 收 ， 僅 剩 下 #。 這 種 格 局 表 示 分 析 成功 ， 否 則 ， 就 說 明 輸 入 串 有 語 法 錯 誤 符 號 棧 的 使 用n 例 ： 文 法 G(E)： E T | E+T T F | T*F F (E) | i輸 入 串 為 i1*i2+i3 ， 分 析 步 驟 為 ： 步 驟 符 號 棧 輸 入 串 動 作0 # i1*i2+i3# 預 備1 #i1 *i2+i3# 進2 #F *i2+i3# 歸 ， 用 Fi3 #T *i2+i3# 歸 ，

13、 用 TF4 #T* i2+i3# 進n G(E)： E T | E+T T F | T*F F (E) | i 步 驟 符 號 棧 輸 入 串 動 作4 #T* i2+i3# 進5 #T*i2 +i3# 進6 #T*F +i3# 歸 ， 用 Fi7 #T +i3# 歸 ， 用 TT*F8 #E +i3# 歸 ， 用 ET9 #E+ i3# 進n G(E)： E T | E+T T F | T*F F (E) | i 步 驟 符 號 棧 輸 入 串 動 作9 #E+ i3# 進10 #E+i3 # 進11 #E+F # 歸 ， 用 Fi12 #E+T # 歸 ， 用 TF13 #E # 歸 ，

14、 用 EE+T14 #E # 接 受n G(E)： E T | E+T T F | T*F F (E) | i n語 法 分 析 的 方 法 ：自 下 而 上 分 析 法 (Bottom-up) 基 本 思 想 ： 從 輸 入 串 開 始 ， 逐 步 進 行 “歸約”，直 到 文 法 的 開 始 符 號 。 即 從 樹 末 端 開 始 ， 構 造 語法 樹 。 所 謂 歸約 ， 是 指 根 據(jù) 文 法 的 產(chǎn) 生 式 規(guī)則 ， 把 產(chǎn) 生 式 的 右 部 替 換 成 左 部 符 號 。 回 顧 歸 約n 采 用 “移進歸約”思 想 進 行 自 下 而 上 分 析 。n 基 本 思 想 ： 用

15、一 個 寄 存 符 號 的 先 進 后 出棧， 把 輸入 符 號 一 個 一 個 地 移 進 到 棧 里 ， 當 棧 頂 形 成 某 個產(chǎn) 生 式 的 候 選 式 時 ， 即 把 棧 頂 的 這 一 部 分 替 換 成(歸約為 )該 產(chǎn) 生 式 的 左 部 符 號 。 規(guī) 范 歸 約n 定 義 ： 令 G是 一 個 文 法 ， S是 文 法 的 開 始 符號 ， 假 定 是 文 法 G的 一 個 句 型 ， 如 果 有 且 AS * A則 稱 是 句 型 相 對 于 非 終 結 符 A的 短 語 。特 別 是 ， 如 果 有 A,則 稱 是 句 型 相 對于 規(guī) 則 A 的 直 接 短 語 。

16、 一 個 句 型 的 最 左直 接 短 語 稱 為 該 句 型 的 句 柄 。 n 定 義 ： 假 定 是 文 法 G的 一 個 句 子 ， 我 們稱 序 列 n， n-1， ， 0 是 的 一 個 規(guī) 范 歸 約 ， 如 果 此 序 列 滿 足 ： 1 n= 2 0為 文 法 的 開 始 符 號 ， 即 0=S 3 對 任 何 i， 0 i n， i-1是 從 i經(jīng) 把 句柄 替 換 成 為 相 應 產(chǎn) 生 式 左 部 符 號 而 得 到的 。 第 五 章 語 法 分 析 自 下 而 上 分 析n 自 下 而 上 分 析 的 基 本 問 題n 算 符 優(yōu) 選 分 析 算 法n LR分 析 法

17、 二 、 算 符 優(yōu) 先 分 析n 四 則 運 算 的 優(yōu) 先 規(guī) 則 ： 先 乘 除 后 加 減 ， 同 級 從 左 到 右n 考 慮 二 義 文 法 文 法 G(E)：G(E)： E i| E+E|E-E|E*E|E/E|(E)n 它 的 句 子 有 幾 種 不 同 的 規(guī) 范 規(guī) 約 。n 歸 約 即 計 算 表 達 式 的 值 。 歸 約 順 序 不 同 ，則 計 算 的 順 序 也 不 同 ， 結 果 也 不 一 樣 。n 如 果 規(guī) 定 算 符 的 優(yōu) 先 次 序 ， 并 按 這 種 規(guī) 定進 行 歸 約 ， 則 歸 約 過 程 是 唯 一 的 。 例 如 ： 句 子 i+i-i*

18、(i+i)E i( )i*EiE E+E EE-i i+E EE G(E)： E i| E+E|E-E|E*E|E/E|(E) E i( )i*EiE E+E EE-i i+ E EE返 回G(E)： E i| E+E|E-E|E*E|E/E|(E) 句 子i+i-i*(i+i)的 歸 約 過 程 是 ：(1) i+i-i*(i+i)(2) E+i-i*(i+i)(3) E+E-i*(i+i)(4) E-i*(i+i)(5) E-E*(i+i)(6) E-E*(E+i)(7) E-E*(E+E)(8) E-E*(E)(9) E-E*E(10) E-E(11) EG(E)： E i| E+E|E

19、-E|E*E|E/E|(E) 句 子i+i-i*(i+i)的 歸 約 過 程 是 ：(1) i+i-i*(i+i)(2) F+i-i*(i+i)(3) T+i-i*(i+i)(4) E+i-i*(i+i)(5) E+F-i*(i+i)(6) E+T-i*(i+i)(7) E-i*(i+i)(8) E-F*(i+i)(9) E-T*(i+i)(10) E-T*(F+i)(11) E-T*(T+i)(12) E-T*(E+i)(13) E-T*(E+F)(14) E-T*(E+T) (15) E-T*(E)(16) E-T*F(17) E-T(18) E無 二 義 文 法 ：G(E)： E T |

20、E+T|E-T T F |T*F|T/F F (E)|i G(E)： E i| E+E|E-E|E*E|E/E|(E) n 起 決 定 作 用 的 是 相 鄰 的 兩 個 算 符 （ 終 結 符 ）之 間 的 優(yōu) 先 關 系 。n 所 謂 算 符 優(yōu) 先 分 析 法 就 是 定 義 算 符 （ 終 結 符 ）之 間 的 某 種 優(yōu) 先 關 系 ， 借 助 于 這 種 關 系 尋 找“可 歸 約 串 ”和 進 行 歸 約 。算 符 優(yōu) 先 分 析 的 基 本 思 想 n 定 義 任 何 兩 個 可 能 相 繼 出 現(xiàn) 的 終 結 符 a與 b的三 種 優(yōu) 先 關 系 a b a的 優(yōu) 先 級 低

21、 于 b a b a的 優(yōu) 先 級 等 于 b a b a的 優(yōu) 先 級 高 于 bn 注 意 ： 與 數(shù) 學 上 的 =不 同 + + （ 先 歸 約 右 邊 的 +） a b并 不 意 味 著 b a， 如 ( + 和 + ( 優(yōu) 先 關 系 算 符 優(yōu) 先 文 法 及 優(yōu) 先 表 構 造n 一 個 文 法 ， 如 果 它 的 任 一 產(chǎn) 生 式 的 右 部 都不 含 兩 個 相 繼 (并 列 )的 非 終 結 符 ， 即 不 含如 下 形 式 的 產(chǎn) 生 式 右 部 ：QR 則 我 們 稱 該 文 法 為 算 符 文 法 。n 約 定 ：a、 b代 表 任 意 終 結 符 ；P、 Q、

22、R代 表 任 意 非 終 結 符 ； 代 表 由 終 結 符 和 非 終 結 符 組 成 的 任 意 序列 ， 包 括 空 字 。 n 假 定 G是 一 個 不 含 -產(chǎn) 生 式 的 算 符 文 法 。對 于 任 何 一 對 終 結 符 a、 b， 我 們 說 ：1. a b， 當 且 僅 當 文 法 G中 含 有 形 如Pab或 PaQb的 產(chǎn) 生 式 ；2. a b， 當 且 僅 當 G中 含 有 形 如 PaR的 產(chǎn) 生 式 ， 而 R b或 R Qb； 3. a b ， 當 且 僅 當 G中 含 有 形 如 PRb的 產(chǎn) 生 式 ， 而 R a或 R aQ。 n 如 果 一 個 算 符

23、 文 法 G中 的 任 何 終 結 符 對 (a，b)至 多 只 滿 足 下 述 三 關 系 之 一 ： a b， a b， a b 則 稱 G是 一 個 算 符 優(yōu) 先 文 法 。 G(E)： E i| E+E|E-E|E*E|E/E|(E)不 是 一 個 算 符 優(yōu) 先 文 法G(E)： E T |E+T|E-T T F |T*F|T/F F (E)|i 是 一 個 算 符 優(yōu) 先 文 法 n 例 :考 慮 下 面 的 文 法 G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | in 由 規(guī) 則 (4)P(E) ， 有 ( )；n

24、 由 規(guī) 則 (1)EE T和 (2)TT*F， 有 *；n 由 (2) TT*F 和 (3) FP F ， 可 得 * ；n 由 (1)EE + T和 E E+T， 可 得 + +；n 由 (3)FPF和 F PF， 可 得 。n 由 (4)P(E)和 EE+TT+TT*F+TF*F+TPF*F+TiF*F+T 有 ( + ( * ( ( i。 n 優(yōu) 先 關 系 表 + * i ( ) # + * i ( ) # n 從 算 符 優(yōu) 先 文 法 G構 造 優(yōu) 先 關 系 表 的 算 法 。n 通 過 檢 查 G的 每 個 產(chǎn) 生 式 的 每 個 候 選 式 ， 可找 出 所 有 滿 足 a

25、 b的 終 結 符 對 。2. a b， 當 且 僅 當 G中 含 有 形 如 PaR的 產(chǎn) 生 式 ， 而 R b或 R Qb； 3. a b ， 當 且 僅 當 G中 含 有 形 如 PRb的 產(chǎn) 生 式 ， 而 R a或 R aQ。 n 確 定 滿 足 關 系 和 的 所 有 終 結 符 對 ：1. a b， 當 且 僅 當 文 法 G中 含 有 形 如Pab或 PaQb的 產(chǎn) 生 式 ； n 從 算 符 優(yōu) 先 文 法 G構 造 優(yōu) 先 關 系 表 的 算 法n 通 過 檢 查 G的 每 個 產(chǎn) 生 式 的 每 個 候 選 式 ， 可找 出 所 有 滿 足 a b的 終 結 符 對 。

26、n 為 確 定 滿 足 關 系 和 的 所 有 終 結 符 對 ：首 先 需 要 對 G的 每 個 非 終 結 符 P構 造 兩 個 集 合FIRSTVT(P)和 LASTVT(P)：a b 當 且 僅 當 G中 含 有 形 如 PaR的 產(chǎn) 生 式 ， 而 R b或 R Qb； n 從 算 符 優(yōu) 先 文 法 G構 造 優(yōu) 先 關 系 表 的 算 法 。n 通 過 檢 查 G的 每 個 產(chǎn) 生 式 的 每 個 候 選 式 ， 可找 出 所 有 滿 足 a b的 終 結 符 對 。n 為 確 定 滿 足 關 系 和 的 所 有 終 結 符 對 ：首 先 需 要 對 G的 每 個 非 終 結 符

27、 P構 造 兩 個 集 合FIRSTVT(P)和 LASTVT(P)： ,|)( NT VQVaaQPaPaPLASTVT 而或 3. a b 當 且 僅 當 G中 含 有 形 如 PRb的 產(chǎn) 生 式 ， 而 R a或 R aQ。 n 從 算 符 優(yōu) 先 文 法 G構 造 優(yōu) 先 關 系 表 的 算 法 。n 通 過 檢 查 G的 每 個 產(chǎn) 生 式 的 每 個 候 選 式 ， 可找 出 所 有 滿 足 a b的 終 結 符 對 。n 確 定 滿 足 關 系 和 的 所 有 終 結 符 對 ：首 先 需 要 對 G的 每 個 非 終 結 符 P構 造 兩 個 集 合FIRSTVT(P)和 L

28、ASTVT(P)： ,|)( NT VQVaaQPaPaPLASTVT 而或 .,|=)( * TVaaaFIRST 比較.,.|)( * TVaAaSaAFOLLOW 比較 q有 了 這 兩 個 集 合 之 后 ， 就 可 以 通 過 檢 查 每個 產(chǎn) 生 式 的 候 選 式 確 定 滿 足 關 系 和 的所 有 終 結 符 對 。假 定 有 個 產(chǎn) 生 式 的 一 個 候 選 形 為aP 那 么 ， 對 任 何 bFIRSTVT(P)， 有 a b。假 定 有 個 產(chǎn) 生 式 的 一 個 候 選 形 為Pb 那 么 ， 對 任 何 aLASTVT(P)， 有 a b。 n 首 先 討 論

29、構 造 集 合 FIRSTVT(P)的 算 法 。n 按 其 定 義 ， 可 用 下 面 兩 條 規(guī) 則 來 構 造 集 合FIRSTVT(P)：1. 若 有 產(chǎn) 生 式 Pa或 PQa， 則aFIRSTVT(P)； （ 直 接 從 產(chǎn) 生 式 看 ）2. 若 aFIRSTVT(Q)， 且 有 產(chǎn) 生 式 PQ，則 aFIRSTVT(P)。構 造 集 合 FIRSTVT(P) 的 算 法將 對 推 導 的 遍 歷 轉(zhuǎn) 換 成 對 產(chǎn) 生 式 的 反 復 遍 歷 n 數(shù) 據(jù) 結 構 ：布 爾 數(shù) 組 FP， a， 使 得 FP， a為 真 的 條 件 是 ，當 且 僅 當 aFIRSTVT(P)

30、。 開 始 時 ， 按 上 述 的規(guī) 則 (1)對 每 個 數(shù) 組 元 素 FP， a賦 初 值 。棧 STACK， 把 所 有 初 值 為 真 的 數(shù) 組 元 素 FP，a的 符 號 對 (P， a)全 都 放 在 STACK之 中 。構 造 集 合 FIRSTVT(P) 的 算 法1. 若 有 產(chǎn) 生 式 Pa或 PQa， 則 aFIRSTVT(P)；（ 直 接 從 產(chǎn) 生 式 看 ）2. 若 aFIRSTVT(Q)， 且 有 產(chǎn) 生 式 PQ， 則aFIRSTVT(P)。 n 運 算 ：如 果 棧 STACK不 空 ， 就 將 頂 項 逐 出 ， 記 此項 為 (Q， a)。 對 于 每

31、 個 形 如PQ 的 產(chǎn) 生 式 ， 若 FP， a為 假 ， 則 變 其 值 為 真且 將 (P， a)推 進 STACK棧 。上 述 過 程 必 須 一 直 重 復 ， 直 至 棧 STACK拆空 為 止 。1. 若 有 產(chǎn) 生 式 Pa或 PQa， 則 aFIRSTVT(P)；（ 直 接 從 產(chǎn) 生 式 看 ）2. 若 aFIRSTVT(Q)， 且 有 產(chǎn) 生 式 PQ， 則aFIRSTVT(P)。構 造 集 合 FIRSTVT(P) 的 算 法 n 程 序 (包 括 一 個 過 程 和 主 程 序 )：PROCEDURE INSERT(P， a)；IF NOT FP， a THENBE

32、GIN FP， a:=TRUE； 把 (P， a)下 推 進 STACK棧 END；構 造 集 合 FIRSTVT(P) 的 算 法1. 若 有 產(chǎn) 生 式 P a或 P Qa， 則 aFIRSTVT(P)； （ 直接 從 產(chǎn) 生 式 看 ）2. 若 aFIRSTVT(Q)， 且 有 產(chǎn) 生 式 P Q， 則aFIRSTVT(P)。 主 程 序 ：BEGIN FOR 每 個 非 終 結 符 P和 終 結 符 a DO FP， a:=FALSE； FOR 每 個 形 如 Pa或 PQa的 產(chǎn) 生 式 DO INSERT(P， a)； WHILE STACK 非 空 DOBEGIN 把 STACK

33、的 頂 項 ， 記 為 (Q， a)， 上 托 出 去 ； FOR 每 條 形 如 PQ的 產(chǎn) 生 式 DOINSERT(P， a)；END OF WHILE；END 1. 若 有 產(chǎn) 生 式 P a或 P Qa， 則 aFIRSTVT(P)；2. 若 aFIRSTVT(Q)， 且 有 產(chǎn) 生 式 P Q， 則 aFIRSTVT(P)。 n 這 個 算 法 的 工 作 結 果 得 到 一 個 二 維 數(shù) 組 F，從 它 可 得 任 何 非 終 結 符 P的 FIRSTVT。FIRSTVT(P) a | FP， a=TRUEn 同 理 ， 可 構 造 計 算 LASTVT的 算 法 。 n 構

34、造 集 合 LASTVT(P)的 算 法 。n 按 其 定 義 ， 可 用 下 面 兩 條 規(guī) 則 來 構 造 集 合LASTVT(P)：1. 若 有 產(chǎn) 生 式 P a或 P aQ， 則 a LASTVT(P)；2. 若 a LASTVT(Q)， 且 有 產(chǎn) 生 式 P Q ，則 a LASTVT(P)。 ,|)( NT VQVaaQPaPaPLASTVT 而或 構 造 集 合 LASTVT(P) 的 算 法 n 例 : 考 慮 下 面 的 文 法 G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i計 算 文 法 G的 FIRS

35、TVT和 LASTVT;1. 若 有 產(chǎn) 生 式 P a或 P Qa， 則 aFIRSTVT(P)； （ 直接 從 產(chǎn) 生 式 看 ）2. 若 aFIRSTVT(Q)， 且 有 產(chǎn) 生 式 P Q， 則aFIRSTVT(P)。1. 若 有 產(chǎn) 生 式 P a或 P aQ， 則 a LASTVT(P)；2. 若 a LASTVT(Q)， 且 有 產(chǎn) 生 式 P Q ， 則 a LASTVT(P)。 + * ( ) i E T F P (,)( (,*,)( (,)( (,*,)( iPFIRSTVT iEFIRSTVT iFFIRSTVT iTFIRSTVT + * ( ) iE T F P )

36、,)( ),*,)( ),)( ),*,)( iPLASTVT iELASTVT iFLASTVT iTLASTVT n 使 用 每 個 非 終 結 符 P的 FIRSTVT(P)和 LASTVT(P)， 就能 夠 構 造 文 法 G的 優(yōu) 先 關 系 表 。 構 造 優(yōu) 先 關 系 表 的 算 法是 ：n 通 過 檢 查 G的 每 個 產(chǎn) 生 式 的 每 個 候 選 式 ， 可 找 出 所 有 滿足 a b的 終 結 符 對 ；n 通 過 檢 查 每 個 產(chǎn) 生 式 的 候 選 式 確 定 滿 足 關 系 和 的所 有 終 結 符 對 ：假 定 有 個 產(chǎn) 生 式 的 一 個 候 選 形 為

37、 aP 那 么 ， 對 任 何 bFIRSTVT(P)， 有 a b。 假 定 有 個 產(chǎn) 生 式 的 一 個 候 選 形 為 Pb 那 么 ， 對 任 何 aLASTVT(P)， 有 a b。構 造 優(yōu) 先 關 系 表 的 算 法 如 果 考 慮 #， 則考 慮 句 型 #S# FOR 每 條 產(chǎn) 生 式 PX1X2Xn DO FOR i:=1 TO n-1 DOBEGIN IF Xi和 Xi+1均 為 終 結 符 THEN 置 Xi Xi+1 IF in-2且 Xi和 Xi+2都 為 終 結 符 但 Xi+1為 非 終 結 符 THEN 置 Xi Xi+2； IF Xi為 終 結 符 而

38、Xi+1為 非 終 結 符 THENFOR FIRSTVT(Xi+1)中 的 每 個 a DO 置 Xi a； IF X i為 非 終 結 符 而 Xi+1為 終 結 符 THEN FOR LASTVT(Xi)中 的 每 個 a DO 置 a Xi+1 END n 例 : 考 慮 下 面 的 文 法 G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i1. 計 算 文 法 G的 FIRSTVT和 LASTVT;2. 構 造 優(yōu) 先 關 系 表 ;3. G是 算 符 優(yōu) 先 文 法 嗎 ? (,)( (,*,)( (,)( (,*,)

39、( iPFIRSTVT iEFIRSTVT iFFIRSTVT iTFIRSTVT ),)( ),*,)( ),)( ),*,)( iPLASTVT iELASTVT iFLASTVT iTLASTVT (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i + * ( ) i+* ()iG結 論 : G是 算 符 優(yōu) 先 文 法 q G的 算 符 優(yōu) 先 關 系 表 第 五 章 語 法 分 析 自 下 而 上 分 析n 自 下 而 上 分 析 的 基 本 問 題n 算 符 優(yōu) 選 分 析 算 法p 計 算 FIRSTVT(P)和 LASTVT(

40、P)集 合p 構 造 算 符 優(yōu) 先 關 系 表n LR分 析 法 n 可 歸 約 串 ， 句 型 ， 短 語 ， 直 接 短 語 ， 句 柄 ，規(guī) 范 歸 約 。n 一 個 文 法 G的 句 型 的 素 短 語 是 指 這 樣 一 個 短語 ， 它 至 少 含 有 一 個 終 結 符 ， 并 且 ， 除 它自 身 之 外 不 再 含 任 何 更 小 的 素 短 語 。n 最 左 素 短 語 是 指 處 于 句 型 最 左 邊 的 那 個 素短 語 。 n 考 慮 下 面 的 文 法 G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) |

41、 i EE F+* TiFTF T P+ET P對 于 句 型 ： T+F*P+i短 語 ：直 接 短 語 ：句 柄 ：素 短 語 ：最 左 素 短 語 ： , T+F*P+iT, F, P , F*P, iT+F*PT, F, P, iTF*P, iF*P n 算 符 優(yōu) 先 文 法 句 型 (括 在 兩 個 之 間 )的 一 般形 式 寫 成 ： #N1a1N2a2NnanNn+1#其 中 ， 每 個 ai都 是 終 結 符 ， Ni是 可 有 可 無 的 非終 結 符 。n 定 理 ： 一 個 算 符 優(yōu) 先 文 法 G的 任 何 句 型 的 最左 素 短 語 是 滿 足 如 下 條 件

42、 的 最 左 子 串 NjajNiaiNi+1， aj-1 aj a j aj+1， ， ai-1 ai ai ai+1 n 使 用 一 個 符 號 棧 S， 用 它 寄 存 終 結 符 和 非 終 結符 ， k代 表 符 號 棧 S的 使 用 深 度 。 k:=1;Sk:=#;REPEAT 把 下 一 個 輸 入 符 號 讀 進a中 ； IF SkVT THEN j:=k ELSE j:=k-1;WHILE Sj a DOBEGIN REPEAT Q:=Sj; IF Sj-1VT THEN j:=j-1 ELSE j:=j-2 UNTIL Sj Q; 把Sj+1Sk歸 約 為 某 個N； k

43、:=j+1; Sk:=N END OF WHILE; IF Sj a OR Sj a THEN BEGIN k:=k+1;Sk:=a END ELSE ERROR /*調(diào) 用 出 錯 診 察 程 序*/ UNTIL a=#自 左 至 右 ， 終 結 符 對 終 結 符 ， 非終 結 符 對 非 終 結 符 ， 而 且 對 應 的終 結 符 相 同 。 N X1 X2 Xk-j Sj+1 Sj+2 Sk n 在 算 法 的 工 作 過 程 中 ， 若 出 現(xiàn) j減 1后 的 值小 于 等 于 0時 ， 則 意 味 著 輸 入 串 有 錯 。 在正 確 的 情 況 下 ， 算 法 工 作 完 畢

44、時 ， 符 號 棧S應 呈 現(xiàn) ： # N #。n 由 于 非 終 結 符 對 歸 約 沒 有 影 響 ， 因 此 ， 非終 結 符 根 本 可 以 不 進 符 號 棧 S。 n 對 于 文 法 的 句 子 來 說 ， 它 的 算 符 優(yōu) 先分 析 的 結 果 (移 進 歸 約 所 得 到 的 分 析樹 )就 是 語 法 樹 。 A.正 確 B.錯 誤 答 案 ： B 自 左 至 右 ， 終 結 符 對 終 結 符 ， 非終 結 符 對 非 終 結 符 ， 而 且 對 應 的終 結 符 相 同 。 N X1 X2 Xk-j Sj+1 Sj+2 Sk n 算 符 優(yōu) 先 分 析 一 般 并 不

45、等 價 于 規(guī) 范 歸 約 。EE +* iT P+iP iP iP EE F+* TiFTF T P+ETiFP iP iP n 考 慮 下 面 的 文 法 G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i的 句 子 i+i*i+i n 算 符 優(yōu) 先 分 析 法 特 點 ：優(yōu) 點 : 簡 單 ， 快 速缺 點 : 可 能 錯 誤 接 受 非 法 句 子 ， 能 力 有 限 .n 算 符 優(yōu) 先 分 析 法 是 一 種 廣 為 應 用 、 行 之有 效 的 方 法 。用 于 分 析 各 類 表 達 式ALGOL 60 n 把

46、每 個 終 結 符 與 兩 個 自 然 數(shù) f()與 g()相 對應 ， 使 得若 1 2， 則 f(1) g(2)f稱 為 入 棧 優(yōu) 先 函 數(shù) ， g稱 為 比 較 優(yōu) 先 函 數(shù) 。n 優(yōu) 點 : 便 于 比 較 ， 節(jié) 省 空 間 ；n 缺 點 : 原 來 不 存 在 優(yōu) 先 關 系 的 兩 個 終 結 符 ， 由 于 自 然 數(shù) 相 對 應 ，變 成 可 以 比 較 的 。 要 進 行 一 些 特 殊 的 判 斷 。 n 文 法 G(E) (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i的 優(yōu) 先 函 數(shù) 如 下 表 + * (

47、 ) i #F 2 4 4 0 6 6 0G 1 3 5 5 0 5 0 對 于 任 何 無 沖 突 優(yōu) 先 關 系 表 都 存 在 優(yōu) 先 函 數(shù) 嗎？ A.是 B.不 是 n 有 許 多 優(yōu) 先 關 系 表 不 存 在 優(yōu) 先 函 數(shù) ， 如 ： 不 存 在 對 應 的 優(yōu) 先 函 數(shù) f和 g 假 定 存 在 f和 g， 則 有 f(a)=g(a)， f(a)g(b)， f(b)=g(a)， f(b)=g(b) 導 致 如 下 矛 盾 : f(a) g(b) = f(b) = g(a) = f(a) 優(yōu) 先 函 數(shù) 如 果 存 在 ， 唯 一 嗎 ？ A.是 B.不 是G如 果 優(yōu) 先

48、函 數(shù) 存 在 ， 則 不 唯 一 (無 窮 多 ) n 如 果 優(yōu) 先 函 數(shù) 存 在 ， 則 可 以 通 過 以 下 三 個 步驟 從 優(yōu) 先 表 構 造 優(yōu) 先 函 數(shù) :1 畫 圖 ： 對 于 每 個 終 結 符 a， 令 其 對 應 兩 個 符 號 fa和 ga， 畫 一 以 所 有 符 號 和 為 結 點 的 方 向 圖 。 如 果a b， 則 從 fa畫 一 條 弧 至 gb， 如 果 a b，則 畫 一 條 弧 從 gb至 fa 。2 數(shù) 數(shù) ： 對 每 個 結 點 都 賦 予 一 個 數(shù) ， 此 數(shù) 等 于 從該 結 點 出 發(fā) 所 能 到 達 的 結 點 (包 括 出 發(fā)

49、點 自 身 )。賦 給 fa的 數(shù) 作 為 f(a)， 賦 給 ga的 數(shù) 作 為 g(a)。3 驗 證 ： 檢 查 所 構 造 出 來 的 函 數(shù) f和 g是 否 與 原 來的 關 系 矛 盾 。 若 沒 有 矛 盾 ， 則 f和 g就 是 要 求 的 優(yōu)先 函 數(shù) ， 若 有 矛 盾 ， 則 不 存 在 優(yōu) 先 函 數(shù) 。 n 例 :取 前 面 文 法 G(E) (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i的 終 結 符 +， *， ， i + * i+*if+ f* f fig + g* g gi + * if 2 4 4 7g

50、1 3 6 6 小 結 ：n算 符 優(yōu) 先 分 析 算 法 最 左 素 短 語n算 符 優(yōu) 先 函 數(shù) 及 其 構 造 方 法 作 業(yè) ：n自 學 P121 典 型 例 題 及 解 答 n作 業(yè) ： p122 ：第 1題 （ 前 3小 問 必 做 ， 第 4小 問 選 擇 其中 一 個 輸 入 串 的 算 符 優(yōu) 先 分 析 過 程 即可 ） ；第 2題第 3題 的 第 (2)小 問第 4題 的 第 （ 2） 小 問 第 五 章 語 法 分 析 自 下 而 上 分 析n 自 下 而 上 分 析 的 基 本 問 題n 算 符 優(yōu) 選 分 析 算 法n LR分 析 法 語 法 分 析 的 方 法

51、：n 自 下 而 上 分 析 法 (Bottom-up)p 基 本 思 想 ： 從 輸 入 串 開 始 ， 逐 步 進 行 “ 歸 約 ” ， 直 到 文 法 的 開 始 符 號 。 即 從 樹 末 端 開 始 ， 構 造 語 法 樹 。p 核 心 問 題 ： 確 定 可 歸 約 串p 算 符 優(yōu) 先 分 析 法 ： 按 照 算 符 的 優(yōu) 先 關 系 和 結 合性 質(zhì) 進 行 語 法 分 析 。 適 合 分 析 表 達 式 。p LR分 析 法 ： 規(guī) 范 歸 約 (句 柄 作 為 可 歸 約 串 )回 顧 n LR分 析 法 ： 1965年 由 Knuth提 出分 析 表 產(chǎn)生 器文 法

52、分 析 表輸 入 輸 出 產(chǎn) 生 分 析 表 LR分 析 器 工 作 LR分 析 總 控 程 序分 析 表 主 要 介 紹1. 總 控 程 序 (LR分 析 器 )的 處 理 思 想2. LR分 析 表 的 構 造 方 法 及 原 理 短 語 、 直 接 短 語 、 句 柄n 定 義 ： 令 G是 一 個 文 法 ， S是 文 法 的 開 始 符號 ， 假 定 是 文 法 G的 一 個 句 型 ， 如 果 有 且 AS * A則 稱 是 句 型 相 對 于 非 終 結 符 A的 短 語 。特 別 是 ， 如 果 有 A,則 稱 是 句 型 相 對于 規(guī) 則 A 的 直 接 短 語 。 一 個

53、句 型 的 最 左直 接 短 語 稱 為 該 句 型 的 句 柄 。 n 在 一 個 句 型 對 應 的 語 法樹 中p 以 某 非 終 結 符 為 根 的 兩 代 以上 的 子 樹 的 所 有 末 端 結 點 從左 到 右 排 列 就 是 相 對 于 該 非終 結 符 的 一 個 短 語p 如 果 子 樹 只 有 兩 代 ， 則 該 短語 就 是 直 接 短 語 。E FF T TTi1 +* E Fi3i2 n 定 義 ： 假 定 是 文 法 G的 一 個 句 子 ， 我 們稱 序 列 n， n-1， ， 0 是 的 一 個 規(guī) 范 歸 約 ， 如 果 此 序 列 滿 足 ： 1 n= 2

54、 0為 文 法 的 開 始 符 號 ， 即 0=S 3 對 任 何 i， 0 i n， i-1是 從 i經(jīng) 把 句柄 替 換 成 為 相 應 產(chǎn) 生 式 左 部 符 號 而 得 到的 。規(guī) 范 歸 約 n規(guī) 范 歸 約 的 關 鍵 問 題 是 尋 找句 柄 .“歷 史 ” ： 已 移 入 符 號 棧 的 內(nèi)容“ 展 望 ” ： 根 據(jù) 產(chǎn) 生 式 推 測 未來 可 能 遇 到 的 輸 入 符 號“ 現(xiàn) 實 ” ： 當 前 的 輸 入 符 號 Xn 輸 入 串 X2 a # X1 # n LR分 析 方 法 ： 把 歷 史 及 展 望 綜 合 抽 象成 狀 態(tài) ； 由 棧 頂 的 狀 態(tài) 和 現(xiàn)

55、 行 的 輸 入 符 號唯 一 確 定 每 一 步 工 作 LR分 析程 序狀 態(tài) 符 號Sm Xm S1 X1S 0 #分 析 棧 action goto LR分 析 表 a1a2ai an# 輸 入 串 輸 出 n LR分 析 器 的 核 心 是 一 張 分 析 表 ：ACTIONs， a： 當 狀 態(tài) s面 臨 輸 入 符 號 a時 ，應 采 取 什 么 動 作 .GOTOs， X： 狀 態(tài) s面 對 文 法 符 號 X時 ， 下一 狀 態(tài) 是 什 么 移 進 (shift) 把 (s， a)的 下 一 狀態(tài) s和 輸 入 符 號 a推 進 棧 ， 下一 輸 入 符 號 變 成 現(xiàn) 行

56、輸 入 符 號 . 歸 約 (reduce)指 用 某 產(chǎn) 生 式 A進行 歸 約 . 假 若 的 長 度 為 r， 歸 約 動 作是 ， 去 除 棧 頂 r個 項 ， 使 狀 態(tài) sm-r變成 棧 頂 狀 態(tài) ， 然 后 把 (sm-r, A)的 下 一狀 態(tài) s=GOTOsm-r, A和 文 法 符 號 A推 進 棧 . 接 受 (acc)宣 布 分 析 成 功 ，停 止 分 析 器 工 作 . 報 錯 n 分 析 開 始 時 :狀 態(tài) 已 歸 約 串 輸 入 串 (s0， #， a1a2 an #)n 以 后 每 步 的 結 果 可 以 表 示 為 :(s0 s1 sm ， # X1 X

57、m ， aiai+1 an #) (s0 s1 sm ， # X1 Xm ， aiai+1 an #)n分 析 器 根 據(jù) ACTION(sm , ai)確 定 下 一 步 動 作1. 若 ACTION(sm , ai)為 移 進 ， 且 s=GOTO(sm, ai),，則 三 元 式 格 局 變 為 : (s0 s1 sms ， # X1 Xm ai， ai+1 an #)2. 若 ACTION(sm , ai)為 按 A歸 約 ， 三 元 式 變 為 : (s0 s1 sm-rs ， # X1 Xm-rA ， aiai+1 an #)此 處 , s=GOTO(sm-r, A), r為 的

58、長 度 , = Xm-r+1 Xm3. 若 ACTION(sm , ai)為 接 受 ， 則 三 元 式 不 再 變 化 ，變 化 過 程 終 止 ， 宣 布 分 析 成 功 .4. 若 ACTION(s m , ai)為 報 錯 ， 則 三 元 式 變 化 過 程 終止 ， 報 告 錯 誤 . (s0 s1 sm-r sm-r+1 sm ， # X1 Xm-r Xm-r+1 Xm ， aiai+1 an #)(s0 s1 sm-r ， # X1 Xm-r， aiai+1 an #)(s0 s1 sm-rs ， # X1 Xm-rA ， aiai+1 an #) LR分 析 器 示 例 ：文

59、法 G(E)： (1) EE T(2) ET(3) TT*F(4) TF(5) F(E)(6) Fi ACTION GOTO狀 態(tài) i + * ( ) # E T F0 s5 s4 1 2 31 s6 acc2 r2 s7 r2 r2 3 r4 r4 r4 r44 s5 s4 8 2 35 r6 r6 r6 r66 s5 s4 9 37 s5 s4 10 8 s6 s119 r1 s7 r1 r110 r3 r3 r3 r311 r5 r5 r5 r5 其 LR分 析 表 為 : n 假 定 輸 入 串 為 i*i+i， LR分 析 器 的 工 作 過 程 :步 驟 狀 態(tài) 符 號 輸 入 串

60、(1) 0 # i*i+i#(2) 05 #i *i+i# 0 # *i+i#(3) 03 #F *i+i# 0 # *i+i# (4) 02 #T *i+i#(5) 027 #T* i+i# TiF * G(E)： (1) EE T(2) ET(3) TT*F(4) TF(5) F(E)(6) Fi n 假 定 輸 入 串 為 i*i+i， LR分 析 器 的 工 作 過 程 :步 驟 狀 態(tài) 符 號 輸 入 串(5) 027 #T* i+i#(6) 0275 #T*i +i# 027 #T* +i#(7) 02710 #T*F +i# 0 # +i#(8) 02 #T +i# iT F*T

61、Fi G(E)： (1) EE T(2) ET(3) TT*F(4) TF(5) F(E)(6) Fi n 假 定 輸 入 串 為 i*i+i， LR分 析 器 的 工 作 過 程 :步 驟 狀 態(tài) 符 號 輸 入 串(8) 02 #T +i# 0 # +i#(9) 01 #E +i#(10) 016 #E+ i#(11) 0165 #E+i # +iT F*TFi E i G(E)： (1) EE T(2) ET(3) TT*F(4) TF(5) F(E)(6) Fi 步 驟 狀 態(tài) 符 號 輸 入 串(11) 0165 #E+i # 016 #E+ #(12) 0163 #E+F # 01

62、6 #E+ #(13) 0169 #E+T # +iT F*TFi E iTF G(E)： (1) EE T(2) ET(3) TT*F(4) TF(5) F(E)(6) Fi 步 驟 狀 態(tài) 符 號 輸 入 串(13) 0169 #E+T # 0 # #(14) 01 #E #(15) 接 受 +iT F*TFi E iTFE G(E)： (1) EE T n 定 義 ： 對 于 一 個 文 法 ， 如 果 能 夠 構 造 一 張分 析 表 ， 使 得 它 的 每 個 入 口 均 是 唯 一 確 定的 ， 則 這 個 文 法 就 稱 為 LR文 法 。n 定 義 ： 一 個 文 法 ， 如

63、果 能 用 一 個 每 步 頂 多向 前 檢 查 k個 輸 入 符 號 的 LR分 析 器 進 行 分析 ， 則 這 個 文 法 就 稱 為 LR(k)文 法 .LR文 法 nLR文 法 不 是 二 義 的 ， 二 義 文 法 肯 定 不 會 是 LR的 。n非 LR結 構 S iCtS | iCtSeS 棧 輸 入 iCtS e#LR文 法 與 二 義 文 法 nLR分 析 器 的 工 作 原 理nLR分 析 器 的 性 質(zhì)p 棧 內(nèi) 的 符 號 串 和 掃 描 剩 下 的 輸 入 串 構 成 了一 個 規(guī) 范 句 型 ；p 一 旦 棧 的 頂 部 出 現(xiàn) 可 歸 約 串 (句 柄 )， 則

64、 進 行歸 約 ；小 結 第 五 章 語 法 分 析 自 下 而 上 分 析n 自 下 而 上 分 析 的 基 本 問 題n 算 符 優(yōu) 選 分 析 算 法n LR分 析 法 LR分 析 器 的 工 作 原 理 LR(0)項 目 集 規(guī) 范 族 的 構 造 回 顧n 假 定 是 文 法 G的 一 個 句 子 ， 我 們 稱 序 列 n， n-1， ， 0 是 的 一 個 規(guī) 范 歸 約 ， 如 果 此 序 列 滿 足 ： 1 n= 2 0為 文 法 的 開 始 符 號 ， 即 0=S 3 對 任 何 i， 0 i n， i-1是 從 i經(jīng) 把 句 柄 替換 成 為 相 應 產(chǎn) 生 式 左 部

65、符 號 而 得 到 的 。 回 顧n 規(guī) 范 歸 約 過 程 中棧 內(nèi) 的 符 號 串 和 掃 描 剩 下 的 輸 入 符 號 串 構 成 了一 個 規(guī) 范 句 型規(guī) 范 歸 約 過 程 中 ， 下 面 哪 種 格 局 不 會 出 現(xiàn) ？棧 內(nèi) 的 如 果 出 現(xiàn) 句 柄 ， 句 柄 一 定 在 棧 的 頂 部X a 句 柄 句 柄 柄句 a 柄句 a 棧內(nèi)永遠不會出現(xiàn)句柄之后的符號！ 字 的 前 綴 、 活 前 綴n 字 的 前 綴 ： 是 指 字 的 任 意 首 部 ， 如 字 abc的前 綴 有 ， a， ab， abcn 活 前 綴 ： 是 指 規(guī) 范 句 型 的 一 個 前 綴 ，

66、這 種 前綴 不 含 句 柄 之 后 的 任 何 符 號 。 即 ， 對 于 規(guī) 范句 型 ， 為 句 柄 ， 如 果 =u1u2ur， 則符 號 串 u1u2ui(1ir)是 的 活 前 綴 。 (必 為 終 結 符 串 )。n 規(guī) 范 歸 約 過 程 中 ， 保 證 分 析 棧 中 總 是 活 前 綴 ，就 說 明 分 析 采 取 的 移 進 /歸 約 動 作 是 正 確 的 指 導 思 想 目 標 驅(qū) 動n 踢 足 球“ 如 果 你 不 知 道 怎 樣 踢 球 ，就 往 球 門 方 向 踢 ” 施 拉 普 納n LR分 析“ 如 果 你 不 知 道 怎 樣 分 析 ，就 保 證 棧 中 總 是 活 前 綴 ”1. 哪 些 字 符 串 是 活 前 綴 ?2. 能 不 能 構 造 一 個 DFA來 識 別活 前 綴 ?回 答 ： 對 于 一 個 文 法 G， 可 以構 造 一 個 DFA， 它 能 識 別 G的 所 有 活 前 綴 。 n 文 法 G的 每 個 產(chǎn) 生 式 的 右 部 添 加 一 個 圓 點稱 為 G的 LR(0)項 目n 如 :AXYZ有 四 個 項 目 ：A.XY