語法分析自下而上分析

《語法分析自下而上分析》由會(huì)員分享，可在線閱讀，更多相關(guān)《語法分析自下而上分析（108頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 第 五 章 語 法 分 析 自 下 而 上 分 析n 自 上 而 下 分 析 法 (Top-down)n 自 下 而 上 分 析 法 (Bottom-up) 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n語 法 分 析 的 方 法 ：自 下 而 上 分 析 法 (Bottom-up) 基 本 思 想 ： 從 輸 入 串 開 始 ， 逐 步 進(jìn) 行 “ 歸 約 ” ，直 到 文 法 的 開 始 符 號(hào) 。 即 從 樹 末 端 開 始 ， 構(gòu) 造 語法 樹 。 所 謂 歸 約 ， 是 指 根 據(jù) 文 法 的 產(chǎn) 生 式 規(guī) 則

2、 ，把 產(chǎn) 生 式 的 右 部 替 換 成 左 部 符 號(hào) 。 算 符 優(yōu) 先 分 析 法 ： 按 照 算 符 的 優(yōu) 先 關(guān) 系 和 結(jié) 合性 質(zhì) 進(jìn) 行 語 法 分 析 。 適 合 分 析 表 達(dá) 式 。 LR分 析 法 ： 規(guī) 范 歸 約 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 5.1.1 歸 約n 采 用 “ 移 進(jìn) 歸 約 ” 思 想 進(jìn) 行 自 下 而 上 分 析 。n 基 本 思 想 ： 用 一 個(gè) 寄 存 符 號(hào) 的 先 進(jìn) 后 出 棧 ，把 輸 入 符 號(hào) 一 個(gè) 一 個(gè) 地 移 進(jìn) 到 棧 里 ， 當(dāng) 棧 頂形 成 某 個(gè) 產(chǎn) 生 式 的 候 選 式 時(shí)

3、， 即 把 棧 頂 的 這一 部 分 替 換 成 (歸 約 為 )該 產(chǎn) 生 式 的 左 部 符 號(hào) 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 步 驟 : 1 2 3 4 5 6 7 8 9 10動(dòng) 作 : 進(jìn) a 進(jìn) b 歸 (2) 進(jìn) b 歸 (3) 進(jìn) c 進(jìn) d 歸 (4) 進(jìn) 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 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室b dba c eSA BA分 析 樹 和 語 法 樹 不 一 定 一 致 。自 下 而 上 分 析 過 程 ： 邊

4、輸 入 單 詞 符 號(hào) ， 邊歸 約 。核 心 問 題 ： 識(shí) 別 可 歸 約 串 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 5.1.2 規(guī) 范 歸 約n 定 義 ： 令 G是 一 個(gè) 文 法 ， S是 文 法 的 開 始 符號(hào) ， 假 定 是 文 法 G的 一 個(gè) 句 型 ， 如 果 有 且 AS * A則 稱 是 句 型 相 對(duì) 于 非 終 結(jié) 符 A的 短 語 。特 別 是 ， 如 果 有 A,則 稱 是 句 型 相 對(duì)于 規(guī) 則 A 的 直 接 短 語 。 一 個(gè) 句 型 的 最 左直 接 短 語 稱 為 該 句 型 的 句 柄 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī)

5、系 602教 研 室 n 在 一 個(gè) 句 型 對(duì) 應(yīng) 的語 法 樹 中 ， 以 某 非終 結(jié) 符 為 根 的 兩 代以 上 的 子 樹 的 所 有末 端 結(jié) 點(diǎn) 從 左 到 右排 列 就 是 相 對(duì) 于 該非 終 結(jié) 符 的 一 個(gè) 短語 ， 如 果 子 樹 只 有兩 代 ， 則 該 短 語 就是 直 接 短 語 。E FF T TTi1 +* E Fi3i2 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 定 義 ： 假 定 是 文 法 G的 一 個(gè) 句 子 ， 我 們稱 序 列 n， n-1， ， 0 是 的 一 個(gè) 規(guī) 范 歸 約 ， 如 果 此 序 列 滿 足 ： 1 n

6、= 2 0為 文 法 的 開 始 符 號(hào) ， 即 0=S 3 對(duì) 任 何 i， 0 i n， i-1是 從 i經(jīng) 把 句 柄 替 換 成 為 相 應(yīng) 產(chǎn) 生 式 左 部 符 號(hào)而 得 到 的 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 把 上 例 倒 過 來 寫 ， 則 得 到 ：S aAcBe aAcde aAbcde abbcde 顯 然 這 是 一 個(gè) 最 右 推 導(dǎo) 。規(guī) 范 歸 約 是 關(guān) 于 是 一 個(gè) 最 右 推 導(dǎo) 的 逆 過 程最 左 歸 約 規(guī) 范 推 導(dǎo)由 規(guī) 范 推 導(dǎo) 推 出 的 句 型 稱 為 規(guī) 范 句 型 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī)

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

8、 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 起 決 定 作 用 的 是 相 鄰 的 兩 個(gè) 算 符 之 間 的 優(yōu)先 關(guān) 系 。n 所 謂 算 符 優(yōu) 先 分 析 法 就 是 定 義 算 符 之 間 的某 種 優(yōu) 先 關(guān) 系 ， 借 助 于 這 種 關(guān) 系 尋 找 “ 可歸 約 串 ” 和 進(jìn) 行 歸 約 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 首 先 必 須 定 義 任 何 兩 個(gè) 可 能 相 繼 出 現(xiàn) 的 終結(jié) 符 a與 b的 優(yōu) 先 關(guān) 系 三 種 關(guān) 系a b a的 優(yōu) 先 級(jí) 低 于 ba b a的 優(yōu) 先 級(jí) 等 于 ba b a的 優(yōu) 先 級(jí)

9、高 于 bn 注 意 ： 與 數(shù) 學(xué) 上 的 =不 同 ， a b并 不 意味 著 b a 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 5.2.1 算 符 優(yōu) 先 文 法 及 優(yōu) 先 表 構(gòu) 造n 一 個(gè) 文 法 ， 如 果 它 的 任 一 產(chǎn) 生 式 的 右 部 都不 含 兩 個(gè) 相 繼 (并 列 )的 非 終 結(jié) 符 ， 即 不 含如 下 形 式 的 產(chǎn) 生 式 右 部 ：QR 則 我 們 稱 該 文 法 為 算 符 文 法 。n 約 定 ：a、 b代 表 任 意 終 結(jié) 符 ；P、 Q、 R代 表 任 意 非 終 結(jié) 符 ； 代 表 由 終 結(jié) 符 和 非 終 結(jié) 符 組

