第六章 算符優(yōu)先分析文法.ppt

1、1,第六章 自底向上優(yōu)先分析,鄭先容,2,本章主要內(nèi)容及學時安排,6.1 自底向上語法優(yōu)先分析概述 6.2 簡單優(yōu)先分析法 6.3 算符優(yōu)先分析法 理論講授：4學時 上機：2學時,6.3 算符優(yōu)先分析法,3,本次課重點與難點,直觀算符優(yōu)先分析法 算符優(yōu)先法的定義（重點） 算符優(yōu)先關系表的構造（重點、難點） 算符優(yōu)先分析算法（難點）,4,回顧簡單優(yōu)先分析法,#,a,b,b,c,d,e,A b,A,A Ab,c,B d,SaAcBe,B,S,A,b,b,a,c,e,A,SaAcBe,aAcde,aAbcde,abbcde,SaAcBe,B d,A Ab,A b,5,回顧簡單優(yōu)先分析法,簡單優(yōu)先分析

2、算法的基本思想：,?,按一定原則求出該文法所有符號之間的優(yōu)先關系，并按照這種關系確定規(guī)約過程中的句柄，是一種規(guī)范規(guī)約。,特點：準確、規(guī)范，但分析效率底，實際使用價值不大。,6,6.3 算符優(yōu)先分析法,算符優(yōu)先分析法 只規(guī)定算符（終結符）之間的優(yōu)先關系。在歸約過程中只要找到句柄就歸約，不必考慮歸約到哪個非終結符，因此不是規(guī)范歸約。 特點：速度快，特別適合于表達式的分析 通過算符之間的優(yōu)先關系來確定句柄,7,先看一個例題：,例. 已知文法GE： EE+E EE*E E i,輸入串i+i*i ，歸約過程如下,8,步驟,符號棧,輸入符號串,優(yōu)先關系,1） # i+i*i# #i 移進,2） #i +i

3、*i# #+ 規(guī)約,3） #E +i*i# #+ 移進,4） #E+ i*i# +i 移進,5） #E+i *i# +* 規(guī)約,6） #E+E *i# +* 移進,7） #E+E* i# *i 移進,8） #E+E*i # *# 規(guī)約,9） #E+E*E # +# 規(guī)約,10） #E+E # # 規(guī)約,11） #E # 接受,動作,GE：EE+E, E E*E, E i 輸入串i+i*i,9,分析可知：若只從 移進歸約的角度來考慮，在第6步時棧頂已出現(xiàn)了句柄E+E，可以進行歸約了，但是明顯是錯誤的，因為這樣就不符合算術運算規(guī)律 。,移進歸約,所以對于表達式，我們可以 人為地規(guī)定其算符的優(yōu)先順序

4、，即給出優(yōu)先級別和同一級別的結合性。,人為,10,算符優(yōu)先分析法,直觀的算符優(yōu)先分析法 算符優(yōu)先分析法 區(qū)別是什么？ 算符優(yōu)先關系的產(chǎn)生,11,算符優(yōu)先關系： a b 表示a優(yōu)先級高于b,注意：優(yōu)先關系的有序性！,直觀算符優(yōu)先分析法,12,優(yōu)先關系的有序性,i i i 因此 有 i i i 因此 有 優(yōu)先關系的有序性,13,（0）i的優(yōu)先級最高 （1）優(yōu)先級次于i，右結合 （2）*和/優(yōu)先級次之，左結合 （3）+和-優(yōu)先級最低，左結合 （4）括號(,)的優(yōu)先級大于括號外的運算符，小于括號內(nèi)的運算符，內(nèi)括號的優(yōu)先性大于外括號 （5）#的優(yōu)先性低于與其相鄰的算符,已知表達式文法GE： EE+E|E

5、-E|E*E|E/E|EE|(E)|i 各算符的優(yōu)先性及結合性如下：,14,簡單算符優(yōu)先關系表如下,15,算符文法的定義,設有一文法G，如果G中沒有形如 ABC (V*) 的產(chǎn)生式，其中B和C為非終結符，則稱G為 算符文法(或稱OG文法)。,即任何一個產(chǎn)生式中都不包含兩個非終結符相鄰的情況，就是算符文法。,16,性質(zhì)1：在算符文法中任何句型都不包含兩個相鄰的非終結符。 性質(zhì)2：如果Ab或（bA）出現(xiàn)在算符文法的句型中，其中AVN， b VT，則中任何含b的短語必含有A。,算符文法的性質(zhì),（含b的短語必含A，含A的短語不一定含b）,17,如果Ab或（bA）出現(xiàn)在算符文法的句型中，其中AVN， b

