精品課程《編譯原理》第6章自底向上語(yǔ)法分析ppt課件

1、6.1 6.1 自底向上語(yǔ)法分析自底向上語(yǔ)法分析一、自底向上方法概述 自底向上方法：從給定終極符串進(jìn)展歸約，并歸約成文法的初始符。 移進(jìn)-歸約方法的四個(gè)動(dòng)作: 移進(jìn):輸入流頭符讀到分析棧中 歸約:分析棧句柄歸約非終極符 接受:分析勝利 報(bào)錯(cuò):處置錯(cuò)誤 例子：對(duì)輸入串a(chǎn)bbcde進(jìn)展分析，檢查該串能否是GS的句子。 GS： SaAcBe Ab AAb Bd對(duì)輸入串a(chǎn)bbcde的最右推導(dǎo)是：SaAcBeaAcdeaAbcdeabbcdeSaAcBeaAcdeaAbcdeabbcde所以移進(jìn)-歸約方法的分析過程如下：移進(jìn)e#aAcB9歸約(Bd)e#aAcd8移進(jìn)de# #aAc7移進(jìn)cde# #a

2、A6歸約(AAb)cde# #aAb5移進(jìn)bcde# #aA4歸約(Ab)bcde# #ab3移進(jìn)bbcde# #a2移進(jìn)abbcde# #1Action 輸入串 符號(hào)棧 步驟 歸約(SaAcBe)#aAcBe10接受#S11例：思索文法 G(E): ET|E+T TF|T*F Fi|(E)并假定已給定終極符串(i+i)*i。下面是對(duì)該串的移入歸約過程: ( ,(i+i)*i) 1=移=( , i+i)*i) 2=移=(i , +i)*i) 3=歸=(F , +i)*i) 4=歸=(T , +i)*i) 5=歸=(E , +i)*i) 6=移=(E+ , i)*i) 7=移=(E+i , )*

3、i) 8=歸=(E+F , )*i) 9=歸=(E+T , )*i) 10 =歸=(E , )*i) 11=移=(E) , *i) 12=歸=(F , *i) 13=歸=(T , *i) 14=移=(T* , i) 15 =移=(T*i , ) 16=歸=(T*F , ) 17 =歸=(T , ) 18=歸=(E , ) 19 設(shè)Si和Sj是文法的恣意兩個(gè)符號(hào)，那么它們?cè)诰湫椭邢噜彸霈F(xiàn)的充要條件是必需滿足以下條件之一：1.有形如USiSj 的產(chǎn)生式2.有形如USiW 且W Sj的產(chǎn)生式3.有形如UVSj 且V Si的產(chǎn)生式的產(chǎn)生式4.有形如UVW 且V Si和W Sj的產(chǎn)生式的產(chǎn)生式+6.2

4、6.2 簡(jiǎn)單優(yōu)先方法簡(jiǎn)單優(yōu)先方法 定義了三種優(yōu)先關(guān)系( , , )其定義如下： Si Sj：當(dāng)且僅當(dāng)存在如下的產(chǎn)生式USiSj 例子：AabABc，其中b與A相鄰 b A Si Sj：當(dāng)且僅當(dāng)存在如下產(chǎn)生式USiW，且有W Sj) + 例子：AabABc Bbcd，其中A與b相鄰 A b 例子：AabABc Accd Bbcb，其中d與b相鄰 d b Si Sj：當(dāng)且僅當(dāng)存在如下產(chǎn)生式 UVW，且有V Si和W Sj) +* 優(yōu)先關(guān)系可用矩陣來(lái)表示，稱這種矩陣為優(yōu)先關(guān)系矩陣。 詳細(xì)定義如以下圖：Msi,sj當(dāng) Si Sj當(dāng) Si Sj當(dāng) Si Sj空否那么* STEP2：對(duì)每個(gè)符號(hào)對(duì)Si，Sj