10、成 的 任 意 序列 ， 包 括 空 字 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 假 定 G是 一 個(gè) 不 含 -產(chǎn) 生 式 的 算 符 文 法 。對(duì) 于 任 何 一 對(duì) 終 結(jié) 符 a、 b， 我 們 說 ：1. a b 當(dāng) 且 僅 當(dāng) 文 法 G中 含 有 形 如Pab或 PaQb的 產(chǎn) 生 式 ；n 如 果 一 個(gè) 算 符 文 法 G中 的 任 何 終 結(jié) 符 對(duì) (a，b)至 多 只 滿 足 下 述 三 關(guān) 系 之 一 ：a b， a b， a b 則 稱 G是 一 個(gè) 算 符 優(yōu) 先 文 法 。2. a b 當(dāng) 且 僅 當(dāng) G中 含 有 形 如 PaR的 產(chǎn)

11、 生 式 ， 而 R b或 R Qb； 3. a b 當(dāng) 且 僅 當(dāng) G中 含 有 形 如 PRb的 產(chǎn) 生 式 ， 而 R a或 R aQ。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 優(yōu) 先 關(guān) 系 表 + * i ( ) # + * i ( ) # 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 從 算 符 優(yōu) 先 文 法 G構(gòu) 造 優(yōu) 先 關(guān) 系 表 的 算 法 。n 通 過 檢 查 G的 每 個(gè) 產(chǎn) 生 式 的 每 個(gè) 候 選 式 ， 可找 出 所 有 滿 足 a b的 終 結(jié) 符 對(duì) 。n 確 定 滿 足 關(guān) 系 和 的 所 有 終 結(jié) 符 對(duì) ：首

