第06章、自底向上優(yōu)先法

1、126.1 自底向上語(yǔ)法分析概述6.2 簡(jiǎn)單優(yōu)先分析6.3 算符優(yōu)先分析 346.1 自底向上語(yǔ)法分析概述p自底向上分析也稱移進(jìn)歸約分析，實(shí)現(xiàn)思想是對(duì)輸入符號(hào)串自左至右進(jìn)行掃描，并將輸入符逐個(gè)移入棧中，邊移入邊分析，一旦棧頂符號(hào)串形成某個(gè)句型的句柄或可歸約串（該句柄或可歸約串對(duì)應(yīng)某產(chǎn)生式的右部），就用該產(chǎn)生式的左部非終結(jié)符代替相應(yīng)右部的文法符號(hào)串，這稱為一步歸約。重復(fù)這一過(guò)程直到歸約到棧中只剩文法的開(kāi)始符號(hào)時(shí)則為分析成功，也就是確認(rèn)輸入串是文法的句子。p自底向上分析的關(guān)鍵問(wèn)題是如何確定可歸約串以進(jìn)行歸約。p自底向上語(yǔ)法分析比自上而下語(yǔ)法分析更有效率，對(duì)語(yǔ)法的限制更少。51. 歸約和語(yǔ)法分析樹(shù)

2、顯然，abbcde是該文法的一個(gè)句子，于是可如右圖構(gòu)造其語(yǔ)法分析樹(shù)。 該語(yǔ)法樹(shù)的構(gòu)造的確是一個(gè)“自左而右、自下而上”的過(guò)程，把這一類分析方法統(tǒng)稱為“自下而上”的。GE: S aAcBe A b|Ab B dabbcdeAABS6自底向上語(yǔ)法分析的策略：移進(jìn)-歸約分析；移進(jìn)就是將一個(gè)終結(jié)符推進(jìn)棧歸約就是將0個(gè)或多個(gè)符號(hào)從棧中彈出，根據(jù)產(chǎn)生式將一個(gè)非終結(jié)符壓入棧接受指宣布最終分析成功，可以把它看成是歸約的一種特殊形式；出錯(cuò)處理指發(fā)現(xiàn)棧頂?shù)膬?nèi)容與輸入串相悖，分析工作無(wú)法正常進(jìn)行。此時(shí)需調(diào)用出錯(cuò)處理程序進(jìn)行診察和校正，并調(diào)整棧頂?shù)膬?nèi)容。2. 移進(jìn)歸約7 在計(jì)算機(jī)上模擬以上的語(yǔ)法分析樹(shù)的構(gòu)造過(guò)程，可借助

3、于一個(gè)符號(hào)棧來(lái)實(shí)現(xiàn)：輸入串：abbcde#步驟：動(dòng)作：符號(hào)棧：12345678910移進(jìn)a移進(jìn)b 歸約b 移進(jìn)b 歸約Ab移進(jìn)c 移進(jìn)d歸約d歸約aAcBe移進(jìn)e歸約產(chǎn)生式：#a#ab#aA#aAb#aA#aAc#aAcd#aAcB#aAcBe#S(2)(3)(4)(1)8上述自下而上分析法就是對(duì)棧的“移進(jìn)歸約”法，更進(jìn)一步的，也就是對(duì)句子的一個(gè)規(guī)范歸約過(guò)程何為規(guī)范歸約呢？（回顧短語(yǔ)、句柄、推導(dǎo)、歸約）9短語(yǔ)、句柄的定義 10推導(dǎo)、規(guī)約的定義 是文法G的產(chǎn)生式，若有v, w滿足：v=, w=, 其中V*,V* 則稱v直接推導(dǎo)到w，記作 v w，也稱w直接歸約到v，就是說(shuō)歸約是推導(dǎo)的逆過(guò)程。 自

