算符優先分析法：它只考慮算符（終結符）之間的優先關係，分析掃描每個規約式的算符間優先關係。
算符文法：即它的任一產生式的右部都不含兩個相繼的非終結符的文法。如果G是一個不含空字元的算法文法，那么只要它的任一對終結符都至多只滿足>，=，<的關係的其中一種，則稱g是一個算符優先文法。< p=""><!--的關係的一種，則稱g是一個算符優先文法。
基本介紹
- 中文名：算符優先分析法
- 類別1：構造FirstVT集的算法
- 類別2：構造LastVT集的算法
- 類別3：構造優先表的算法
算符文法,構造FirstVT集的算法,構造LastVT集的算法,構造優先表的算法,算符優先算法,
算符文法
分類
對於一個算符優先文法，只要能構造出它的算符優先表，就可以利用算符優先分析方法，分析一個句子是否符合這個文法的定義。
那么定義FirstVT(P)={a|P(+=>)a···或P(+=>)Qa···，a屬於終結字元集，而Q屬於非終結字元集}，其中···表示所有字元集
LastVT（P）={a|P(+=>)···a或P(+=>)···aQ，a屬於終結字元集，而Q屬於非終結字元集}
由以下兩條規則來構造FirstVT集：
(1) 若有產生式P=>a···、或P=>Qa···，則a屬於FirstVT（P）；
(2) 若有a屬於FirstVT（Q），且有產生式P=>Q···，則a屬於FirstVT(P);
類似的有構造LastVT集的規則：
(1) 若有產生式P=>···a或P=>···aQ，則a屬於LastVT集。
(2) 若a屬於LastVT（Q），且有產生式P=>···Q，則a屬於LastVT（P）集。
構造FirstVT集的算法
Begin
For 每個非終結符P和終結符a Do F[P，a]=FALSE；
For 每個形如P=>a···或P=>Qa···的產生式……（1）
DO insert（P，a）
While Stack 非空 Do
Begin
把Stack 的頂項，記為（Q，a），上托出去；
For每條形如P=>Q···的產生式DO …….（2）
Insert（P，a）
End of while；
END
構造LastVT集的算法
將上述算法的對應的（1），（2）分別修改為
For 每個形如P-〉…a或P-〉…aQ的產生式,
For每條形如P-〉…Q的產生式
便可得。
假定G是一個不含空字元產生式的算符文法。對於任何一對終結符a,b,
(1)a=b,若且唯若G中含有形如P－>…ab…或P－>…aQb…的產生式；
(2)a<b, 若且唯若G中含有形如P－>…aR…的產生式,而R－〉b…或R->Qb…；
(3)a>b, 若且唯若G中含有形如P－>…Rb…的產生式,而R－>…a或R->…aQ；
這樣再結合上次的FirststVT和LastVT集的概念便可以由文法自動構造出算符優先表。
再定義一個素短語的概念：它至少含有一個終結符，並且，除它自身之外不再含任何更小的素短語，所謂最左素短語就是處於句型最左邊的素短語。而一個算符優先文法G的任何句型的最左素短語是滿足以下條件的最左子串NaNb…NcNdN(N是非終結符，a,b,c,d是終結符)
a<b b=…=c c>d
這樣形成一個駝峰結構，當找到這樣一個子串的時候，它們優先權相等的一段就可以歸約為一個非終結符，否則報錯。
因此算符優先文法分析就是找到這樣的字串並歸約，最終所有終結符都被成功歸約為##時表明這個句子符合所定義的文法要求。
構造優先表的算法
For每條產生式P－〉X1X2…Xn DO
For i=1;to n-1 Do
Begin
If xi和xi+1 均為終結符 then 置 xi=xi+1
If i<=n-2 且 xi 和 xi+2都為終結符
但Xi+1為非終結 then 置 xi=xi+1
If xi為終結符而xi+1為非終結符 then
For FirstVt(xi+1)中的每個a DO
置 xi<a;
If xi為非終結符而xi+1為終結符 then
For LastVt(xi)中的每個a DO
置 a>xi;
END
算符優先算法
K=1; s[k]=’#’
Repeat
把下一個輸入符號讀進a中；
Ifs[k]屬於Vt，then j=k else j=k-1;
While s[j]> a do
Begin
Reapeat
Q=s[j];
If s[j-1]屬於Vt then j=j-1 else j=j-2
Until s[j]<Q
把s[j+1]…s[k]歸約某個N；
K=j+1
S[k]=N
End of while
If s[j]<a or s[j]=a then
Begin k=k+1; s[k]=a end
Else 出錯
UNTIL a=’#’