12、 先 需 要 對(duì) G的 每 個(gè) 非 終 結(jié) 符 P構(gòu) 造 兩 個(gè) 集 合FIRSTVT(P)和 LASTVT(P)：FIRSTVT P a P a P Qa a V Q V T N( ) | , , 或 而 ,|)( NT VQVaaQPaPaPLASTVT 而或 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 q有 了 這 兩 個(gè) 集 合 之 后 ， 就 可 以 通 過 檢 查 每個(gè) 產(chǎn) 生 式 的 候 選 式 確 定 滿 足 關(guān) 系 和 的所 有 終 結(jié) 符 對(duì) 。假 定 有 個(gè) 產(chǎn) 生 式 的 一 個(gè) 候 選 形 為aP 那 么 ， 對(duì) 任 何 bFIRSTVT(P)， 有 a

13、 b。假 定 有 個(gè) 產(chǎn) 生 式 的 一 個(gè) 候 選 形 為Pb 那 么 ， 對(duì) 任 何 aLASTVT(P)， 有 a b。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 首 先 討 論 構(gòu) 造 集 合 FIRSTVT(P)的 算 法 。 按其 定 義 ， 可 用 下 面 兩 條 規(guī) 則 來 構(gòu) 造 集 合FIRSTVT(P)：1. 若 有 產(chǎn) 生 式 Pa或 PQa， 則aFIRSTVT(P)；2. 若 aFIRSTVT(Q)， 且 有 產(chǎn) 生 式 PQ，則 aFIRSTVT(P)。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 數(shù) 據(jù) 結(jié) 構(gòu) ：布 爾 數(shù)

14、 組 FP， a， 使 得 FP， a為 真 的 條 件 是 ，當(dāng) 且 僅 當(dāng) aFIRSTVT(P)。 開 始 時(shí) ， 按 上 述 的規(guī) 則 (1)對(duì) 每 個(gè) 數(shù) 組 元 素 FP， a賦 初 值 。棧 STACK， 把 所 有 初 值 為 真 的 數(shù) 組 元 素 FP，a的 符 號(hào) 對(duì) (P， a)全 都 放 在 STACK之 中 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 運(yùn) 算 ：如 果 棧 STACK不 空 ， 就 將 頂 項(xiàng) 逐 出 ， 記 此項(xiàng) 為 (Q， a)。 對(duì) 于 每 個(gè) 形 如PQ 的 產(chǎn) 生 式 ， 若 FP， a為 假 ， 則 變 其 值 為

15、真且 將 (P， a)推 進(jìn) STACK棧 。上 述 過 程 必 須 一 直 重 復(fù) ， 直 至 棧 STACK拆空 為 止 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 如 果 把 這 個(gè) 算 法 稍 為 形 式 化 一 點(diǎn) ， 我 們可 得 如 下 所 示 的 一 個(gè) 程 序 (包 括 一 個(gè) 過 程和 主 程 序 )：PROCEDURE INSERT(P， a)；IF NOT FP， a THENBEGIN FP， a:=TRUE； 把 (P， a)下 推 進(jìn) STACK棧 END； 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 主 程 序 ：BEGIN

16、FOR 每 個(gè) 非 終 結(jié) 符 P和 終 結(jié) 符 a DO FP， a:=FALSE； FOR 每 個(gè) 形 如 Pa或 PQa的 產(chǎn) 生 式 DO INSERT(P， a)； WHILE STACK 非 空 DOBEGIN 把 STACK的 頂 項(xiàng) ， 記 為 (Q， a)， 上 托 出 去 ； FOR 每 條 形 如 PQ的 產(chǎn) 生 式 DOINSERT(P， a)；END OF WHILE；END 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 這 個(gè) 算 法 的 工 作 結(jié) 果 得 到 一 個(gè) 二 維 數(shù) 組 F，從 它 可 得 任 何 非 終 結(jié) 符 P的 FIRSTVT

17、。FIRSTVT(P) a | FP， a=TRUEn 同 理 ， 可 構(gòu) 造 計(jì) 算 LASTVT的 算 法 。n 使 用 每 個(gè) 非 終 結(jié) 符 P的 FIRSTVT(P)和LASTVT(P)， 就 能 夠 構(gòu) 造 文 法 G的 優(yōu) 先表 。 構(gòu) 造 優(yōu) 先 表 的 算 法 是 ： 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 FOR 每 條 產(chǎn) 生 式 PX1X2Xn DO FOR i:=1 TO n-1 DOBEGIN IF Xi和 Xi+1均 為 終 結(jié) 符 THEN 置 Xi Xi+1 IF in-2且 Xi和 Xi+2都 為 終 結(jié) 符 但 Xi+1為 非 終 結(jié) 符

18、 THEN 置 Xi Xi+2； IF Xi為 終 結(jié) 符 而 Xi+1為 非 終 結(jié) 符 THENFOR FIRSTVT(Xi+1)中 的 每 個(gè) a DO 置 Xi a； IF X i為 非 終 結(jié) 符 而 Xi+1為 終 結(jié) 符 THEN FOR LASTVT(Xi)中 的 每 個(gè) a DO 置 a Xi+1 END 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 例 : 考 慮 下 面 的 文 法 G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i1. 計(jì) 算 文 法 G的 FIRSTVT和 LASTVT;2

19、. 構(gòu) 造 優(yōu) 先 關(guān) 系 表 ;3. G是 算 符 優(yōu) 先 文 法 嗎 ? 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 + * ( ) i E T F P (,)( (,*,)( (,)( (,*,)( iPFIRSTVT iEFIRSTVT iFFIRSTVT iTFIRSTVT + * ( ) iE T F P ),)( ),*,)( ),)( ),*,)( iPLASTVT iELASTVT iFLASTVT iTLASTVT 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 + * ( ) i+*( )iG結(jié) 論 : G是 算 符 優(yōu) 先 文 法 q G的 算

20、符 優(yōu) 先 關(guān) 系 表 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 5.2.2 算 符 優(yōu) 先 分 析 算 法n 可 歸 約 串 ， 句 型 ， 短 語 ， 直 接 短 語 ， 句 柄 ，規(guī) 范 歸 約 。n 一 個(gè) 文 法 G的 句 型 的 素 短 語 是 指 這 樣 一 個(gè) 短語 ， 它 至 少 含 有 一 個(gè) 終 結(jié) 符 ， 并 且 ， 除 它自 身 之 外 不 再 含 任 何 更 小 的 素 短 語 。n 最 左 素 短 語 是 指 處 于 句 型 最 左 邊 的 那 個(gè) 素短 語 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 考 慮 下 面 的 文

21、法 G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i EE F+* TiFTF T P+ET P句 型 ： T+F*P+i短 語 ： T+F*P+i, T, F， P, F*P, i, T+F*P直 接 短 語 ： T, F, P, i句 柄 ： T素 短 語 ： F*P, i最 左 素 短 語 ： F*P 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 算 符 優(yōu) 先 文 法 句 型 (括 在 兩 個(gè) 之 間 )的 一 般形 式 寫 成 ： #N1a1N2a2NnanNn+1#其 中 ， 每 個(gè) ai都 是 終

22、結(jié) 符 ， Ni是 可 有 可 無 的 非終 結(jié) 符 。n 定 理 ： 一 個(gè) 算 符 優(yōu) 先 文 法 G的 任 何 句 型 的 最左 素 短 語 是 滿 足 如 下 條 件 的 最 左 子 串 NjajNiaiNi+1， aj-1 aj aj aj+1， ， ai-1 ai a i ai+1 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 算 符 優(yōu) 先 分 析 算 法n 使 用 一 個(gè) 符 號(hào) 棧 S， 用 它 寄 存 終 結(jié) 符 和 非 終結(jié) 符 ， k代 表 符 號(hào) 棧 S的 使 用 深 度 。1 k:=1; Sk:=#;2 REPEAT3 把 下 一 個(gè) 輸 入 符 號(hào)

23、 讀 進(jìn) a中 ；4 IF SkVT THEN j:=k ELSE j:=k-1;5 WHILE Sj a DO6 BEGIN7 REPEAT8 Q:=Sj;9 IF Sj-1V T THEN j:=j-1 ELSE j:=j-210 UNTIL Sj Q; 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 11 把 Sj+1Sk歸 約 為 某 個(gè) N；12 k:=j+1;13 Sk:=N14 END OF WHILE;15 IF Sj a OR Sj a THEN16 BEGIN k:=k+1;Sk:=a END17 ELSE ERROR /*調(diào) 用 出 錯(cuò) 診 察 程 序 */18

24、 UNTIL a=# 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 在 算 法 的 工 作 過 程 中 ， 若 出 現(xiàn) j減 1后 的 值小 于 等 于 0時(shí) ， 則 意 味 著 輸 入 串 有 錯(cuò) 。 在正 確 的 情 況 下 ， 算 法 工 作 完 畢 時(shí) ， 符 號(hào) 棧S應(yīng) 呈 現(xiàn) ： # N #。n 算 法 的 第 11行 中 的 N是 指 那 樣 一 個(gè) 產(chǎn) 生 式的 左 部 符 號(hào) ， 此 產(chǎn) 生 式 的 右 部 和Sj+1Sk 構(gòu) 成 如 下 一 一 對(duì) 應(yīng) 關(guān) 系 ： 自左 至 右 ， 終 結(jié) 符 對(duì) 終 結(jié) 符 ， 非 終 結(jié) 符 對(duì) 非終 結(jié) 符 ， 而 且

25、 對(duì) 應(yīng) 的 終 結(jié) 符 相 同 。 由 于 非終 結(jié) 符 對(duì) 歸 約 沒 有 影 響 ， 因 此 ， 非 終 結(jié) 符根 本 可 以 不 進(jìn) 符 號(hào) 棧 S。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 算 符 優(yōu) 先 分 析 一 般 并 不 等 價(jià) 于 規(guī) 范 歸 約 。EE +* iT P+iP iP iP EE F+* TiFTF T P+ETiFP iP iP 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 算 符 優(yōu) 先 分 析 法 特 點(diǎn) ：優(yōu) 點(diǎn) : 簡 單 ， 快 速缺 點(diǎn) : 可 能 錯(cuò) 誤 接 受 非 法 句 子 ， 能 力 有 限 .n 算

26、 符 優(yōu) 先 分 析 法 是 一 種 廣 為 應(yīng) 用 、 行 之有 效 的 方 法 。用 于 分 析 各 類 表 達(dá) 式ALGOL 60 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 5.2.3 優(yōu) 先 函 數(shù)n 把 每 個(gè) 終 結(jié) 符 與 兩 個(gè) 自 然 數(shù) f()與 g()相 對(duì)應(yīng) ， 使 得若 1 2， 則 f(1) g(2)f稱 為 入 棧 優(yōu) 先 函 數(shù) ， g稱 為 比 較 優(yōu) 先 函 數(shù) 。n 優(yōu) 點(diǎn) :便 于 比 較 ， 節(jié) 省 空 間 ；n 缺 點(diǎn) :原 來 不 存 在 優(yōu) 先 關(guān) 系 的 兩 個(gè) 終 結(jié) 符 ， 由于 自 然 數(shù) 相 對(duì) 應(yīng) ， 變 成 可 以

27、比 較 的 。 要 進(jìn) 行一 些 特 殊 的 判 斷 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 文 法 G(E) (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i的 優(yōu) 先 函 數(shù) 如 下 表 + * ( ) i #F 2 4 4 0 6 6 0G 1 3 5 5 0 5 0 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 有 許 多 優(yōu) 先 關(guān) 系 表 不 存 在 優(yōu) 先 函 數(shù) ， 如 ：a bab 不 存 在 對(duì) 應(yīng) 的 優(yōu) 先 函 數(shù) f和 g 假 定 存 在 f和 g， 則 有 f(a)=g(

28、a)， f(a)g(b)， f(b)=g(a)， f(b)=g(b) 導(dǎo) 致 如 下 矛 盾 : f(a) g(b) = f(b) = g(a) = f(a)G如 果 優(yōu) 先 函 數(shù) 存 在 ， 則 不 唯 一 (無 窮 多 ) 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 如 果 優(yōu) 先 函 數(shù) 存 在 ， 則 可 以 通 過 以 下 三 個(gè) 步驟 從 優(yōu) 先 表 構(gòu) 造 優(yōu) 先 函 數(shù) :1 對(duì) 于 每 個(gè) 終 結(jié) 符 a， 令 其 對(duì) 應(yīng) 兩 個(gè) 符 號(hào) fa和 ga，畫 一 以 所 有 符 號(hào) 和 為 結(jié) 點(diǎn) 的 方 向 圖 。 如 果 a b，則 從 fa畫 一 條

29、弧 至 gb， 如 果 a b， 則 畫 一 條 弧從 gb至 fa 。2 對(duì) 每 個(gè) 結(jié) 點(diǎn) 都 賦 予 一 個(gè) 數(shù) ， 此 數(shù) 等 于 從 該 結(jié) 點(diǎn)出 發(fā) 所 能 到 達(dá) 的 結(jié) 點(diǎn) (包 括 出 發(fā) 點(diǎn) 自 身 )。 賦 給 fa的 數(shù) 作 為 f(a)， 賦 給 ga的 數(shù) 作 為 g(a)。3 檢 查 所 構(gòu) 造 出 來 的 函 數(shù) f和 g是 否 與 原 來 的 關(guān) 系矛 盾 。 若 沒 有 矛 盾 ， 則 f和 g就 是 要 求 的 優(yōu) 先 函 數(shù) ，若 有 矛 盾 ， 則 不 存 在 優(yōu) 先 函 數(shù) 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 現(xiàn) 在 必

30、 須 證 明 ： 若 a b， 則 f(a) g(b)；若 a b， 則 f(a) g(b)。n 第 一 個(gè) 關(guān) 系 可 從 函 數(shù) 的 構(gòu) 造 直 接 獲 得 。 因?yàn)?， 若 a b， 則 既 有 從 fa到 gb的 弧 ， 又 有從 gb到 fa的 弧 。 所 以 ， fa和 gb所 能 到 達(dá) 的 結(jié)是 全 同 的 。n 至 于 a b和 a b的 情 形 ， 只 須 證 明 其 一 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 如 果 a b， 則 有 從 fa到 gb的 弧 。 也 就 是 ，gb能 到 達(dá) 的 任 何 結(jié) fa也 能 到 達(dá) 。 因 此 ，f(

31、a) g(b)。我 們 所 需 證 明 的 是 ， 在 這 種 情 況 下 ， f(a)g(b)不 應(yīng) 成 立 。我 們 將 指 出 ， 如 果 f(a) g(b)， 則 根 本 不 存在 優(yōu) 先 函 數(shù) 。 假 若 f(a) g(b)， 那 么 必 有 如下 的 回 路 ： 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 因 此 有a b, a1 b, a1 b1, , am bm, a bm對(duì) 任 何 優(yōu) 先 函 數(shù) f和 g來 說 ， 必 定 有f(a) g(b) f(a1) g(b1) f(am) g(bm) f(a)從 而 導(dǎo) 致 f(a) f(a)， 產(chǎn) 生 矛 盾 。

