樣題與課件編譯原理第6章

1、1第六章自底向上的優(yōu)先分析法2它的實現(xiàn)思想是對輸入符號串自左向右進行掃描，并將輸入符逐個移入一個后進先出棧中，邊移入邊分析，一旦棧頂符號串形成某個句型的句柄時，(該句柄對應(yīng)某產(chǎn)生式的右部)，就用該產(chǎn)生式的左部非終結(jié)符代替相應(yīng)右部的文法符號串，這稱為一步歸約。重復(fù)這一過程直到歸約到棧中只剩文法的開始符號時則為分析成功，6.1 自底向上分析概述 自底向上分析法(或自下而上分析)，也稱移進-歸約分析法。由于自底向上分析的移進-歸約過程是自頂向下最右推導(dǎo)的逆過程，而最右推導(dǎo)為規(guī)范推導(dǎo)，自左向右的歸約過程也稱規(guī)范歸約。3例(P102)SaAcBe aAcde aAbcde abbcde由此我們可以構(gòu)造它

2、的逆過程即歸約過程。先設(shè)一個先進后出的符號棧，并把句子左括號“#”號放入 棧底，其分析過程如下頁：設(shè)文法GS為：(1) SaAcBe(2) Ab(3) AAb(4) Bd對輸入串a(chǎn)bbcde#進行分析，檢查該符號串是否是GS的句子。容易看出對輸入串a(chǎn)bbcde的最右推導(dǎo)是：4文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B dabbcde步驟符號棧輸入符號串動作 1） # abbcde# 移進 2） #a bbcde# 移進A 3） #ab bcde# 歸約(Ab) 4） #aA bcde# 移進A 5） #aAb cde# 歸約(AAb) 6） #aA cde# 移進

3、 7） #aAc de# 移進B 8） # aAcd e# 歸約(Bd) 9） #aAcB e# 移進11） #S # 接受S10） #aAcBe # 歸約SaAcBeaAcdeaAbcdeabbcde5在上述移進-歸約或自底向上構(gòu)造語法樹的過程中，我們怎么知道何時移進，何時歸約，不能只簡單地看成棧頂出現(xiàn)某一產(chǎn)生式的右部就可用相應(yīng)產(chǎn)生式歸約，例如在上表分析到第5)步時棧中的符號串是#aAb，棧頂符號串b和Ab分別是產(chǎn)生式(2)，(3)的右部，這時到底用(2)歸約還是用(3)歸約是自底向上分析要解決的關(guān)鍵問題。由此可見自底向上分析的關(guān)鍵問題是在分析過程中如何確定句柄，也就是說如何知道何時在棧頂符

4、號串中已形成某句型的句柄，那么就可以確定何時可以進行歸約。66.2簡單優(yōu)先分析法6.2.1 優(yōu)先關(guān)系 首先定義優(yōu)先關(guān)系的表示: X Y表示X的優(yōu)先性等于Y。 X Y表示X的優(yōu)先性低于Y X Y表示X的優(yōu)先性高于Y。優(yōu)先關(guān)系是有序的， X Y不一定Y X；X Y不一定Y X；X Y不一定Y X；簡單優(yōu)先分析法是按照文法符號(終結(jié)符和非終結(jié)符)的優(yōu)先關(guān)系確定句柄的.因此,首先要介紹兩個文法符號的優(yōu)先關(guān)系如何確定.7(1)X Y 當(dāng)且僅當(dāng)G中存在產(chǎn)生式AXY(2)X Y 當(dāng)且僅當(dāng)G中存在產(chǎn)生式AXB,且B Y(3)X Y 當(dāng)且僅當(dāng)G中存在產(chǎn)生式ABD, 且B X和D Y見P104-105頁的例題6.

5、2簡單優(yōu)先文法的定義(P105)簡單優(yōu)先分析法 (P105)86.3 算符優(yōu)先分析法 算符優(yōu)先分析的基本思想是只規(guī)定算符(廣義為終結(jié)符)之間的優(yōu)先關(guān)系，也就是只考慮終結(jié)符之間的優(yōu)先關(guān)系，不考慮非終結(jié)符之間的優(yōu)先關(guān)系。9如何確定算符優(yōu)先關(guān)系？人為確定：（1）i的優(yōu)先級最高（1） 優(yōu)先級次于i，右結(jié)合（2）*和/優(yōu)先級次之，左結(jié)合（3）+和-優(yōu)先級最低，左結(jié)合（4）括號(,)的優(yōu)先級大于括號外的運算符，小于括號內(nèi)的運算符，內(nèi)括號的優(yōu)先性大于外括號（5）#的優(yōu)先性低于與其相鄰的算符算符優(yōu)先關(guān)系表10例如:若有文法G為：(1) EE+E(2) EE*E(3) Ei對輸入串i+i*i的歸約過程可表示為表

