1、第六章自底向上的優先分析法 自底向上語法分析概述 簡單優先分析 算符優先分析2019/5/2616.1自底向上語法分析概述 自底向上語法分析試圖將一個字符串歸約至開始符號。 自下而上語法分析比自頂向下語法分析更有效率，對語法的限制更少 “移進-歸約”：從輸入字符串開始，逐步進行歸約直到歸約到文法的開始符號。2019/5/262分析符號串abbcde是否GS的句子SABA對輸入串abbcde#的移進-規約分析過程ab2019/5/b26cde3步驟符號棧輸入符號串動作1）2）3）4）5）6）7）8）9）10）11）#abbcde#移進#abbcde#移進#abbcde#歸約(Ab)#aAbcde

2、#移進#aAbcde#歸約(AAb)#aAcde#移進#aAcde#移進# aAcde#歸約(Bd)#aAcBe#移進#aAcBe#歸約(SaAcBe)#S#接受文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d歸約過程恰好是最右推導的逆過程：SÞ aAcBeÞ aAcde Þ aAbcde Þ abbcde規范歸約定義：句柄假定是文法G的一個句子，我們稱序列n, n- 1, 0是的一個規范歸約。如果此序列滿足： 1、 n= 2、 0為開始符號。3、對任何i,0<i<=n, i-1是從i經把句柄替換為相應產生式的左部

3、符號而得到的。規范歸約也稱最左歸約，最右推導稱為規范推導。規范推導得到的句型成為規范句型。如果文法G無二義，則規范推導的逆過程一定是規范歸約。2019/5/264“移進-歸約”法的棧實現自頂向下：初始：分析棧：#S輸入串:a1a2an#（結束：）分析過程：用產生式的右部替換左部。自底向上：初始：分析棧：#輸入串:a1a2an#S#（結束：）分析過程：自左至右把輸入符號串W的符號一一移進棧里，一旦發現棧頂的一部分符號形成一個可歸約串，就把棧中這個子串用相應的歸約符號替換。四類操作：移進，歸約，接受，出錯處理。缺20點19/5/265E文法GE：E Ò T + E | TT Ò

4、 int * T | int | (E)TE|int * int + int int | * int + int移進移進移進規約 T Ò intTTint* | int + intint * int | + int int * T | + int T | + intT + | int T + int | T + T |+intintint*規約T Ò int * T移進移進規約T Ò int規約E Ò T規約E Ò T + ET + E |2019/5/266E |A Shift-Reduce Parse in Detail (1)|int *

5、 int + int+int­intint*2019/5/267A Shift-Reduce Parse in Detail (2)|int * int + int int | * int + int+intintint*­2019/5/268A Shift-Reduce Parse in Detail (3)|int * int + int int | * int + intint* | int + int+intint­int*2019/5/269A Shift-Reduce Parse in Detail (4)|int * int + int int |

6、* int + intint* | int + intint * int | + int+­intintint*2019/5/2610A Shift-Reduce Parse in Detail (5)|int * int + int int | * int + intint* | int + intint * int | + intint * T | + intT+­intintint*2019/5/2611A Shift-Reduce Parse in Detail (6)|int * int + int int | * int + intint* | int + in

7、tint * int | + int int * T | + intT | + intTT+­intintint*2019/5/2612A Shift-Reduce Parse in Detail (7)|int * int + int int | * int + intint* | int + intint * int | + int int * T | + int T | + intT + | intTT+intintint*­2019/5/2613A Shift-Reduce Parse in Detail (8)|int * int + int int | * in

8、t + intint* | int + intint * int | + int int * T | + int T | + intT + | intT + int |TT+intintint­14*2019/5/26A Shift-Reduce Parse in Detail (9)|int * int + int int | * int + intint* | int + intint * int | + int int * T | + int T | + intT + | intT + int | T + T |TTT+intintint­15*2019/5/26A

9、Shift-Reduce Parse in Detail (10)|int * int + int int | * int + intint* | int + intint * int | + int int * T | + int T | + intT + | int T + int | T + T |T + E |TETT+intintint*­2019/5/2616A Shift-Reduce Parse in Detail (11)|int * int + intEint | * int + intint* | int + intint * int | + int int *