32、因 此 ， 不 存 在優(yōu) 先 函 數(shù) f和 g。 fa1fa famgb1gb gbm 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 例 :取 前 面 文 法 G(E) (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i的 終 結(jié) 符 +， *， ， i 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 + * i+*if+ f* f fig + g* g gi + * if 2 4 4 7g 1 3 6 6 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 5.3 LR分 析 法n LR分 析 法 ： 196

33、5年 由 Knuth提 出分 析 表 產(chǎn)生 器文 法 分 析 表輸 入 輸 出 產(chǎn) 生 分 析 表 LR分 析 器 工 作 LR分 析 總 控 程 序分 析 表 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 主 要 介 紹1. 總 控 程 序 (LR分 析 器 )的 處 理 思 想2. LR分 析 表 的 構(gòu) 造 方 法 及 原 理 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 5.3.1 LR分 析 器n規(guī) 范 歸 約 的 關(guān) 鍵 問 題 是 尋找 句 柄 .“歷 史 ” ： 已 移 入 符 號(hào) 棧 的內(nèi) 容“ 展 望 ” ： 根 據(jù) 產(chǎn) 生 式 推測(cè) 未 來 可 能

34、 遇 到 的 輸 入 符號(hào)“ 現(xiàn) 實(shí) ” ： 當(dāng) 前 的 輸 入 符號(hào) Xn 輸 入 串 X2 a # X1 # 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n LR分 析 方 法 ： 把 歷 史 及 展 望 綜 合 抽 象成 狀 態(tài) ； 由 棧 頂 的 狀 態(tài) 和 現(xiàn) 行 的 輸 入 符 號(hào)唯 一 確 定 每 一 步 工 作 LR分 析程 序狀 態(tài) 符 號(hào)Sm Xm S1 X1S0 #分 析 棧 action goto LR分 析 表a1a2ai an# 輸 入 串 輸 出 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n LR分 析 器 的 核 心 是 一 張 分

35、 析 表 ：ACTIONs， a： 當(dāng) 狀 態(tài) s面 臨 輸 入 符 號(hào) a時(shí) ，應(yīng) 采 取 什 么 動(dòng) 作 .GOTOs， X： 狀 態(tài) s面 對(duì) 文 法 符 號(hào) X時(shí) ， 下一 狀 態(tài) 是 什 么 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 每 一 項(xiàng) ACTIONs， a所 規(guī) 定 的 四 種 動(dòng) 作 :1. 移 進(jìn) 把 (s， a)的 下 一 狀 態(tài) s和 輸 入 符 號(hào) a推進(jìn) 棧 ， 下 一 輸 入 符 號(hào) 變 成 現(xiàn) 行 輸 入 符 號(hào) .2. 歸 約 指 用 某 產(chǎn) 生 式 A進(jìn) 行 歸 約 . 假 若 的 長 度 為 r， 歸 約 動(dòng) 作 是 ， 去 除 棧

36、 頂 r個(gè) 項(xiàng) ，使 狀 態(tài) sm-r變 成 棧 頂 狀 態(tài) ， 然 后 把 (sm-r, A)的下 一 狀 態(tài) s=GOTOsm-r, A和 文 法 符 號(hào) A推 進(jìn)棧 .3. 接 受 宣 布 分 析 成 功 ， 停 止 分 析 器 工 作 .4. 報(bào) 錯(cuò) 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 分 析 開 始 時(shí) :狀 態(tài) 已 歸 約 串 輸 入 串 (s0， #， a1a2 an #)n 以 后 每 步 的 結(jié) 果 可 以 表 示 為 :(s0 s1 sm ， # X1 Xm ， aiai+1 an #) 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 (

37、s0 s1 sm ， # X1 Xm ， aiai+1 an #)n分 析 器 根 據(jù) ACTION(sm , ai)確 定 下 一 步 動(dòng) 作1. 若 ACTION(sm , ai)為 移 進(jìn) ， 且 s， 則 三 元 式 格 局變 為 : (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為 的 長 度 , = Xm-r+1 Xm3. 若 ACTION(sm

38、, ai)為 接 受 ， 則 三 元 式 不 再 變 化 ，變 化 過 程 終 止 ， 宣 布 分 析 成 功 .4. 若 ACTION(s m , ai)為 報(bào) 錯(cuò) ， 則 三 元 式 變 化 過 程終 止 ， 報(bào) 告 錯(cuò) 誤 . 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 LR分 析 器 示 例 ：文 法 G(E)： (1) EE T(2) ET(3) TT*F(4) TF(5) F(E)(6) Fi 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 ACTION GOTO狀 態(tài) i + * ( ) # E T F0 s5 s4 1 2 31 s6 acc2 r2 s

39、7 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分 析 表 為 : 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 假 定 輸 入 串 為 i*i+i， LR分 析 器 的 工 作 過 程 :步 驟 狀 態(tài) 符 號(hào) 輸 入 串(1) 0 # i*i+i#(2) 05 #i *i+i#(3) 03 #F *i+i#(4) 02 #T *i+i#(5) 027 #T* i+i#(6) 02

40、75 #T*i +i#(7) 02710 #T*F +i#(8) 02 #T +i#(9) 01 #E +i#(10) 016 #E+ i# 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 步 驟 狀 態(tài) 符 號(hào) 輸 入 串(11) 0165 #E+i #(12) 0163 #E+F #(13) 0169 #E+T #(14) 01 #E #(15) 接 受 EE*T T+FF Fi ii 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 定 義 ： 對(duì) 于 一 個(gè) 文 法 ， 如 果 能 夠 構(gòu) 造 一 張分 析 表 ， 使 得 它 的 每 個(gè) 入 口 均 是 唯 一

41、確 定的 ， 則 這 個(gè) 文 法 就 稱 為 LR文 法 。n 定 義 ： 一 個(gè) 文 法 ， 如 果 能 用 一 個(gè) 每 步 頂 多向 前 檢 查 k個(gè) 輸 入 符 號(hào) 的 LR分 析 器 進(jìn) 行 分析 ， 則 這 個(gè) 文 法 就 稱 為 LR(k)文 法 .n 非 LR結(jié) 構(gòu)LR文 法 不 是 二 義 的 ， 二 義 文 法 肯 定 不 會(huì) 是 LR的 。 S iCtS | iCtSeS 棧 輸 入 iCtS e# 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 5.3.2 LR(0)項(xiàng) 目 集 族 和 LR(0)分析 表 的 構(gòu) 造n 字 的 前 綴 ： 是 指 字 的 任 意

42、 首 部 ， 如 字 abc的前 綴 有 ， a， ab， abcn 活 前 綴 ： 是 指 規(guī) 范 句 型 的 一 個(gè) 前 綴 ， 這 種 前綴 不 含 句 柄 之 后 的 任 何 符 號(hào) 。 即 ， 對(duì) 于 規(guī) 范句 型 ， 為 句 柄 ， 如 果 =u1u2ur， 則符 號(hào) 串 u1u2ui(1ir)是 的 活 前 綴 。 (必 為 終 結(jié) 符 串 )n 對(duì) 于 一 個(gè) 文 法 G, 可 以 構(gòu) 造 一 個(gè) DFA,它 能 識(shí)別 G的 所 有 活 前 綴 . 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 文 法 G的 每 個(gè) 產(chǎn) 生 式 的 右 部 添 加 一 個(gè) 圓點(diǎn)

43、稱 為 G的 LR(0)項(xiàng) 目n 如 :AXYZ有 四 個(gè) 項(xiàng) 目 ：A.XYZ AX.YZ AXY.Z AXYZ. FA . 稱 為 歸 約 項(xiàng) 目 F歸 約 項(xiàng) 目 S . 稱 為 接 受 項(xiàng) 目 FA .a (aVT) 稱 為 移 進(jìn) 項(xiàng) 目 F A .B (BV N) 稱 為 待 約 項(xiàng) 目 . 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n文 法 G(S) SE EaA|bB AcA|d BcB|d n 該 文 法 的 項(xiàng) 目 有 ：1. SE 2. SE 3. EaA 4. EaA 5. EaA 6. AcA7. AcA 8. AcA 9. Ad 10. Ad 11.

44、 EbB 12. EbB13. EbB 14. BcB 15. BcB 16. BcB 17. Bd 18. Bd 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 構(gòu) 造 識(shí) 別 文 法 所 有 活 前 綴 的 NFA方 法 1. 若 狀 態(tài) i為 XX1 Xi-1.Xi Xn ， 狀 態(tài) j為 XX1 Xi-1Xi .Xi+1 Xn ， 則 從 狀 態(tài) i畫 一 條 標(biāo) 志 為 Xi的 有 向 邊 到 狀 態(tài) j； 2. 若 狀 態(tài) i為 X .A ， A為 非 終 結(jié) 符 ， 則 從 狀 態(tài) i畫 一 條 邊 到 所 有 狀 態(tài) A.。n 把 識(shí) 別 文 法 所 有 活 前

45、綴 的 NFA確 定 化 。n 構(gòu) 成 識(shí) 別 一 個(gè) 文 法 活 前 綴 的 DFA的 項(xiàng) 目 集(狀 態(tài) )的 全 體 稱 為 文 法 的 LR(0)項(xiàng) 目 集 規(guī) 范族 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 6 7 89 104 531 211 12 1314 15 16 1817 a AE b B Bc Ac d識(shí) 別 活 前 綴 的 NFA 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室識(shí) 別 活 前 綴 的 DFA 0: SE EaA EbB 4: AcA AcA Ad 2: EaA AcA Ad1: SE3: EbB BcB Bd5: BcB B

46、cB Bd 11: Bd9: BcB7: EbB10: Ad6: EaA 8: AcAcc bEa dAcc dddBAB 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 有 效 項(xiàng) 目n 我 們 說 項(xiàng) 目 A 1.2對(duì) 活 前 綴 1是 有 效的 ， 其 條 件 是 存 在 規(guī) 范 推 導(dǎo) 21R*R AS q在 任 何 時(shí) 候 ， 分 析 棧 中 的 活 前 綴 X1X2 Xm的 有 效 項(xiàng) 目 集 正 是 棧 頂 狀 態(tài) Sm所 代 表 的那 個(gè) 集 合 。 也 正 是 從 識(shí) 別 活 前 綴 的 DFA的 初態(tài) 出 發(fā) ， 讀 出 X1X2 Xm后 到 達(dá) 的 那 個(gè) 項(xiàng)

47、目集 (狀 態(tài) )。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 結(jié) 論 : 若 項(xiàng) 目 A .B對(duì) 活 前 綴 =是 有效 的 且 B 是 一 個(gè) 產(chǎn) 生 式 ， 則 項(xiàng) 目 B .對(duì) =也 是 有 效 的 。 BAS RR * 所 以 ， B .對(duì) =也 是 有 效 的 。 RRRR BBAS * *R設(shè) ， 那 么 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 文 法 G(S) SE EaA|bB AcA|d BcB|d n 考 慮 ： 項(xiàng) 目 ： B c.B B . cB B . d 活 前 綴 ： bcS E bB bcBS E bB bcB bcc

48、BS E bB bcB bcd 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 LR(0)項(xiàng) 目 集 規(guī) 范 族 的 構(gòu) 造n 假 定 文 法 G是 一 個(gè) 以 S為 開 始 符 號(hào) 的 文 法 ，我 們 構(gòu) 造 一 個(gè) G， 它 包 含 了 整 個(gè) G， 但 它引 進(jìn) 了 一 個(gè) 不 出 現(xiàn) 在 G中 的 非 終 結(jié) 符 S，并 加 進(jìn) 一 個(gè) 新 產(chǎn) 生 式 SS， 而 這 個(gè) S是G的 開 始 符 號(hào) 。 那 么 ， 我 們 稱 G是 G的 拓廣 文 法 。 這 樣 ， 便 會(huì) 有 一 個(gè) 僅 含 項(xiàng) 目SS.的 狀 態(tài) ， 這 就 是 唯 一 的 “ 接 受 ” 態(tài) 。 國

49、防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 假 定 I是 文 法 G的 任 一 項(xiàng) 目 集 ， 定 義 和 構(gòu) 造I的 閉 包 CLOSURE(I)如 下 ：1. I的 任 何 項(xiàng) 目 都 屬 于 CLOSURE(I)；2. 若 AB屬 于 CLOSURE(I)， 那 么 ，對(duì) 任 何 關(guān) 于 B的 產(chǎn) 生 式 B， 項(xiàng) 目 B也屬 于 CLOSURE(I)；3. 重 復(fù) 執(zhí) 行 上 述 兩 步 驟 直 至 CLOSURE(I) 不 再 增 大 為 止 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 為 了 識(shí) 別 活 前 綴 ， 我 們 定 義 一 個(gè) 狀 態(tài)

50、 轉(zhuǎn) 換函 數(shù) GO是 一 個(gè) 狀 態(tài) 轉(zhuǎn) 換 函 數(shù) 。 I是 一 個(gè) 項(xiàng)目 集 ， X是 一 個(gè) 文 法 符 號(hào) 。 函 數(shù) 值 GO(I，X)定 義 為 ：GO(I， X) CLOSURE(J) 其 中 J 任 何 形 如 AX的 項(xiàng) 目 | A X屬 于 I。G 直 觀 上 說 ， 若 I是 對(duì) 某 個(gè) 活 前 綴 有 效 的項(xiàng) 目 集 ， 那 么 ， GO(I， X)便 是 對(duì) X 有 效的 項(xiàng) 目 集 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 文 法 G(S) SE EaA|bB AcA|d BcB|d n I0=SE, EaA, EbB GO(I0, E)

51、= closure(J)=closure(SE)= SE = I1 GO(I0, a)= closure(J)=closure(EaA) = EaA, AcA, Ad )=I 2 GO(I0, b)= closure(J)=closure (E b.B) =E b.B, B.cB, B.d= I3 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n構(gòu) 造 文 法 G的 拓 廣 文 法 G的 LR(0)項(xiàng) 目 集 規(guī)范 族 算 法 ：PROCEDURE ITEMSETS(G)；BEGINC:=CLOSURE(SS)；REPEAT FOR C中 每 個(gè) 項(xiàng) 目 集 I和 G的 每 個(gè) 符