4、左向右的規(guī)約過(guò)程也稱規(guī)范歸約，是最右推導(dǎo)的逆過(guò)程，因此規(guī)范歸約也稱最左歸約；最右推導(dǎo)常被稱為規(guī)范推導(dǎo)，由規(guī)范推導(dǎo)得到的句型稱為規(guī)范句型。 再來(lái)看上述的例子，每一步歸約都是替換句柄：11算法應(yīng)考慮的問(wèn)題 何時(shí)移進(jìn)？ 在每一步中如何選擇子串進(jìn)行歸約？ 算法是否能夠終止？ 算法是否快速？ 算法是否能夠處理所有的情況？12歸約歸約T iT + i | 移進(jìn)移進(jìn)T + | i移進(jìn)移進(jìn)i | * i + i移進(jìn)移進(jìn)i * | i + i移進(jìn)移進(jìn)|i * i + iE |歸約歸約E T + ET + E |歸約歸約E TT + T |移進(jìn)移進(jìn)T | + i歸約歸約T i * Ti * T | + i歸約歸約

5、 T ii * i | + i文法文法GE：E T + E | TT i * T | i | (E)ETE+i*iTiT13 我們?nèi)绾螞Q定什么時(shí)候移進(jìn)，什么時(shí)候歸約？ 考慮 i | * i + i 我們可以用 T i 進(jìn)行歸約，而得到 T| * i + i 致命錯(cuò)誤: 無(wú)法歸約到開(kāi)始符號(hào) E 直覺(jué): 歸約時(shí)應(yīng)想辦法歸約到文法的開(kāi)始符號(hào) 一般的移進(jìn)-歸約策略： 若句柄在棧頂出現(xiàn)，則歸約 否則移進(jìn)14自底向上的分析算法 優(yōu)先分析法 -簡(jiǎn)單優(yōu)先分析法 -算符優(yōu)先分析法 LR分析 -LR(0) -SLR(1) -LR(1)156.2 簡(jiǎn)單優(yōu)先分析法 對(duì)一個(gè)文法按一定原則求出該文法所有符號(hào)（終結(jié)符和非終

6、結(jié)符）之間的優(yōu)先關(guān)系，按照這種關(guān)系確定歸約過(guò)程中的句柄。 它的歸約實(shí)際上是一種規(guī)范歸約。16一、簡(jiǎn)單優(yōu)先分析基本思想 1、對(duì)句型中相鄰的文法符號(hào)規(guī)定優(yōu)先關(guān)系，以尋找句型中的句柄； 2、規(guī)定句柄內(nèi)各相鄰符號(hào)之間具有相同的優(yōu)先級(jí)； 3、規(guī)定句柄兩端符號(hào)優(yōu)先級(jí)要比位于句柄之外而又和句柄相鄰的符號(hào)的優(yōu)先級(jí)高，以先歸約句柄； 4、對(duì)于文法中所有符號(hào)，只要它們可能在某個(gè)句型中相鄰，就要為它們規(guī)定相應(yīng)的優(yōu)先關(guān)系，若某兩個(gè)符號(hào)永遠(yuǎn)不可能相鄰，則它們之間就無(wú)關(guān)系。17 優(yōu)先關(guān)系 X =Y 文法G中存在產(chǎn)生式A.XY. X Y 文法G中存在產(chǎn)生式A.XB.，且B Y. X Y 文法G中存在產(chǎn)生式A.BD.，且B

7、.X,D Y. 對(duì)任何X， - 若文法開(kāi)始符號(hào)S = X，則# X，則X#。* *18優(yōu)先關(guān)系舉例 GS: S bAb (1) A (B|a (2) B Aa) (3)19 根據(jù)優(yōu)先關(guān)系的定義，將簡(jiǎn)單優(yōu)先文法中各文法符號(hào)之間的這種關(guān)系用一個(gè)矩陣表示，稱作簡(jiǎn)單優(yōu)先矩陣。 簡(jiǎn)單優(yōu)先矩陣的構(gòu)造可通過(guò)定義求出，也可通過(guò)Warshall算法實(shí)現(xiàn)。 具體方法我們不作討論。 20簡(jiǎn)單優(yōu)先關(guān)系矩陣 S b A ( B a ) # S b A ( B a ) # GS: S bAb (1) A (B|a (2) B Aa) (3) 空白處表示這兩個(gè)終結(jié)符不能相鄰，故沒(méi)優(yōu)先關(guān)系 對(duì)于與#相鄰的符號(hào)，所有符號(hào) #，

