一種數學運算。
基本介紹
- 中文名：優先函式
- 外文名：Precedence function
- 分類：入棧優先函式和比較優先函式
- 方法：Bell方法和Floyd方法
函式定義,有向圖法,構造方法,
函式定義
無論是簡單優先分析還是算符優先分析，都需要一個優先矩陣，用來指示各符號對間的優先關係。如果在編譯程式工作時，把優先矩陣存放在記憶體中，則勢必占用大量的存儲空間。例如，對於一個100階的優先矩陣，它的元素共有10 000個，而每一元素至少需用兩個二進位表示 (因為每個符號對間都有4種可能的狀態之一)，故存放這樣的矩陣共需20 000個二進位，即2 500個位元組。因此就很有必要尋找一種既反映符號對間的優先關係，而所需的存儲空間又不太大的表示方法。
通常，解決上述問題的一個途徑是根據所給的優先矩陣 (在下面的討論中，我們將不對簡單優先文法和算符優先文法加以區分，因為討論所得的結論對兩者都是適用的)，構造兩個離散函式f和g，並用它們去代替原來的優先矩陣，此f和g把符號Si映射為自然數，且滿足：
當Si<·Sj時，f(Si)<·g(Sj)
當Si=·Sj時，f(Si)=·g(Sj)
當Si>·Sj時，f(Si)>·g(Sj)
我們把f和g分別稱為入棧優先函式和比較優先函式。顯然，如果這樣的函式能夠構造出來，那么，在用優先分析法進行語法分析的過程中，每當需要查詢一個符號對(Si,Sj)間的優先關係時，就只須比較f(Si)和g(Sj)的大小即可。這樣一來，就把記錄優先關係所需的存儲空間由n2個單位壓縮至2n個單位。因此，我們通常把上述做法稱為優先矩陣的線性化。例如，對於算符優先文法G[E]的優先矩陣 (見圖46)，經線性化之後，可得如下的優先函式。
[]+[]*[]([])[]i[]#f[]2[]4[]0[]4[]4[]0g[]1[]3[]5[]0[]5[]0
在介紹構造優先函式的具體方法之前，我們先指出下面的重要事實：
(1) 不是所有的優先矩陣都能線性化。例如，優先矩陣
[]S1[]S2[]S3S1[]>·[]<·S2[][]=·[]<·S3[]=·[][]=·
就不能線性化。這是因為，若假定優先函式f和g存在，則由上述矩陣所給出的優先關係，f和g應滿足
f(S1)>g(S1)f(S3)=g(S1)f(S3)=g(S3)
f(S2)<g(S3)f(S2)=g(S2)f(S1)<g(S2)
但另一方面，從上述關係式可以推出
f(S1)>f(S1)
這就出現了矛盾，故可知滿足上述關係的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個符號S1,S2,…,Sn (若G為簡單優先文法，Si∈V∪{#}；若G為算符優先文法，則Si∈VT∪{#}，下同)，如果優先函式f,g存在，則可按如下的步驟來構造：
(1) 對於每一Si，分別作以fi和gi為標記的結點，並按下述方式構造以f1,f2,…,fn及g1,g2,…,gn為結點的有向圖：
若有Si>·Sj或Si=·Sj，則從結點fi引一條至結點gj的矢線；若有Si<·Sj或Si=·Sj，則從結點gj引一條至結點fi的矢線。
(2) 對有向圖中每一結點，我們都賦給一個整數，此整數就是從該結點出發，沿著矢線所能到達的結點個數 (包括出髮結點在內)，賦給結點fi的整數就是函式值f(Si)；賦給結點gi的整數就是函式值g(Si)。
(3) 對所構造的函式f和g進行檢驗，若它們與原優先關係相容，則f和g即為所求的優先函式；否則，原優先矩陣就不能線性化。
構造方法
對於給定的優先矩陣，如果它可以線性化，也可按下面的算法求出它的優先函式f和g。
1)首先，給f和g賦初值，即對每一符號Si，置
f(Si)=g(Si)=1(i=1,2,…,n)
2)進行疊代，即對每一符號對(Si,Sj)：
(1) 若Si>·Sj，但有f(Si)≤g(Sj)，則執行f(Si)=g(Sj)+1；
(2) 若Si<·Sj，但有f(Si)≥g(Sj)，則g(Sj)=f(Si)+1；
(3) 若Si=·Sj，但f(Si)≠g(Sj)，則令f(Si)和g(Sj)中的最小者等於其中的最大者。
3)重複步驟2，直到過程收斂為止。