6、6.3。步驟 棧當(dāng)前輸入字符剩余輸入串動作1i+i*i#+ 歸約3E+i*i#+移進4#E+i*i#+* 歸約6#E+E*i#+*移進7#E+E*i#*#歸約9#E+E*E#*#歸約10#E+E#+#歸約11#E#接受11 算符優(yōu)先文法的定義定義：如果不含空產(chǎn)生式的上下文無關(guān)文法 G 中沒有形如 ABC的產(chǎn)生式，其中B，CVN 則稱G 為算符文法（OG）。例6.1 GE：EE+E|E*E|i 是OG文法性質(zhì)1：在算符文法中任何句型都不包含兩個相鄰的非終結(jié)符.（證明P108，用歸納法證明）性質(zhì)2：如 Ab 或 bA 出現(xiàn)在算符文法的 句型 中，其中 AVN，bVT， 則 中任何 含 b 的短語必

7、含有A。（注意：含A的短語不一定含b)用反證法P10812證明：性質(zhì)1用歸納法設(shè)是句型，即S S=0 1 . n-1 n=推導(dǎo)長度為n，歸納起點n=1時，S=0 1=，即S ，必存在產(chǎn)生式S，而由算符文法的定義，文法的產(chǎn)生式中無相鄰的非終結(jié)符，顯然滿足性質(zhì)1。假設(shè)n1, n-1滿足性質(zhì)1。若n-1=A，A為非終結(jié)符。由假設(shè)的尾符號和的首符號都不可能是非終結(jié)符，否則與假設(shè)矛盾。又若A是文法的產(chǎn)生式，則有n-1 n=而A是文法的原產(chǎn)生式，不含兩個相鄰的非終結(jié)符，所以也不含兩個相鄰的非終結(jié)符。滿足性質(zhì)1。證畢。 13 證明：性質(zhì)2用反證法。因為由算符文法的性質(zhì)1知可有：S =bA若存在B b，這時b

8、和A不同時歸約，則必有S BA, 這樣在句型BA中存在相鄰的非終結(jié)符B和A，所以與性質(zhì)1矛 盾，證畢。注意：含b的短語必含A，含A的短語不一定含b。14算符優(yōu)先關(guān)系的定義：在OG中 定義 （算符優(yōu)先關(guān)系） a = b G中有形如：Aab 或A aBb.的產(chǎn)生式。 a b G中有形如: A Bb的產(chǎn)生 式,而 B a 或 B aC規(guī)定 若 S a或 S Ca 則 # #15在 OG文法 G 中，若任意兩個終結(jié)符間至多有一種算符優(yōu)先關(guān)系存在，則稱G 為算符優(yōu)先文法(OPG)。注意：不允許 bc, b+*+16算符優(yōu)先關(guān)系表的構(gòu)造首先定義如下兩個集合：FIRSTVT(B)=bB b 或 B CbLA

9、STVT(B)=aB a 或 B aC按如下算法計算出給定文法中任何兩個終結(jié)符對(a,b)之間的優(yōu)先關(guān)系： 1) =關(guān)系直接看產(chǎn)生式的右部，若出現(xiàn)了A ab或 A aBb,則a=b 2)關(guān)系求出每個非終結(jié)符B的FIRSTVT(B)若AaB,則bFIRSTVT(B),則ab 即a關(guān)系求出每個非終結(jié)符B的LASTVT(B)若ABb,則aLASTVT(B),則ab 即 LASTVT(B)b17如何求FIRSTVT集:若有產(chǎn)生式A a 或A Ba 則aFIRSTVT(A)若a FIRSTVT(B)且有產(chǎn)生式A B 則a FIRSTVT(A)如何求LASTVT集:若有產(chǎn)生式A a或A aB 則aLAST

10、VT(A)若a LASTVT(B)且有產(chǎn)生式A B則a LASTVT(A)18計算算符優(yōu)先關(guān)系例文法GE： (0) E#E#(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) PiFIRSTVT(E)=#FIRSTVT(E)=+,*,(,iFIRSTVT(T)=*,(,iFIRSTVT(F)=,(,iFIRSTVT(P)=(,iLASTVT(E)=#LASTVT(E)=+,*,),iLASTVT(T)=*,),iLASTVT(F)=,),iLASTVT(P)=),i先計算每個非終結(jié)符的FirstVt集和LastVt集19(0)E#E# (1) EE

