第6章自底向上優(yōu)先分析法

第6章自底向上優(yōu)先分析法自底向上分析方法自底向上分析方法，也稱移進-歸約分析法。實現(xiàn)思想：對輸入符號串自左向右進行掃描，并將輸入符逐個移入一個后進先出棧中，邊移入邊分析，一旦棧頂符號串形成某個句型的句柄時，（該句型對應(yīng)某產(chǎn)生式的右部），就用該產(chǎn)生式的非終結(jié)符代替相應(yīng)右部的文法符號串，這稱為。重復(fù)這一過程直到歸約到棧中只剩文法的開始符號時則為分析成功，也就確認(rèn)輸入串是文法的句子。S10）#aAcBe#歸約(S→aAcBe)文法G[S]：

(1)S→aAcBe

(2)A→b

(3)A→Ab

(4)B→dabbcde步驟符號棧輸入符號串動作1）#abbcde#移進2）#abbcde#移進A3）#abbcde#歸約(A→b)4）#aAbcde#移進A5）#aAbcde#歸約(A→Ab)6）#aAcde#移進7）#aAcde#移進B8）#aAcde#歸約(B→d)9）#aAcBe#移進11）#S#接受分析符號串a(chǎn)bbcde是否為G[S]的句子？對輸入串a(chǎn)bbcde#的移進-規(guī)約分析過程SaAcBeaAcdeaAbcdeabbcde算法應(yīng)考慮的問題算法是否能夠終止？算法是否快速？算法是否能夠處理所有的情況？在每一步中如何選擇子串進行歸約？自下而上語法分析的策略：移進-規(guī)約分析。移進就是將一個終結(jié)符推進棧。歸約就是將0個或多個符號從棧中彈出，根據(jù)產(chǎn)生式將一個非終結(jié)符壓入棧。移進-歸約過程是自頂向下最右推導(dǎo)的逆過程（規(guī)范歸約）。簡單優(yōu)先分析法對一個文法按一定原則求出該文法所有符號（終結(jié)符和非終結(jié)符）之間的優(yōu)先關(guān)系，按照這種關(guān)系確定歸約過程中的句柄，它的歸約實際上是一種規(guī)范歸約。算符優(yōu)先分析法只規(guī)定算符（終結(jié)符）之間的優(yōu)先關(guān)系。找到句柄就歸約，不是規(guī)范歸約。優(yōu)先分析法簡單優(yōu)先分析法按照文法符號（包括終結(jié)符和非終結(jié)符）的優(yōu)先關(guān)系確定句柄。文法G[S]：

(1)S→bAb

(2)A→(B|a

(3)B→Aa)

步驟符號棧輸入符號串動作1）#b(aa)b##<b,移進2）#b(aa)b#b<(,移進3）#b(aa)b#(<a,移進4）#b(aa)b#a>a,歸約A→a5）#b(Aa)b#A=a,移進6）#b(Aa)b#a=),移進7）#b(Aa)b#)>b,歸約B→Aa)8）#b(Bb#B>b,歸約A→(B9）#bAb#A=b,移進10）#bAb#b>#,歸約S→bAb11）#S#接受對輸入串b(aa)#的簡單優(yōu)先分析過程簡單優(yōu)先關(guān)系矩陣優(yōu)先關(guān)系優(yōu)先關(guān)系X=Y文法G中存在產(chǎn)生式A→...XY...X<Y文法G中存在產(chǎn)生式A→...XB...，

且BY...X>Y文法G中存在產(chǎn)生式A→...BD...，

且B...X,DY...如何確定兩個文法符號之間的優(yōu)先關(guān)系？返回調(diào)用簡單優(yōu)先文法的定義滿足以下條件的文法是簡單優(yōu)先文法（1）在文法符號集V中，任意兩個符號之間最多只有一種優(yōu)先關(guān)系成立。（2）在文法中任意兩個產(chǎn)生式?jīng)]有相同的右部。（3）不含空產(chǎn)生式。簡單優(yōu)先分析法根據(jù)已知優(yōu)先文法構(gòu)造相應(yīng)優(yōu)先關(guān)系矩陣，并將文法的產(chǎn)生式保存，設(shè)置符號棧S，算法步驟如下：將輸入符號串a(chǎn)1a2a3...an#依次逐個存入符號棧S中，直到遇到棧頂符號ai的優(yōu)先性>下一個待輸入符號aj時為止。棧頂當(dāng)前符號ai為句柄尾，由此向左在棧中找句柄的頭符號ak，即找到ak-1<ak為止。由句柄ak...ai在文法的產(chǎn)生式中查找右部為ak...ai的產(chǎn)生式，若找到則用相應(yīng)左部代替句柄，若找不到則為出錯，這時可斷定輸入串不是該文法的句子。重復(fù)上述三步，直到歸約完輸入符號串，棧中只剩文法的開始符號為止。如何確定優(yōu)先關(guān)系？文法G[S]：

(1)S→bAb

(2)A→(B|a

(3)B→Aa)

