自底向上優(yōu)先分析法ppt課件

1、編譯原理編譯原理第第6 6章章 自底向上優(yōu)先分析法自底向上優(yōu)先分析法 自底向上優(yōu)先分析概述 簡單優(yōu)先分析 算符優(yōu)先分析編譯原理編譯原理自底向上分析方法自底向上分析方法 自底向上分析方法，也稱移進-歸約分析法。 實現(xiàn)思想： 對輸入符號串自左向右進展掃描，并將輸入符逐個移入一個后進先出棧中，邊移入邊分析，一旦棧頂符號串構(gòu)成某個句型的句柄時，該句型對應(yīng)某產(chǎn)生式的右部，就用該產(chǎn)生式的左部非終結(jié)符替代相應(yīng)右部的文法符號串，這稱為歸約。 反復(fù)這一過程直到歸約到棧中只剩文法的開場符號時那么為分析勝利，也就確認輸入串是文法的句子。S10 #aAcBe # 歸約歸約(SaAcBe)文法文法GS：1 S aAcB

2、e2 A b3 A Ab4 B da b b c de步驟步驟符號棧符號棧輸入符號串輸入符號串動作動作 1 # abbcde# 移進移進 2 #a bbcde# 移進移進A 3 #ab bcde# 歸約歸約(Ab) 4 #aA bcde# 移進移進A 5 #aAb cde# 歸約歸約(AAb) 6 #aA cde# 移進移進 7 #aAc de# 移進移進B 8 # aAcd e# 歸約歸約(Bd) 9 #aAcB e# 移進移進11 #S # 接受接受分析符號串分析符號串a(chǎn)bbcdeabbcde能否為能否為GSGS的句子？的句子？對輸入串a(chǎn)bbcde#的移進-規(guī)約分析過程SaAcBe aAc

3、de aAbcde abbcde編譯原理編譯原理算法應(yīng)思索的問題算法應(yīng)思索的問題 算法能否可以終止？算法能否可以終止？ 算法能否快速？算法能否快速？ 算法能否可以處置一切的情況？算法能否可以處置一切的情況？ 在每一步中如何選擇子串進展歸約？在每一步中如何選擇子串進展歸約？編譯原理編譯原理自下而上語法分析的戰(zhàn)略：移進自下而上語法分析的戰(zhàn)略：移進- -規(guī)約分析。規(guī)約分析。移進就是將一個終結(jié)符推進棧。移進就是將一個終結(jié)符推進棧。歸約就是將歸約就是將0 0個或多個符號從棧中彈出，根個或多個符號從棧中彈出，根據(jù)產(chǎn)生式將一個非終結(jié)符壓入棧。據(jù)產(chǎn)生式將一個非終結(jié)符壓入棧。移進移進- -歸約過程是自頂向下最右

4、推導(dǎo)的逆過歸約過程是自頂向下最右推導(dǎo)的逆過程規(guī)范歸約。程規(guī)范歸約。編譯原理編譯原理 簡單優(yōu)先分析法 對一個文法按一定原那么求出該文法一切符號終結(jié)符和非終結(jié)符之間的優(yōu)先關(guān)系，按照這種關(guān)系確定歸約過程中的句柄，它的歸約實踐上是一種規(guī)范歸約。 算符優(yōu)先分析法 只規(guī)定算符終結(jié)符之間的優(yōu)先關(guān)系。找到句柄就歸約，不是規(guī)范歸約。優(yōu)先分析法優(yōu)先分析法編譯原理編譯原理簡單優(yōu)先分析法簡單優(yōu)先分析法 按照文法符號包括終結(jié)符和非終結(jié)符 的優(yōu)先關(guān)系確定句柄。編譯原理編譯原理文法文法GSGS：1 1 S bAb S bAb2 2 A A B|aB|a3 3 B Aa B AaSbA(Ba)#Sb=A=(=a=)#步驟步驟

5、符號棧符號棧輸入符號串輸入符號串動作動作 1 # baab# #b,移進移進 2 #b aab# b,移進移進 3 #b aab# a,歸約歸約Aa 5 #bA ab# A=a,移進移進 6 #bAa b# a=,移進移進 7 #bAa b# b,歸約歸約BAa 8 #bB b# Bb,歸約歸約AB 9 #bA b# A=b,移進移進10 #bAb # b#,歸約歸約SbAb11 #S # 接受接受對輸入串baa#的簡單優(yōu)先分析過程簡單優(yōu)先關(guān)系矩陣編譯原理編譯原理優(yōu)先關(guān)系優(yōu)先關(guān)系優(yōu)先關(guān)系優(yōu)先關(guān)系X=Y 文法文法G中存在產(chǎn)生式中存在產(chǎn)生式A.XY.XY 文法文法G中存在產(chǎn)生式中存在產(chǎn)生式A.BD

