自下而上的語法分析

1、1,第六章 自下而上的語法分析,清華大學(xué)計算機系,2,自下而上語法分析概述簡單優(yōu)先分析算符優(yōu)先分析,3,自下而上語法分析概述,As the name suggests, bottom-up parsing begins with a string and tries to backwards to the start symbol by applying the productions in reverse.也稱為移進(jìn)--歸約分

2、析,自底向上的語法分析,.,VAR,；,A,BEGIN,END,READ,（,）,A,VAR A;BEGIN READ(A)END.,移進(jìn)規(guī)約接受錯誤,4,自下而上語法分析概述,如名字如示，自下而上語法分析試圖將一個字符串反向歸約至開始符號。自下而上語法分析比自上而下語法分析更有效率，對語法的限制更少,5,文法G[S]：(1) S → aAcBe(2) A → b(3) A → Ab(4) B → d,a,b,b

3、,c,d,e,,,,步驟,符號棧,輸入符號串,動作,,1） # abbcde# 移進(jìn),2） #a bbcde# 移進(jìn),4） #aA bcde# 移進(jìn),6） #aA cde# 移進(jìn),7） #aAc de# 移進(jìn),9）

4、 #aAcB e# 移進(jìn),11） #S # 接受,分析符號串a(chǎn)bbcde是否G[S]的句子,對輸入串a(chǎn)bbcde#的移進(jìn)-規(guī)約分析過程,6,自下而上語法分析算法的一般描述,Let I = input stringrepeatpick a non-empty substring ? of Iwhere X? ? is a p

5、roductionif no such ?, backtrackreplace one ? by X in Iuntil I = “S” (the start symbol) or all possibilities are exhausted,7,算法應(yīng)考慮的問題,算法是否能夠終止？算法是否快速？算法是否能夠處理所有的情況？在每一步中如何選擇子串進(jìn)行歸約？,8,自下而上語法分析的策略：移進(jìn)-規(guī)約分析；移進(jìn)

6、就是將一個終結(jié)符推進(jìn)棧歸約就是將0個或多個符號從棧中彈出，根據(jù)產(chǎn)生式將一個非終結(jié)符壓入棧移進(jìn)-歸約過程是自頂向下最右推導(dǎo)的逆過程（規(guī)范歸約）,9,文法G[E]：E ? T + E | TT ? int * T | int | (E),E,T,E,+,int,*,int,T,int,T,10,A Shift-Reduce Parse in Detail (1),+,int,*,int,int,?,11,A Shift-Reduce

7、 Parse in Detail (2),+,int,*,int,int,?,12,A Shift-Reduce Parse in Detail (3),+,int,*,int,int,?,13,A Shift-Reduce Parse in Detail (4),+,int,*,int,int,?,14,A Shift-Reduce Parse in Detail (5),+,int,*,int,int,T,?,15,A Shift-

8、Reduce Parse in Detail (6),T,+,int,*,int,int,T,?,16,A Shift-Reduce Parse in Detail (7),T,+,int,*,int,int,T,?,17,A Shift-Reduce Parse in Detail (8),T,+,int,*,int,int,T,?,18,A Shift-Reduce Parse in Detail (9),T,+,int,*,int

9、,T,int,T,?,19,A Shift-Reduce Parse in Detail (10),T,E,+,int,*,int,T,int,T,?,20,A Shift-Reduce Parse in Detail (11),E,T,E,+,int,*,int,T,int,T,?,21,我們?nèi)绾螞Q定什么時候移進(jìn)，什么時候規(guī)約？考慮 int | * int + int我們可以用 T ? int進(jìn)行歸約，而得到 T | * int

10、+ int致命錯誤: 無法規(guī)約到開始符號 E直覺: Want to reduce only if the result can still be reduced to the start symbol一般的移進(jìn)-歸約策略：若句柄在棧頂出現(xiàn)，則歸約否則移進(jìn)句柄（Handles）:句型的最左直接短語,22,短語、直接短語、句柄的定義：文法G[S]， S αAδ且A b則稱b是句型αbδ相對于非終結(jié)符A的短語。

