【正文】 Y Y Y N N N 優(yōu)先函數(shù) ? 定義 ? 構造方法 ? 由定義進行構造 ? 由關系圖進行構造 ? 示例 ? 通過定義計算優(yōu)先函數(shù)關系 ? 通過關系圖計算優(yōu)先函數(shù)關系 ? 優(yōu)先函數(shù)分析的特點 優(yōu)先函數(shù)定義 ? 定義兩個函數(shù) f、 g ， 滿足如下條件： ? 當 a?b， 則令 f(a)＝ g(b) ? 當 a?b， 則令 f(a)＜ g(b) ? 當 a?b， 則令 f(a)＞ g(b) ? 對 f、 g可稱它為優(yōu)先函數(shù)。 ? 優(yōu)先函數(shù)的值可以用整數(shù)表示。 ? 對優(yōu)先函數(shù)每個元素的值都增加同一個常數(shù)，優(yōu)先關系不變，所以對同一個文法的優(yōu)先關系矩陣對應的優(yōu)先函數(shù)不唯一。 ? 有一些優(yōu)先關系矩陣中的優(yōu)先關系是唯一的，卻不存在優(yōu)先函數(shù)。 ? 示例 由定義構造優(yōu)先函數(shù) ? 若已知文法 G終結符之間的優(yōu)先關系，可按如下步驟構造其優(yōu)先函數(shù) f， g: ? a)對每個終結符 a?VT(包括 在內(nèi) )令 f(a)＝ g(a)＝ 1 (也可是其它整數(shù) )。 ? b)如果 a?b， 而 f(a) ≤g(b)， 則令 f(a)＝ g(b)+1 ? c)如果 a?b而 f(a)≥g(b) ， 則令 g(b)＝ f(a)+1 ? d)如果 a?b， 而 f(a)≠g(b) ， 則令 min{f(a)， g(b)}=max{f(a)， g(b)} ? e)重復 b)~d)直到過程收斂。 ? 如果重復過程中有一個值大于 2n， 則表明該算符優(yōu)先文法不存在算符優(yōu)先函數(shù)。 由關系圖構造優(yōu)先函數(shù) ? a對所有終結符 a(包括‘ ’)用有下腳標的 fa， gb為結點名，畫出 2n個結點。 ? b若 ai ?aj； 或 ai ?aj ， 則從 fai到 gaj畫一條箭弧。 ? c若 ai ?aj； 或 ai ?aj， 則從 gaj到 fai畫一條箭弧。 ? d給每個結點賦一個數(shù)，此數(shù)等于從該結點出發(fā)所能到達的結點 (包括該結點自身在內(nèi) )的個數(shù)。賦結結點 fai的數(shù)，就是函數(shù) f(ai)的值，賦給 gaj的數(shù)，就是函數(shù) g(aj)的值。 ? e對構造出的優(yōu)先函數(shù)，按優(yōu)先關系矩陣檢查一遍是否滿足優(yōu)先關系的條件，若不滿足時，則在關系圖中有回路說明不存在優(yōu)先函數(shù)。 由定義計算優(yōu)先函數(shù)關系示例 ? 其優(yōu)先函數(shù)的構造過程為： ? 首先；把所有 f(a)、g(a)的值置為 1如右表中的初值 (0次迭代 )。 ? 然后對算符優(yōu)先關系矩陣遠行掃描，按前述算法規(guī)則的 b)~e)修改函數(shù) f(a)， g(a)的值，這是個迭代過程，一直進行到優(yōu)先函數(shù)的值再無變化為止 (收斂 )。 + * ↑ i ( ) + ? ? ? ? ? ? ? * ? ? ? ? ? ? ? ↑ ? ? ? ? ? ? ? i ? ? ? ? ? ( ? ? ? ? ? ? ) ? ? ? ? ? ? ? ? ? ? ? 迭代次數(shù) + * ↑ i ( ) 0(初值 ) f 1 1 1 1 1 1 1 g 1 1 1 1 1 1 1 1 f 2 4 4 6 1 5 1 g 2 3 5 5 5 1 1 2 f 3 5 5 7 1 7 1 g 2 4 6 6 6 1 1 3 f 3 5 5 7 1 7 1 g 2 4 6 6 6 1 1 由關系圖計算優(yōu)先函數(shù)關系示例 i * + i ? ? ? * ? ? ? ? + ? ? ? ? ? ? ? ? i * + f 6 6 4 2 g 7 5 3 2 fi gi g* f* f+ g+ g f 不存在優(yōu)先函數(shù)關系示例 ? 由于若存在優(yōu)先函數(shù) f， g， 則必定滿足下列條件： ? 由矩陣的第一行應有 f(a)＝ g(a)， f(a)＞ g(b) ? 由矩陣的第二行應有 f(b)＝ g(a)， f(b)＝ g(b) ? 這樣導致有 f(a)＝ g(a)＝ f(b)＝ g(b) ? 與 f(a)＞ g(b)矛盾，因而優(yōu)先函數(shù)不存在。 a b a ? ? b ? ? fa fb ga gb a b f 4 4 g 4 4 優(yōu)先函數(shù)分析的特點 ? 優(yōu)點： ? 占用空間少 。 ? 缺點： ? 在利用優(yōu)先關系矩陣進行優(yōu)先分析時，當兩個終結符對無優(yōu)先關系的情況時，優(yōu)先關系矩陣的相應元素為 出錯信息 ， ? 用優(yōu)先函數(shù)進行優(yōu)先分析時，對兩個終結符對沒有優(yōu)先關系時不能區(qū)分，因而出錯時 不能準確地指出錯誤位置 。 ? 例如： ? 若有表達式 i+ii*i在分析過程中只能在匹配產(chǎn)生式時，用算符優(yōu)先文法的性質 (任何句型不可能有相鄰的非終結符出現(xiàn) )或對于表達式可用運算對象和運算符相間的方式檢查是否出錯。如例中表達式串當歸約到 N十 NN… 可發(fā)現(xiàn)錯誤，是由于句型中有兩個相鄰的非終結符，而不是由于 ii不能相鄰。 ? 表達式為 i+i*i(i+i)按算符優(yōu)先矩陣‘ i’與‘ (’無優(yōu)先關系，當歸約分析 N十 N*i時，能即時發(fā)現(xiàn)錯誤，而用優(yōu)先函數(shù)分析則此時發(fā)現(xiàn)不了錯誤，直到歸約到 N+N*NN時，才能由兩非終結符相鄰的出現(xiàn)而發(fā)現(xiàn)錯誤，因而不能準確指出錯誤位置。 算符優(yōu)先分析法的局限性 ?一般語言的文法很難滿足算符優(yōu)先文法的條件； ?很難避免把錯誤的句子得到正確的歸約； ?算符優(yōu)先分析法僅適用于表達式的語法分析。