自下而上分析和優(yōu)先分析法

1、第六章 自下而上分析和優(yōu)先分析法1、教學(xué)目的及要求：要求理解算符優(yōu)先文法、最左素短語、有效項目的基本概念；掌握算符優(yōu)先分析方法。 對給定的文法能夠判斷該文法是否是算符文法 對給定的算符文法能夠判斷該文法是否是算符優(yōu)先文法 對給定的算符文法能構(gòu)造算符優(yōu)先關(guān)系表，并能利用算符優(yōu)先關(guān)系表判斷該文法是否是算符優(yōu)先文法。 能應(yīng)用算符優(yōu)先分析算法對給定的輸入串進(jìn)行移進(jìn)-歸約分析，在分析的每一步能確定當(dāng)前應(yīng)移進(jìn)還是歸約，并能判斷所給的輸入串是否是該文法的句子。 了解算符優(yōu)先分析法的優(yōu)缺點和實際應(yīng)用中的局限性。2、教學(xué)內(nèi)容：自下而上語法分析（算符優(yōu)先分析法），算符優(yōu)先分析。3、教學(xué)重點：歸約，算符優(yōu)先表構(gòu)造。

2、4、教學(xué)難點： 通過本章學(xué)習(xí)后，學(xué)員應(yīng)該能知道算符文法的形式。 對一個給定的算符文法能構(gòu)造算符優(yōu)先關(guān)系分析表，并能判別所給文法是否為 算符優(yōu)先文法。 分清規(guī)范句型的句柄和最左素短語的區(qū)別，進(jìn)而分清算符優(yōu)先歸約和規(guī)范歸約的區(qū)別。 算符優(yōu)先分析的可歸約串是句型的最左素短語，在分析過程中如何尋找可歸約串是算符優(yōu)先分析的關(guān)鍵問題。對一個給定的輸入串能應(yīng)用算符優(yōu)先關(guān)系分析表給出分析（歸約）步驟，并最終判斷所給輸入串是否為該文法的句子。5、課前思考 什么是自下而上語法分析的策略？ 什么是移進(jìn)-歸約分析？ 移進(jìn)-歸約過程和自頂向下最右推導(dǎo)有何關(guān)系？ 自下而上語法分析成功的標(biāo)志是什么？ 什么是可歸約串？ 移進(jìn)

3、-歸約過程的關(guān)鍵問題是什么？ 如何確定可歸約串？ 如何決定什么時候移進(jìn)，什么時候歸約？ 什么是算符文法？什么是算符優(yōu)先文法？ 算符優(yōu)先分析是如何識別可歸約串的？ 算符優(yōu)先分析法的優(yōu)缺點和局限性有哪些？6、章節(jié)內(nèi)容第一節(jié) 自下而上語法分析第二節(jié) 算符優(yōu)先分析法6.1 自下而上語法分析自底向上的語法分析是從給定的符號串本身出發(fā)，試圖逐步將它歸約為文法的開始符號，由于在進(jìn)行自底向上的語法分析時，通常所采用的是最左歸約，即規(guī)范歸約，因此實現(xiàn)此種語法分析的關(guān)鍵，是在分析的每一步，如何尋找或確定當(dāng)前句型的句柄以及確定將句柄歸約為什么非終結(jié)符號。 一、自下而上語法分析方法的分類根據(jù)尋找句柄策略的不同，形成不

4、同的自底向上的分析方法，如優(yōu)先分析法及LR分析法。1、優(yōu)先分析法優(yōu)先分析法是在文法的一些符號之間建立優(yōu)先關(guān)系，并根據(jù)此優(yōu)先關(guān)系來確定句型的句柄。2、LR分析法LR分析法則根據(jù)分析過程中迄今已經(jīng)取得的信息，并向前查看若干個輸入符號來確定當(dāng)前應(yīng)采取的分析動作。二、自下而上分析法的實現(xiàn)思想實現(xiàn)自底向上的分析，使用一個先進(jìn)后出的分析棧存放分析過程中所得的文法符號；開始狀態(tài)：分析棧底放置一個界符#，然后將輸入符號逐個推入棧內(nèi)；一旦在分析棧的棧頂出現(xiàn)句柄，就用相應(yīng)產(chǎn)生式的左部去替換這個句柄，即進(jìn)行一次歸約，由于歸約，得到新的棧頂，此時再查看棧的頂部是否形成新的句柄，若是，再進(jìn)行歸約；反之，則繼續(xù)將后續(xù)的輸