8、# 所有符號(hào)21 滿足以下條件的文法是簡(jiǎn)單優(yōu)先文法（1）在文法符號(hào)集V中，任意兩個(gè)符號(hào)之間最多只有一種優(yōu)先關(guān)系成立。（2）在文法中任意兩個(gè)產(chǎn)生式?jīng)]有相同的右部。 22 讀入一個(gè)單詞后，比較棧頂符號(hào)和該單詞的優(yōu)先級(jí)，若棧頂符號(hào)優(yōu)先級(jí)低于或等于該單詞，繼續(xù)讀入；若棧頂符號(hào)優(yōu)先級(jí)高于讀入符號(hào)，則找句柄進(jìn)行歸約，然后繼續(xù)讀入。直到最后棧內(nèi)只剩下開(kāi)始符號(hào)，輸入串讀到“”為止。此時(shí)識(shí)別正確。23文法文法GS：(1) S bAb(2) A (B|a(3) B Aa)步驟步驟符號(hào)棧符號(hào)棧輸入符號(hào)串輸入符號(hào)串動(dòng)作動(dòng)作 1） # b(aa)b# #b,移進(jìn)移進(jìn) 2） #b (aa)b# b(,移進(jìn)移進(jìn) 3） #b

9、( aa)b# (a,歸約歸約Aa 5） #b(A a)b# A=a,移進(jìn)移進(jìn) 6） #b(Aa )b# a=),移進(jìn)移進(jìn) 7） #b(Aa) b# )b,歸約歸約BAa) 8） #b(B b# Bb,歸約歸約A(B 9） #bA b# A=b,移進(jìn)移進(jìn)10） #bAb # b#,歸約歸約SbAb11） #S # 接受接受對(duì)輸入串對(duì)輸入串b(aa)b#的簡(jiǎn)單優(yōu)先分析過(guò)程的簡(jiǎn)單優(yōu)先分析過(guò)程簡(jiǎn)單優(yōu)先關(guān)系矩陣 S b A ( B a ) # S b A ( B a ) # 24 優(yōu)點(diǎn)：技術(shù)簡(jiǎn)單，準(zhǔn)確，規(guī)范 缺點(diǎn)：適用范圍小，分析表尺寸太大，分析效率低。 256.3 算符優(yōu)先分析 某些文法具有“算符”

10、特性表達(dá)式運(yùn)算符（優(yōu)先級(jí)、結(jié)合性）人為地規(guī)定其算符的優(yōu)先順序，即給出優(yōu)先級(jí)別和同一級(jí)別的結(jié)合性 只規(guī)定算符（終結(jié)符）之間的優(yōu)先關(guān)系。只考慮算符之間的優(yōu)先關(guān)系來(lái)確定句柄，找到句柄就歸約，不是規(guī)范歸約。26 1、自底向上歸約 2、規(guī)定算符(更一般地說(shuō)，指終結(jié)符)的優(yōu)先級(jí)及結(jié)合規(guī)則，以使得分析過(guò)程唯一 3、比較相鄰兩個(gè)算符而決定動(dòng)作 注：1)這里的關(guān)鍵是對(duì)所有算符定義某種優(yōu)先關(guān)系 2)直觀算符優(yōu)先分析法是仿效四則運(yùn)算的計(jì)算過(guò)程而構(gòu)造的一種語(yǔ)法分析方法 27如何確定算符優(yōu)先關(guān)系？（1）i 的優(yōu)先級(jí)最高（2） 優(yōu)先級(jí)次于i，右結(jié)合（3）*和/優(yōu)先級(jí)次之，左結(jié)合（4）+和-優(yōu)先級(jí)最低，左結(jié)合（5）括號(hào)(,

11、)的優(yōu)先級(jí)大于括號(hào)外的運(yùn)算符，小于括號(hào)內(nèi)的運(yùn)算符，內(nèi)括號(hào)的優(yōu)先級(jí)大于外括號(hào)（6）#的優(yōu)先級(jí)低于與其相鄰的算符實(shí)例：文法GE：EE+EE*EEE(E)i算符優(yōu)先關(guān)系表28文法GE：EE+EE*EEE(E)i步驟步驟符號(hào)棧符號(hào)棧輸入符號(hào)串輸入符號(hào)串動(dòng)作動(dòng)作 1） # i+i*i# #i,移進(jìn)移進(jìn) 2） #i +i*i# #+,歸約歸約 3） #E +i*i# #+,移進(jìn)移進(jìn) 4） #E+ i*i# +i,移進(jìn)移進(jìn) 5） #E+i *i# +*,歸約歸約 6） #E+E *i# +*,移進(jìn)移進(jìn) 7） #E+E* i# *i,移進(jìn)移進(jìn) 8） #E+E*i # *#,歸約歸約 9） #E+E*E # +