6、 VT，則中任何含b的短語必含有A。,S,=abA,中含b的短語不含有A。,B,含b的短語不含有其他元素；,含b的短語含有它前面的元素。,B,含A的短語不一定含b。,B,18,設G是一個算符文法，a和b是任意兩個終結符，A，B，C是非終結符，算符優(yōu)先關系如下： (1)a=b當且僅當G中含有形如Aab或AaBb的產(chǎn)生式; (2) ab當且僅當G中含有形如ABb的產(chǎn)生式，且Ba或BaC 。,算符優(yōu)先關系的定義,19,(2) ab當且僅當G中含有形如AaB的產(chǎn)生式，且Bb或BCb;,(3) ab當且僅當G中含有形如ABb的產(chǎn)生式，且Ba或BaC 。,20,設有一不含產(chǎn)生式的算符文法G，如果對任意兩個

7、終結符a，b之間至多只有= ，三種關系的一種成立，則稱G是一個算符優(yōu)先文法(也稱OPG文法)。,即a b，a b，b a同時存在。,算符優(yōu)先文法的定義,?,21,例：已知表達式文法GE： EE+E | E*E | (E) | i 證明GE不是OPG文法。 證明如下：,a b當且僅當G中含有形如AaB的產(chǎn)生式，且Bb或BCb；,a b當且僅當G中含有形如ABb的產(chǎn)生式，且Ba或BaC 。,因為：EE+E ， EE*E 則有 + *,又因為：EE*E, EE+E 則有 + *,所以不是算符優(yōu)先文法。,22,用表格形式來表示各終結符號的優(yōu)先關系，這種表稱為優(yōu)先關系表。 構造優(yōu)先關系表的方法：按照定義

8、來構造 按關系圖來構造,首先引入兩個概念： FIRSTVT集合LASTVT集合 (其中表示V*中的符號串),+,+,算符優(yōu)先關系表,按照定義來構造,firstVT(B)=b|Bb 或 BCb,lastVT(B)=a|Ba 或 BaC,+,+,表示由B推導出的第一個算符（終結符）,表示由B推導出的最后算符（終結符）,23,1) = 關系 直接看產(chǎn)生式的右部，若出現(xiàn)了A ab或A aBb，則a=b 2) 關系 求出每個非終結符B的LASTVT(B) 若ABb，則aLASTVT(B)，ab,三種算符優(yōu)先關系的計算：,24,例：已知文法如下，計算優(yōu)先關系 E#E# EE+T|T TT*F|F FPF|

9、P P（E）|i,分析： 計算優(yōu)先關系實際上是求 ，（，）， i 之間的優(yōu)先關系,25,求 = 關系, E#E# # = # P(E) ( = ) 寫入優(yōu)先關系表,E#E# EE+T|T TT*F|F FPF|P P（E）|i,= 關系 直接看產(chǎn)生式的右部，若出現(xiàn)了A ab或A aBb，則a=b,26,求 關系,求出每個非終結符B的FIRSTVT(B) 若AaB，則bFIRSTVT(B)，ab,E#E# EE+T|T TT*F|F FPF|P P（E）|i,FIRSTVT(E) FIRSTVT(E) FIRSTVT(T) FIRSTVT(F) FIRSTVT(P),=# =+,*, ( , i