5、入符號移入棧內(nèi)；分析成功：重復(fù)上述過程，若最終能將全部輸入符號移掉，且分析棧中只留下棧底符號#及最后一步歸約所得文法開始符號，則表明輸入串的分析成功；語法錯誤：若全部輸入符號已被移掉，而分析棧不能出現(xiàn)上述格局，則表明輸入符號串不是文法的句子，存在語法錯誤。三、自下而上語法分析過程例：有文法GS：S®AB|c，A ®bA|a，B ®aSb|c，用上述“移進(jìn)歸約”分析方法對輸入串bbaacb所作的分析過程：移進(jìn)歸約分析過程可能采取的動作有四種：移進(jìn)、歸約、接受和報錯。因采用最左歸約，故一旦句柄在分析棧形成，必然出現(xiàn)在棧頂。當(dāng)一個貌似句柄的符號串出現(xiàn)在棧頂時，不能貿(mào)然按

6、某一產(chǎn)生式進(jìn)行歸約，否則將導(dǎo)致錯誤結(jié)果。如上例步驟7。如何正確確定句型的句柄，如何正確地用產(chǎn)生式進(jìn)行歸約，是實現(xiàn)自底向上語法分析的關(guān)鍵。6.2 算符優(yōu)先分析法一、概述算符優(yōu)先分析法是仿照算術(shù)式的四則運算過程的一種語法分析方法，該方法首先規(guī)定運算符之間的優(yōu)先關(guān)系和結(jié)合性質(zhì)，然后利用這種關(guān)系，用比較相鄰運算符的優(yōu)先順序來確定句型的“句柄”和進(jìn)行歸約，這種歸約未必是嚴(yán)格的最左歸約，每一步未必是當(dāng)前句型的句柄。例：有文法GE：E ®E+E|E-E|E*E|E/E|(E)|i該文法為二義性文法，其句子有不同的規(guī)范推導(dǎo)，歸約過程中句柄不唯一，若采用運算符優(yōu)先順序和結(jié)合原則的規(guī)定，并按這種規(guī)定進(jìn)行

7、歸約，則該句子的歸約過程就是唯一的。如i+i*i的歸約過程：(1) i+i*i 按E ®i 歸約(2)E+i*i 按E ®i 歸約(3) E+E*i 按E ®i 歸約(4) E+E*E 按E ®E*E 歸約(5) E+E按E ®E+E 歸約(6) E該歸約過程是唯一的。在上述的整個歸約過程中，起決定作用的是相鄰兩個終結(jié)符的優(yōu)先關(guān)系，所以應(yīng)用算符優(yōu)先分析法自底向上地分析句子?？梢灾桓鶕?jù)相鄰運算符的優(yōu)先關(guān)系，就能方便地并且唯一的確定歸約的“句柄”?？梢杂脕矸治龆x性文法所產(chǎn)生的語義。直觀算符優(yōu)先分析對一個給定文法G，人為地規(guī)定其算符的優(yōu)先順序，即給

8、出優(yōu)先級別和同一個級別中的結(jié)合性質(zhì)，算符間的優(yōu)先關(guān)系有三種：Ø a ba的優(yōu)先級高于bØ a ba的優(yōu)先級等于bØ a ba的優(yōu)先級低于bØ 這三個關(guān)系不同于數(shù)學(xué)中的<,>,=,它們是有序的，如a b不意味著b a，a b不意味b a。如有文法GE：E®E+E|E*E|(E)|i，其終結(jié)符的優(yōu)先關(guān)系如下表：優(yōu)先關(guān)系矩陣二、直觀算符優(yōu)先分析法用已經(jīng)建立起來的文法GE的優(yōu)先關(guān)系矩陣，構(gòu)造一個分析該文法句子的算法，即直觀算符優(yōu)先分析法，為便于比較相鄰運算符的優(yōu)先級，使用兩個工作棧，一個為運算符棧，以O(shè)PTR表示，用來存放運算符（包括括號和