12、#,歸約歸約10） #E+E # #,歸約歸約11） #E # 接受接受對(duì)輸入串i+i*i的算符優(yōu)先分析過(guò)程算符優(yōu)先關(guān)系表29 定義: 設(shè)有一文法G，如果G中沒(méi)有形如 ABC的產(chǎn)生式，其中B和C為非終結(jié)符，則稱G 為算符文法（也稱OGOperator Grammar）。 性質(zhì)1：在算符文法中任何句型都不包含兩個(gè)相鄰的非終結(jié)符. 性質(zhì)2：若 Va 或 aV 出現(xiàn)在算符文法的句型 中，其中VVN,aVT, 則 中任何含 a 的短語(yǔ)必含有V.（既包含該算符左右兩邊的非終結(jié)符）30 設(shè)G是一個(gè)不包含空串產(chǎn)生式的算符文法，并設(shè)a,b VT; P,Q,R VN ，定義關(guān)系：1)a b 當(dāng)且僅當(dāng)G中含有形如

13、P ab產(chǎn)生式，或者P aRb產(chǎn)生式；2)a b 當(dāng)且僅當(dāng)G中含有形如P aR的產(chǎn)生式，且R=b, 或R = Qb;3)a b 當(dāng)且僅當(dāng)G中有形如P Rb產(chǎn)生式，且R =a，或R =aQ.規(guī)定 若 S x或 S Vx 則 # x若S x 或 S xV 則 x #+31 設(shè)有一不含產(chǎn)生式的算符文法G，若任意兩個(gè)終結(jié)符間至多存在一種算符優(yōu)先關(guān)系，則稱G 為算符優(yōu)先文法(OPGOperation Priority Grammar)。結(jié)論 算符優(yōu)先文法是無(wú)二義的。32 首先引入兩個(gè)概念 FIRSTVT(B)=b|B b或B Cb. 對(duì)于非終結(jié)符B，其往下推導(dǎo)所可能出現(xiàn)的首個(gè)算符 LASTVT(B)=a

14、|B a或B .aC 對(duì)于非終結(jié)符B，其往下推導(dǎo)所可能出現(xiàn)的最后一個(gè)算符 由定義直接構(gòu)造 由關(guān)系圖法構(gòu)造算符優(yōu)先關(guān)系表(不講)33構(gòu)造集合FIRSTVT(P)的算法 根據(jù)FIRSTVT(P)的定義，按下面的規(guī)則來(lái)構(gòu)造： (1) 若有產(chǎn)生式P a或P Qa ，則 a FIRSTVT(P) (2) 若a FIRSTVT(Q)，且有產(chǎn)生式 P Q，則 a FIRSTVT(P) 例 GS: S aAcBe A Ab|b B dFIRSTVT(S)=a FIRSTVT(A)=bFIRSTVT(B)=d34構(gòu)造集合LASTVT(P)的算法 根據(jù)LASTVT(P)的定義，按下面的規(guī)則來(lái)構(gòu)造： (1) 若有產(chǎn)