52、 號(hào) X DO IF GO(I， X)非 空 且 不 屬 于 C THEN 把 GO(I， X)放 入 C族 中 ;UNTIL C 不 再 增 大ENDn轉(zhuǎn) 換 函 數(shù) GO把 項(xiàng) 目 集 連 接 成 一 個(gè) DFA轉(zhuǎn) 換 圖 . 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 0: SE EaA EbB 4: AcA AcA Adc 5: BcB BcB Bd c 3: EbB BcB Bdb 1: SEE 2: EaA AcA Ada 11: Bdd 8: AcAAcc d 10: Addd 9: BcBB 6: EaA A 7: EbBB 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系

53、 602教 研 室 LR(0)分 析 表 的 構(gòu) 造n 假 若 一 個(gè) 文 法 G的 拓 廣 文 法 G的 活 前 綴識(shí) 別 自 動(dòng) 機(jī) 中 的 每 個(gè) 狀 態(tài) (項(xiàng) 目 集 )不 存 在下 述 情 況 ： 1) 既 含 移 進(jìn) 項(xiàng) 目 又 含 歸 約 項(xiàng) 目 ， 2) 含 有 多 個(gè) 歸 約 項(xiàng) 目 則 稱 G是 一 個(gè) LR(0)文 法 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 構(gòu) 造 LR(0)分 析 表 的 算 法n 令 每 個(gè) 項(xiàng) 目 集 Ik的 下 標(biāo) k作 為 分 析 器 的 狀 態(tài) ，包 含 項(xiàng) 目 SS的 集 合 Ik的 下 標(biāo) k為 分 析 器的 初 態(tài)

