自底向上優先分析法第一頁，共五十四頁，編輯于2023年，星期三第06章自底向上優先分析法自底向上優先分析概述簡單優先分析法算符優先分析法第二頁，共五十四頁，編輯于2023年，星期三自底向上分析方法概述自底向上分析方法，也稱移進-歸約分析法。實現思想是對輸入符號串自左向右進行掃描，并將輸入符逐個移入一個后進先出棧中，邊移入邊分析，一旦棧頂符號串形成某個句型的句柄時，就用該產生式的左部非終結符代替相應右部的文法符號串，這稱為一步歸約。重復這一過程直到歸約到棧中只剩文法的開始符號時則為分析成功，也就確認輸入串是文法的句子。示例第三頁，共五十四頁，編輯于2023年，星期三abbcde步驟符號棧輸入符號串動作1）# abbcde# 移進2）#a bbcde# 移進A3）#ab bcde# 歸約(A→b)4）#aA bcde# 移進A5）#aAb cde# 歸約(A→Ab)6）#aA cde# 移進7）#aAc de# 移進B8）#aAcd e# 歸約(B→d)9）#aAcB e# 移進11）#S # 接受S10）#aAcBe# 歸約(S→aAcBe)分析符號串abbcde是否G[S]的句子對輸入串abbcde#的移進-規約分析過程SaAcBeaAcdeaAbcdeabbcde最右推導：示例文法G[S]：

(1)S→aAcBe

(2)A→b

(3)A→Ab

(4)B→d第四頁，共五十四頁，編輯于2023年，星期三簡單優先分析法按照文法符號（包括終結符和非終結符）的優先關系確定句柄。定義優先關系簡單優先文法優先關系矩陣：表示文法符號之間關系的矩陣。算法示例第五頁，共五十四頁，編輯于2023年，星期三優先關系X

?Y：表示X、Y的優先關系相同，當且僅當文法G中存在產生式A→...XY…；X?Y：表示X的優先性比Y的要低，當且僅當文法G中存在產生式A→...XB...，且BY...X?Y：表示X的優先性比Y的要高，當且僅當文法G中存在產生式A→...BD...，且B...X，DY優先關系的定義第六頁，共五十四頁，編輯于2023年，星期三簡單優先文法的定義滿足以下條件的文法是簡單優先文法：（1）在文法符號集V中，任意兩個符號之間最多只有一種優先關系成立；（2）在文法中任意兩個產生式沒有相同的右部。第七頁，共五十四頁，編輯于2023年，星期三簡單優先分析法——算法根據已知優先文法構造相應優先關系矩陣，并將文法的產生式保存，設置符號棧S，算法步驟如下：將輸入符號串a1a2a3...an#依次逐個存入符號棧S中，直到遇到棧頂符號ai的優先性.>下一個待輸入符號aj時為止。棧頂當前符號ai為句柄尾，由此向左在棧中找句柄的頭符號ak，即找到ak-1?ak為止。由句柄ak...ai在文法的產生式中查找右部為ak...ai的產生式，若找到則用相應左部代替句柄，若找不到則為出錯，這時可斷定輸入串不是該文法的句子。重復上述三步，直到歸約完輸入符號串，棧中只剩文法的開始符號為止。第八頁，共五十四頁，編輯于2023年，星期三簡單優先文法分析示例文法G[S]：(1)S→bAb(2)A→(B|a(3)B→Aa)1、確定文法符號之間的關系2、求出文法的簡單優先關系矩陣3、對輸入串進行分析（輸入串b(aa)b#）第九頁，共五十四頁，編輯于2023年，星期三確定文法符號之間的關系1.求?關系：由(1)：b?A A?b由(2)：(?B由(3)：A?a a?)2.求?關系：由(1)(2)：b?(b?a由(2)(3)：(?A(?((?a3.求?關系：由(1)：B?b a?b )?b由(3)：B?a a?a )?a第十頁，共五十四頁，編輯于2023年，星期三求出文法的簡單優先關系矩陣“#”用來表示語句括號，其優先關系低于所有與其有相鄰關系的文法符號。第十一頁，共五十四頁，編輯于2023年，星期三對輸入串進行分析（輸入串b(aa)b#）步驟符號棧輸入符號串動作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#接受文法G[S]：

(1)S→bAb

(2)A→(B|a

(3)B→Aa)

