編譯原理自下而上語(yǔ)法分析.ppt
《編譯原理自下而上語(yǔ)法分析.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《編譯原理自下而上語(yǔ)法分析.ppt（36頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
自下而上語(yǔ)法分析,掌握自底相上分析的基本思想，基本概念掌握算符優(yōu)先關(guān)系的判定，求FIRSTVT集,LASTVT集,構(gòu)造算符優(yōu)先關(guān)系表，能運(yùn)用算符優(yōu)先分析方法進(jìn)行表達(dá)式分析掌握最左素短語(yǔ)、句柄的定義與判定理解規(guī)范規(guī)約與算符優(yōu)先歸約的區(qū)別LR(0)和SLR文法的理解,自下而上的語(yǔ)法分析,實(shí)現(xiàn)思想從輸入符號(hào)串開(kāi)始，從左到右進(jìn)行掃描，將輸入符號(hào)逐個(gè)移入一個(gè)棧中，邊移入邊分析，一旦棧頂符號(hào)串形成某個(gè)產(chǎn)生式的右部時(shí)，就用該產(chǎn)生式的左部非終結(jié)符代替，稱為歸約。重復(fù)這一過(guò)程，直到歸約到棧中只剩下文法的開(kāi)始符號(hào)時(shí)，則分析成功，稱為“移進(jìn)-歸約”方法。從語(yǔ)法樹(shù)的角度看：從語(yǔ)法樹(shù)的樹(shù)葉開(kāi)始，逐步向上歸約構(gòu)造分析樹(shù)，直到形成根結(jié)。是推導(dǎo)的逆過(guò)程。核心尋找可歸約串(這是關(guān)鍵)進(jìn)行規(guī)約。用不同的方法尋找可歸約串，就可獲得不同的分析方法。,最左推導(dǎo)(Left-mostDerive)每次推導(dǎo)都替換當(dāng)前句型的最左邊的非終結(jié)符?！c最右歸約對(duì)應(yīng)最右推導(dǎo)(Right-mostDerive)每次推導(dǎo)都替換當(dāng)前句型的最右邊的非終結(jié)符。——與最左歸約(規(guī)范歸約)對(duì)應(yīng)，得規(guī)范句型,例：設(shè)有文法G[S]：(1)S?aAcBe(2)A?b(3)A?Ab(4)B?d使用最右推導(dǎo)：因?yàn)镾=>aAcBe=>aAcde=>aAbcde=>abbcde，所以abbcde是文法G的句子。,步驟動(dòng)作,(1)S?aAcBe(2)A?b(3)A?Ab(4)B?d,最左歸約過(guò)程是最右推導(dǎo)的逆過(guò)程，對(duì)輸入串a(chǎn)bbcde的歸約過(guò)程如下：,該分析過(guò)程反復(fù)執(zhí)行“移進(jìn)”和“歸約”兩個(gè)動(dòng)作，直到棧中只有開(kāi)始符號(hào)為止。,a,ba,Aa,bAa,Aa,cAa,dcAa,BcAa,eBcAa,S,語(yǔ)法分析樹(shù)的生成演示,abbcde,A,A,B,S,,,,,,,,,,A→b,A→Ab,B→d,S→aAcBe,(1)S?aAcBe(2)A?b(3)A?Ab(4)B?d,這種分析過(guò)程具有如下特點(diǎn)：從輸入串的開(kāi)始依次讀入單詞(移進(jìn)棧中)。一旦發(fā)現(xiàn)可歸約串(某個(gè)產(chǎn)生式的右端)就立即歸約。歸約就是將棧頂?shù)囊淮?hào)用文法產(chǎn)生式的左部代替，歸約可能重復(fù)多次，然后繼續(xù)移進(jìn)。若最終能歸約成文法的開(kāi)始符號(hào)，則分析成功。關(guān)鍵是如何判斷可歸約串？,問(wèn)題的提出：①在構(gòu)造語(yǔ)法樹(shù)的過(guò)程中，何時(shí)歸約？當(dāng)可歸約串出現(xiàn)在棧頂時(shí)就進(jìn)行歸約。②如何知道在棧頂符號(hào)串中已經(jīng)形成可歸約串？如何進(jìn)行歸約？通過(guò)不同的自底向上的分析算法來(lái)解釋，不同的算法對(duì)可歸約串的定義是不同的，但分析過(guò)程都有一個(gè)共同的特點(diǎn)：邊移進(jìn)邊歸約。,規(guī)范歸約概念,有文法G，開(kāi)始符號(hào)為S,如果有S=>xβy,則xβy是文法G的句型，x,y是任意的符號(hào)串如果有S=>xAy,且有A=>β,則β是句型xβy相對(duì)于非終結(jié)符A的短語(yǔ)如果有S=>xAy,且有A->β,則β是句型xβy相對(duì)于A->β的直接短語(yǔ)位于一個(gè)句型最左邊的直接短語(yǔ)稱為句柄。,注:每次歸約的部分必須是稱之為句柄的字符串(最右推導(dǎo))。關(guān)鍵的問(wèn)題是如何識(shí)別句柄,例子,下面的例子說(shuō)明作為短語(yǔ)的兩個(gè)條件缺一不可。[例]考慮表達(dá)式文法：E?T|E+TT?F|T*FF?i|(E)對(duì)于句型i*i+i推導(dǎo)E?E+T?E+F?E+i?T+i?T*F+T?T*i+i?F*i+i?i*i+i盡管有E?+i+i但是,i+i并不是該句型的一個(gè)短語(yǔ)，因?yàn)椴淮嬖趶腅(文法開(kāi)始符）到i*E的推導(dǎo)。,句型的短語(yǔ)和句柄舉例,文法：S→(T)|εT→S|T,S|a短語(yǔ)：句型((a),S)S=*>(T,S)T=+>(a)句型((T,S),S)S=*>((T),S)T=+>T,S句型(a,(T),(T,S))直接短語(yǔ)以及句柄：S=*>(T,(T),(T,S))T=>aS=*>(a,S,(T,S))S=>(T)S=*>(a,(T),(T))T=>T,S,短語(yǔ)與語(yǔ)法樹(shù)的關(guān)系,短語(yǔ)：語(yǔ)法樹(shù)子樹(shù)的葉子結(jié)點(diǎn)組成的符號(hào)串。直接短語(yǔ)：語(yǔ)法樹(shù)簡(jiǎn)單子樹(shù)（只有父子兩代）的葉子結(jié)點(diǎn)組成的符號(hào)串。句柄：語(yǔ)法樹(shù)最左邊簡(jiǎn)單子樹(shù)的葉子結(jié)點(diǎn)組成的符號(hào)串。,,短語(yǔ)與語(yǔ)法樹(shù)關(guān)系的例子,句型(a,(T),(T,S))的語(yǔ)法樹(shù)：,用句柄對(duì)句子abbcde進(jìn)行歸約,用句柄對(duì)句子進(jìn)行歸約的過(guò)程與用移進(jìn)-歸約過(guò)程是一致的，使用歸約的產(chǎn)生式及其順序是一致的。,(1)S?aAcBe(2)A?b(3)A?Ab(4)B?d,(2)A?b,(3)A?Ab,aAbcde,aAcde,(4)B?d,(1)S?aAcBe,aAcBe,S,,,,,規(guī)范歸約的定義,假定α是文法G的一個(gè)句子，如果序列：αn,αn-1,……,α0(=S)滿足如下條件，則序列αn,αn-1,……,α0是一個(gè)規(guī)范歸約:(1)αn=α是給定的句子(2)α0=S是文法的開(kāi)始符號(hào)(3)對(duì)任何i,0E+T|TT->T*F|FF->(E)|i對(duì)輸入串i1+i2*i3的規(guī)范歸約過(guò)程：,動(dòng)作棧輸入緩沖區(qū)1)準(zhǔn)備#i1+i2*i3#2)移進(jìn)#i1+i2*i3#3)歸約F→i#F+i2*i3#4)歸約T→F#T+i2*i3#5)歸約E→T#E+i2*i3#6)移進(jìn)#E+i2*i3#7)移進(jìn)#E+i2*i3#8)歸約F→i#E+F*i3#9)歸約T→F#E+T*i3#10)移進(jìn)#E+T*i3#11)移進(jìn)#E+T*i3#12)歸約F→i#E+T*F#13)歸約T→T*F#E+T#14)歸約E→E+T#E#15)接受,,,,,,,,,,所得的結(jié)果是：用產(chǎn)生式序列表示語(yǔ)法分析樹(shù),E->E+T|TT->T*F|FF->(E)|i,i1+i2*i3,F,,T,,E,F,,T,F,T,E,算符優(yōu)先分析,算符優(yōu)先分析法的思想源于表達(dá)式的分析，即利用相鄰終結(jié)符號(hào)之間的關(guān)系來(lái)尋找可歸約串。將句型中的終結(jié)符號(hào)當(dāng)作“算符”，借助于算符之間的優(yōu)先關(guān)系確定可歸約串。顯然，在一個(gè)符號(hào)串中，任意兩個(gè)相鄰終結(jié)符號(hào)a和b之間，只可能存在以下四種優(yōu)先關(guān)系：(1)a,b優(yōu)先性相同，記作ab。(2)a優(yōu)先性高于b，記作ab。(3)a優(yōu)先性低于b，記作ab。(4)a與b不可能相鄰，即此符號(hào)串不是句型(出錯(cuò))。如果以上四種關(guān)系中的任意兩種都不會(huì)同時(shí)成立，則可以根據(jù)終結(jié)符號(hào)之間的歸約關(guān)系進(jìn)行語(yǔ)法分析。,算符文法:一個(gè)上下無(wú)關(guān)文法G,如果沒(méi)有P->?,且沒(méi)有P->...QR...(P,Q,R屬于非終結(jié)符),則G是一個(gè)算符文法。算符優(yōu)先關(guān)系的定義：ab,G中有P->...ab...或P->...aQb...(在同一產(chǎn)生式中)ab,G中有P->...aR...的產(chǎn)生式,且R=>b...或R=>Qb...ab,G中有P->...Rb...的產(chǎn)生式,且R=>...a或R=>...aQ,算符優(yōu)先文法（OPG）的定義,+,+,+,+,例：E→E+E|E*E|(E)|i證明不是OPG文法。因?yàn)椋篍→E+E，E?E*E則有+*又因?yàn)椋篍→E*E,E?E+E則有+*所以不是算符優(yōu)先文法。,算符優(yōu)先文法算符文法G的任何終結(jié)符a,b之間要么沒(méi)有優(yōu)先關(guān)系，若有優(yōu)先關(guān)系,至多有,,中的一種成立,則G為一算符優(yōu)先文法。,算符優(yōu)先關(guān)系表的構(gòu)造,FIRSTVT集定義：對(duì)每個(gè)非終結(jié)符P,FIRSTVT(P)={a|P=>a...或P=>Qa...,a為終結(jié)符,P，Q為非終結(jié)符},由優(yōu)先性低于的定義和FIRSTVT集合的定義可以得出：若存在某個(gè)產(chǎn)生式：…aP…，對(duì)所有：b∈FIRSTVT(P)，都有：ab。,按照下面兩條規(guī)則來(lái)構(gòu)造FIRSTVT集：①若有產(chǎn)生式P->a...或P->Qa...,則a∈FIRSTVT(P)②若有產(chǎn)生式P->R...,則FIRSTVT(R)包含在FIRSTVT(P)中,LASTVT集定義：對(duì)每個(gè)非終結(jié)符P,LASTVT(P)={a|P=>...a或P=>...aQ,a為終結(jié)符,P，Q為非終結(jié)符},+,+,由優(yōu)先性高于的定義和LASTVT集合的定義可以得出：若存在某個(gè)產(chǎn)生式：…Pb…，對(duì)所有：a∈LASTVT(P)，都有：ab。,按照下面兩條規(guī)則來(lái)構(gòu)造LASTVT集：①若有產(chǎn)生式P->...a或P->...aQ,則a∈LASTVT(P)②若有產(chǎn)生式P->...R,則LASTVT(R)包含在LASTVT(P)中,構(gòu)造優(yōu)先關(guān)系表如果每個(gè)非終結(jié)符的FIRSTVT和LASTVT集均已知,則可構(gòu)造優(yōu)先關(guān)系表。若產(chǎn)生式右部有...aP...的形式,則對(duì)于每個(gè)b∈FIRSTVT(P)都有ab若產(chǎn)生式右部有...Pb的形式,則對(duì)于每個(gè)a∈LASTVT(P)集,都有ab若產(chǎn)生是形如：A→…ab…或A→…aBb…形式，則有ab構(gòu)造優(yōu)先關(guān)系表的算法如下：,For每條形如P?X1X2…Xn的產(chǎn)生式dofori=1ton-1do{ifXi和Xi+1都是終結(jié)符thenXi=Xi+1ifiXi+1},算符優(yōu)先分析算法,通過(guò)比較終結(jié)符間的優(yōu)先關(guān)系來(lái)實(shí)現(xiàn)根據(jù)優(yōu)先分析的原理，語(yǔ)法分析程序的任務(wù)是：不斷移進(jìn)輸入符號(hào)，識(shí)別可歸約串并進(jìn)行歸約。分析的方法：根據(jù)優(yōu)先性“高于”來(lái)識(shí)別可歸約串的頭，根據(jù)優(yōu)先性“低于”來(lái)識(shí)別可歸約串的尾。各種優(yōu)先關(guān)系已經(jīng)存于優(yōu)先關(guān)系表中。,,不能識(shí)別只由一個(gè)非終結(jié)符組成的句柄。不能保證每次對(duì)句柄進(jìn)行歸約,在算符優(yōu)先分析過(guò)程中,每次歸約的符號(hào)串,是當(dāng)前句型的最左素短語(yǔ)。素短語(yǔ)：至少含有一個(gè)終結(jié)符,且除自身外,不再包含任何其它更小的素短語(yǔ)。最左素短語(yǔ)(leftmostprimephrase)：是指位于句型最左邊的那個(gè)素短語(yǔ)。,例：下述文法的一個(gè)句型：T*F+i其短語(yǔ)、素短語(yǔ)、最左素短語(yǔ)分別是？,E?T|E+TT?F|T*FF?i|(E),短語(yǔ)有：i,T*F,T*F+i素短語(yǔ)有：i,T*F最左素短語(yǔ)是：T*F,例:文法GE->E+T|TT->T*F|FF->(E)|i句型T+T*F+i的語(yǔ)法樹(shù)如圖：,根據(jù)語(yǔ)法樹(shù)可知：句型#T+T*F+i#的短語(yǔ)有：T—相對(duì)非終結(jié)符E的短語(yǔ)T*F—相對(duì)非終結(jié)符T的短語(yǔ)T+T*F—相對(duì)非終結(jié)符E的短語(yǔ)i—相對(duì)非終結(jié)符P、F、T的短語(yǔ)T+T*F+i—相對(duì)非終結(jié)符E的短語(yǔ),根據(jù)素短語(yǔ)的定義可知：i和T*F為素短語(yǔ)。其中：T+T*F(含T*F素短語(yǔ))、T+T*F+i(含T*F素短語(yǔ))和T(不含終結(jié)符)也不是素短語(yǔ)T*F為最左素短語(yǔ)。,,一個(gè)算符文法G的某個(gè)句型的最左素短語(yǔ)可描述：設(shè)句型的一般形式為(Ni∈VN∪{ε},ai∈VT#N1a1N2a2…NnanNn+1#它的最左素短語(yǔ)是滿足下列條件的最左子串：NiaiNi+1ai+1…NjajNj+1其中：ai-1≮ai,,ai≡ai+1…..aj-1≡aj，aj≯aj+1,該定理說(shuō)明了最左素短語(yǔ)與周圍符號(hào)之間的關(guān)系,算符優(yōu)先分析過(guò)程：(根據(jù)最左素短語(yǔ)的定義)句型的一般形式:#N1a1N2a2...NnanNn+1#(ai為終結(jié)符,Ni為可有可無(wú)的非終結(jié)符)從左向右掃描各符號(hào),依次查看算符優(yōu)先矩陣,直至找到滿足ai>ai+1的終結(jié)符為止,一直移進(jìn)，再?gòu)腶i開(kāi)始往左掃描,直至找到滿足關(guān)系aj-1aj的終結(jié)符為止,進(jìn)行歸約。此時(shí),形如:NjajNj+1aj+1.....NiaiNi+1的子串即為最左素短語(yǔ)，應(yīng)被歸約。分析過(guò)程的結(jié)束：分析棧中為#S，輸入串為#,例:E->E+T|TT->T*F|FF->(E)|i把#入棧,讀一符號(hào)i,因?yàn)?+,所以歸約:F->i因#*,所以歸約:F->i因+#,所以歸約:F->i因*>#,所以歸約:T->F*F因+>#,所以歸約:E->T+F分析成功,求i+i*i的算符優(yōu)先分析過(guò)程,棧輸入緩沖區(qū)#i+i*i##i+i*i##F+i*i##F+i*i##F+i*i##F+F*i##F+F*i##F+F*i##F+F*F##F+T##E#,k=1;s[k]=‘#’;a=下一個(gè)輸入符號(hào);WHILE(a≠‘#’)DO{IFs[k]∈VTTHENj=kELSEj=k-1;//s[j]為棧頂終結(jié)符WHILEs[j]>aDO//當(dāng)棧頂終結(jié)符優(yōu)先級(jí)高于輸入符號(hào)時(shí){//尋找最左素短語(yǔ)進(jìn)行歸約DO{q=s[j];ifs[j-1]∈VTTHENj=j-1ELSEj=j-2;}WHILE(nots[j]下載提示(請(qǐng)認(rèn)真閱讀)
- 1.請(qǐng)仔細(xì)閱讀文檔，確保文檔完整性，對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔，不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請(qǐng)點(diǎn)此認(rèn)領(lǐng)！既往收益都?xì)w您。
文檔包含非法信息？點(diǎn)此舉報(bào)后獲取現(xiàn)金獎(jiǎng)勵(lì)！
下載文檔到電腦，查找使用更方便
9.9 積分
| 下載 |
還剩頁(yè)未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁(yè)顯示word圖標(biāo)，表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制：
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 編譯 原理 自下而上 語(yǔ)法分析
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書(shū)面授權(quán)，請(qǐng)勿作他用。
鏈接地址：http://appdesigncorp.com/p-3529924.html