11、+T (2) ET (3) TT*F (4) TF(5) FPF|P (6) P(E) (7) Pi3)關(guān)系找形如：ABb的產(chǎn)生式E#: 則 LASTVT(E)#E+: 則 LASTVT(E)+ T*: 則 LASTVT(T)* P: 則 LASTVT(P) E): 則 LASTVT(E)2）關(guān)系找形如AaB的產(chǎn)生式#E：則 #FIRSTVT(E)+T: 則 +FIRSTVT(T) *F: 則 *FIRSTVT(F)F: 則 FIRSTVT(F)(E: 則 (FIRSTVT(E)1)=關(guān)系由產(chǎn)生式(0)和(6),得#=#， ( = )20表達式文法GE的算符優(yōu)先關(guān)表21算符優(yōu)先分析算符優(yōu)先分析

12、的可歸約 串是句型的最左素短語定義 G 的句型的素短語是一個短語，它至少包含一個終結(jié)符，且除自身外不再包含其他素短語。即素短語必須滿足下列兩個條件:1、至少包含一個終結(jié)符號。2、該短語不再包含滿足第一個條件的更小的短語。處于句型最左邊的素短語為最左素短語 22文法GE：(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi句型T+T*F+i其短語有：T+T*F+iT+T*FTT*FiEET+ETF*FTTi句型T+T*F+i的最左素短語為：T*FE+TFE句型T+T*F+i的素短語為：T*F， iETTi句型T+T+i的素短語是: T+T 和 i

13、,其中最左素短語:T+T23課堂練習(xí)：分別求句型Ei、E+F的短語、簡單短語、句柄、素短語、最左素短語 E T F + i E短語：E+i, i簡單短語： i句柄：i素短語：i最左素短語：i短語：E+F, F簡單短語：F句柄：F素短語： E+F最左素短語： E+F E T F + E例: 文法GE EE+T|T TT*F|F F(E)|i24算符優(yōu)先分析算法前面介紹了如何對已給定的文法按其產(chǎn)生式構(gòu)造算符優(yōu)先關(guān)系表，有了算符優(yōu)先關(guān)系表并滿足算符優(yōu)先文法時，我們就可以對任意給定的符號串進行歸約分析，進而判定輸入串是否為該文法的句子。然而用算符優(yōu)先分析法的歸約過程與規(guī)范歸約是不同的。例：表達式文法：

14、(0)E#E# (1) EE+T (2) ET (3) TT*F (4) TF(5) FPF|P (6) P(E) (7) Pi對i+i#的規(guī)范規(guī)約和算符優(yōu)先規(guī)約見P115表6.7和表6.8注意在算符優(yōu)先分析過程中，因去掉了單非終結(jié)符之間的歸約，非終結(jié)符的名字沒有任何意義。所以在歸約過程中所有的非終結(jié)符都用同一個名字。 25 算符優(yōu)先文法句型的性質(zhì)算符文法的任何一個句型應(yīng)為如下形式：N1a1N2a2 . Nnan Nn+1其中N k(1kn+1)為非終結(jié)符或空，ak(1kn)為終結(jié)符算符優(yōu)先文法句型的最左素短語NiaiNi+1ai+1 . Njaj Nj+1滿足：ai-1 aiai =ai+1

15、 = =aj-1 =ajaj aj+1即：ai-1 aj+1 算符優(yōu)先分析過程歸約時，只能把 和 之間的符號串作為可歸約串進行歸約。26 算符優(yōu)先分析句型有如下性質(zhì)：如果aNb(或ab)出現(xiàn)在句型r中，則a和b之間有且只有一種 優(yōu)先關(guān)系,即：若a b則在r中必含有b而不含a的短語存在。若a b則在r中必含有a而不含b的短語存在。若a b則在r中含有a的短語必含有b，反之亦然。27由于算符優(yōu)先分析法去掉了單非終結(jié)符之間的歸約，盡管在分析過程中，當(dāng)決定是否為句柄時采取一些檢查措施，但仍難完全避免把錯誤的句子得到正確的歸約。例如，下述文法是一個算符優(yōu)先文法，其產(chǎn)生式為：SS;D|DDD(T)|HHa|(S)TT+S|S其中VNS，D，T，H，VT；,(,),a,+，S為