簡單優先文法

編譯程序的工作過程通常是詞法分析、語法分析、語義分析、代碼生成、代碼優化。編譯程序的這些過程的執行先後就構成了編譯程序的邏輯結構，但是這些邏輯結構不一定是按照某一個固定順序的，也有可能是按照平行或者互鎖的方式執行的。

簡單優先分析文法的基本思想是對一個文法按一定的原則求出該文法所有符號包括終結符和非終結符之間的優先關係，按照這種關係確定規約過程中的句柄，它的規約過程實際上是規範規約。在演演算法實現過程中，主要使用visual C++進行編程。

簡單優先分析方法

·一種shift-reduce分析方法

·根據文法符號的優先關係確定句柄

·文法符號的優先關係的確定

簡單優先分析中的三種關係

X≌Y ：當且僅當存在一個產生式A→…XY…X<|Y ：當且僅當存在一個產生式A→…XB…

並有B=>Y…。X|>Y ：當且僅當存在一個產生式A→…BC…

並有B=>…X，C=>Y…。

文法G為簡單優先文法如果滿足：對於任意兩個語法符號X和Y，至多成立一種 優先關係；任意兩個產生式都具有不同的右部。

文法優先關係的確定

FIRST(W) ={S | W=>S…，S∈(VN∪VT)}LAST(W) ={S | W=>…S，S∈(VN ∪VT)}

若有U→…SiSj…: 則有Si ≌ Sj ;若有U→…SIW…:則有Si<|Sj，且Sj∈FIRST(W)若有U→…VW…:則有Si|>Sj ，且Si∈LAST(V),

Sj∈(FIRST(W)∪{W})。

輸入流的結束標誌 ‘#’，文法的開始符為Z，#<|S，S∈FIRST(Z); 且#<|Z

S|>#，S∈LAST(Z); 且Z|># 簡單優先分析演演算法要點

找第一個使Sj|>Sj+1的Sj從Sj開始往前(左)找第一個使Si-1<|Si的Si用SiSi+1…Sj去查產生式的右部，並用相應的左部符號代替句柄SiSi+1…Sj (歸約) 。重複上述過程，直至輸入符結束。如果歸約出文法的開始符號則成功。否則失敗。