9、#）；另一個稱運算對象棧，以O(shè)PND表示，用來存放運算對象（包括最基本的運算對象和運算結(jié)果），用#代表分析句子的左右分界符。分析開始時，OPTR棧中壓入左界符#，OPND棧為空，同時令q代表OPTR當(dāng)前棧頂符號，a存放新輸入的符號，則分析算法的步驟：(1)把下一個輸入符號讀至a中；(2)若a為i，則把它推進(jìn)OPND棧，轉(zhuǎn)第一步。(3)若q a，則應(yīng)根據(jù)規(guī)則E® E1q E2進(jìn)行歸約，E1和E2代表OPND棧頂?shù)拇胃咴妥罡咴械倪\算對象，先將E1和E2從OPND棧中彈出，然后把代表該子表達(dá)式運算結(jié)果的E壓入OPND中，同時把q從OPTR棧頂彈出，然后重新進(jìn)入第(2)步；(4)若q a

10、，則只有一種情況， q=“(”,a=“)”，此種情況下，彈出OPTR棧頂最高元的“(”,放棄a中的右括號，轉(zhuǎn)第(1)步；(5)若q a，把a移進(jìn)OPTR棧，轉(zhuǎn)第(1)步；(6)若q=a=“#”，分析過程結(jié)束；(7)若q與a不存在優(yōu)先關(guān)系，即矩陣元素為空，輸入串有錯，調(diào)錯誤處理程序進(jìn)行處理。分析成功的標(biāo)志是（必要條件）：OPTR棧底的“#”與輸入串后的“#”相遇，而OPND棧中僅含一項，這一項代表整個表達(dá)式的分析結(jié)果，若非這種情況，意味著分析失敗，即表達(dá)式有語法錯誤；在(3)和(4)，當(dāng)要形成Eq E和(E)時，若OPND棧中沒有足夠的項數(shù)，也表示輸入串有錯。上面算法對GE所定義的算術(shù)表達(dá)式的分

11、析有效，所有算符優(yōu)先分析大體上如此工作。在該分析過程中由于使用了兩個棧，當(dāng)讀進(jìn)的符號一旦被判斷出是運算對象時，就立即推進(jìn)運算對象棧，而不與運算符棧的棧頂符號比較優(yōu)先級，故沒有用到作為終結(jié)符的運算對象與其它算符之間的優(yōu)先關(guān)系。使用算符優(yōu)先分析法便于直接將表達(dá)式翻譯成目標(biāo)指令。三、算符優(yōu)先文法的定義1、算符文法定義設(shè)有一文法G，如果G中沒有形如A ®BC的產(chǎn)生式，其中B和C為非終結(jié)符，稱G為算符文法（OG文法），即在OG文法中，不存在包含兩個相鄰非終結(jié)符號的產(chǎn)生式的右部。2、算符文法性質(zhì)(性質(zhì)一)在算符文法中，任何句型都不包含兩個相鄰的非終結(jié)符。證明：用歸納法，設(shè)r是句型，有S=W0&#

12、222;W1Þ.ÞWn=r，推導(dǎo)長度為n。(1)歸納基礎(chǔ)：n=1時， S=W0ÞW1=r，即SÞr，必存在產(chǎn)生式S® r，而有算符文法定義，文法的產(chǎn)生式中無相鄰的非終結(jié)符，該性質(zhì)成立。(2)假設(shè)n>1， Wn-1滿足性質(zhì)若Wn-1=aAd,AÎVN，由假設(shè)a的尾符號與的d首符號不可能為非終結(jié)符，否則與假設(shè)矛盾，又若Ab®是文法的產(chǎn)生式，則有Wn-1 Þ Wn = dba= r， Ab®不含有兩個相鄰的非終結(jié)符，所以adb也不含有兩個相鄰的非終結(jié)符。(性質(zhì)二)如果Ab或bA出現(xiàn)在算符文法的句型r中，其

13、中AÎVN ， bÎVT,則r中任何含b的短語必含有A。證明：用反證法， S r=abAb，若存在B ab，則A和B不同時歸約，則有S B Ab，與性質(zhì)一矛盾。得證。含b的短語必含A，含A的短語不一定含b。四、算符優(yōu)先關(guān)系定義設(shè)G是一個算符文法，a和b是任意兩個終結(jié)符，A,B,C ÎVN，算符優(yōu)先關(guān)系定義如下：Ø a b，當(dāng)且僅當(dāng)G中含有形如A®ab或A®aBb的產(chǎn)生式。Ø a b，G中含有形如A®aB，且B b或B CbØ a b，G中含有形如A®Bb，且B a或B aC。以上關(guān)系可用語法樹說

14、明：五、算符優(yōu)先文法的定義設(shè)一不含e產(chǎn)生式的算符文法，如果任意兩個終結(jié)符對a，b之間至多有, 三種關(guān)系的一種成立，則稱G是一個算符優(yōu)先文法(OPG文法)。兩個終結(jié)符之間的優(yōu)先關(guān)系是有序的，允許有a b，b a同時存在，而不允許有ab，ab，ab中兩種同時存在。例1、有文法GE：E®E+T|T，T ®T*F|F，F(xiàn) ®(E)|i因為 E®E+T，EÞE+T，故+ EÞT Þ T*F， 故*+ EÞT ÞF Þ(E) 故)+ EÞT ÞF Þ i 故i+可得前面優(yōu)先關(guān)系

