算符優(yōu)先分析

算符優(yōu)先分析第一頁，共十五頁，編輯于2023年，星期三算符優(yōu)先分析自下而上分析算法模型----移進歸約算符優(yōu)先分析不是規(guī)范歸約算符優(yōu)先分析的可歸約串是句型的最左素短語定義cfg（上下文無關文法）G的句型的素短語是一個短語，它至少包含一個終結符，且除自身外不再包含其他素短語。處于句型最左邊的素短語為最左素短語文法G[S]SαAδ且A則稱是句型α

δ相對于非終結符A的短語

第二頁，共十五頁，編輯于2023年，星期三文法G[E]：

(1)E→E+T

(2)E→T

(3)T→T*F

(4)T→F

(5)F→PF|P

(6)P→(E)

(7)P→i句型T+T*F+i

其短語有：

T+T*F+i

T+T*F

T

T*F

iEET++ETF*FTTi最左素短語為：T*F句型T+T+F的素短語為：T+TE++TFE句型T+T+i的素短語為：i素短語為：T*F，iETTi第三頁，共十五頁，編輯于2023年，星期三分析程序模型

總控程序算符優(yōu)先關系表產(chǎn)生式輸入串##輸出第四頁，共十五頁，編輯于2023年，星期三如何確定算符優(yōu)先關系？人為確定：（1）i的優(yōu)先級最高（1）優(yōu)先級次于i，右結合（2）*和/優(yōu)先級次之，左結合（3）+和-優(yōu)先級最低，左結合（4）括號‘(’,‘)’的優(yōu)先級大于括號外的運算符，小于括號內(nèi)的運算符，內(nèi)括號的優(yōu)先性大于外括號（5）#的優(yōu)先性低于與其相鄰的算符文法G[E]：E→E+E|E-E|E*E|E/E|EE|(E)|i算符優(yōu)先關系表第五頁，共十五頁，編輯于2023年，星期三算符優(yōu)先文法的定義定義：如果不含空產(chǎn)生式的上下文無關文法G中沒有形如A…BC…的產(chǎn)生式，其中B，C∈VN則稱G為算符文法（OG）。例7.1G[E]：E→E+E|E-|E*E|E/E|EE|(E)|i例7.2G’[E]:E→E＋T|TT→T*F|FF→P↑F｜PP→(E)|i性質(zhì)1：在算符文法中任何句型都不包含兩個相鄰的非終結符.性質(zhì)2：如Ab

或bA出現(xiàn)在算符文法的句型中，其中A∈VN，b∈VT，則中任何含b

的短語必含有A。第六頁，共十五頁，編輯于2023年，星期三算符優(yōu)先關系在OG中定義

（算符優(yōu)先關系）

a=bG中有形如：A…ab…

或A…aBb...的產(chǎn)生式。

a<bG中有形如:A…aB…的產(chǎn)生式, 而

Bb…或BCb…a>bG中有形如:A…Bb…的產(chǎn)生 式,而

B…a

或B…aC

規(guī)定

若

Sa…或

SCa…則

#

<

a

若

S…a

或

S…aC則

a

>

#第七頁，共十五頁，編輯于2023年，星期三在OG文法G中，若任意兩個終結符間至多有一種算符優(yōu)先關系存在，則稱G為算符優(yōu)先文法(OPG)。注意：允許b>c,c>b;不允許b>c,b<c,b=c中任兩個同時存在。b=c不一定c=b。例7.1中：“（”=“）”，“）”<>“（”。

結論:算符優(yōu)先文法是無二義的。第八頁，共十五頁，編輯于2023年，星期三算符優(yōu)先關系表的構造首先定義如下兩個集合：FIRSTVT(B)=｛b｜Bb…或BCb…｝LASTVT(B)=｛a｜B…a或B…aC｝按如下算法計算出給定文法中任何兩個終結符對(a,b)之間的優(yōu)先關系：

1)‘=‘關系直接看產(chǎn)生式的右部，若出現(xiàn)了

A→…ab…或A→…aBb,則a=b2)’<‘關系求出每個非終結符B的FIRSTVT(B)若A→…aB…,則b∈FIRSTVT(B),則a<b3)’>’關系求出每個非終結符B的LASTVT(B)若A→…Bb…,則a∈LASTVT(B),則a>b第九頁，共十五頁，編輯于2023年，星期三計算算符優(yōu)先關系例文法G’[E’]：

(0)E’→#E#

(1)E→E+T

(2)E→T

(3)T→T*F

(4)T→F

(5)F→PF|P

(6)P→(E)

(7)P→iFIRSTVT(E’)={#}

FIRSTVT(E)={+,*,,(,i}

FIRSTVT(T)={*,,(,i}

FIRSTVT(F)={,(,i}

FIRSTVT(P)={(,i}

LASTVT(E’)={#}

LASTVT(E)={+,*,,),i}

LASTVT(T)={*,,),i}

LASTVT(F)={,),i}

LASTVT(P)={),i}第十頁，共十五頁，編輯于2023年，星期三(0)E’→#E#(1)E→E+T(2)E→T(3)T→T*F(4)T→F

(5)F→PF|P(6)P→(E)(7)P→i

3)‘>’關系

找形如：A→…Bb…的產(chǎn)生式

E#:則LASTVT(E)>#

E+:則LASTVT(E)>+

T*:則LASTVT(T)>*

P:則LASTVT(P)>

E):則LASTVT(E)>)2）‘<’關系

找形如A→…aB…的產(chǎn)生式

#E：則#<FIRSTVT(E)

+T:則+<FIRSTVT(T)

*F:則*<FIRSTVT(F)

F:則<FIRSTVT(F)

(E:則(<FIRSTVT(E)1)‘=’關系

由產(chǎn)生式(0)和(6),得

#=#，(

=)第十一頁，共十五頁，編輯于2023年，星期三

表達式文法G’[E’]的算符優(yōu)先關表第十二頁，共十五頁，編輯于2023年，星期三算符優(yōu)先分析算法算符優(yōu)先文法句型的性質(zhì)算符文法的任何一個句型應為如下形式：＃N1a1N2a2...NnanNn+1＃其中Nk(1≤k≤n+1)為非終結符或空，ak(1≤k≤n)為終結符算符優(yōu)先文法句型的最左素短語NiaiNi+1ai+1...NjajNj+1滿足：ai-1

＜aiai=ai+1=……=aj-1=ajaj

＞aj+1即：ai-1<ai=ai-1=...=aj-1=aj>aj+1第十三頁，共十五頁，編輯于2023年，星期三

1k:=1;S[k]:=“#”2 repeat

read

下一符號到a;3 ifS[k]Vtthenj:=kelsej:=k-1;4 whileS[j]>ado5 {repeat6 Q:=S[j];7 ifS[j-1]Vtthenj:=j-18 elsej:=j-29 untilS[j]<Q;10將

S[j+1]S[j+2]…S[k]歸約到某個N;//11 k:=j+1;12 S[k]:=N;13 }14 if(S[j]<aorS[j]