11、若有A ? b則稱b是句型αbδ相對于該規(guī)則A → b的直接短語。 一個句型的最左直接短語稱為該句型的句柄。,23,Conflicts,實際應(yīng)用中可能出現(xiàn)的’沖突‘移進(jìn)與歸約都合法，產(chǎn)生移進(jìn)-歸約沖突歸約時可以適用兩個不同的產(chǎn)生式，產(chǎn)生歸約-歸約沖突,24,Source of Conflicts,二義文法會導(dǎo)致‘沖突’但應(yīng)注意，許多的非二義文法同樣會導(dǎo)致‘沖突’,25,Conflict Example,考慮下面的二義文法:,

12、26,One Shift-Reduce Parse,27,Another Shift-Reduce Parse,28,Conflict Solutions,改寫文法根據(jù)產(chǎn)生式出現(xiàn)的順序來選擇根據(jù)算符的優(yōu)先級,29,自下而上的分析算法,優(yōu)先分析法簡單優(yōu)先分析法算符優(yōu)先分析法LR分析,30,簡單優(yōu)先分析法,按照文法符號（包括終結(jié)符和非終結(jié)符）的優(yōu)先關(guān)系確定句柄。示例見下頁,31,文法G[S]：(1) S → bAb(2) A

13、 → (B|a(3) B → Aa),步驟,符號棧,輸入符號串,動作,,1） # b(aa)b# #<b,移進(jìn),2） #b (aa)b# b<(,移進(jìn),3） #b( aa)b# (<a,移進(jìn),4） #b(a a)b# a>a,歸約A→a,5

14、） #b(A a)b# A=a,移進(jìn),6） #b(Aa )b# a=),移進(jìn),7） #b(Aa) b# )>b,歸約B→Aa),8） #b(B b# B>b,歸約A→(B,9） #bA b# A=b,移進(jìn),10）

15、 #bAb # b>#,歸約S→bAb,11） #S # 接受,對輸入串b(aa)#的簡單優(yōu)先分析過程,簡單優(yōu)先關(guān)系矩陣,32,優(yōu)先關(guān)系,優(yōu)先關(guān)系X=Y ? 文法G中存在產(chǎn)生式A→...XY...XY? 文法G中存在產(chǎn)生式A→...BD...，且B ...X,D Y...如何確定兩個文法符號之間的優(yōu)先關(guān)系？,33,簡單優(yōu)

16、先文法的定義,滿足以下條件的文法是簡單優(yōu)先文法（1）在文法符號集V中，任意兩個符號之間最多只有一種優(yōu)先關(guān)系成立。（2）在文法中任意兩個產(chǎn)生式?jīng)]有相同的右部（3）不含空產(chǎn)生式,34,算符優(yōu)先分析,某些文法具有“算符”特性表達(dá)式運算符（優(yōu)先級、結(jié)合性）人為地規(guī)定其算符的優(yōu)先順序，即給出優(yōu)先級別和同一級別的結(jié)合性只考慮算符之間的優(yōu)先關(guān)系來確定句柄,35,文法G[E]：E→E+E|E-E|E*E|E/E|E?E|(E)|i,步驟,符

17、號棧,輸入符號串,動作,,1） # i+i*i# #<i,移進(jìn),2） #i +i*i# #+,規(guī)約,3） #E +i*i# #<+,移進(jìn),4） #E+ i*i# +<i,移進(jìn),5） #E+i *i#

18、 +*,規(guī)約,6） #E+E *i# +<*,移進(jìn),7） #E+E* i# *<i,移進(jìn),8） #E+E*i # *#,規(guī)約,9） #E+E*E # +#,規(guī)約,10） #E+E #

19、 ##,規(guī)約,11） #E # 接受,對輸入串i+i*i的算符優(yōu)先分析過程,,算符優(yōu)先關(guān)系表,36,如何確定算符優(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)先性低于與其相鄰的算

20、符,文法G[E]：E→E+E|E-E|E*E|E/E|E?E|(E)|i,算符優(yōu)先關(guān)系表,37,算符文法的定義,定義 如果不含空產(chǎn)生式的上下文無關(guān)文法 G 中沒有形如 U?…VW…的產(chǎn)生式，其中V,W∈VN則稱G 為算符文法（OG）。性質(zhì)1：在算符文法中任何句型都不包含兩個相鄰的非終結(jié)符.(數(shù)學(xué)歸納法)性質(zhì)2：如 Vx 或 xV 出現(xiàn)在算符文法的 句型 ? 中，其中V∈VN,x∈VT, 則 ? 中任何 含 x 的短語必含有V.（