10、 T | + int T | + intT + | int T + int | T + T | T + E |E |2019/5/26TETT+intintint*­176.2自底向上的優先分析算法優先分析法 簡單優先分析法 算符優先分析法2019/5/2618簡單優先分析法按照文法符號（包括終結符和非終結符） 的優先關系確定句柄。示例見下頁2019/5/2619步驟1）2）3）4）5）6）7）8）9）10）11）符號棧#b #b( #b(a#b(A#b(Aa #b(Aa) #b(B#bA #bAb #S輸入符號串b(aa)b# (aa)b# aa)b#a)b# a)b#)b# b#

11、 b#b# #動作#<b,移進b<(,移進(<a,移進a>a,歸約Aa A=a,移進a=),移進)>b,歸約BAa) B>b,歸約A(BA=b,移進 b>#,歸約SbAb接受對輸入串b(aa)#的簡單優先分析過程簡單優先關系矩陣2019/5/2620SbA(Ba)#S>b=<<>A=(<<=<B>>a>>=)>>#<<文法GS：(1) S bAb(2) A (B|a(3) B Aa)優先關系優先關系 X=Y Û 文法G中存在產生式A.XY. X<Y

12、Û 文法G中存在產生式A.XB.，且B +Y.Þ X>YÛ 文法G中存在產生式A.BD.，+*且B Þ.X,D ÞY.#的優先級<所有符號，所有符號的優先級>#，這里僅對與#相鄰的文法符號而言。2019/5/2621簡單優先文法的定義滿足以下條件的文法是簡單優先文法（1） 在文法符號集V中，任意兩個符號之間最多只有一種優先關系成立。（2） 在文法中任意兩個產生式沒有相同的右部。2019/5/2622簡單優先分析法的算法步驟將輸入符號串a1a2an#依次逐個存入符號棧S中，直到遇到棧頂符號ai的優先性> 下一個待輸入符號a

13、j為止。棧頂當前符號ai為句柄尾，由此向左在棧中找句柄的頭符號ak，即找到ak-1<ak為止。由句柄akai在文法的產生式中查找右部為akai的產生式，若找到則用相應左部代替句柄，若找不到則為出錯。重復1，2，3步，直到棧中只剩開始符。2019/5/2623算符優先分析某些文法具有“算符”特性表達式運算符（優先級、結合性）人為地規定其算符的優先順序，即給出優先級別和同一級別的結合性只考慮算符之間的優先關系2019/5/2624文法GE：EE+E|E-E|E*E|E/E|E­E|(E)|i步驟符號棧輸入符號串動作1）2）3）4）5）6）7）8）9）10）11）#i #E #E+#

14、E+i #E+E #E+E*#E+E*i #E+E*E #E+E#Ei+i*i#+i*i#+i*i# i*i#*i#*i# i# # # #<i,移進#<i>+,規約#<+,移進+<i,移進+<i>*,規約+<*,移進*<i,移進*<i>#,規約+<*>#,規約#<+>#,規約接受算符優先關系表對輸入串i+i*i的算符優先分析過程標志：棧中只剩#N，輸入符號串剩#歸約225+-*/­()i#+>><<<<><>->><<

15、;<<><>*>>>><<><>/>>>><<><>­>>>><<><>(<<<<<<=<)>>>>>>>i>>>>>>>#<<<<<<<=如何確定算符優先關系？文法GE：EE+E|E-E|E*E|E/E|E­E|(E)

16、|i（1）i的優先級最高（1） ­優先級次于i，右結合（2） *和/優先級次之，左結合（3） +和-優先級最低，左結合（4） 括號(,)的優先級大于括號外的運算符，小于括號內的運算符，內括號的優先性大于外括號（5） #的優先性低于與其相鄰的算符算符優先關系表2019/5/2626+-*/­()i#+>><<<<><>->><<<<><>*>>>><<><>/>>>><<>&

