1、1,第六章 自底向上優(yōu)先分析,鄭先容,2,本章主要內(nèi)容及學(xué)時(shí)安排,6.1 自底向上語(yǔ)法優(yōu)先分析概述 6.2 簡(jiǎn)單優(yōu)先分析法 6.3 算符優(yōu)先分析法 理論講授：4學(xué)時(shí) 上機(jī)：2學(xué)時(shí),6.3 算符優(yōu)先分析法,3,本次課重點(diǎn)與難點(diǎn),直觀算符優(yōu)先分析法 算符優(yōu)先法的定義（重點(diǎn)） 算符優(yōu)先關(guān)系表的構(gòu)造（重點(diǎn)、難點(diǎn)） 算符優(yōu)先分析算法（難點(diǎn)）,4,回顧簡(jiǎn)單優(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,回顧簡(jiǎn)單優(yōu)先分析法,簡(jiǎn)單優(yōu)先分析

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

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

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

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

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

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

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

9、P P（E）|i,分析： 計(jì)算優(yōu)先關(guān)系實(shí)際上是求 ，（，）， i 之間的優(yōu)先關(guān)系,25,求 = 關(guān)系, E#E# # = # P(E) ( = ) 寫(xiě)入優(yōu)先關(guān)系表,E#E# EE+T|T TT*F|F FPF|P P（E）|i,= 關(guān)系 直接看產(chǎn)生式的右部，若出現(xiàn)了A ab或A aBb，則a=b,26,求 關(guān)系,求出每個(gè)非終結(jié)符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)先關(guān)系表,28,其中表示V*中的符號(hào)串 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) 此外，沒(méi)有符合定義要求的元素包含在FIRSTVT(E)中

11、，即FIRSTVT(E)#,29,求FIRSTVT(E),E#E# EE+T ET TT*F TF FPF FP P（E ） Pi,其中表示V*中的符號(hào)串 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,求 關(guān)系,求出每個(gè)非終結(jié)符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*中的符號(hào)串 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) 此外，沒(méi)有符合定義要求的元素包含在LASTVT(E)中，即LASTVT(E) #,32,求LASTVT(E),其中表示V*中的符號(hào)串 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)先關(guān)系表,34,算符優(yōu)先關(guān)系表,35,算符優(yōu)先分析算法,歸約過(guò)程中，只考慮終結(jié)符之間的優(yōu)先關(guān)系來(lái)確定句柄，而與非終結(jié)符無(wú)關(guān)。這樣去掉了單非終結(jié)符的歸約，所以用算符優(yōu)先分析法的規(guī)約過(guò)程與規(guī)范歸約是不同的。 為解決在算符優(yōu)先分析過(guò)程中如何尋找句柄，引進(jìn)最左素短語(yǔ)的概念。,36,算符優(yōu)先分析句型的性質(zhì),算符文法的任一句型有如下形式：#N1a1N2a2.NnanNn+1#, 若Niai.NjajNj+1為句柄，則有ai-1 ai+1 對(duì)于算符優(yōu)先文法，若句型r中含有aNb(或ab) 若ab，則在r中必有含a而不含b的短語(yǔ)存在 若a=b，則在r

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