15、生式P a或P aQ ，則 a LASTVT(P) (2) 若a LASTVT(Q)，且有產(chǎn)生式P Q ，則 a LASTVT(P)例GS: S aAcBe A Ab|b B dLASTVT(S)=e LASTVT(A)=bLASTVT(B)=d35如何計(jì)算算符優(yōu)先關(guān)系1) 關(guān)系 直接看產(chǎn)生式的右部，若出現(xiàn)了A ab或A aBb,則a b2) 關(guān)系 求出每個(gè)非終結(jié)符B的FIRSTVT(B) 若AaB,則 bFIRSTVT(B),a b3) 關(guān)系 求出每個(gè)非終結(jié)符B的LASTVT(B) 若ABb,則 aLASTVT(B),a b36acebd#acebd#GS: S aAcBe A Ab|b B

16、 dFIRSTVTLASTVTS a e A b b B d d 相當(dāng)于：相當(dāng)于：#S# FIRSTVT(S)LASTVT(S) # #37例例2:文法文法GE：EE+T|E-T|T TT*F|T/F|F FP F|P P(E)|iFIRSTVT(E)=#FIRSTVT(E)=+,-,*,/, ,(,iFIRSTVT(T)=*,/, ,(,iFIRSTVT(F)= ,(,iFIRSTVT(P)=(,iLASTVT(E)=#LASTVT(E)=+,-,*,/, ,),iLASTVT(T)=*,/, ,),iLASTVT(F)= ,),iLASTVT(P)=),i1) 關(guān)系關(guān)系由產(chǎn)生式由產(chǎn)生式(0

17、)和和(6),得得# #，（，（ ）2） 關(guān)系關(guān)系找形如：找形如：AaB的產(chǎn)生式的產(chǎn)生式3) 關(guān)系關(guān)系找形如：找形如：ABb的產(chǎn)生式的產(chǎn)生式LASTVT(E) #+-*/ ()i#+-*/ ()i# 38 歸約過(guò)程中，只考慮終結(jié)符之間的優(yōu)先關(guān)系來(lái)確定句柄，而與非終結(jié)符無(wú)關(guān)。這樣去掉了單非終結(jié)符的歸約，所以用算符優(yōu)先分析法的歸約過(guò)程與規(guī)范歸約是不同的； 為解決在算符優(yōu)先分析過(guò)程中如何尋找可歸約串，引進(jìn)最左素短語(yǔ)的概念。39 素短語(yǔ)定義 上下文無(wú)關(guān)文法 G 的句型的素短語(yǔ)是一個(gè)短語(yǔ)，它至少包含一個(gè)終結(jié)符，且除自身外不再包含其他素短語(yǔ)。 處于句型最左邊的素短語(yǔ)為最左素短語(yǔ) 算符文法的任一句型有如下形

18、式：#N1a1N2a2.NnanNn+1#, 若 ai-1 ai ai+1 . aj-1 aj ai+1，則有Niai.NjajNj+1為句柄40文法文法GE：(1) EE+T(2) ET(3) TT*F(4) TF(5) FP F|P(6) P(E)(7) Pi句型句型T+T*F+i其短語(yǔ)有：其短語(yǔ)有：T；T*F； i；T+T*F+i；T+T*FEET+ETF* FTTi素短語(yǔ)有：素短語(yǔ)有：T*F, i最左素短語(yǔ)為：最左素短語(yǔ)為：T*F句型句型N+N*N+i的歸約過(guò)程的歸約過(guò)程N(yùn)N+NNi* NNN41最左素短語(yǔ)的判斷假定文法的句型的一般形式為: N1a1 N2a2 Nnan Nn+1# 其