5、填寫優(yōu)先關(guān)系矩陣。構(gòu)造優(yōu)先關(guān)系矩陣步驟：* STEP1：對(duì)每個(gè)非終極符號(hào)W求下面兩種集合 FIRST(W)=S|W S,S(VnVt) LAST(W)=S|W S,S(VnVt)+例子：假設(shè)有文法 GZ: ZbMb Ma|( L LM a )第一步： Zb M b b M Zb M b(a b ( b a第二步： Zb M b M b Zb M b)La ) b L b a b)a(bLMZ)a(bLMZ所以對(duì)GZ: ZbMb Ma|( L LM a ) 有：FRIST(M)= (,a LAST(M)= ),L,a 有下表：) L abLASTM ( a( abFIRSTLMZ定義3.13 滿

6、足下面兩個(gè)條件的文法稱為簡(jiǎn)單優(yōu)先文法。 1.恣意兩個(gè)符號(hào)至多成立一種關(guān)系 2.恣意兩個(gè)產(chǎn)生式具有不同右部 例子：GZ: EE+T|T TT*F|F F(E)|i EE+TT*F+ T + T下面文法均不為簡(jiǎn)單優(yōu)先文法 v G1:Bav Da (有兩個(gè)一樣的右部)v G2:EE+T|Tv TT*F|F v F(E)|i (其中( E,( E)定理3.10 設(shè)S1S2Sn是簡(jiǎn)單優(yōu)先文法的規(guī)范句型,其子串SiSi+1Sj滿足條件:Si-1 Si，Si Si+1 Sj ， Sj Sj+1，那么SiSi+1Sj定為句柄。 例子：ZabCDe a b C D e 那么bCD是句柄。+ 試用簡(jiǎn)單優(yōu)先方法分析

7、符號(hào)串b( a a )b 能否為該文法的句子。例：設(shè)有GZ: ZbMb Ma|( L LM a )分析句子b( a a )b的過程：)a(bLMZ)a(bLMZ(aa)b# #bb(aa)b# #b(aa)b# #歸約符 輸入流 分析棧 關(guān)系 a)b# #b(aMa)b# #b(aa)b# #b(M移進(jìn)工程的處置移進(jìn)工程的處置b#bMMb#b(LLb# #b(Ma)b# #b(Maa)b# #b(MMa)b# #b(aaa)b# #b(aa)b# #bb(aa)b# #歸約符 輸入流 分析棧 Z#bMb停#Z關(guān)系 算符優(yōu)先文法的定義算符優(yōu)先文法的定義 算符優(yōu)先關(guān)系表的構(gòu)造算符優(yōu)先關(guān)系表的構(gòu)造

8、算符優(yōu)先分析算法算符優(yōu)先分析算法 算符優(yōu)先分析法的局限性算符優(yōu)先分析法的局限性6.3 6.3 算符優(yōu)先方法算符優(yōu)先方法分析程序模型分析程序模型總控程序算符優(yōu)先關(guān)系表產(chǎn)生式輸入串#輸出6.3.1 直觀算符優(yōu)先分析法直觀算符優(yōu)先分析法 自下而上分析算法自下而上分析算法 模型模型-移進(jìn)歸約移進(jìn)歸約 算符優(yōu)先分析不是規(guī)范歸約算符優(yōu)先分析不是規(guī)范歸約如何確定算符優(yōu)先關(guān)系？如何確定算符優(yōu)先關(guān)系？人為確定：人為確定：1 1i i的優(yōu)先級(jí)最高的優(yōu)先級(jí)最高1 1 優(yōu)先級(jí)次于優(yōu)先級(jí)次于i i，右，右結(jié)合結(jié)合2 2* *和和/ /優(yōu)先級(jí)次之，左優(yōu)先級(jí)次之，左結(jié)合結(jié)合3 3+ +和和- -優(yōu)先級(jí)最低，左優(yōu)先級(jí)最低，左

9、結(jié)合結(jié)合4 4括號(hào)括號(hào)( (, ,) )的優(yōu)先級(jí)大的優(yōu)先級(jí)大于括號(hào)外的運(yùn)算符，小于于括號(hào)外的運(yùn)算符，小于括號(hào)內(nèi)的運(yùn)算符，內(nèi)括號(hào)括號(hào)內(nèi)的運(yùn)算符，內(nèi)括號(hào)的優(yōu)先性大于外括號(hào)的優(yōu)先性大于外括號(hào)5 5# #的優(yōu)先性低于與其相的優(yōu)先性低于與其相鄰的算符鄰的算符文法文法GE：EE+E|E-E|E*E|E/E|EE|(E)|i+-*/ ()i#+-*/ (=i#=算符優(yōu)先關(guān)系表算符優(yōu)先關(guān)系表 6.3.2 算符優(yōu)先文法的定義算符優(yōu)先文法的定義 定義：假設(shè)不含空產(chǎn)生式的上下文無(wú)關(guān)文法定義：假設(shè)不含空產(chǎn)生式的上下文無(wú)關(guān)文法 G G 中中沒有形如沒有形如 A ABCBC的產(chǎn)生式，其中的產(chǎn)生式，其中B B，CVN CV

10、N 那那么稱么稱G G 為算符文法為算符文法OGOG。 例例6.1 GE6.1 GE：EE+E|E-|EEE+E|E-|E* *E|E/E|EE|E/E|EE|(E)|iE|(E)|i 例例6.2 G6.2 GE: EEE: EET|TT|T TT TT* *F|FF|F FPF FPFP P P(E)|i P(E)|i 性質(zhì)性質(zhì)1 1：在算符文法中任何句型都不包含兩個(gè)相鄰：在算符文法中任何句型都不包含兩個(gè)相鄰的非終結(jié)符的非終結(jié)符. . 性質(zhì)性質(zhì)2 2：如：如 Ab Ab 或或 bA bA 出如今算符文法的出如今算符文法的 句型句型 中，其中中，其中 AVN AVN，bVTbVT， 那么那么

11、中任何中任何 含含 b b 的短語(yǔ)必含有的短語(yǔ)必含有A A。算符優(yōu)先關(guān)系算符優(yōu)先關(guān)系在在OGOG中中 定義定義 算符優(yōu)先關(guān)系算符優(yōu)先關(guān)系 a = b G a = b G中有形如：中有形如：A Aabab 或或A A aBb. aBb.的產(chǎn)生式。的產(chǎn)生式。 a b G a b G a b G中有形如中有形如: A : A Bb Bb的產(chǎn)生的產(chǎn)生 式式, ,而而 B a B a 或或 B aC B aC 規(guī)定規(guī)定 假設(shè)假設(shè) S a S a或或 S Ca S Ca 那么那么 # a # # a #在在 OG OG文法文法 G G 中，假設(shè)恣意兩個(gè)終結(jié)符間至多中，假設(shè)恣意兩個(gè)終結(jié)符間至多有一種算符優(yōu)先

12、關(guān)系存在，那么稱有一種算符優(yōu)先關(guān)系存在，那么稱G G 為算符優(yōu)為算符優(yōu)先文法先文法(OPG)(OPG)。留意：允許留意：允許bc, cb;bc, cb;不允許不允許 bc, bc, bc, b=c中任兩個(gè)中任兩個(gè) 同時(shí)存在。同時(shí)存在。b=c b=c 不一定不一定 c = b c = b。例例6.16.1中：中：“ = = “，“。 結(jié)論結(jié)論 : : 算符優(yōu)先文法是無(wú)二義的。算符優(yōu)先文法是無(wú)二義的。6.3.3 算符優(yōu)先關(guān)系表的構(gòu)造算符優(yōu)先關(guān)系表的構(gòu)造首先定義如下兩個(gè)集合：首先定義如下兩個(gè)集合：FIRSTVT(B)=bB b 或或 B CbLASTVT(B)=aB a 或或 B aC按如下算法計(jì)算

13、出給定文法中任何兩個(gè)終結(jié)符對(duì)按如下算法計(jì)算出給定文法中任何兩個(gè)終結(jié)符對(duì)(a,b)之間的之間的優(yōu)先關(guān)系：優(yōu)先關(guān)系： 1) =關(guān)系關(guān)系直接看產(chǎn)生式的右部，假設(shè)出現(xiàn)了直接看產(chǎn)生式的右部，假設(shè)出現(xiàn)了A ab或或 A aBb,那么那么a=b 2)關(guān)系關(guān)系求出每個(gè)非終結(jié)符求出每個(gè)非終結(jié)符B的的FIRSTVT(B)假設(shè)假設(shè)AaB,那么那么bFIRSTVT(B),那么那么a關(guān)系關(guān)系求出每個(gè)非終結(jié)符求出每個(gè)非終結(jié)符B的的LASTVT(B)假設(shè)假設(shè)ABb,那么那么aLASTVT(B),那么那么ab計(jì)算算符優(yōu)先關(guān)系計(jì)算算符優(yōu)先關(guān)系例例6.3 文法文法GE：(0) E#E#(1) EE+T(2) ET(3) TT*F

14、(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(0)E#E# (1) EE+T (2) ET (3) TT*F (4) TF(5) FPF|P (6) P(E) (7) Pi3)關(guān)系關(guān)系找形如：找形如：ABb的產(chǎn)生式的產(chǎn)生式E#: 那么那么 LASTVT(E)#E+: 那么那么 LASTVT(E)

15、+ T*: 那么那么 LASTVT(T)* P: 那么那么 LASTVT(P) E): 那么那么 LASTVT(E)2關(guān)系關(guān)系找形如找形如AaB的產(chǎn)生式的產(chǎn)生式#E：那么：那么 #FIRSTVT(E)+T: 那么那么 +FIRSTVT(T) *F: 那么那么 *FIRSTVT(F)F: 那么那么 FIRSTVT(F)(E: 那么那么 ( * ( = i # = 6.3.4 算符優(yōu)先分析算法算符優(yōu)先分析算法 算符優(yōu)先文法句型的性質(zhì)算符文法的任何一個(gè)句型應(yīng)為如下方式：N1a1N2a2 . Nnan Nn+1其中N k(1kn+1)為非終結(jié)符或空，ak(1kn)為終結(jié)符算符優(yōu)先文法句型的最左素短語(yǔ)N

16、iaiNi+1ai+1 . Njaj Nj+1滿足：ai-1 aiai =ai+1 = =aj-1 =ajaj aj+1即：ai-1 aj+1 算符優(yōu)先分析的可歸約算符優(yōu)先分析的可歸約 串是句型的最左素短語(yǔ)串是句型的最左素短語(yǔ) 定義定義 cfg上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法 G 的句型的素短的句型的素短語(yǔ)是一個(gè)短語(yǔ)，它至少包含一個(gè)終結(jié)符，且除語(yǔ)是一個(gè)短語(yǔ)，它至少包含一個(gè)終結(jié)符，且除本身外不再包含其他素短語(yǔ)。處于句型最左邊本身外不再包含其他素短語(yǔ)。處于句型最左邊的素短語(yǔ)為最左素短語(yǔ)的素短語(yǔ)為最左素短語(yǔ) 文法文法GS短語(yǔ)的定義短語(yǔ)的定義 S A且且A 那么稱那么稱是句型是句型相對(duì)于非相對(duì)于非終結(jié)符終

17、結(jié)符A的短語(yǔ)的短語(yǔ) *例：有文法例：有文法GE：(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi1. 畫出句型畫出句型T+T*F+i的語(yǔ)法樹并寫出改句型的一切短語(yǔ)。的語(yǔ)法樹并寫出改句型的一切短語(yǔ)。2. 寫出句型寫出句型T+T*F+i的簡(jiǎn)單短語(yǔ)和句柄。的簡(jiǎn)單短語(yǔ)和句柄。3.寫出句型寫出句型T+T*F+i的素短語(yǔ)和最左素短語(yǔ)。的素短語(yǔ)和最左素短語(yǔ)。文法文法GE：(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi句型句型T+T*F+i其短語(yǔ)有：其短語(yǔ)有：T+T*F+iT+T*FTT*FiEET+ET* FTTi最左素短語(yǔ)為：最左素短語(yǔ)為：T*FF素短語(yǔ)為：素短語(yǔ)為：T*F， i簡(jiǎn)單短語(yǔ)為：簡(jiǎn)單短語(yǔ)為：T ， T*F， i句柄為：句柄為：T句型句型T+T*F+i的語(yǔ)法樹的語(yǔ)法樹EET+ET* FTTi 句型句型T+T*F+i進(jìn)進(jìn)展算符優(yōu)先分析時(shí)語(yǔ)展算符優(yōu)先分析時(shí)語(yǔ)法樹的框架法樹的框架FNNN+NN* NNi 省略了省略了ET, ET, ET的規(guī)約的規(guī)約F句型句型T+T+F的素短語(yǔ)為：的素短語(yǔ)為：T+T最左素短語(yǔ)是最左素短語(yǔ)是T+TE+ TE句型句型T+T+i