【正文】 I8 r(3) T ( i + ( i … E … E+ … E+T … T … ( … (E … (E) … i 文法 a * ( b + c ) F T T E F F T E T F E a b c + ( )* 。+T E I6 ) T(E)i ( I5 T(ET TE) E T OK r(1) I0 T ET(E) T+T EE+i E E’ET TE E = + = + 語法分析方法綜合示例 G(Z)： Z dAZ | bAc A aA | c |ε 【 例 】 給定文法如下： Ⅰ. 遞歸子程序法； Ⅱ. LL(1) 分析法； ※ 試分別用下述分析法，對給定的 符號(hào)串 進(jìn)行語法分析： Ⅲ. LR(0)( 或 SLR（ 1） )分析法； 設(shè) 給定的符號(hào)串為： α = bac ∵ Z = bAc = baAc = ba ε c = bac ∴ bac 是文法 G(Z) 的一個(gè)句子。b ， 當(dāng)且僅當(dāng)有 P?… aR… ，且 R b… 或 R Qb… ； = + ③ a 算符優(yōu)先分析 (2)頭符號(hào)集合和尾符號(hào)集合 設(shè) a∈V T， P,R∈V N， 則 : FIRSTVT(P)={a| P a…… 或 P Ra…… }, = + LASTVT(P) ={a| P …… a 或 P …… aR}。si的 si（句柄的頭） ② 用 sisi+1… sj去查文法產(chǎn)生式，若有 A?sisi+1… sj，則： Xk：棧頂 符 ； 歸約 移進(jìn) 簡單優(yōu)先控制器 y 簡單優(yōu)先分析表 是優(yōu)先分析法的知識(shí)表 ,是 文法 的一種機(jī)內(nèi)表示形式： 終結(jié)符 +非終結(jié)符 + … a … Z 優(yōu)先關(guān)系符號(hào) 終結(jié)符+非終結(jié)符+ 3. 簡單優(yōu)先控制程序設(shè)計(jì) 開始 PUSH() NEXT(w) 查優(yōu)先分析表R(Xk,w)=? 空 ? n err (S) 結(jié)束 PUSH W POP(sj)， POP(sj1)， … POP(si)； PUSH(A)。 sj ， 當(dāng)且僅當(dāng)有 U?… Vsj… ，且 si∈LASTVT(V) 。 例 文法，就是 簡單優(yōu)先 文法， 請看： ② 文法符號(hào)之間至多有一種優(yōu)先關(guān)系！ 【 算法 】 ① si sj ， 當(dāng)且僅當(dāng)有 U?… si sj … ； ② si + 簡單優(yōu)先分析器的基本組成： ※ 優(yōu)先 分析法要求文法應(yīng)是 簡單優(yōu)先 文法 。 e b a = + 【 例 】 G(S): S?aAeB|b， A?Sb|e， B?aA S A B a b e S A (3)頭符號(hào)集合和尾符號(hào)集合 設(shè) A∈V N， si ， sj是兩個(gè)文法符號(hào) 。b， eb， Ba …… ③ sia， ae， a 如： a A， A e， e B， S b； ① si sj ，當(dāng)且僅當(dāng)有 U?… si sj … ； ? 優(yōu)先關(guān)系的定義 G(S): S?aAeB|b A?Sb|e B?aA ② si 結(jié)論：一個(gè)句型的句柄，位于第一次（自左至右）出現(xiàn)在 a A e e a A e e e a e e b e… 當(dāng)把優(yōu)先關(guān)系納入待分析的符號(hào)串時(shí)，有如下關(guān)系： ； 如： be, e； 如： a . 簡單優(yōu)先分析法基本概念 ※ 簡單優(yōu)先分析法的基本要點(diǎn)有三： 1. 什么是簡單優(yōu)先分析法？ 2. 簡單優(yōu)先分析過程示例 符號(hào)串： ? = abbeae S a A e B S b b a G(S): S?aAeB|b A?Sb|e B?aA A e 句柄產(chǎn)生式 操 作 剩余串 w 分析棧 移進(jìn) ,NEXT a e e a 移進(jìn) ,NEXT e a a A 移進(jìn) ,NEXT e a A e 歸約 A e aAe a 歸約 B aA aAe a A Sb S b 歸約 e a e b a 移進(jìn) ,NEXT b b e a e a 歸約 a e e a S 移進(jìn) ,NEXT e a e b a 移進(jìn) ,NEXT b e a e b A A a a b e e 句柄 (接上頁 ) ? 利用分析棧記錄行分析過程： 【 注 】 何時(shí)棧頂出現(xiàn) 句柄？ 怎樣求當(dāng)前 句柄產(chǎn)生式 ？ 設(shè) 待分析的符號(hào)串 : abbeae S b aAe B 句柄 S aAeB 歸約 S OK 語法樹 ① 同時(shí)歸約者為相等關(guān)系，記作 ； 3. 文法符號(hào)之間的優(yōu)先關(guān)系 ? 歸約過程中如何確認(rèn) 句柄 ？ ※ 是否是句柄 ，還要看其所在符號(hào)串中的 位置 。 該方法利用 文法符號(hào) 之間的 優(yōu)先關(guān)系 來確定待歸約的句柄 ，即可確定當(dāng)前句型的 句柄 。 ※ 求： follow(A)={a} ； follow(B)={c} 0 + S A a c OK r(1) r(4) d r(3) r(2) B ① ② ④ ⑤ ⑥ ③ ⑦ d 0 + S A a c OK r(1) ,r(4) d r(3) r(2) B ① ② ④ ⑤ ⑥ ③ ⑥ 確定化 ∵ :{ r? ,r? } ∴ 稱為 歸約 /歸約沖突！ ⑥ 非確定機(jī) S` S1(0) S A2a3 ? | B4c5? A d6 ? 。 ? 擴(kuò)展 文法 ， 構(gòu)造 句柄識(shí)別器： G`(S`): 即 若 w=a 則 r(3) 。 Bd7 ? 【 例 】 G(S): SAa|Bc ； Ad。 ※ 通過查看 ‘ 當(dāng)前單詞 ’ ，是否可以解決？為此： r(3) 0 + Z a A b OK r(1) r(2) c r(3) ? ① ② ③ ④ ⑤ d ⑥ ⑦ Z`Z(0) ZaAb(1) Acd(2) ?(3) SLR(1)分析表 b r(3) SLR(1)句柄識(shí)別器： ? 擴(kuò)展 句柄識(shí)別器， 構(gòu)造 SLR(1)分析表 d Z A 1 5 0 4 6 3 2 c b a r(2) d6 r(1) Z1 A3 OK a2 r(1) r(1) r(1) r(1) r(2) r(2) r(2) r(2) b4 c5 r(3) 注意與 LR(0)分析表的區(qū)別！ 0 + Z a A b OK r(1) r(2) c ① ② ③ ④ ⑤ d ⑥ ※ 如此可以解決沖突的文法，稱為SLR(1)文法 。 Z a2A3b4(1) A c5d6(2)|?7(3) G`(Z`): ※ 經(jīng)確定化 (消 ε邊 )： ※ 句柄識(shí)別器 出現(xiàn)沖突 ： ∵ ② :{c5,r(3),A3} ∴ 稱為 移 進(jìn) /歸約沖突！ 看到： ∩{c}= ? ； 解決辦法： 求： follow(A)= ∴ 若 w=c 則 c5 。 【 注 】 下面僅通過實(shí)例探討 LR(0)分析表 的簡單擴(kuò)展問題 稱為 SLR(1)分析法。 Z a2A3b4(1)。 取 A ? (j) ① POP(?)。 ③ R(1,):= OK 。 例 文法，就是 LR(0)文法， 請看 ： ② 歸約 時(shí)不必查看當(dāng)前符號(hào)； 【 算法 】 ? 根據(jù) 句柄識(shí)別器， 填寫 LR(0)分析表： ① 若 ?(i,x)=k,x∈(V N+VT),則 R(i,x):= xk 。 注 B b9 B10 (4)| c11 (5) Z` Z1 (0) Z a2 B3 A4 d5 (1) A b6 c7 (2)| c8 (3) 句柄 【 例 】 文法的句柄識(shí)別器 : + LR(0)分析器的基本組成： ※LR(0) 分析法要求文法應(yīng)是 LR(0）文法 。 … B b9 B10 (4)| c11 (5) Z` Z1 (0) Z a2 B3 A4 d5 (1) A b6 c7 (2)| c8 (3) G`(Z`) ※ 句柄識(shí)別器 的自動(dòng)機(jī)構(gòu)造示例： 其中： r(j) 歸約函數(shù) (即 按序號(hào)為 (j)的 產(chǎn)生式 歸約！ )； ? 移進(jìn)狀態(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`) 符號(hào)說明 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 ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ 由 擴(kuò)展文法 到句柄識(shí)別器的構(gòu)造過程如右圖所示： 【 例 】 5， 7， 8， 10， 11； 分析結(jié)束 (OK)。 ?(3,A)=4。 【 表示 】 : 0狀態(tài) ‘ 預(yù)見 ’ Z 后變換為 1狀態(tài) ！ 設(shè)編碼 ‘ 0’作為自動(dòng)機(jī)的 開始狀態(tài) ， 第二個(gè)產(chǎn)生式，構(gòu)造 自動(dòng)機(jī) ： 則 第一個(gè)產(chǎn)生式，構(gòu)造 自動(dòng)機(jī) ： ?(0,a)=2。 ② ‘預(yù)見 ’ 某個(gè) 非終結(jié)符 ，也就 ‘ 預(yù)見 ’ 其所有 產(chǎn)生式的頭符號(hào) 。 ① 怎樣判斷棧頂出現(xiàn)的 句柄 不是 bc,而是 c ? ∴ 顯然是錯(cuò)誤的 (從文法中可判定： aA不能相鄰 !) ∵ 若用 bc 歸約，則有 abccd aAcd( ) = . ∵ 若用 A作父親，則有 abccd abAcd( ) = . ∴ 顯然是錯(cuò)誤的 (從文法中可判定： Ac不能相鄰 ! 語法樹 ※ 我們討論如下兩個(gè)問題： abc cd 分析棧 ① 擴(kuò)展文法，使 文法符號(hào) 附有 位置 信息： B b9 B10 (4)| c11 (5) Z` Z1 (0) Z a2 B3 A4 d5 (1) A b6 c7 (2)| c8 (3) ※ 增設(shè)一個(gè)產(chǎn)生式 (如： Z` Z )， ※ 帶有 位置 編碼的