6、.，且且B .X,D Y.如何確定兩個文法符號之間的優(yōu)先關(guān)系？如何確定兩個文法符號之間的優(yōu)先關(guān)系？*編譯原理編譯原理簡單優(yōu)先文法的定義簡單優(yōu)先文法的定義 滿足以下條件的文法是簡單優(yōu)先文法1在文法符號集V中，恣意兩個符號之間最多只需一種優(yōu)先關(guān)系成立。2在文法中恣意兩個產(chǎn)生式?jīng)]有一樣的右部。3不含空產(chǎn)生式。編譯原理編譯原理簡單優(yōu)先分析法簡單優(yōu)先分析法根據(jù)優(yōu)先文法構(gòu)造相應(yīng)優(yōu)先關(guān)系矩陣，并將文法的產(chǎn)生式保管，設(shè)置符號棧S，算法步驟如下：將輸入符號串a(chǎn)1a2a3.an#依次逐個存入符號棧S中，直到遇到棧頂符號ai的優(yōu)先性下一個待輸入符號aj時為止。棧頂當前符號ai為句柄尾，由此向左在棧中找句柄的頭符號a

7、k，即找到ak-1ak為止。由句柄ak.ai在文法的產(chǎn)生式中查找右部為ak.ai的產(chǎn)生式，假設(shè)找到那么用相應(yīng)左部替代句柄，假設(shè)找不到那么為出錯，這時可斷定輸入串不是該文法的句子。反復(fù)上述三步，直到歸約完輸入符號串，棧中只剩文法的開場符號為止。編譯原理編譯原理如何確定優(yōu)先關(guān)系？如何確定優(yōu)先關(guān)系？文法文法GS：1 S bAb2 A B|a3 B Aa1.求求=關(guān)系：關(guān)系：由由1：b=A A=b由由2：=B由由3：A=a a=2.求求關(guān)系：關(guān)系：由由12：b ba由由23：A 關(guān)系：關(guān)系：由由1：Bb ab b由由3：Ba aa a4.#SbA(Ba)#Sb=A=(=a=)#編譯原理編譯原理算符優(yōu)先

8、分析法算符優(yōu)先分析法 某些文法具有“算符特性 表達式運算符優(yōu)先級、結(jié)合性 人為地規(guī)定其算符的優(yōu)先順序，即給出優(yōu)先級別和同一級別的結(jié)合性 只思索算符之間的優(yōu)先關(guān)系來確定句柄編譯原理編譯原理文法文法GE：EE+E|E-E|E*E|E/E|EE|E|i步驟步驟符號棧符號棧輸入符號串輸入符號串動作動作 1 # i+i*i# #i,移進移進 2 #i +i*i# #+,規(guī)約規(guī)約 3 #E +i*i# #+,移進移進 4 #E+ i*i# +i,移進移進 5 #E+i *i# +*,規(guī)約規(guī)約 6 #E+E *i# +*,移進移進 7 #E+E* i# *i,移進移進 8 #E+E*i # *#,規(guī)約規(guī)約

9、9 #E+E*E # +#,規(guī)約規(guī)約10 #E+E # #,規(guī)約規(guī)約11 #E # 接受接受對輸入串對輸入串i+ii+i* *i i的算符優(yōu)先分析過程的算符優(yōu)先分析過程+ - * / ()i #+ -* / (= i# -*/ (=i# =算符優(yōu)先關(guān)系表算符優(yōu)先關(guān)系表編譯原理編譯原理算符文法的定義算符文法的定義 定義定義 假設(shè)不含空產(chǎn)生式的上下文無關(guān)文法假設(shè)不含空產(chǎn)生式的上下文無關(guān)文法 G G 中沒有形如中沒有形如 U UVWVW的產(chǎn)生式，其中的產(chǎn)生式，其中V,WVNV,WVN那么稱那么稱G G 為算符文法為算符文法OGOG。 性質(zhì)性質(zhì)1 1：在算符文法中任何句型都不包含兩個：在算符文法中任何

10、句型都不包含兩個相鄰的非終結(jié)符相鄰的非終結(jié)符. .數(shù)學(xué)歸納法數(shù)學(xué)歸納法 性質(zhì)性質(zhì)2 2：如：如 Vx Vx 或或 xV xV 出如今算符文法的句型出如今算符文法的句型 中，其中中，其中VVN,xVT, VVN,xVT, 那么那么 中任何含中任何含 x x 的短語必含有的短語必含有V.V.反證法反證法編譯原理編譯原理算符優(yōu)先關(guān)系的定義算符優(yōu)先關(guān)系的定義在在OGOG中中 定義定義 算符優(yōu)先關(guān)系算符優(yōu)先關(guān)系x = y Gx = y G中有形如中有形如.U.Uxyxy或或U U xVy. xVy.的產(chǎn)的產(chǎn)生式。生式。x y Gx y Gxy G中有形如中有形如.U .U Wy Wy的產(chǎn)生式的產(chǎn)生式,