19、中ai是終結(jié)符，Ni是可有可無(wú)的非終結(jié)符,設(shè)最左素短語(yǔ)為Niai Njaj Nj1 , 必有： ai-1 ai ai+1 aj aj+1 則 Niai Njaj Nj1一定能歸約為某非終結(jié)符。42算符優(yōu)先分析算法k=1,sk=#;/s為符號(hào)棧，#壓入棧，sk為棧頂項(xiàng)do a=getsym( );/讀入下一個(gè)符號(hào)給a if(skVT) j=k; else j=k-1; while(sj a) do/在棧中尋找滿足的sj sj+1 sk a的sj+1，即最左素短語(yǔ)的頭 Q= sj ; if(sj-1VT) j=j-1; else j=j-2; while(sj Q) sj+1 sk歸約為N; /歸

20、約最左素短語(yǔ) k=j+1; sk=N;/end of while if(sj a| sj a)k=k+1;sk=a; /移進(jìn) else error while(a!=# /符號(hào)棧中不是#S)43算符優(yōu)先分析算法-說(shuō)明 (1) 算法結(jié)束時(shí)，若棧內(nèi)只有“”和某非終結(jié)符，讀頭下為“”，則表示分析成功，否則輸入串有錯(cuò)。 (2) 在進(jìn)行最左素短語(yǔ)歸約時(shí)，只要能找出產(chǎn)生式，其右部的終結(jié)符與棧頂?shù)娜舾山K結(jié)符有一一對(duì)應(yīng)的關(guān)系，當(dāng)名稱相同，位置也相同時(shí)即可進(jìn)行歸約，由于最左素短語(yǔ)不考慮非終結(jié)符，所以歸約成什么符號(hào)無(wú)關(guān)緊要。 (3) 通用算符優(yōu)先分析不考慮非終結(jié)符，終結(jié)符和非終結(jié)符放在同一個(gè)棧中。44文法文法GE

21、： EE+T|E-T|T TT*F|T/F|F FP F|P P(E)|i步驟步驟符號(hào)棧符號(hào)棧輸入符號(hào)串輸入符號(hào)串動(dòng)作動(dòng)作 1） # i+i*i# #i,移進(jìn)移進(jìn) 2） #i +i*i# #+,規(guī)約規(guī)約 3） #N +i*i# #+,移進(jìn)移進(jìn) 4） #N+ i*i# +i,移進(jìn)移進(jìn) 5） #N+i *i# +*,規(guī)約規(guī)約 6） #N+N *i# +*,移進(jìn)移進(jìn) 7） #N+N* i# *i,移進(jìn)移進(jìn) 8） #N+N*i # *#,規(guī)約規(guī)約 9） #N+N*N # +#,規(guī)約規(guī)約10） #N+N # #,規(guī)約規(guī)約11） #N # 接受接受 因此符號(hào)串因此符號(hào)串i+i*i是文法是文法GE的句子的句

22、子 對(duì)輸入串對(duì)輸入串i+i*i的算符優(yōu)先分析過(guò)程的算符優(yōu)先分析過(guò)程算符優(yōu)先分析算法-例算符優(yōu)先關(guān)系表+ - * / ()i #+-*/ ()i#451.作用 減小優(yōu)先表的空間占有量。2. 基本思想 將每個(gè)終結(jié)符與一對(duì)整數(shù)f(),g()聯(lián)系在一起。其中， f()是在棧內(nèi)時(shí)的優(yōu)先數(shù)， g()是還未進(jìn)棧時(shí)的優(yōu)先數(shù)，叫比較優(yōu)先數(shù)。且有如下關(guān)系：若 1 2 則f(1)g(2) 這樣就可將優(yōu)先表轉(zhuǎn)換為優(yōu)先函數(shù)表，所需存儲(chǔ)空間也由n*n個(gè)單元減少到2*n個(gè)單元。同時(shí)把比較運(yùn)算轉(zhuǎn)化成數(shù)學(xué)的比較大小，方便了語(yǔ)法分析過(guò)程。463、優(yōu)先表向優(yōu)先函數(shù)的轉(zhuǎn)化 -逐次加1法1）對(duì)所有終結(jié)符a（包括#），令f(a)g(a)=c，c為一任意常數(shù)。2）對(duì)所有終結(jié)符：若a b 而f(a)=g(b),則取g(b) = f(a)+1；若a b 而f(a)g(b),則取f(