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