17、lt;>­>>>><<><>(<<<<<<=<)>>>>>>>i>>>>>>>#<<<<<<<=算符文法的定義定義如果不含空產生式的上下文無關文法 G 中沒有形如 UÒVW的產生式，其中V,WVN則稱G 為算符文法（OG）。性質1：在算符文法中任何句型都不包含兩個相鄰的非終結符.(數學歸納法)出現在算符文法的句型 a 中，則 a 中任何含 x 的短語

18、必含有性質2：如 Vx 或 xV其中VVN,xVT, V.（反證法）2019/5/2627算符優先關系的定義在OG中 定義（算符優先關系）G中有形如.UÒxy或U Ò xVy.的產生式。x = yG中+有形如.U ÒxW的產生式,而x < y+Wy.或WVyÞÞG中有+ 形如.U Ò+Wy的產生式,而x>yW Þx或W Þ xV+若 S Þx 或SÞ Vx# < xx > # 規定則則+S ÞxS ÞxV或2019/5/2628算符優先文法的定義 在

19、OG文法G 中，若任意兩個終結符間至多有一種算符優先關系存在，則稱G為算符優先文法(OPG)。結論算符優先文法是無二義的。2019/5/2629算符優先關系表的構造由定義直接構造由關系圖法構造算符優先關系表2019/5/2630首先引入兩個概念 FIRSTVT(B)=b|B + b或B+Cb.ÞÞ 對于非終結符B，其往下推導所可能出現的首個算符+ LASTVT(B)=a|BÞ a或B Þ. aC 對于非終結符B，其往下推導所可能出現的最后一個算符2019/5/2631如何計算算符優先關系1) =關系 直接看產生式的右部，若出現了A ab或A aBb,則a

20、=b2)<關系 求出每個非終結符B的FIRSTVT(B) 若AaB,則²bFIRSTVT(B),a<b3)>關系 求出每個非終結符B的LASTVT(B)2019/5/26 若ABb,則²aLASTVT(B),a>b321)=關系由產生式(0)和(6),得#=#，（=） 2）<關系找形如：AaB的產生式#E：則#<FIRSTVT(E)+T: 則+<FIRSTVT(T)*F: 則*<FIRSTVT(F)­F:則 ­<FIRSTVT(F) (E: 則 (<FIRSTVT(E)3)>關系找形如：A

21、Bb的產生式E# ,則 LASTVT(E)>#E+ ,則 LASTVT(E)>+ T* ,則 LASTVT(T)>* P­ ,則 LASTVT(P)>­E) ,則 LASTVT(E)>)33+-*/­()i#+>><<<<><>->><<<<><>*>>>><<><>/>>>><<><>­>>>

22、><<><>(<<<<<<=<)>>>>>>>i> 201>9/5/2>6>>>>#<<<<<<<=文法GE：(0) E#E#(1) EE+T(2) ET(3) TT*F(4) TF(5) FP­F|P(6) P(E)(7) PiFIRSTVT(E)=# FIRSTVT(E)=+,*,­,(,iFIRSTVT(T)=*,­,(,iFIRSTVT(F)=­

23、,(,iFIRSTVT(P)=(,iLASTVT(E)=# LASTVT(E)=+,*,­,),iLASTVT(T)=*,­,),iLASTVT(F)=­,),iLASTVT(P)=),i算符優先分析算法歸約過程中，只考慮終結符之間的優先關系來確定句柄，而與非終結符無關。這樣去掉了對非終結符的歸約，所以用算符優先分析法的規約過程與規范歸約是不同的，P110.為解決在算符優先分析過程中如何尋找可歸約串，引進最左素短語的概念2019/5/2634算符文法的任一句型有如下形式：#N1a1N2a2.NnanNn+1#,若NiaiNjajNj+1為句柄，則有ai-1<ai=ai+1=.= aj-1 = aj> ai+1對于算符優先文法，如果aNb(或ab)出現在句型r中 若a<b，則在r中必含有b而不含a的短語存在 若a>b，則在r中必含有a而不含b的短語存在 若a=