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