11、,而而 W xW x或或W xVW xV規(guī)定規(guī)定 假設(shè)假設(shè) S x S x或或S Vx S Vx 那么那么 # x # # x #編譯原理編譯原理算符優(yōu)先文法的定義算符優(yōu)先文法的定義 在 OG文法 G 中，假設(shè)恣意兩個終結(jié)符間至多有一種算符優(yōu)先關(guān)系存在，那么稱G 為算符優(yōu)先文法OPG。 留意：允許bc,cb;不允許bc,bc,b=c 結(jié)論： 算符優(yōu)先文法是無二義的。編譯原理編譯原理算符優(yōu)先關(guān)系表的構(gòu)造算符優(yōu)先關(guān)系表的構(gòu)造由定義直接構(gòu)造由定義直接構(gòu)造由關(guān)系圖法構(gòu)造算符優(yōu)先關(guān)系表由關(guān)系圖法構(gòu)造算符優(yōu)先關(guān)系表編譯原理編譯原理 首先引入兩個概念首先引入兩個概念 FIRSTVTFIRSTVTB B=b|

12、B b=b|B b或或B Cb.B Cb.對于非終結(jié)符對于非終結(jié)符B B，其往下推導(dǎo)所能夠呈現(xiàn)的首，其往下推導(dǎo)所能夠呈現(xiàn)的首個算符。個算符。 LASTVTLASTVTB B=a|B a=a|B a或或B . aCB . aC對于非終結(jié)符對于非終結(jié)符B B，其往下推導(dǎo)所能夠呈現(xiàn)的最，其往下推導(dǎo)所能夠呈現(xiàn)的最后一個算符。后一個算符。編譯原理編譯原理如何計算算符優(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)系求出每個非終結(jié)符求出每個非終結(jié)符B的的FIRSTVTB， 假設(shè)假設(shè)AaB,那么那么bFIR

13、STVTB,那么那么a關(guān)系關(guān)系求出每個非終結(jié)符求出每個非終結(jié)符B的的LASTVTB， 假設(shè)假設(shè)ABb,那么那么aLASTVTB,那么那么ab。編譯原理編譯原理文法文法GE：0 E#E#1 EE+T2 ET3 TT*F4 TF5 FPF|P6 PE7 PiFIRSTVTE=#FIRSTVTE=+,*,iFIRSTVTT=*,iFIRSTVTF=,iFIRSTVTP=,iLASTVTE=#LASTVTE=+,*,iLASTVTT=*,iLASTVTF=,iLASTVTP=,i+-*/ ()i#+-*/ (=i#=1=關(guān)系關(guān)系由產(chǎn)生式由產(chǎn)生式0和和6,得得#=#，=2關(guān)系關(guān)系找形如：找形如：AaB的

14、產(chǎn)生式的產(chǎn)生式#E：那么：那么#FIRSTVTE+T: 那么那么+FIRSTVTT *F: 那么那么*FIRSTVTFF:那么那么 FIRSTVTFE: 那么那么 關(guān)系關(guān)系找形如：找形如：ABb的產(chǎn)生式的產(chǎn)生式E# ,那么那么 LASTVTE#E+ ,那么那么 LASTVTE+ T* ,那么那么 LASTVTT* P ,那么那么 LASTVTP E ,那么那么 LASTVTE編譯原理編譯原理算符優(yōu)先分析算法算符優(yōu)先分析算法 歸約過程中，只思索終結(jié)符之間的優(yōu)先關(guān)系來確定句柄，而與非終結(jié)符無關(guān)。這樣去掉了單非終結(jié)符的歸約，所以用算符優(yōu)先分析法的規(guī)約過程與規(guī)范歸約是不同的，P110. 為處置在算符優(yōu)

15、先分析過程中如何尋覓句柄，引進最左素短語的概念。編譯原理編譯原理最左素短語最左素短語 算符文法的任一句型有如下方式：#N1a1N2a2.NnanNn+1#,假設(shè)Niai.NjajNj+1為句柄，那么有 ai-1 ai+1 對于算符優(yōu)先文法，假設(shè)aNb或ab出如今句型r中 假設(shè)ab，那么在r中必含有a而不含b的短語存在。 假設(shè)a=b，那么在r中含有a的短語必含有b，反之亦然。 定義 cfg G 的句型的素短語是一個短語，它至少包含一個終結(jié)符，且除本身外不再包含其他素短語。處于句型最左邊的素短語為最左素短語。編譯原理編譯原理文法文法GEGE：1 1 EE+T EE+T2 2 ET ET3 3 TT TT* *F F4 4 TF TF5 5 FPFPF|PF|P6 6 P PE E7 7 Pi Pi句型句型#T+T*F+i#其短語有：其短語有：T+T*F+iT+T*FTT*FiEET+ETF