10、 =*, ( , i =, ( , i = ( , i ,E#E#且P(E)則#,(FIRSTVT(E) #+,#*,#,#(,#I,(+,(*,(,(,(i,EE+T則+FIRSTVT(T) +*,+,+(,+i,TT*F且FPF則*,FIRSTVT(F) ,(,i,*,*(,*i,27,算符優(yōu)先關系表,28,其中表示V*中的符號串 FIRSTVT(B)=b|Bb 或 BCb,這里E#E#， E #E#,E#E# EE+T ET TT*F TF FPF FP P（E ） Pi,+,+,求FIRSTVT(E), # FIRSTVT(E) 此外，沒有符合定義要求的元素包含在FIRSTVT(E)中

11、，即FIRSTVT(E)#,29,求FIRSTVT(E),E#E# EE+T ET TT*F TF FPF FP P（E ） Pi,其中表示V*中的符號串 FIRSTVT(B)=b|Bb 或 BCb,這里 EE+T ， E E+T, + FIRSTVT(E),這里 ET，TT*F, E T*F,+,+,+, * FIRSTVT(E),這里ET,TF,FPF,EPF,+, FIRSTVT(E),這里ET,TF,FP, P(E)|i, E(E)且Ei,+,+, (,i FIRSTVT(E),= +,*,(,i,30,求 關系,求出每個非終結符B的LASTVT(B) 若ABb，則aLASTVT(B)

12、，ab,E#E# EE+T|T TT*F|F FPF|P P（E）|i,LASTVT(E) LASTVT(E) LASTVT(T) LASTVT(F) LASTVT(P),=# =+,*, ) , i =*, ) , i =, ) , i = ) , i ,E#E#且P(E)且EE+T 則LASTVT(E)+,#,) +#,*#,#,)#,i#,+),*),),),i), +,*+,+,)+,i+,FPF 則LASTVT(P) ),i,TT*F 則LASTVT(T)* *,*,)*,i*,31,其中表示V*中的符號串 LASTVT(B)=a|Ba 或 BaC,這里E#E#，E #E#,E#E#

13、 EE+T ET TT*F TF FPF FP P（E ） Pi,+,+,求LASTVT(E), #LASTVT(E) 此外，沒有符合定義要求的元素包含在LASTVT(E)中，即LASTVT(E) #,32,求LASTVT(E),其中表示V*中的符號串 LASTVT(B)=a|Ba 或 BaC,E#E# EE+T ET TT*F TF FPF FP P（E ） Pi,這里 EE+T ， E E+T, + LASTVT(E),這里 ET，TT*F, E T*F, * LASTVT(E),這里ET,TF,FPF,EPF, LASTVT(E),這里ET,TF,FP, P(E)|i, E(E)且Ei,

14、 ),iLASTVT(E),= +,*,),i,33,算符優(yōu)先關系表,34,算符優(yōu)先關系表,35,算符優(yōu)先分析算法,歸約過程中，只考慮終結符之間的優(yōu)先關系來確定句柄，而與非終結符無關。這樣去掉了單非終結符的歸約，所以用算符優(yōu)先分析法的規(guī)約過程與規(guī)范歸約是不同的。 為解決在算符優(yōu)先分析過程中如何尋找句柄，引進最左素短語的概念。,36,算符優(yōu)先分析句型的性質(zhì),算符文法的任一句型有如下形式：#N1a1N2a2.NnanNn+1#, 若Niai.NjajNj+1為句柄，則有ai-1 ai+1 對于算符優(yōu)先文法，若句型r中含有aNb(或ab) 若ab，則在r中必有含a而不含b的短語存在 若a=b，則在r

15、中含有a的短語必含有b，反之亦然,37,最左素短語,定義：設有文法GS，其中句型的素短語是一個短語，它至少包含一個終結符，并除自身外不包含其它素短語，最左邊的素短語稱最左素短語。 例：文法GE: EE+T|T TT*F|F FPF|P P（E）|I 尋找句型#T+T*F+i#的最左素短語,算符優(yōu)先規(guī)約的關鍵,38,句型#T+T*F+i#的短語有： T ； T*F ； T+T*F ； i； T+T*F+i .,句型#T+T*F+i#的語法樹,設有文法GS，其中句型的素短語是一個短語，它至少包含一個終結符，并除自身外不包含其它素短語，最左邊的素短語稱最左素短語。,根據(jù)素短語的定義可知： i和T*F為素短語。 其中：T+T*F和T+T*F+i 不是素短語。T*F為最左素短語。,39,對于上例，輸入符號串i+i*i# ，算符優(yōu)先規(guī)約過程,步驟,符號棧,輸入符號串,優(yōu)先關系,1） # i+i*i# #i 移進,2） #i +i*i# i+ 規(guī)約,3） #F +i*i# #+ 移進,4） #F+ i*i# +i 移進,5） #F+i *i# i* 規(guī)約,6） #F+F *i# +* 移進,7） #F+F* i# *i 移進,8） #F+F*i # i# 規(guī)