【正文】 f(b)=g(a)， f(b)=g(b) ? 導致如下矛盾 : ? f(a) g(b) = f(b) = g(a) = f(a) ? 如果優(yōu)先函數(shù)存在，則不唯一 (無窮多 ) 優(yōu)先函數(shù) a b a ≒ ≯ b ≒ ≒ ? 如果優(yōu)先函數(shù)存在，則可以通過以下三個步驟從優(yōu)先表構造優(yōu)先函數(shù) : ?1 對于每個終結符 a，令其對應兩個符號 fa和 ga，畫一以所有符號 fa和 ga為結點的方向圖。由于非終結符對歸約沒有影響，因此，非終結符根本可以不進符號棧 S。 ? 15 IF S[j]≮ a OR S[j]≒ a THEN ? 16 BEGIN k:=k+1。 ? 5 WHILE S[j]≯ a DO ? 6 BEGIN ? 7 REPEAT ? 8 Q:=S[j]。 ? 用于分析各類表達式 ? ALGOL 60 ? 算符優(yōu)先分析法 特點 ： ? 優(yōu)點 : 簡單，快速 ? 缺點 : 可能錯誤接受非法句子，能力有限 . ? 算符優(yōu)先分析算法： ? 使用一個 符號棧 S，用它寄存終結符和非終結符， k代表 符號棧 S的 使用深度 。 ? 一個文法 G的句型的 素短語 是指這樣一個短語，它至少含有一個終結符，并且，除它自身之外不再含任何更小的素短語。 算符優(yōu)先文法及優(yōu)先表構造 ? 使用每個非終結符 P的 FIRSTVT(P)和 LASTVT(P)，就能夠構造文法 G的優(yōu)先表。對于每個形如 P→Q… 的產(chǎn)生式，若 F[P， a]為假，則變其值為真且將 (P， a)推進 STACK棧。 FIRSTVT(P)的算法 ? 數(shù)據(jù)結構： ? 布爾數(shù)組 F[P， a]，使得 F[P， a]為真的條件是，當且僅當 a?FIRSTVT(P)。 ? 確定滿足關系 ≮ 和 ≯ 的所有終結符對： 首先需要對 G的每個非終結符 P構造兩個集合FIRSTVT(P)和 LASTVT(P)： 算符優(yōu)先文法及優(yōu)先表構造 F I R S T V T P a P a P Qa a V Q VT N( ) { | , , }? ? ? ? ?? ?? ?或 而},|{)( NT VQVaaQPaPaPL A S T V T ????? ?? 而或 ?? 算符優(yōu)先文法及優(yōu)先表構造 ? 有了這兩個集合之后，就可以通過檢查每個產(chǎn)生式的候選式確定滿足關系 ≮ 和 ≯ 的所有終結符對。 2. a≮ b 當且僅當 G中含有形如 P→… aR… 的產(chǎn)生式，而 R b… 或 R Qb… ； ????3. a≯ b 當且僅當 G中含有形如 P→… Rb… 的產(chǎn)生式，而 R … a或 R … aQ。 算符優(yōu)先分析 ? 定義任何兩個可能相繼出現(xiàn)的終結符 a與 b的優(yōu)先關系 ： 三種關系 a ≮ b a的優(yōu)先級低于 b a ≒ b a的優(yōu)先級等于 b a ≯ b a的優(yōu)先級高于 b ? 注意 ：與數(shù)學上的 、 、 =不同， a ≮ b并不意味著 b ≯ a ? 算符優(yōu)先文法及優(yōu)先表構造 ? 一個文法，如果它的任一 產(chǎn)生式的右部都不含兩個相繼 (并列 )的非終結符 ，即不含如下形式的產(chǎn)生式右部： … QR… 則我們稱該文法為 算符文法 。歸約順序不同，則計算的順序也不同，結果也不一樣。 ?① 移進 (shift): 把當前輸入中的下一個終結符移進棧； ?② 歸約 (reduce): 句柄在棧頂已形成，用適當產(chǎn)生式左部代替句柄； ?③ 接受 (accept): 宣告分析成功； ?④ 報錯 (error): 發(fā)現(xiàn)語法錯誤，調用錯誤恢復例程。 Sa A eA b c dBbSa A eA b c dBSa A edBSa A eB( a ) ( b) ( c ) ( d)S( e )圖 剪句柄的過程 (a) 句子； (b) 剪去 b之后； (c) 剪去 Abc之后； (d) 剪去 d之后； (e) 開始符號 符號棧的使用與語法樹的表示 ? 從分析樹上直觀地看，“ 剪句柄 ”的方法十分簡單。 ? 規(guī)范歸約是關于是一個最右推導的逆過程 ?最左歸約 規(guī)范推導 ? 由規(guī)范推導推出的句型稱為 規(guī)范句型 。 步驟 : 1 2 3 4 5 6 7 8 9 10動作 : 進 a 進 b 歸 (2 ) 進 b 歸 (3 ) 進 c 進 d 歸 (4 ) 進 e 歸 (1 )ed B Bb c c c cb A A A A A A Aa a a a a a a a a S 歸約的語法樹分析法 ? 分析樹和語法樹 ?不一定一致 ? 自下而上分析過程 ?邊輸入單詞符號，邊歸約 ? 核心問題 ?識別可歸約串 b d b a c e S A B A 規(guī)范歸約簡述 ? 定義：令 G是一個文法， S是文法的開始符號，假定 ???是文法 G的一個句型 ，如果有 且 ??AS *? ???A則 ?稱是句型 ???相對于非終結符 A的 短語 。 a bbcde b Ab c ded abbcde e B S 移進 歸約分析 ? 例：設文法 G[S]： (1) S ? aAcBe (2) A ? b (3) A ? Ab (4) B ? d 試對 abbcde進行 “ 移進 歸約 ” 分析。 規(guī)范歸約簡述 ? 把上例倒過來寫，則得到： ?S ? aAcBe? aAcde ? aAbcde ? abbcde ? 顯然這是一個 最右推導 。該推導即分析樹 “ 剪句柄 ”的全過程。 符號棧的使用與語法樹的表示 ? 在 移進 —歸約分析模式 中，符號棧的使用有以下四種操作形式。 ? 歸約即計算表達式的值。 ? 所謂 算符優(yōu)先分析法 就是定義算符之間的某種優(yōu)先關系，借助于這種關系尋找 “ 可歸約串 ” 和進行歸約 。對于任何一對終結符 a、 b，我們說： 1. a≒ b 當且僅當文法 G中含有形如P→… ab… 或 P→… aQb… 的產(chǎn)生式； ? 如