【文章內容簡介】 … B b9 B10 (4)| c11 (5) Z` Z1 (0) Z a2 B3 A4 d5 (1) A b6 c7 (2)| c8 (3) G`(Z`) ※ 句柄識別器 的自動機構造示例： 其中： r(j) 歸約函數(shù) (即 按序號為 (j)的 產生式 歸約！ )； ? 移進狀態(tài)： ? 歸約狀態(tài)： B b9 B10 (4)| c11 (5) Z` Z1 (0) Z a2 B3 A4 d5 (1) A b6 c7 (2)| c8 (3) G`(Z`) 符號說明 0， 2， 3， 4， 6， 9 ； ① 0 11 + Z a B b b B c c A d b c OK r(3) r(1) r(2) r(4) r(5) c ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ 由 擴展文法 到句柄識別器的構造過程如右圖所示： 【 例 】 5， 7， 8， 10， 11； 分析結束 (OK)。 ? 接受狀態(tài)： 1 ① 0 11 + Z a B b b B c c A d b c OK r? r? r? r? r? c ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ ※ 根據(jù)句柄識別器進行 LR分析過程： ※ 根據(jù)句柄識別器， abccd 識別過程： (0,a) =(0a2b9B10,c) =(0a2B3A4,d) =(0a2,b) =(0a2b9,c) =(0a2b9c11,c) =(0a2B3,c) = (0a2B3c8,d) =(0a2B3A4d5,) =(0Z1,)=0k 句柄識別器又稱 ? 活前綴圖 ? : 意思是在最左歸約過程中，識別了句柄，實際上也就識別了以句柄為后綴的該句型 (規(guī)范句型 )的前部符號串。 注 B b9 B10 (4)| c11 (5) Z` Z1 (0) Z a2 B3 A4 d5 (1) A b6 c7 (2)| c8 (3) 句柄 【 例 】 文法的句柄識別器 : + LR(0)分析器的基本組成： ※LR(0) 分析法要求文法應是 LR(0）文法 。 LR(0)分析表 LR(0)控制器 ※LR( 0)中的 0,是指 不必查看當前符號 就可確認 句柄 之意； LR(0)分析器設計 1. LR(0)文法 及其判定 ① 句柄識別器中， 移 進 和 歸約 不沖突；即 移進和歸約不同時發(fā)生！ ※ 滿足下述特點的文法稱為 LR(0)文法 。 例 文法，就是 LR(0)文法， 請看 ： ② 歸約 時不必查看當前符號； 【 算法 】 ? 根據(jù) 句柄識別器， 填寫 LR(0)分析表： ① 若 ?(i,x)=k,x∈(V N+VT),則 R(i,x):= xk 。 ② 若 狀態(tài) i 標記有（ ， r(j)), 則 對任何 a ∈(V T+{}）， R(i,a):= r(j) 。 ③ R(1,):= OK 。 2. LR(0)分析表構造 ? 擴展文法，構造句柄識別器； LR()分析表是 LR()分析法的知識表 ,是 句柄識別器 的一種機內表示形式： 狀態(tài)編碼 終結符 + 非終結符 R(_,_): 0 1 … a … Z … n ak OK Zk r(j) r(j) … ① 0 11 + Z a B b b B c c A d b c OK r? r? r? r? r? c ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ LR(0)分析表 ※ 【 例 】 文法 構造過程： 9 10 Z A 1 5 0 4 8 d 6 7 11 3 2 B c b a B10 c11 b9 r(4) r(4) r(4) r(4) r(4) Z1 A4 OK r(1) r(1) r(1) r(1) r(1) a2 d5 r(3) r(3) r(3) r(3) r(3) r(5) r(2) r(5) r(2) c7 r(2) r(2) r(2) r(5) r(5) r(5) c8 b6 B3 b9 c11 3. LR(0)控制程序設計 開始 PUSH(0) NEXT(w) 查 LR(0)分析表R(Xk,w)=? R=空 ? Y err R=OK 結束 R=r(j) R=Wi PUSH Wi 則 PUSH Ai。 取 A ? (j) ① POP(?)。 ② 若 R(Xk,A)=Ai Xk 棧頂 文法出現(xiàn) ； 歸約 移進 LR( )控制器 n ● ※ LR(0) 分析法小結示例 G(Z): Z aBAd A bc | c B bB | c 【 例 】文法 : ? 擴展文法，使 文法符號 附有 位置 信息： B b9 B10 (4)| c11 (5) Z` Z1 (0) Z a2 B3 A4 d5 (1) A b6 c7 (2)| c8 (3) ? 由 擴展文法 構造句柄識別器： ① 0 11 + Z a B b b B c c A d b c OK r(3) r(1) r(2) r(4) r(5) c ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ ① 0 11 + Z a B b b B c c A d b c OK r? r? r? r? r? c ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ 9 10 Z A 1 5 0 4 8 d 6 7 11 3 2 B c b a B10 c11 b9 r(4) r(4) r(4) r(4) r(4) Z1 A4 OK r(1) r(1) r(1) r(1) r(1) a2 d5 r(3) r(3) r(3) r(3) r(3) r(5) r(2) r(5) r(2) c7 r(2) r(2) r(2) r(5) r(5) r(5) c8 b6 B3 b9 c11 ? 由句柄識別器構造 LR(0)分析表： ? LR(0)分析法 分析過程 示例： 剩余串 操 作 w 分析棧 0 a2 b9 B10 PUSH(c8),NEXT(w) d c 0 a2 REDUCE(3) d 0 a2 B3 PUSH(d5),NEXT(w) d 0 a2 B3 REDUCE(1) 0 a2 B3 A4 OK 0 d d cd ccd bccd PUSH(c11),NEXT(w) c 0 a2 PUSH(a2),NEXT(w) a 0 REDUCE(4) c REDUCE(5) c 0 a2 b9 PUSH(b9),NEXT(w) b 0 a2 b9 c11 B3 c8 A4 d5 Z1 查分析表 查產生式 控制程序 ※ 符號串： abccd ※ 【 例 】 LR(0)分析法示例 1： ※ 構造下述文法的 LR(0)分析表： G(Z)： Z aAb , A cA | d ① ② ③ ④ ⑤ ⑥ ⑦ 0 + Z a A d b c A OK r(1) r(2) r(3) c d ? 構造句柄識別器： ? 擴展文法 ： G`(Z`) Z` Z1 (0) Z a2 A3 b4 (1) A c5 A6 (2)| d7 (3) ? 設計 LR(0) 分析表： r(3) r(2) d7 r(1) d7 d Z1 Z A6 A3 A OK 1 c5 5 a2 0 r(1) (1) r(1) r(1) 4 r(3) r(2) r(2) r(2) r(2) 6 r(3) r(3) r(3) 7 b4 3 c5 2 c b a ① ② ③ ④ ⑤ ⑥ ⑦ 0 + Z a A d b c A OK r(1) r(2) r(3) c d ※ 【 例 】 左遞歸文法的 LR(0)分析表構造： d Z A 1 5 0 4 6 3 2 c b a ① ② ③ ④ ⑥ ⑤ 0 + Z a A d b c OK r(1) r(2) r(3) Z`Z1(0)。 Z a2A3b4(1)。 A A3c5(2)|d6(3) G`(Z`) 【 注 】 為了使句柄識別器是 確定機 ，左遞歸產生式 (2)中的 A要與 (1)中的 A編碼相同 !?, r(3) r(2) r(1) d6 Z1 A3 OK r(2) r(2) r(2) r(2) a2 r(1) r(1) r(1) r(1) r(3) r(3) r(3) r(3) c5 b4 ※ 【 例 】 LR(0)分析法示例 1 ※ 構造下述文法的 LR(0)分析表： G(Z) Z aAb , A Ac | d ? 擴展文法： G`(Z`) Z` Z1 (0) Z a2 A3 b4 (1) A A5c6 (2)| d7 (3) ? 構造可歸前綴圖： ① ② ③ ④ ⑤ ⑥ ⑦ 0 + Z a A d b A c OK r(1) r(2) r(3) (接上頁 ) ∵ ?（ 2， A)={3,5}, ∴ 是個非確定機； ① ② ③ ④ ⑥ ⑤ 0 + Z a A d b c OK r(1) r(2) r(3) ※ 確定化的可歸前綴圖： ① ② ③ ④ ⑤ ⑥ ⑦ 0 + Z a A d b A c OK r(1) r(2) r