15、矩陣，文法GE是OG文法，并在任意兩個終結(jié)符號之間至多有一個優(yōu)先關(guān)系成立，故該文法為OPG文法。例2、GE：E®E+E|E*E|(E)|iE ® E1+E2，E1ÞE*E， *+E ® E1*E2，E2ÞE+E，*+故該文法是算符文法，但不是算符優(yōu)先文法。六、算符優(yōu)先關(guān)系表的構(gòu)造通過檢查G的每條規(guī)則的每一個選擇，可以找出所有滿足ab的終結(jié)符號對，為找出所有滿足關(guān)系和的終結(jié)符號對，首先需要對G的每個非終結(jié)符號B構(gòu)造兩個集合FIRSTVT(B)和LASTVT(B)：Ø FIRSTVT(B)=b|Bb.或BCbØ LASTVT(B

16、)=a|Ba或BaC三種關(guān)系：Ø 關(guān)系：A ®ab或A ®aBb則有abØ 關(guān)系：求出每個非終結(jié)符B的FIRSTVT(B)，對形如產(chǎn)生式A ®aB，對于每一 bÎ FIRSTVT(B)，則有ab成立。Ø 關(guān)系：求出每個非終結(jié)符B的LASTVT(B)，對形如產(chǎn)生式A ®Bb，對于每一aÎ LASTVT(B)，則有ab成立。例3、有表達(dá)式文法E®#E#， E®E+T|T，T®T*F|F，F(xiàn)®P­F|P，P ®(E)|i(1)計算優(yōu)先關(guān)系由E®

17、;#E#， P ®(E)有#，()(2)計算FIRSTVT和LASTVT集合FIRSTVT(E)=#FIRSTVT(E)=+,*, ­,(,iFIRSTVT(T)=*, ­,(,i FIRSTVT(F)=­,(,iFIRSTVT(P)=(,i LASTVT(E)=#LASTVT(E)=+,*, ­,),i LASTVT(T)=*, ­,),iLASTVT(F)=­,),i LASTVT(P)=),i(3)關(guān)系#E #FIRSTVT(E)，+T +FIRSTVT(T)*F *FIRSTVT(F)，­F ­F

