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

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

(1)S→aAcBe

(2)A→b

(3)A→Ab

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

(1)S→bAb

(2)A→(B|a

(3)B→Aa)

步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#b(aa)b##<b,移進(jìn)2）#b(aa)b#b<(,移進(jìn)3）#b(aa)b#(<a,移進(jìn)4）#b(aa)b#a>a,歸約A→a5）#b(Aa)b#A=a,移進(jìn)6）#b(Aa)b#a=),移進(jìn)7）#b(Aa)b#)>b,歸約B→Aa)8）#b(Bb#B>b,歸約A→(B9）#bAb#A=b,移進(jìn)10）#bAb#b>#,歸約S→bAb11）#S#接受對(duì)輸入串b(aa)#的簡(jiǎn)單優(yōu)先分析過程簡(jiǎn)單優(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...如何確定兩個(gè)文法符號(hào)之間的優(yōu)先關(guān)系？返回調(diào)用簡(jiǎn)單優(yōu)先文法的定義滿足以下條件的文法是簡(jiǎn)單優(yōu)先文法（1）在文法符號(hào)集V中，任意兩個(gè)符號(hào)之間最多只有一種優(yōu)先關(guān)系成立。（2）在文法中任意兩個(gè)產(chǎn)生式?jīng)]有相同的右部。（3）不含空產(chǎn)生式。簡(jiǎn)單優(yōu)先分析法根據(jù)已知優(yōu)先文法構(gòu)造相應(yīng)優(yōu)先關(guān)系矩陣，并將文法的產(chǎn)生式保存，設(shè)置符號(hào)棧S，算法步驟如下：將輸入符號(hào)串a(chǎn)1a2a3...an#依次逐個(gè)存入符號(hào)棧S中，直到遇到棧頂符號(hào)ai的優(yōu)先性>下一個(gè)待輸入符號(hào)aj時(shí)為止。棧頂當(dāng)前符號(hào)ai為句柄尾，由此向左在棧中找句柄的頭符號(hào)ak，即找到ak-1<ak為止。由句柄ak...ai在文法的產(chǎn)生式中查找右部為ak...ai的產(chǎn)生式，若找到則用相應(yīng)左部代替句柄，若找不到則為出錯(cuò)，這時(shí)可斷定輸入串不是該文法的句子。重復(fù)上述三步，直到歸約完輸入符號(hào)串，棧中只剩文法的開始符號(hào)為止。如何確定優(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.#<所有符號(hào)，所有符號(hào)>#查看關(guān)系定義算符優(yōu)先分析法某些文法具有“算符”特性表達(dá)式運(yùn)算符（優(yōu)先級(jí)、結(jié)合性）人為地規(guī)定其算符的優(yōu)先順序，即給出優(yōu)先級(jí)別和同一級(jí)別的結(jié)合性只考慮算符之間的優(yōu)先關(guān)系來確定句柄文法G[E]：E→E+E|E-E|E*E|E/E|EE|(E)|i步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#i+i*i##<i,移進(jìn)2）#i+i*i##<i>+,規(guī)約3）#E+i*i##<+,移進(jìn)4）#E+i*i#+<i,移進(jìn)5）#E+i*i#+<i>*,規(guī)約6）#E+E*i#+<*,移進(jìn)7）#E+E*i#*<i,移進(jìn)8）#E+E*i#*<i>#,規(guī)約9）#E+E*E#+<*>#,規(guī)約10）#E+E##<+>#,規(guī)約11）#E#接受對(duì)輸入串i+i*i的算符優(yōu)先分析過程算符優(yōu)先關(guān)系表如何確定算符優(yōu)先關(guān)系？i的優(yōu)先級(jí)最高優(yōu)先級(jí)次于i，右結(jié)合*和/優(yōu)先級(jí)次之，左結(jié)合+和-優(yōu)先級(jí)最低，左結(jié)合括號(hào)‘(’,‘)’的優(yōu)先級(jí)大于括號(hào)外的運(yùn)算符，小于括號(hào)內(nèi)的運(yùn)算符，內(nèi)括號(hào)的優(yōu)先性大于外括號(hào)#的優(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：在算符文法中任何句型都不包含兩個(gè)相鄰的非終結(jié)符.(數(shù)學(xué)歸納法)性質(zhì)2：如Vx或xV出現(xiàn)在算符文法的句型中，其中V∈VN,x∈VT,則中任何含x的短語(yǔ)必含有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中，若任意兩個(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)系表首先引入兩個(gè)概念FIRSTVT(B)={b|Bb…或BCb...}對(duì)于非終結(jié)符B，其往下推導(dǎo)所可能出現(xiàn)的首個(gè)算符。LASTVT(B)={a|B…a或B...aC}對(duì)于非終結(jié)符B，其往下推導(dǎo)所可能出現(xiàn)的最后一個(gè)算符。如何計(jì)算算符優(yōu)先關(guān)系1)‘=‘關(guān)系直接看產(chǎn)生式的右部，若出現(xiàn)了

A→…ab…或A→…aBb,則a=b。2)’<‘關(guān)系求出每個(gè)非終結(jié)符B的FIRSTVT(B)，若A→…aB…,則b∈FIRSTVT(B),則a<b。3)’>’關(guān)系求出每個(gè)非終結(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)先分析過程中如何尋找句柄，引進(jìn)最左素短語(yǔ)的概念。最左素短語(yǔ)算符文法的任一句型有如下形式：

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