第十二頁，共五十四頁，編輯于2023年，星期三算符優先分析法某些文法具有“算符”特性表達式運算符（優先級、結合性）；人為地規定其算符的優先順序，即給出優先級別和同一級別的結合性；只考慮算符之間的優先關系來確定句柄。定義算符文法算符優先關系算法優先文法最左素短語算符優先關系表的構造算符優先分析法概述算符優先文法的性質算符優先分析算法優先函數算符優先分析法的局限性第十三頁，共五十四頁，編輯于2023年，星期三算符文法的定義如果不含空產生式的上下文無關文法G中沒有形如U…BC…的產生式，其中B，C∈VN，則稱G為算符文法（OperaterGrammar，OG）。性質1：在算符文法中任何句型都不包含兩個相鄰的非終結符。（歸納法）2：如Vx或xV出現在算符文法的句型中，其中V∈VN,x∈VT,則中任何含x的短語必含有V。（反證法）第十四頁，共五十四頁，編輯于2023年，星期三用歸納法設是句型，即S?*S=ω0?ω1?...?ωn-1?ωn=推導長度為n，歸納起點n=1時，S=ω0?ω1=

，即S?，必存在產生式S→，而由算符文法的定義，文法的產生式中無相鄰的非終結符，顯然滿足性質1。假設n＞1,ωn-1滿足性質1。若ωn-1=A，A為非終結符。由假設知α的尾符號和δ的首符號都不可能是非終結符，否則與假設矛盾。又若A→是文法的產生式，則有ωn-1?ωn==而A→是文法的原產生式，不含兩個相鄰的非終結符，所以也不含兩個相鄰的非終結符。滿足性質1。證畢。第十五頁，共五十四頁，編輯于2023年，星期三反證法因為由算符文法的性質1知可有：S?*=bAβ若存在B?*b，這時b和A不同時歸約，則必有S?*BAβ,這樣在句型BAβ中存在相鄰的非終結符B和A，所以與性質1矛盾，證畢。注意：含b的短語必含A，含A的短語不一定含b。第十六頁，共五十四頁，編輯于2023年，星期三算符優先關系的定義設G是不含產生式的文法,a、b是任意兩個終結符，A、B、C是非終結符，算符優先關系的定義如下：a?b當且僅當G中有形如A…ab…或A…aBb…的產生式。

a?b當且僅當G中有形如A…aB…的產生式,且B?+b…或B?+Cb…a?b當且僅當G中有形如A…Bb…的產生式,且B?+…a或B?…aC注意：算符優先關系中不存在遞推關系，即a?bb?c?a?c或a?bb?c?a?c或a?bb?c?a?c優先關系的語法樹表示方式第十七頁，共五十四頁，編輯于2023年，星期三優先關系的語法樹表示方式第十八頁，共五十四頁，編輯于2023年，星期三算符優先文法的定義設G是不含產生式的算符文法,如果對任意兩個終結符對a、b之間至多只有一種算符優先關系存在，則稱G為算符優先文法。

結論

算符優先文法是無二義的。第十九頁，共五十四頁，編輯于2023年，星期三算符優先關系表的構造集合的定義：FIRSTVT(B)={b|B?+b…或B?+Cb...}對于非終結符B，其往下推導所可能出現的首個算符（終結符）LASTVT(B)={a|B?+…a或B?+...aC}對于非終結符B，其往下推導所可能出現的最后一個算符（終結符）構造方式：由定義直接構造由關系圖法構造構造算法第二十頁，共五十四頁，編輯于2023年，星期三由定義計算算符優先關系直接計算算法計算關系圖計算第二十一頁，共五十四頁，編輯于2023年，星期三直接計算算符優先關系‘?‘關系直接看產生式的右部，若出現了

A→…ab…或A→…aBb,則a?b’?‘關系求出每個非終結符B的FIRSTVT(B)若A→…aB…,則b∈FIRSTVT(B),a?b’?’關系求出每個非終結符B的LASTVT(B)若A→…Bb…,則a∈LASTVT(B),a?b示例第二十二頁，共五十四頁，編輯于2023年，星期三直接計算示例文法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)?關系

由產生式(0)和(6),得

#?#，（?）3)?關系

找形如：A→…Bb…的產生式

E#,則LASTVT(E)?#

E+,則LASTVT(E)?+

T*,則LASTVT(T)?*

P,則LASTVT(P)?

E),則LASTVT(E)>)2）?關系

找形如：A→…aB…的產生式

#E：則#?FIRSTVT(E)

+T:則+?FIRSTVT(T)

*F:則*?FIRSTVT(F)

F:則?FIRSTVT(F)