18、IRSTVT(F)(E (FIRSTVT(E)(4)關(guān)系E# LASTVT(E)#，E+ LASTVT(E)+T* LASTVT(T)*，P­ LASTVT(P)­E) LASTVT(E)七、構(gòu)造FIRSTVT(A)的算法按照定義，可用下面兩條規(guī)則構(gòu)造集合FIRSTVT(A)：(1)若有產(chǎn)生式A®a或A®Ba，則aÎFIRSTVT(A)。(2)若有產(chǎn)生式A®B，且bÎFIRSTVT(B)，則bÎFIRSTVT(A)。建立一布爾數(shù)組F，使得FA,a為真的條件是當(dāng)且僅當(dāng)aÎFIRSTVT(A)。開始時：按規(guī)則

19、(1)對每個數(shù)組元素FA,a賦初值，用一個棧STACK把所有初值為真的數(shù)組元素FA,a的符號對(A,a)全部放在STACK棧中，然后，對棧STACK施加如下運算：如果STACK不空，將棧頂元素彈出，記為(B,a)，用規(guī)則(2)對每個形如A®B的產(chǎn)生式，若FA,a為假，則變其值為真，并將(A,a)推進(jìn)STACK棧。上述過程重復(fù)到STACK為空為止。（具體算法用程序描述如下： ）先定義一個過程：PROCEDURE INSERT(A,a); IF NOT FA,a THEN BEGIN FA,a:=TRUE PUSH(A,a) ONTO STACK END;主程序為：BEGIN FOR 每

20、一個非終結(jié)符A和終結(jié)符a DO FA,a:=FALSE; FOR 每個形如A®a或A®Ba的產(chǎn)生式DO INSERT(A,a) WHILE STACK 非空 DO BEGIN 把STACK棧頂記為(B,a)上托出去; FOR 每個形如A®B的產(chǎn)生式 DO INSERT(A,a) ENDEND. 該算法的工作結(jié)果得到一個二維數(shù)組F，從它可得到任何非終結(jié)符A的FIRSTVT(A)。FIRSTVT(A)=a|FA,a=TRUE八、構(gòu)造LASTVT(A)的算法構(gòu)造集合計算LASTVT(1)若有產(chǎn)生式A® a或A®a B，則aÎLASTVT(A

21、)。(2)若有產(chǎn)生式A®,B，且aÎLASTVT(B)，則aÎLASTVT(A)。使用每個終結(jié)符A的FIRSTVT(A)和LASTVT(A)即可構(gòu)造文法G的算符優(yōu)先關(guān)系表，算法為：FOR 每個產(chǎn)生式A®X1X2Xn DO FOR i:=1 TO n-1 DO BEGIN IF Xi和Xi+1均為終結(jié)符 THEN 置 XiXi+1; IF i£n-2且Xi和Xi+2均為終結(jié)符, Xi+1為非終結(jié)符 THEN 置 XiXi+2; IF Xi為終結(jié)符而Xi+1為非終結(jié)符 THEN FOR FIRSTVT(Xi+1)中的每個b DO 置 Xib; IF

22、 Xi為非終結(jié)符而Xi+1為終結(jié)符 THEN FOR LASTVT(Xi)中的每個a DO 置 aXi+1; END九、算符優(yōu)先分析算法算符優(yōu)先分析算法是一種自底向上的分析算法，但不是嚴(yán)格從左到右的，在每一步分析中，它將識別和歸約所謂的最左素短語。1、最左素短語的定義文法句型的素短語是一個短語，它至少包含一個終結(jié)符號，并且除它自身外，不再包含其它素短語，最左邊的素短語稱最左素短語。例如有表達(dá)式文法GE為：E®E+T|T,T®T*F|F,F®P­F|P,P ®(E)|i,現(xiàn)有句型#T+T*F+i#，該句型的短語為：T+T*F+i, T+T*F,

23、T, T*F, i素短語：包含終結(jié)符且不含其它素短語，故為T*F， i。而句柄為T，但不是素短語，T*F為最左素短語。2、算符優(yōu)先文法的句型算符優(yōu)先文法的任何一個句型應(yīng)為如下形式#N1a1N2a2NnanNn+1#，其中ai為終結(jié)符號，Ni(1£i £n+1)為非終結(jié)符或e。若有NiaiNjajNj+1為句柄，則Ni和Nj+1在句柄中。該句柄中終結(jié)符之間的關(guān)系：§ ai-1 ai§ ai ai+1 ai+2 aj§ aj aj+1 定理：一個OPG句型的最左素短語是滿足下列條件的左子串NiaiNjajNj+1Ø ai-1 aiØ ai ai+1 ai+2 ajØ aj aj+1 出現(xiàn)在ai左端或aj右端的非終結(jié)符號一定屬