優先函數

無論是簡單優先分析還是算符優先分析，都需要一個優先矩陣，用來指示各符號對間的優先關係。如果在編譯程序工作時，把優先矩陣存放在內存中，則勢必佔用大量的存儲空間。例如，對於一個100階的優先矩陣，它的元素共有10 000個，而每一元素至少需用兩個二進位表示 (因為每個符號對間都有4種可能的狀態之一)，故存放這樣的矩陣共需20 000個二進位，即2 500個位元組。因此就很有必要尋找一種既反映符號對間的優先關係，而所需的存儲空間又不太大的表示方法。

通常，解決上述問題的一個途徑是根據所給的優先矩陣 (在下面的討論中，我們將不對簡單優先文法和算符優先文法加以區分，因為討論所得的結論對兩者都是適用的)，構造兩個離散函數f和g，並用它們去代替原來的優先矩陣，此f和g把符號映射為自然數，且滿足：

當時，

當時，

當時，

我們把f和g分別稱為入棧優先函數和比較優先函數。顯然，如果這樣的函數能夠構造出來，那麼，在用優先分析法進行語法分析的過程中，每當需要查詢一個符號對間的優先關係時，就只須比較和的大小即可。這樣一來，就把記錄優先關係所需的存儲空間由個單位壓縮至2n個單位。因此，我們通常把上述做法稱為優先矩陣的線性化。例如，對於算符優先文法G[E]的優先矩陣 (見圖46)，經線性化之後，可得如下的優先函數。

#

在介紹構造優先函數的具體方法之前，我們先指出下面的重要事實：

(1) 不是所有的優先矩陣都能線性化。例如，優先矩陣

就不能線性化。這是因為，若假定優先函數f和g存在，則由上述矩陣所給出的優先關係，f和g應滿足

但另一方面，從上述關係式可以推出

這就出現了矛盾，故可知滿足上述關係的f和g並不存在。

(2) 對給定的優先矩陣而言，若優先函數存在，則必存在無窮多對，即優先函數不惟一。例如，對於文法G[E]，除上述優先函數之外，以下所示也是它的優先函數。

[]+[]*[]([])[]i[]#f[]3[]5[]1[]5[]5[]1g[]2[]4[]6[]1[]6[]1

(3) 當一個優先矩陣線性化后，就對每一符號都賦予了一對優先數。這樣一來，對於那些原先不存在關係的符號對 (如G[E]中的符號對(i,i)等)，也可比較其優先數了，因而在語法分析過程中，就可能掩蓋 (至少推遲發現)輸入串中的語法錯誤。對此問題，需要通過其它語法檢查手段來解決。

下面，我們介紹兩種將優先矩陣線性化的方法。

設已給的優先文法G[S]有n個符號(若G為簡單優先文法，{#}；若G為算符優先文法，則{#}，下同)，如果優先函數f,g存在，則可按如下的步驟來構造：

(1) 對於每一，分別作以和為標記的結點，並按下述方式構造以及為結點的有向圖：

若有或，則從結點fi引一條至結點的矢線；若有或，則從結點引一條至結點的矢線。

(2) 對有向圖中每一結點，我們都賦給一個整數，此整數就是從該結點出發，沿著矢線所能到達的結點個數 (包括出髮結點在內)，賦給結點fi的整數就是函數值；賦給結點的整數就是函數值。

(3) 對所構造的函數f和g進行檢驗，若它們與原優先關係相容，則f和g即為所求的優先函數；否則，原優先矩陣就不能線性化。

對於給定的優先矩陣，如果它可以線性化，也可按下面的演演算法求出它的優先函數f和g。

1)首先，給f和g賦初值，即對每一符號，置

2)進行迭代，即對每一符號對 ：

(1) 若，但有，則執行；

(2) 若，但有，則；

(3) 若，但，則令和中的最小者等於其中的最大者。

3)重複步驟2，直到過程收斂為止。