自下而上語法分析習(xí)題.ppt

《自下而上語法分析習(xí)題.ppt》由會員分享，可在線閱讀，更多相關(guān)《自下而上語法分析習(xí)題.ppt（26頁珍藏版）》請在裝配圖網(wǎng)上搜索。

自下而上語法分析方法習(xí)題課,第五章,本章要求,1.掌握自下而上分析的基本思想，基本概念2.掌握算符優(yōu)先文法、算符優(yōu)先關(guān)系的判定3.掌握最左素短語、句柄的定義與判定4.掌握求FirstVT集,LastVT集,學(xué)會構(gòu)造算符優(yōu)先關(guān)系表,能用算符優(yōu)先分析法進行表達式分析,問題的提出：①在構(gòu)造語法樹的過程中，何時歸約？當可歸約串出現(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)鍵的問題是如何識別句柄,例：考慮如下文法：,求句型i1*i2+i3的短語、直接短語和句柄。,E?T|E+TT?F|T*FF?i|(E),從語法分析樹來識別：一棵子樹是由樹的某個結(jié)點連同它的所有子孫組成的。子樹的所有端末結(jié)點自左至右排列成一個相對子樹根的短語。直接短語：只有父子兩代結(jié)點形成的短語。句柄：最左子樹的直接短語。,從語法樹可以看出：i1,i2,i3,i1*i2,i1*i2+i3是句型i1*i2+i3的短語直接短語有：i1,i2,i3句柄是：i1,E?T|E+TT?F|T*FF?i|(E),句型i1*i2+i3的語法樹如圖：,練習(xí),1、令文法G1為：E→E+T|TT→T*F|FF→(E)|i證明E+T*F是它的一個句型，指出這個句型的所有短語、直接短語和句柄。,T*F是句型E+T*F相對于T的短語,E+T*F句型E+T*F相對于E的短語,T*F是句型E+T*F相對于T的直接短語,T*F是句柄,2對下述文法，求句型E+T*F+i的短語、直接短語、句柄,E?T|E+TT?F|T*FF?i|(E),短語有：i,T*F,E+T*F,E+T*F+i直接短語有：i,T*F句柄是：T*F,練習(xí),規(guī)范歸約的定義：,假定α是文法G的一個句子，如果序列：αn,αn-1,……,α0(=S)滿足如下條件，則序列αn,αn-1,……,α0是一個規(guī)范歸約:(1)αn=α是給定的句子(2)α0=S是文法的開始符號(3)對任何i,0g(b)，f(b)=g(a)，f(b)=g(b)導(dǎo)致如下矛盾:f(a)>g(b)=f(b)=g(a)=f(a)如果優(yōu)先函數(shù)存在，則不唯一(無窮多),如果優(yōu)先函數(shù)存在，則可以通過以下三個步驟從優(yōu)先表構(gòu)造優(yōu)先函數(shù):1對于每個終結(jié)符a，令其對應(yīng)兩個符號fa和ga，畫一以所有符號和為結(jié)點的方向圖。如果ab，則從fa畫一條弧至gb，如果ab，則畫一條弧從gb至fa。2對每個結(jié)點都賦予一個數(shù)，此數(shù)等于從該結(jié)點出發(fā)所能到達的結(jié)點(包括出發(fā)點自身)。賦給fa的數(shù)作為f(a)，賦給ga的數(shù)作為g(a)。3檢查所構(gòu)造出來的函數(shù)f和g是否與原來的關(guān)系矛盾。若沒有矛盾，則f和g就是要求的優(yōu)先函數(shù)，若有矛盾，則不存在優(yōu)先函數(shù)。,現(xiàn)在必須證明：若ab，則f(a)＝g(b)；若ab，則f(a)g(b)。第一個關(guān)系可從函數(shù)的構(gòu)造直接獲得。因為，若ab，則既有從fa到gb的弧，又有從gb到fa的弧。所以，fa和gb所能到達的結(jié)是全同的。至于ab和ab的情形，只須證明其一。,1對于每個終結(jié)符a，令其對應(yīng)兩個符號fa和ga，畫一以所有符號和為結(jié)點的方向圖。如果ab，則從fa畫一條弧至gb，如果ab，則畫一條弧從gb至fa。,如果ab，則有從fa到gb的弧。也就是，gb能到達的任何結(jié)fa也能到達。因此，f(a)?g(b)。我們所需證明的是，在這種情況下，f(a)＝g(b)不應(yīng)成立。我們將指出，如果f(a)＝g(b)，則根本不存在優(yōu)先函數(shù)。假若f(a)＝g(b)，那么必有如下的回路：,因此有ab,a1b,a1b1,…,ambm,abm對任何優(yōu)先函數(shù)f’和g’來說，必定有f’(a)>g’(b)?f’(a1)?g’(b1)?…?f’(am)?g’(bm)?f’(a)從而導(dǎo)致f’(a)>f’(a)，產(chǎn)生矛盾。因此，不存在優(yōu)先函數(shù)f和g。,例:取前面文法G(E)(1)E→E+T|T(2)T→T*F|F(3)F→P?F|P(4)P→(E)|i的終結(jié)符+，*，↑，i,