定義
設G=(VN，VT,P,S)是一已化簡的文法，V=VN∪VT，並設Si和Sj是V中的任意兩個符號，若G中存在這樣的規範句型
α=…SiSj…
則此相鄰的兩個符號Si，Sj和α的句柄之間的關係必然是下述情況之一：
(1) 若Si在句柄中，而Sj不在句柄中 (如圖42(a)所示)，則Si顯然為句柄的尾符號，故G中必有形如A→…Si的產生式，使Si先於Sj被歸約。此時，我們就說符號Si優於Sj，且記為Si>· Sj。此外，由於Sj出現在規範句型的句柄之右，故可知Sj必為終結符號。
(2) 若Si與Sj同時處於α的句柄之中 (如圖42(b)所示)，則G中必有形如A→…SiSj…的產生式，使Si和Sj同時被歸約。此時，我們就說Si和Sj有相同的優先關係，且記為Si=·Sj。
(3) 若Sj在句柄中，而Si不在句柄之中 (如圖42(c)所示)，則Sj顯然為句柄的頭符號，故G中必有形如A→Sj…的產生式，使Sj先於Si被歸約。此時就Si和Sj的優先關係而言，我們說Si低於Sj且記為Si<·Sj。
(4) 若Si和Sj均不在句型α的句柄之中，由於Si和Sj已相鄰地在α中出現，則必有G的另一規範句型β，使Si和Sj在β中相鄰地出現，且與β的句柄的關係有上述三種情況之一。然而，也可能有這樣的情況，對G中的某些符號序偶(Sr,St)而言，G中並不存在任何使Sr和St相鄰出現的句型，此時我們就說Sr和St間不存在任何優先關係。
應當指出，上面所引入的三種優先關係都是對文法中的符號序偶來定義的，它們都不具有對稱性。即若Sr>· St，並不一定有St<·Sr；即使存在Sr=·St也不意味著St=·Sr必然存在。
定義了上述三種優先關係之後，我們便可給出所謂簡單優先文法的定義如下。
定義4?1若一文法G的任何兩個符號之間至多存在一種優先關係，且任意兩個不同的產生式均無相同的右部，則稱G為簡單優先文法。
現在的問題是： 對於一個給定的文法G來說，如何找出它的各個符號序偶間的優先關係?如何檢驗G是否為簡單優先文法?顯然，實質上這是同一問題的兩個方面。因為，如果我們有辦法找出G的各符號序偶間的優先關係，則第二個問題也就迎刃而解了。
繼續考慮其它句型的語法樹，我們就可得到G中的全部優先關係。通常，我們把一個文法的全部優先關係用一個矩陣來表示，稱為優先矩陣。優先矩陣中的每一個元素P[i,j]指明序偶(Si,Sj)間的優先關係。當序偶(Sr,St)不存在優先關係時，相應的元素P[r,t]則為空白。從所得的優先矩陣可以看出，文法的各符號序偶間至多只有一種優先關係，故此文法為簡單優先文法。
上面，我們通過查看文法的若干句型來構造優先矩陣。稍後我們還要介紹一種更為有效的構造優先矩陣的方法。
算法
應當指出，我們之所以把具有上述性質的文法稱為簡單優先文法，是因為在進行語法分析時，為了尋找一個句型的句柄之頭符號和尾符號，只須逐次查看相鄰兩個符號的優先關係即可。具體地說，也就是從左至右依次掃視句型中的符號X1X2…Xm，並在掃描過程中檢查相鄰兩符號間的優先關係，一旦出現關係Xi+k>·Xi+k+1時，此Xi+k即為句柄的尾符號。然後再從Xi+k開始，從右至左逐個查看已掃過的符號，直到某相鄰的兩個符號間有優先關係Xi-1<·Xi時，此Xi為句柄的頭符號。事實上，我們可以證明： 對於簡單優先文法的任何規範句型X1X2…Xm而言，它的句柄是該句型中，滿足
Xi-1<·Xi
Xi=·Xi+1=·…=·Xi+k
Xi+k>·Xi+k+1
的最左子串XiXi+1…Xi+k。
據此，我們給出採用簡單優先分析方法的識別程式如程式44所示。
程式 44簡單優先分析驅動程式
#define SUCCESS1
#define ERROR0
#define MAXINPUT300
#define MAXSTACK100
#define STARTSYMBOL ′S′
int stack[MAXSTACK], a[MAXINPUT];
int IsHigherThan (int, int);/*prioriy detection*/
int IsLowerThan (int, int);/*prioriy detection*/
int RightSideOfAProduction (int begin, int end, int len);/*find production*/
int parscr (void)
{int i,k,r;
i=0; k=0;
stack[0]=′#′;
r=a[k++];
do {int j, LeftSide;
while (!IsHigherThan(stack[i],r))
{stack[++i]=r; r=a[k++];}
j=i;
while (!IsLowerThan (stack[j-1],stack[j]))j--;
LeftSide=RightSideOfAProduction (stack[j],stack[i],i-j+1);
if (LeftSide)
{/* LeftSide!=0 means the production exists*/
i=j; stack[i]=LeftSide;
}
else /*There is no production which matches the right side*/
if (i==2 && r==′#′ && stack[i]==STARTSYMBOL) return SUCCESS;
else return ERROR;
}while(1);
}/*end*/
對上述驅動程式所調用的一些函式的功能簡述如下：
(1) 函式IsHigher()和IsLower()分別用來檢測兩個文法符號Si和Sj是否具有關係Si>·Sj和Si<·Sj，並根據關係成立與否分別回送值1和值0。
(2) 函式RightSideOfAProduction()用來在產生式集之中查找這樣的產生式，其右部具有指定的頭、尾符號及指定的長度，且與出現在棧頂的句柄相匹配，若找到則回送該產生式左部非終結符號的編號 (大於零的整數)，否則回送值0。
構造方法
在上例中，為構造優先矩陣，我們首先為文法的若干句型構造相應的語法樹，然後對每一語法樹，考察它的直接子樹中的末端結點，以確定有關符號對之間的優先關係，接著便剪去此直接子樹的末端結點，並對剪枝後的語法樹再重複上述過程，如此等等。顯然，套用此種方法，有時我們需要考察足夠多的語法樹之後，才能把文法中的全部優先關係尋找出來。下面，我們再介紹一種確保一次求出全部優先關係的方法，此方法以布爾矩陣運算作為基礎。
在給出構造簡單優先矩陣的算法之前，我們先在文法G的字彙表V上，定義若干個二元關係，並據此重新定義上述三種優先關係。
定義4?2(關係LEAD)若且唯若G中存在形如A→B…的產生式時，有A LEAD B；若且唯若A?+B…時，A LEAD+B。
定義4?3(關係LAST)若且唯若G中存在形如A→…B的產生式時，有A LAST B；若且唯若A?+…B時，有A LAST+B。
定義4?4設R為一關係，我們將R的轉置記為TRANSPOSE(R)，且定義為：若且唯若aRb時，b TRANSPOSE(R) a。
定義4?5若且唯若G中存在形如U→…SiSj…的產生式時，Si=·Sj。
定義4?6若且唯若G中存在形如
U→…SiW…(4?23)
的產生式，且
W?+Sj…(4?24)
時，有Si<·Sj。
由產生式(4?23)及定義4?5，可得
Si=·W
而由推導式(4?24)及定義4?2，又得到
WLEAD+Sj
從而可知，若且唯若
Si(=·)(LEAD)+Sj(4?25)
時，Si<·Sj。
定義4?7若且唯若G中存在形如
U→…W1W2…(4?26)
的產生式，且有
W1?+…Si(4?27)
及W2?*Sj…Sj∈VT(4?28)
時，Si>· Sj。
由產生式(4?26)、推導式(4?27)及(4?28)，有
W1=·W2W1 LAST+ SiW2 LEAD* Sj
(其中，LEAD*=I+LEAD+,I為恆等關係)上面第二個關係可改寫為
Si TRANSPOSE(LAST+) W1
於是可知，若且唯若Sj∈VT，且
Si (TRANSPOSE(LAST+))(=·)(I+LEAD+) Sj(4?29)
時，有Si>· Sj，其中I為恆等關係。
現在以文法G：
S→AcA→ASA→AaA→b(4?30)
為例，介紹構造簡單優先矩陣的算法。在此過程中，需要計算上面所定義的那些關係的布爾矩陣。這些布爾矩陣的階數就是文法字彙表所含符號的個數。對於關係R的布爾矩陣，用記號BR表示，且對字彙表{S1,S2,…,Sn}中的兩個符號Si和Sj，若且唯若SiR Sj時，BR[i,j]=1，否則BR[i,j]=0，對於文法(4?30)構造相應簡單優先矩陣的步驟如下：
1?作布爾矩陣B=·，根據定義4?5，從文法(4?30)中的諸產生式可直接寫出
B=·= S[]A[]a[]b[]c〖〗S
A
a
b
c0[]0[]0[]0[]0
1[]0[]1[]0[]1
0[]0[]0[]0[]0
0[]0[]0[]0[]0
0[]0[]0[]0[]0
2?作布爾矩陣B<·，為此
(1) 作布爾矩陣
BLEAD=0[]1[]0[]0[]0
0[]1[]0[]1[]0
0[]0[]0[]0[]0
0[]0[]0[]0[]0
0[]0[]0[]0[]0
(2) 由Warshall算法[11，17]，計算
BLEAD+=0[]1[]0[]1[]0
0[]1[]0[]1[]0
0[]0[]0[]0[]0
0[]0[]0[]0[]0
0[]0[]0[]0[]0
(3) 根據(4?25)，作
B<·=B=·BLEAD+=0[]0[]0[]0[]0
1[]0[]1[]0[]1
0[]0[]0[]0[]0
0[]0[]0[]0[]0
0[]0[]0[]0[]00[]1[]0[]1[]0
0[]1[]0[]1[]0
0[]0[]0[]0[]0
0[]0[]0[]0[]0
0[]0[]0[]0[]0=0[]0[]0[]0[]0
0[]1[]0[]1[]0
0[]0[]0[]0[]0
0[]0[]0[]0[]0
0[]0[]0[]0[]0
0[]0[]0[]0[]0
3?作布爾矩陣B>· ，為此
(1) 作布爾矩陣
BLAST=0[]0[]0[]0[]1
1[]0[]1[]1[]0
0[]0[]0[]0[]0
0[]0[]0[]0[]0
0[]0[]0[]0[]0
(2) 計算
BLAST+=0[]0[]0[]0[]1
1[]0[]1[]1[]1
0[]0[]0[]0[]0
0[]0[]0[]0[]0
0[]0[]0[]0[]0
(3) 作布爾矩陣
BTRANSPOSE(LAST+)=0[]1[]0[]0[]0
0[]0[]0[]0[]0
0[]1[]0[]0[]0
0[]1[]0[]0[]0
1[]1[]0[]0[]0
(4) 計算
B>·′=BTRANSPOSE(LAST+)B=·BLEAD*=0[]1[]0[]0[]0
0[]0[]0[]0[]0
0[]1[]0[]0[]0
0[]1[]0[]0[]0
1[]1[]0[]0[]00[]0[]0[]0[]0
1[]0[]1[]0[]1
0[]0[]0[]0[]0
0[]0[]0[]0[]0
0[]0[]0[]0[]01[]1[]0[]1[]0
0[]1[]0[]1[]0
0[]0[]1[]0[]0
0[]0[]0[]1[]0
0[]0[]0[]0[]1=
S[]A[]a[]b[]c
S
A
a
b
c1[]1[]1[]1[]1
0[]0[]0[]0[]0
1[]1[]1[]1[]1
1[]1[]1[]1[]1
1[]1[]1[]1[]1
(5) 由於在式(4?29)中Sj應為終結符號，故為了得到B>· ，必須在上步所求得的布爾矩陣B>·′ 中，將對應於非終結符號的列置零，於是有
B>· =0[]0[]1[]1[]1
0[]0[]0[]0[]0
0[]0[]1[]1[]1
0[]0[]1[]1[]1
0[]0[]1[]1[]1
4?對於所求的B=·,B<·及B>· ，檢查如下等式
B=·∧B>·=B=·∧B<·=B>·∧B<·=0
是否成立。若是，則表明所構造的簡單優先矩陣無多重定義的元素，因而所給文法為簡單優先文法；否則，它就不是簡單優先文法。最後，將布爾矩陣B=·、B>·及B<·所分別指出的優先關係組裝到一個矩陣之中，便得到了所求的全部簡單優先關係。對於本例，有
[]S[]A[]a[]b[]cS[4]>·[]>·[]>·A[]=·[]<·[]=·[]<·[]=·a[4]>·[]>·[]>·b[4]>·[]>·[]>·c[4]>·[]>·[]>·
局限性
從前面的討論已看到： 上述優先分析技術簡單易行，已有一套構造簡單優先矩陣的形式化算法，從設計分析程式到具體地進行語法分析都可機械地進行。看來，它似乎是一種可靠和有效的方法，其實在套用上，它卻有很大的局限性。這主要表現在對文法有較強的要求。因為對通常的文法而言，它的某些符號對之間的優先關係往往會多於一種，也就是說，所給的文法常常並非簡單優先文法。特別是當文法具有左遞歸時，就往往會導致這種情況的發生。例如，當文法中同時含有形如
U→…SiSj…
及
Sj→Sj…
的產生式時，在符號Si和Sj之間，便同時有Si=·Sj及Si<·Sj兩種關係。類似地，當文法具有右遞歸性時，關係=·及>· 也可能出現在同一符號對之間。
為避免上述矛盾，我們可在文法中引入一新的非終結符號W，而將上面的第一個產生式改寫為如下兩個產生式
U→…SiW…
W→Sj…
此時，優先關係Si=·Sj及Si<·Sj將為新的優先關係Si=·W及Si<·Sj所代替，從而就解決了上述矛盾。通常，將改寫文法的這種方法稱為分層法或析出法。
然而，應當指出，上述採用分層技術消除多重優先關係的嘗試未必總能得到成功。例如，當Si和Sj間既有Si<·Sj也同時有關係Si>·Sj時，上述方法就不能奏效。有時也可能出現這樣的情況，即舊的矛盾雖然解決了，但又引出新的矛盾。特別是對於一些規模較大，而所含矛盾又較多的文法，即使上述方法能夠取得成功，為改寫文法也十分費力。同時，由於改寫文法所引入的一些單產生式，也將增加文法的複雜性和降低語法分析的效率，因此，當我們所面臨的不是簡單優先文法時，還是以選用另外的語法分析方法為宜。此處我們之所以要介紹這種分析方法，一則因為它比較簡單；二則也是因為由它可較容易地過渡到其它更為有效的分析方法。
最後，我們再來分析一下簡單優先分析之所以存在上述缺點的內在原因。
從簡單優先文法的定義來看，在用這種方法進行分析時，為了識別一個句型的句柄，每次僅使用了句柄周圍很少的符號進行判斷，即每次只考察句型中相鄰兩符號的優先關係。可以想像，如果不再局限於相鄰的兩個符號，而是查看更多的符號，或者取另外的不相鄰的符號進行考察，則發生上述矛盾的情況可能會得到改善，例如，為了確定句柄的尾符號，我們不僅要查看Si,Si+1，而且還查看Si-1，Si和Si+1，或者Si,Si+1及Si+2，甚至更多的符號 (如像後面介紹的LR(K)分析那樣)。下面，不妨以文法G[E]中的句型E+T*F為例來說明此點。前面已經看到，G[E]不是一個簡單的優先文法，但若按簡單優先關係來考慮，就會出現下面的情況：
#<·E=·+=·
<·T*F#(4?31)
由於符號+和T之間同時存在優先關係+=·T及+<·T，若以前者為準，則+和T都應是句柄中的符號；若按後者，則T可能是句柄的頭符號，而+決不會出現在句柄中，可見，僅根據相鄰兩個符號間的優先關係尚不足以判斷T是否為句柄的頭符號，或者說+是否在句柄中。但若除考慮+和T外，再向前查看一個符號，則當句型中出現+T*這樣的結構時，由於乘法運算總是先於加法運算，所以+不可能在句柄之中；而當出現形如+T+的結構時，由於加法運算服從左結合規則，此時，最先歸約的自然應是子串E+T，即T是句柄的尾符號。顯而易見，上述這種決策實際上是根據運算符+和*或者+和+間的優先關係來作出的。於是，就自然啟發我們考慮一種更為有效的分析方法——算符優先分析法。
