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

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

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

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

4、推導(dǎo)的逆過(guò)歸約過(guò)程是自頂向下最右推導(dǎo)的逆過(guò)程規(guī)范歸約。程規(guī)范歸約。編譯原理編譯原理 簡(jiǎn)單優(yōu)先分析法 對(duì)一個(gè)文法按一定原那么求出該文法一切符號(hào)終結(jié)符和非終結(jié)符之間的優(yōu)先關(guān)系，按照這種關(guān)系確定歸約過(guò)程中的句柄，它的歸約實(shí)踐上是一種規(guī)范歸約。 算符優(yōu)先分析法 只規(guī)定算符終結(jié)符之間的優(yōu)先關(guān)系。找到句柄就歸約，不是規(guī)范歸約。優(yōu)先分析法優(yōu)先分析法編譯原理編譯原理簡(jiǎn)單優(yōu)先分析法簡(jiǎn)單優(yōu)先分析法 按照文法符號(hào)包括終結(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、符號(hào)棧符號(hào)棧輸入符號(hào)串輸入符號(hào)串動(dòng)作動(dòng)作 1 # baab# #b,移進(jìn)移進(jìn) 2 #b aab# b,移進(jìn)移進(jìn) 3 #b aab# a,歸約歸約Aa 5 #bA ab# A=a,移進(jìn)移進(jìn) 6 #bAa b# a=,移進(jìn)移進(jìn) 7 #bAa b# b,歸約歸約BAa 8 #bB b# Bb,歸約歸約AB 9 #bA b# A=b,移進(jìn)移進(jìn)10 #bAb # b#,歸約歸約SbAb11 #S # 接受接受對(duì)輸入串baa#的簡(jiǎn)單優(yōu)先分析過(guò)程簡(jiǎn)單優(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.如何確定兩個(gè)文法符號(hào)之間的優(yōu)先關(guān)系？如何確定兩個(gè)文法符號(hào)之間的優(yōu)先關(guān)系？*編譯原理編譯原理簡(jiǎn)單優(yōu)先文法的定義簡(jiǎn)單優(yōu)先文法的定義 滿足以下條件的文法是簡(jiǎn)單優(yōu)先文法1在文法符號(hào)集V中，恣意兩個(gè)符號(hào)之間最多只需一種優(yōu)先關(guān)系成立。2在文法中恣意兩個(gè)產(chǎn)生式?jīng)]有一樣的右部。3不含空產(chǎn)生式。編譯原理編譯原理簡(jiǎn)單優(yōu)先分析法簡(jiǎn)單優(yōu)先分析法根據(jù)優(yōu)先文法構(gòu)造相應(yīng)優(yōu)先關(guān)系矩陣，并將文法的產(chǎn)生式保管，設(shè)置符號(hào)棧S，算法步驟如下：將輸入符號(hào)串a(chǎn)1a2a3.an#依次逐個(gè)存入符號(hào)棧S中，直到遇到棧頂符號(hào)ai的優(yōu)先性下一個(gè)待輸入符號(hào)aj時(shí)為止。棧頂當(dāng)前符號(hào)ai為句柄尾，由此向左在棧中找句柄的頭符號(hào)a

7、k，即找到ak-1ak為止。由句柄ak.ai在文法的產(chǎn)生式中查找右部為ak.ai的產(chǎn)生式，假設(shè)找到那么用相應(yīng)左部替代句柄，假設(shè)找不到那么為出錯(cuò)，這時(shí)可斷定輸入串不是該文法的句子。反復(fù)上述三步，直到歸約完輸入符號(hào)串，棧中只剩文法的開(kāi)場(chǎng)符號(hào)為止。編譯原理編譯原理如何確定優(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)先分析法 某些文法具有“算符特性 表達(dá)式運(yùn)算符優(yōu)先級(jí)、結(jié)合性 人為地規(guī)定其算符的優(yōu)先順序，即給出優(yōu)先級(jí)別和同一級(jí)別的結(jié)合性 只思索算符之間的優(yōu)先關(guān)系來(lái)確定句柄編譯原理編譯原理文法文法GE：EE+E|E-E|E*E|E/E|EE|E|i步驟步驟符號(hào)棧符號(hào)棧輸入符號(hào)串輸入符號(hào)串動(dòng)作動(dòng)作 1 # i+i*i# #i,移進(jìn)移進(jìn) 2 #i +i*i# #+,規(guī)約規(guī)約 3 #E +i*i# #+,移進(jìn)移進(jìn) 4 #E+ i*i# +i,移進(jìn)移進(jìn) 5 #E+i *i# +*,規(guī)約規(guī)約 6 #E+E *i# +*,移進(jìn)移進(jìn) 7 #E+E* i# *i,移進(jìn)移進(jìn) 8 #E+E*i # *#,規(guī)約規(guī)約

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

10、句型都不包含兩個(gè)相鄰的非終結(jié)符相鄰的非終結(jié)符. .數(shù)學(xué)歸納法數(shù)學(xué)歸納法 性質(zhì)性質(zhì)2 2：如：如 Vx Vx 或或 xV xV 出如今算符文法的句型出如今算符文法的句型 中，其中中，其中VVN,xVT, VVN,xVT, 那么那么 中任何含中任何含 x x 的短語(yǔ)必含有的短語(yǔ)必含有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è)恣意兩個(gè)終結(jié)符間至多有一種算符優(yōu)先關(guān)系存在，那么稱G 為算符優(yōu)先文法OPG。 留意：允許bc,cb;不允許bc,bc,b=c 結(jié)論： 算符優(yōu)先文法是無(wú)二義的。編譯原理編譯原理算符優(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)系表編譯原理編譯原理 首先引入兩個(gè)概念首先引入兩個(gè)概念 FIRSTVTFIRSTVTB B=b|

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

13、STVTB,那么那么a關(guān)系關(guān)系求出每個(gè)非終結(jié)符求出每個(gè)非終結(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)先分析算法 歸約過(guò)程中，只思索終結(jié)符之間的優(yōu)先關(guān)系來(lái)確定句柄，而與非終結(jié)符無(wú)關(guān)。這樣去掉了單非終結(jié)符的歸約，所以用算符優(yōu)先分析法的規(guī)約過(guò)程與規(guī)范歸約是不同的，P110. 為處置在算符優(yōu)

15、先分析過(guò)程中如何尋覓句柄，引進(jìn)最左素短語(yǔ)的概念。編譯原理編譯原理最左素短語(yǔ)最左素短語(yǔ) 算符文法的任一句型有如下方式：#N1a1N2a2.NnanNn+1#,假設(shè)Niai.NjajNj+1為句柄，那么有 ai-1 ai+1 對(duì)于算符優(yōu)先文法，假設(shè)aNb或ab出如今句型r中 假設(shè)ab，那么在r中必含有a而不含b的短語(yǔ)存在。 假設(shè)a=b，那么在r中含有a的短語(yǔ)必含有b，反之亦然。 定義 cfg G 的句型的素短語(yǔ)是一個(gè)短語(yǔ)，它至少包含一個(gè)終結(jié)符，且除本身外不再包含其他素短語(yǔ)。處于句型最左邊的素短語(yǔ)為最左素短語(yǔ)。編譯原理編譯原理文法文法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#其短語(yǔ)有：其短語(yǔ)有：T+T*F+iT+T*FTT*FiEET+ETF