1.求=關(guān)系：由(1)：b=A A=b由(2)：(=B由(3)：A=a a=)2.求<關(guān)系：由(1)(2)：b<(b<a由(2)(3)：(<A(<((<a3.求>關(guān)系：由(1)：B>b a>b )>b由(3)：B>a a>a )>a4.#<所有符號，所有符號>#查看關(guān)系定義算符優(yōu)先分析法某些文法具有“算符”特性表達(dá)式運算符（優(yōu)先級、結(jié)合性）人為地規(guī)定其算符的優(yōu)先順序，即給出優(yōu)先級別和同一級別的結(jié)合性只考慮算符之間的優(yōu)先關(guān)系來確定句柄文法G[E]：E→E+E|E-E|E*E|E/E|EE|(E)|i步驟符號棧輸入符號串動作1）#i+i*i##<i,移進2）#i+i*i##<i>+,規(guī)約3）#E+i*i##<+,移進4）#E+i*i#+<i,移進5）#E+i*i#+<i>*,規(guī)約6）#E+E*i#+<*,移進7）#E+E*i#*<i,移進8）#E+E*i#*<i>#,規(guī)約9）#E+E*E#+<*>#,規(guī)約10）#E+E##<+>#,規(guī)約11）#E#接受對輸入串i+i*i的算符優(yōu)先分析過程算符優(yōu)先關(guān)系表如何確定算符優(yōu)先關(guān)系？i的優(yōu)先級最高優(yōu)先級次于i，右結(jié)合*和/優(yōu)先級次之，左結(jié)合+和-優(yōu)先級最低，左結(jié)合括號‘(’,‘)’的優(yōu)先級大于括號外的運算符，小于括號內(nèi)的運算符，內(nèi)括號的優(yōu)先性大于外括號#的優(yōu)先性低于與其相鄰的算符文法G[E]：E→E+E|E-E|E*E|E/E|EE|(E)|i算符優(yōu)先關(guān)系表算符文法的定義定義如果不含空產(chǎn)生式的上下文無關(guān)文法G中沒有形如U…VW…的產(chǎn)生式，其中V,W∈VN則稱G為算符文法（OG）。性質(zhì)1：在算符文法中任何句型都不包含兩個相鄰的非終結(jié)符.(數(shù)學(xué)歸納法)性質(zhì)2：如Vx或xV出現(xiàn)在算符文法的句型中，其中V∈VN,x∈VT,則中任何含x的短語必含有V.（反證法）算符優(yōu)先關(guān)系的定義在OG中定義（算符優(yōu)先關(guān)系）x=yG中有形如.U…xy…或U

…xVy..的產(chǎn)生式。x<yG中有形如.U

…xW…的產(chǎn)生式,而 Wy….或WVy…

x>yG中有形如.U

…Wy…的產(chǎn)生式,而 W…x或W…xV規(guī)定若Sx…或SVx…

則#<x若S…x或S…xV則x>#算符優(yōu)先文法的定義在OG文法G中，若任意兩個終結(jié)符間至多有一種算符優(yōu)先關(guān)系存在，則稱G為算符優(yōu)先文法(OPG)。

注意：允許b>c,c>b;不允許b>c,b<c,b=c

結(jié)論：算符優(yōu)先文法是無二義的。算符優(yōu)先關(guān)系表的構(gòu)造由定義直接構(gòu)造由關(guān)系圖法構(gòu)造算符優(yōu)先關(guān)系表首先引入兩個概念FIRSTVT(B)={b|Bb…或BCb...}對于非終結(jié)符B，其往下推導(dǎo)所可能出現(xiàn)的首個算符。LASTVT(B)={a|B…a或B...aC}對于非終結(jié)符B，其往下推導(dǎo)所可能出現(xiàn)的最后一個算符。如何計算算符優(yōu)先關(guān)系1)‘=‘關(guān)系直接看產(chǎn)生式的右部，若出現(xiàn)了

A→…ab…或A→…aBb,則a=b。2)’<‘關(guān)系求出每個非終結(jié)符B的FIRSTVT(B)，若A→…aB…,則b∈FIRSTVT(B),則a<b。3)’>’關(guān)系求出每個非終結(jié)符B的LASTVT(B)，若A→…Bb…,則a∈LASTVT(B),則a>b。文法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}1)‘=’關(guān)系

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

#=#，（=）

2）‘<’關(guān)系

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

#E：則#<FIRSTVT(E)

+T:則+<FIRSTVT(T)

*F:則*<FIRSTVT(F)

F:則<FIRSTVT(F)

(E:則(<FIRSTVT(E)3)‘>’關(guān)系

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

E#,則LASTVT(E)>#

E+,則LASTVT(E)>+

T*,則LASTVT(T)>*

P,則LASTVT(P)>

E),則LASTVT(E)>)算符優(yōu)先分析算法歸約過程中，只考慮終結(jié)符之間的優(yōu)先關(guān)系來確定句柄，而與非終結(jié)符無關(guān)。這樣去掉了單非終結(jié)符的歸約，所以用算符優(yōu)先分析法的規(guī)約過程與規(guī)范歸約是不同的，P110.為解決在算符優(yōu)先分析過程中如何尋找句柄，引進最左素短語的概念。最左素短語算符文法的任一句型有如下形式：

#N1a1N2a2......NnanNn+1#,若Niai......NjajNj+1為句柄，則有ai-1<ai=ai=...=aj-1=aj>ai+1對于算符優(yōu)先文法，如果aNb(或ab)出現(xiàn)在句型r中若a<b，則在r中必含有b而不含a的短語存在。若a>b，則在r中必含有a而不含b的短語存