(E:則(?FIRSTVT(E)

+*↑i()#+???????*???????↑???????i???

??(??????

)???

??#?????

?第二十三頁，共五十四頁，編輯于2023年，星期三算法計算算符優先關系算法規則：1、若有產生式Aa…或ABa…，則aFIRSTVT(A)，其中A、B為非終結符，a為終結符；2、若aFIRSTVT(B)且有產生式ABb…，則有aFIRSTVT(A)。算法：文本描述按規則1對每個數組元素F[A，a]賦初值，并對數組元素F[A，a]初值為真的符號對(A．a)都放入棧中，然后對棧做如下運算。當棧不空時，就將棧頂項彈出，并記為(B，a)，再用規則2，若F[A，a]為假，則使其變為真，且將(A，a)推進棧，如此重復直到棧折空為止。程序描述示例第二十四頁，共五十四頁，編輯于2023年，星期三程序描述將置為真的操作：PROCEDUREINSERT(A．a);IFNOTF[A，a]THENBEGINF[A．a]：＝TRUNPUSH(A．a)0NT0STRACKEND主程序：BEGIN(MAIN)FOR每一個非終結符A和終結符a，DOF[A，a]：＝FALSE；FOR每個形如Aa··或ABa…的產生式DOINSERT(A，a)WHILESTACK非空DOBEGIN把STACK的頂項記為(B，a)托出去FOR每個形如AB…的產生式DoINSERT(A，a)ENDEND第二十五頁，共五十四頁，編輯于2023年，星期三算法計算示例文法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→i首次掃描STRACK的初值：

(6)(P,i)

(5)(P,()

(4)(F,)

(3)(T,*)

(2)(E,+)

(1)(E’,#)棧頂（6）的改變：

FP(F,i)

TF(T,i)

ET(E,i)由于無右部以E開始的產生式，所以(E,i)彈出后無進棧項，此時當前的棧頂為(P,()。棧頂（5）的改變：

FP(F,()

TF(T,()

ET(E,()(E,（)彈出后無進棧項，此時當前的棧頂為(F,)。棧頂（4）的改變：

TF(T,)

ET(E,)(E,)彈出后無進棧項，此時當前的棧頂為(T,*)。棧頂（3）的改變：

ET(E,*)以下逐次彈出棧頂元素后，都再無進棧項，直至棧空。

+*↑i()#E’

1E11111

T

111

F

111

P

11

FIRSTVT(E’)={#}

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

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

FIRSTVT(F)={,(,i}

FIRSTVT(P)={(,i}第二十六頁，共五十四頁，編輯于2023年，星期三關系圖計算算符優先關系關系圖的構造方法圖中的結點為非終結符的FIRSTVT(A)和終結符;對每一個形如Aa…或ABa…的產生式，則構造由FIRSTVT(A)結點到終結符結點(a)用箭弧連接的圖形；對每一個形如AB…的產生式，則對應圖中由FIRSTVT(A)結點到FIRSTVT(B)結點用箭弧連接；對每一非終結符的FIRSTVT(A)經箭弧有路徑能到達的終結符結點(a)，則有aFIRSTVT(A)。示例第二十七頁，共五十四頁，編輯于2023年，星期三關系圖計算示例FIRSTVT(E’)FIRSTVT(E)FIRSTVT(T)FIRSTVT(F)FIRSTVT(P)#+*()文法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→i第二十八頁，共五十四頁，編輯于2023年，星期三由關系圖法計算算符優先關系文法符號的關系定義優先關系與符號關系之間的聯系算符關系構造規則?的關系構造規則?的關系構造規則示例文法符號之間的關系文法終結符之間的?關系圖文法終結符之間的?關系圖第二十九頁，共五十四頁，編輯于2023年，星期三文法符號的關系定義（6.4）設G=(VN，VT，P，S)是一個上下文無關文法，則：AFIRSTB當且僅當存在形如AB?的產生式；ALASTB當且僅當存在形如A?B的產生式；BFIRSTTERMb當且僅當存在形如Bb?或BCb?的產生式；BLASTTERMa當且僅當存在形如B?a或B?aC的產生式；XFOLLOWEDBYY當且僅當存在形如A?XY?的產生式，中必須是一個為終結符，另一個為非終結符；AFIRST*B當且僅當存在形如AB或存在AX1?，X1X2?，?，Xn-1Xn?，XnB?的產生式序列；ALAST*B當且僅當存在形如BA或存在A?X1，X1?X2，?，Xn-1?Xn，Xn?B的產生式序列。第三十頁，共五十四頁，編輯于2023年，星期三優先關系與符號關系之間的聯系a?b?aFOLLOWEDBYBBFIRST*PPFIRSTTERMba?b?存在形如A?aB?的產生式,其中B?+b?或B?+Cb?而B?+b?可寫成B?*P??b?

B?+Cb?可寫成B?*P??Cb?所以B?+b?或B?+Cb??BFIRST*PPFIRSTTERMba?b?(BLAST*PPLASTTERMa)TBFOLLOWEDBYba?b?存在形如A?Bb?的產生式,其中B?+a?或B?+aC?而B?+?

a可寫成B?*?

P??a

B?+?

aC可寫成B?*?

P??aC所以B?+?

a或B?+?

aC?BLAST*PPLASTTERMa第三十一頁，共五十四頁，編輯于2023年，星期三?的關系構造規則凡有終結符在前非終結符在后相鄰關系的，則由終結符結點到非終結符結點畫一箭弧。對有FIRSTTERM關系的非終結符和終結符對，則從非終結符結點到終結符點畫一箭弧。對非終結符對之間存在FIRST關系的，從左邊的非終結符結點到右邊的非終結符結點畫一箭弧。對每個終結符結點a凡有路徑能到達另一終結符結點b的，則有a?b關系存在。第三十二頁，共五十四頁，編輯于2023年，星期三?的關系構造規則對非終結符和終結符相鄰關系的，由非終結符結點到終結符結點畫一箭弧。對有LASTTERM關系的，由終結符結點到非終結符結點畫一箭弧。對LAST關系的非終結符對，由后面的非終結符結點到前面的非終結符結點畫一箭弧。對每個終結符結點a凡有路徑能到達另一終結符結點b的，則有a?b的關系成立。第三十三頁，共五十四頁，編輯于2023年，星期三文法符號之間的關系ELASTTTLASTFFLASTFFLASTPFIRST關系有EFIRSTEEFIRSTTTFIRSTTTFIRSTFFFIRSTPFIRSTTBRM關系有EFIRSTTBRM+TFIRSTTBRM*FFIRSTTBRM

PFIRSTTBRM(PFIRSTTBRMi終結符在前非終結符在后的相鄰關系有#FOLLOWEDBYE(FOLLOWEDBYE+FOLLOWEDBYT*FOLLOWEDBYF

FOLLOWEDBYFELASTTERM+TLASTTERM*FLASTTERM

PLASTTERM)PLASTTERMiEFOLLOWEDBY#EFOLLOWEDBY+EFOLLOWEDBY)TFOLLOWEDBY*PFOLLOWEDBY文法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→i第三十四頁，共五十四頁，編輯于2023年，星期三文法終結符之間的?關系圖FP+*(i#+(*ET第三十五頁，共五十四頁，編輯于2023年，星期三文法終結符之間的?關系圖P+*(i#+(*ETF第三十六頁，共五十四頁，編輯于2023年，星期三構造文法的優先關系算法for(每個產生式A→X1X2…Xn)

for(i=1;i<=n-1;i++)

{

if(Xi和Xi+1均為終結符)置Xi?Xi+1

；

if(i≤n-2且Xi和Xi+2均為終結符,但Xi+1為非終結符)

置Xi?Xi+1

；

if(Xi為終結符,Xi+1為非終結符)

for(FIRSTVT(Xi+1)中的每個b)置Xi?b;

if(Xi為非終結符,Xi+1為終結符)

for(LASTVT(Xi)中的每個a)置a?Xi+1;

};第三十七頁，共五十四頁，編輯于2023年，星期三最左素短語文法G[S]句型的素短語是這樣一個短語，它至少包含一個終結符號，并且，除它自身之外，不再包含其他素短語。最左素短語是指處于句型最左邊的那個素短語。算符優先文法句型的最左素短語是唯一的。示例查找最左素短語的方法：在句型中加入優先關系，例如：i+i*i

#?i

i?+

+?i

i?*

*?i

i?#1、找最左素短語的右端；從左至右掃描符號串直至遇到第一個?為止。2、找最左素短語的左端；然后向回掃描(向左)越過任何?，直至一個?被發現。3、歸約；可歸約串包括在第1步所遇到的?的左邊和第2步所遇到的?的右邊的所有終結符號，包括插入在中間的或環繞在兩旁的非終結符號。第三十八頁，共五十四頁，編輯于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

i最左素短語為：T*F素短語：T*F，i*EET++ETFFTTi句型T+T*F+i的語法樹最左素短語示例第三十九頁，共五十四頁，編輯于2023年，星期三算符優先分析法概述1.算符優先分析法是一種特別有利于表達式分析，宜于手工實現的語法分析方法。2.算符優先分析過程是自下而上的歸約過程，但未必是嚴格的最左歸約，因此，它不是一種規范歸約法。3.所謂算符優先分析法就是仿效算術表達式的運算過程而設計的一種語法分析方法；這種方法的關鍵在于規定算符（終結符）的優先順序和結合性質。示例第四十頁，共五十四頁，編輯于2023年，星期三算符優先分析法示例文法G[E]：

(1)E→E+T(2)E→T(3)T→T*F(4)T→F

(5)F→(E)(7)F→i對輸入串i+i#的規約過程：規范規約算符優先規約第四十一頁，共五十四頁，編輯于2023年，星期三規范規約示例步驟棧剩余輸入串句柄歸約用產生式1#i+i#

2#i+i#iF→i3#F+i#FT→F4#T+i#TE→T5#E+i#

6#E+i#

7#E+i#iF→i8#E+F#FT→F9#E+T#E+FE→E+T10#E#

接受第四十二頁，共五十四頁，編輯于2023年，星期三算符優先規約示例步驟棧優先關系當前符號剩余輸入串移進或歸約1#?ii+i#移進2#i?++i#歸約3#F?++i#移進4#F+?i#移進5#F+i?#

歸約6#F+F?#

歸約7#F?#

接受第四十三頁，共五十四頁，編輯于2023年，星期三算符優先文法的性質對于算符優先文法，如果aNb(或ab)出現在句型r中,則之間有且僅有一種優先關系，即：若a?b，則在r中必含有b而不含a的短語存在；若a?b，則在r中必含有a而不含b的短語存在；若a?b，則在r中含有a的短語必含有b，反之亦然。算符文法的任一句型有如下形式：

#N1a1N2a2......NnanNn+1#,若Niai......NjajNj+1為句柄，則Ni、

Nj+1在句柄中，且該句柄中終結符之間的關系為：ai-1?aiai?ai+1?...?aj-1?ajaj?ai+1第四十四頁，共五十四頁，編輯于2023年，星期三算符優先分析算法算符優先分析歸約的關鍵是尋找最左素短語。開始當前輸入符讀入a置初值k=1,S[k]=‘#’S[k]VT?S[j]?a?S[j]?a?j=kj=k-1Q=S[j]S[j-1]VT?j=j-1j=j-2S[j]?Q?S[j+1]?S[k]歸約為Nk=j+1S[k]=NK=k+1S[k]=aS[j].=a?S[j].=#?出錯檢查是否正常結束？結束YNNYYYNNYYYYYNNN第四十五頁，共五十四頁，編輯于2023年，星期三優先函數定義構造方法由定義進行構造由關系圖進行構造示例通過定義計算優先函數關系通過關系圖計算優先函數關系優先函數分析的特點第四十六頁，共五十四頁，編輯于2023年，星期三優先函數定義定義兩個函數f、g，滿足如下條件：當a?b，則令f(a)＝g(b)當a?b，則令f(a)＜g(b)當a?b，則令f(a)＞g(b)對f、g可稱它為優先函數。優先函數的值可以用整數表示。對優先函數每個元素的值都增加同一個常數，優先關系不變，所以對同一個文法的優先關系矩陣對應的優先函數不唯一。有一些優先關系矩陣中的優先關系是唯一的，卻不存在優先函數。示例第四十七頁，共五十四頁，編輯于2023年，星期三由定義構造優先函數若已知文法G終結符之間的優先關系，可按如下步驟構造其優先函數f，g:a)對每個終結符a?VT(包括#在內)令f(a)＝g(a)＝1(也可是其它整數)。b)如果a?b，而f(a)≤g(b)，則令f(a)＝g(b)+1c)如果a?b而f(a)≥g(b)，則令g(b)＝f(a)+1d)如果a?b，而f(a)≠g(b)，則令

min{f(a)，g(b)}=max{f(a)，g(b)}e)重復b)~d)直到過程收斂。如果重復過程中有一個值大于2n，則表明該算符優先文法不存在算符優先函數。第四十八頁，共五十四頁，編輯于2023年，星期三由關系圖構造優先函數a對所有終結符a(包括‘#’)用有下腳標的fa，gb為結點名，畫出2n個結點。b若ai?aj；或ai?aj

，則從fai到gaj畫一條箭弧。c若ai?aj；或ai?aj，則從gaj到fai畫一條箭弧。d給每個結點賦一個數，此數等于從該結點出發所能到達的結點(包括該結點自身在內)的個數。賦結結點fai的數，就是函數f(ai)的值，賦給gaj的數，就是函數g(aj)