21、反證法）,38,算符優(yōu)先關(guān)系的定義,在OG中 定義 （算符優(yōu)先關(guān)系） x = y G中有形如.U?…xy…或U ? …xVy.. 的產(chǎn)生式。 x y G中有形如.U ? …Wy…的產(chǎn)生式,而 W …x或W … xV規(guī)定 若 S x…或 S Vx… 則 # #,39,算

22、符優(yōu)先文法的定義,在 OG文法 G 中，若任意兩個終結(jié)符間至多有一種算符優(yōu)先關(guān)系存在，則稱G 為算符優(yōu)先文法(OPG)。注意：允許b>c,c>b;不允許b>c,b<c,b=c 結(jié)論 算符優(yōu)先文法是無二義的。,40,算符優(yōu)先關(guān)系表的構(gòu)造,由定義直接構(gòu)造由關(guān)系圖法構(gòu)造算符優(yōu)先關(guān)系表,41,首先引入兩個概念FIRSTVT(B)={b|B b…或B Cb...}對于非終結(jié)符B，其往下推導(dǎo)所可

23、能出現(xiàn)的首個算符LASTVT(B)={a|B a…或B aC...}對于非終結(jié)符B，其往下推導(dǎo)所可能出現(xiàn)的最后一個算符,42,如何計算算符優(yōu)先關(guān)系,1) ‘=‘關(guān)系直接看產(chǎn)生式的右部，若出現(xiàn)了A →…ab…或A →…aBb,則a=b2)’’關(guān)系求出每個非終結(jié)符B的LASTVT(B)若A→…Bb…,則?a∈LASTVT(B),a>b,43,文法G[E]：(0) E’→#E#(1) E→E+T(2)

24、 E→T(3) T→T*F(4) T→F(5) F→P?F|P(6) P→(E)(7) P→i,FIRSTVT(E’)={#}FIRSTVT(E)={+,*,?,(,i}FIRSTVT(T)={*,?,(,i}FIRSTVT(F)={?,(,i}FIRSTVT(P)={(,i}LASTVT(E’)={#}LASTVT(E)={+,*,?,),i}LASTVT(T)={*,?,),i}LASTVT(F)={?,)

25、,i}LASTVT(P)={),i},1)‘=’關(guān)系由產(chǎn)生式(0)和(6),得#=#，（=）2）‘<’關(guān)系找形如：A→…aB…的產(chǎn)生式#E：則#<FIRSTVT(E)+T: 則+<FIRSTVT(T) *F: 則*<FIRSTVT(F)?F:則 ?<FIRSTVT(F)(E: 則 (<FIRSTVT(E),3)‘>’關(guān)系找形如：A→…Bb…的產(chǎn)生式E# ,則 LASTV

26、T(E)>#E+ ,則 LASTVT(E)>+ T* ,則 LASTVT(T)>* P? ,則 LASTVT(P)>? E) ,則 LASTVT(E)>),44,算符優(yōu)先分析算法,歸約過程中，只考慮終結(jié)符之間的優(yōu)先關(guān)系來確定句柄，而與非終結(jié)符無關(guān)。這樣去掉了單非終結(jié)符的歸約，所以用算符優(yōu)先分析法的規(guī)約過程與規(guī)范歸約是不同的，P110.為解決在算符優(yōu)先分析過程中如何尋找句柄，引進(jìn)最左素短語的概念,4

27、5,算符文法的任一句型有如下形式：#N1a1N2a2......NnanNn+1#,若Niai......NjajNj+1為句柄，則有ai-1 ai+1對于算符優(yōu)先文法，如果aNb(或ab)出現(xiàn)在句型r中若ab，則在r中必含有a而不含b的短語存在若a=b，則在r中含有a的短語必含有b，反之亦然定義 cfg G 的句型的素短語是一個短語，它至少包含一個終結(jié)符，且除自身外不再包含其他素短語。處于句型最左邊的素短語為最左素短

28、語,46,文法G[E]：(1) E→E+T(2) E→T(3) T→T*F(4) T→F(5) F→P?F|P(6) P→(E)(7) P→i,句型#T+T*F+i#其短語有：T+T*F+iT+T*FTT*Fi,E,E,T,+,+,E,T,F,*,F,T,T,i,,,,,,,,,,,,,最左素短語為：T*F,句型#N+N*N+i#的歸約過程,N,N,+,+,N,N,i,*,N,N,,,,,,,,,,,N,47,