54、 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 分 析 表 的 ACTION和 GOTO子 表 構(gòu) 造 方 法 ：1. 若 項(xiàng) 目 Aa屬 于 Ik且 GO(Ik, a) Ij， a為 終 結(jié)符 ， 則 置 ACTIONk,a 為 “ sj”。2. 若 項(xiàng) 目 A屬 于 Ik， 那 么 ， 對(duì) 任 何 終 結(jié) 符 a(或結(jié) 束 符 #)， 置 ACTIONk,a為 “ rj”(假 定 產(chǎn) 生 式A是 文 法 G的 第 j個(gè) 產(chǎn) 生 式 )。3. 若 項(xiàng) 目 SS屬 于 Ik， 則 置 ACTIONk,#為 “ acc”。4. 若 GO(Ik,A) Ij， A為 非 終 結(jié)

55、符 ， 則 置GOTOk,A=j。5. 分 析 表 中 凡 不 能 用 規(guī) 則 1至 4填 入 信 息 的 空 白 格均 置 上 “ 報(bào) 錯(cuò) 標(biāo) 志 ” 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n LR(0)分 析 表 為ACTION GOTO狀 態(tài) a b c d # E A B0 s2 s3 11 acc2 s4 s10 6 3 s5 s11 74 s4 s10 85 s5 s116 r1 r1 r1 r1 r1 97 r2 r2 r2 r2 r28 r3 r3 r3 r3 r39 r5 r5 r5 r5 r5 10 r4 r4 r4 r4 r411 r6 r6 r6

56、 r6 r6 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 例 : 按 上 表 對(duì) acccd進(jìn) 行 分 析n 步 驟 狀 態(tài) 符 號(hào) 輸 入 串1 0 # acccd#2 02 #a cccd#3 024 #ac ccd#4 0244 #acc cd#5 02444 #accc d#6 0244410 #acccd #7 024448 #acccA #8 02448 #accA #9 0248 #acA #10 026 #aA #11 01 #E # 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 5.3.3 SLR分 析 表 的 構(gòu) 造n LR(0)文 法 太 簡

57、 單 ， 沒 有 實(shí) 用 價(jià) 值 .n 假 定 一 個(gè) LR(0)規(guī) 范 族 中 含 有 如 下 的 一 個(gè) 項(xiàng) 目 集(狀 態(tài) )I Xb， A， B。FOLLOW(A)和 FOLLOW(B)的 交 集 為 ， 且 不 包含 b， 那 么 ， 當(dāng) 狀 態(tài) I面 臨 任 何 輸 入 符 號(hào) a時(shí) ， 可 以 :1. 若 a=b， 則 移 進(jìn) ；2. 若 aFOLLOW(A)， 用 產(chǎn) 生 式 A進(jìn) 行 歸 約 ；3. 若 aFOLLOW(B)， 用 產(chǎn) 生 式 B進(jìn) 行 歸 約 ；4. 此 外 ， 報(bào) 錯(cuò) 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 假 定 LR(0)規(guī)

58、范 族 的 一 個(gè) 項(xiàng) 目 集 I=A1a11，A2a22， ， Amamm， B1，B2， ， Bn 如 果 集 合 a1， ， am，F(xiàn)OLLOW(B1)， ， FOLLOW(Bn)兩 兩 不 相交 (包 括 不 得 有 兩 個(gè) FOLLOW集 合 有 #)， 則 ：1. 若 a是 某 個(gè) ai， i=1,2,m， 則 移 進(jìn) ；2. 若 aFOLLOW(Bi)， i=1,2,n， 則 用 產(chǎn) 生 式Bi進(jìn) 行 歸 約 ；3. 此 外 ， 報(bào) 錯(cuò) 。n 沖 突 性 動(dòng) 作 的 這 種 解 決 辦 法 叫 做 SLR(1)解 決辦 法 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研

59、 室 構(gòu) 造 SLR(1)分 析 表 方 法 :n 首 先 把 G拓 廣 為 G， 對(duì) G構(gòu) 造 LR(0)項(xiàng) 目集 規(guī) 范 族 C和 活 前 綴 識(shí) 別 自 動(dòng) 機(jī) 的 狀 態(tài) 轉(zhuǎn)換 函 數(shù) GO.n 然 后 使 用 C和 GO， 按 下 面 的 算 法 構(gòu) 造 SLR分 析 表 ：令 每 個(gè) 項(xiàng) 目 集 Ik的 下 標(biāo) k作 為 分 析 器 的 狀 態(tài) ，包 含 項(xiàng) 目 SS的 集 合 Ik的 下 標(biāo) k為 分 析 器 的初 態(tài) 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 分 析 表 的 ACTION和 GOTO子 表 構(gòu) 造 方 法 ：1. 若 項(xiàng) 目 Aa屬 于 Ik

60、且 GO(Ik,a)=Ij， a為 終 結(jié) 符 ，則 置 ACTIONk,a為 “ sj”；2. 若 項(xiàng) 目 A屬 于 Ik， 那 么 ， 對(duì) 任 何 終 結(jié) 符 a，aFOLLOW(A)， 置 ACTIONk,a為 “ rj”； 其 中 ，假 定 A為 文 法 G的 第 j個(gè) 產(chǎn) 生 式 ；3. 若 項(xiàng) 目 SS屬 于 Ik， 則 置 ACTIONk,#為 “ acc”;4. 若 GO(Ik,A) Ij， A為 非 終 結(jié) 符 ， 則 置GOTOk,A=j；5. 分 析 表 中 凡 不 能 用 規(guī) 則 1至 4填 入 信 息 的 空 白 格 均置 上 “ 出 錯(cuò) 標(biāo) 志 ” 。 國 防 科

61、技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 按 上 述 方 法 構(gòu) 造 出 的 ACTION與 GOTO表如 果 不 含 多 重 入 口 ， 則 稱 該 文 法 為 SLR(1)文 法 。n 使 用 SLR表 的 分 析 器 叫 做 一 個(gè) SLR分 析 器 。n 每 個(gè) SLR(1)文 法 都 是 無 二 義 的 。 但 也 存 在許 多 無 二 義 文 法 不 是 SLR(1)的 . 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 例 5.11 考 察 下 面 的 拓 廣 文 法 ：(0) SE(1) EE+T(2) ET(3) TT*F(4) TF(5) F(E)(6

62、) Fi 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 這 個(gè) 文 法 的 LR(0)項(xiàng) 目 集 規(guī) 范 族 為 ：I0: SE EE+T ET TT*F TT*F TF F (E) FiI1: SE EE+TI 2: ET TT*FI3: TF I4: F(E) EE+T ET TT*F TF F (E) FiI5 : FiI6: EE+T TT*F TF F(E) Fi I7: TT*F F(E) FiI8: F(E) EE+TI9: EE+T TT*FI 10: TT*FI11: F(E) 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n I1、 I2和 I9

63、都 含 有 “ 移 進(jìn) 歸 約 ” 沖 突 。n FOLLOW(E) #, ), +，I0 I1I 2 I3I4I5 I6I7 I8 I9 I10I11E + T *T Ti F( i ( FE (Fi +F* ( ) 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 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

64、r311 r5 r5 r5 r5 其 分 析 表 如 下 : 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n 非 SLR文 法 示 例 ： 考 慮 如 下 文 法 ：(0) SS(1) SL=R(2) SR(3) L*R(4) Li(5) RL計(jì) 算 FOLLOW集 合 所 得 到 的 超 前 符 號(hào) 集 合 可能 大 于 實(shí) 際 能 出 現(xiàn) 的 超 前 符 號(hào) 集 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 這 個(gè) 文 法 的 LR(0)項(xiàng) 目 集 規(guī) 范 族 為 ：I0： SS SL=R SR S*R Li RLI1： SS I2： SL=R RLI3： S

65、RI4： L*R RL L*R LiI 5： Li I6： SL=R RL L*R LiI7： L*RI 9： SL=RI8： RL 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 R S = i L R * L * * R i i L 活 前 綴 識(shí) 別 器 1 2 0 3 4 6 7 5 8 9 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 n SLR在 方 法 中 ,如 果 項(xiàng) 目 集 Ii含 項(xiàng) 目 A.而且 下 一 輸 入 符 號(hào) aFOLLOW(A),則 狀 態(tài) i面 臨 a時(shí) ,可 選 用 “ 用 A歸 約 ” 動(dòng) 作 。 但在 有 些 情 況 下 ,當(dāng) 狀

66、 態(tài) i顯 現(xiàn) 于 棧 頂 時(shí) ,棧 里的 活 前 綴 未 必 允 許 把 歸 約 為 A， 因 為 可 能根 本 就 不 存 在 一 個(gè) 形 如 “ Aa”的 規(guī) 范 句 型 。因 此 ， 在 這 種 情 況 下 ， 用 “ A ”歸 約 不一 定 合 適 。n 如 上 例 ， 當(dāng) 狀 態(tài) 2顯 現(xiàn) 于 棧 頂 而 且 面 臨 輸入 符 號(hào) 為 =時(shí) ， 實(shí) 際 上 不 能 用 對(duì) 棧 頂 L進(jìn)行 歸 約 ， 因 為 這 個(gè) 文 法 不 含 “ R=”為 前 綴的 規(guī) 范 句 型 。 國 防 科 技 大 學(xué) 計(jì) 算 機(jī) 系 602教 研 室 5.3.4 規(guī) 范 LR分 析 表 的 構(gòu) 造n 我 們 需 要 重 新 定 義 項(xiàng) 目 ， 使 得 每 個(gè) 項(xiàng) 目 都附 帶 有 k個(gè) 終 結(jié) 符 。 每 個(gè) 項(xiàng) 目 的 一 般 形 式是 A, a1a2ak ， 這 樣 的 一 個(gè) 項(xiàng) 目 稱為 一 個(gè) LR(k)項(xiàng) 目 。 項(xiàng) 目 中 的 a1a2ak 稱為 它 的 向 前 搜 索 符 串 (或 展 望 串 )。n 向 前 搜 索 符 串 僅 對(duì) 歸 約 項(xiàng) 目 A，a1a2ak有 意 義