《編譯原理課程教案》第4章：自下而上語法分析.ppt

《《編譯原理課程教案》第4章：自下而上語法分析.ppt》由會員分享，可在線閱讀，更多相關(guān)《《編譯原理課程教案》第4章：自下而上語法分析.ppt（71頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

自下而上語法分析方法,第四章（2）,本章要求,主要內(nèi)容：自下而上語法分析的概念，規(guī)范歸約，算符優(yōu)先分析方法及其相關(guān)概念。重點(diǎn)掌握：掌握自下而上分析的基本思想，基本概念，算符優(yōu)先文法、算符優(yōu)先關(guān)系的判定，最左素短語、句柄、活前綴的定義與判定，求FirstVT集,LastVT集,構(gòu)造算符優(yōu)先關(guān)系表,能用算符優(yōu)先分析法進(jìn)行表達(dá)式分析,G=({E},{i,+,*,(,)},P,E)P：E?E+EE?E*EE?(E)E?i,使用最左推導(dǎo)：E?E*E?(E)*E?(E+E)*E?(i+E)*E?(i+i)*E?(i+i)*i,例：判定輸入串(i+i)*i是否是下述文法的句子？,結(jié)論：自上而下語法分析采用最左推導(dǎo)，每一步推導(dǎo)使用哪個(gè)產(chǎn)生式要視當(dāng)前非終結(jié)符匹配輸入字符串中的哪個(gè)符號來確定。自下而上語法分析是最左推導(dǎo)的逆過程，由輸入符號串反向推導(dǎo)到文法的開始符號。,自下而上的語法分析,實(shí)現(xiàn)思想：“移進(jìn)-歸約”方法設(shè)置一個(gè)棧，將輸入符號逐個(gè)移進(jìn)棧中，棧頂形成某產(chǎn)生式的右部時(shí)，就用左部去代替，稱為歸約。重復(fù)這一過程，直到棧中只剩下文法的開始符號，就確認(rèn)輸入串是文法的句子，分析成功，否則出錯(cuò)。語法樹：從樹葉開始，逐步向上歸約構(gòu)造分析樹，直到形成根結(jié)。是推導(dǎo)的逆過程。核心尋找句柄(這是關(guān)鍵)進(jìn)行規(guī)約。用不同的方法尋找句柄，就可獲得不同的分析方法。,最左推導(dǎo)(Left-mostDerive)每次推導(dǎo)都替換當(dāng)前句型的最左邊的非終結(jié)符?！c最右歸約對應(yīng)最右推導(dǎo)(Right-mostDerive)每次推導(dǎo)都替換當(dāng)前句型的最右邊的非終結(jié)符。——與最左歸約(規(guī)范歸約)對應(yīng)，得規(guī)范句型,例：設(shè)有文法G[S]：(1)S?aAcBe(2)A?b(3)A?Ab(4)B?d使用最右推導(dǎo)：因?yàn)镾aAcBeaAcdeaAbcdeabbcde，所以abbcde是文法G的句子。,步驟動作,(1)S?aAcBe(2)A?b(3)A?Ab(4)B?d,最左歸約過程是最右推導(dǎo)的逆過程，對輸入串a(chǎn)bbcde的歸約過程如下：,該分析過程反復(fù)執(zhí)行“移進(jìn)”和“歸約”兩個(gè)動作，直到棧中只有開始符號為止。,a,b,A,c,S,,,,,,,b,d,B,e,A,這種分析過程具有如下特點(diǎn)：從輸入串的開始依次讀入單詞(移進(jìn)棧中)。一旦發(fā)現(xiàn)可歸約串(某個(gè)產(chǎn)生式的右端)就立即歸約。歸約就是將棧頂?shù)囊淮栍梦姆óa(chǎn)生式的左部代替，歸約可能重復(fù)多次，然后繼續(xù)移進(jìn)。若最終能歸約成文法的開始符號，則分析成功。由于總是將句型的最左邊的可歸約串替換成非終結(jié)符，該方法與最右推導(dǎo)對應(yīng)。關(guān)鍵是如何判斷可歸約串？,語法分析樹的生成演示,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,問題的提出：①在構(gòu)造語法樹的過程中，何時(shí)歸約？當(dāng)可歸約串出現(xiàn)在棧頂時(shí)就進(jìn)行歸約。②如何知道在棧頂符號串中已經(jīng)形成可歸約串？如何進(jìn)行歸約？通過不同的自底向上的分析算法來解釋，不同的算法對可歸約串的定義是不同的，但分析過程都有一個(gè)共同的特點(diǎn)：邊移進(jìn)邊歸約。,規(guī)范歸約的概念,有文法G，開始符號為S,如果有S=>xβy,則xβy是文法G的句型，x,y是任意的符號串如果有S=>xAy,且有A=>β,則β是句型xβy相對于非終結(jié)符A的短語如果有S=>xAy,且有A->β,則β是句型xβy相對于A->β的直接短語位于一個(gè)句型最左邊的直接短語稱為句柄.,注意:每次歸約的部分必須是句柄(最右推導(dǎo))。關(guān)鍵的問題是如何識別句柄,例：考慮如下文法：,求句型i1*i2+i3的短語、直接短語和句柄。,E?T|E+TT?F|T*FF?i|(E),因此：短語有：i1,i2,i3,i1*i2,i1*i2+i3直接短語有：i1,i2,i3句柄是：i1,E=>F*i2+i3E=>i1*F+i3E=>i1*i2+F,E=>T+i3（T=>T*F=>i1*i2）E=>i1*i2+i3,F?i,從語法分析樹來識別：一棵子樹是由樹的某個(gè)結(jié)點(diǎn)連同它的所有子孫組成的。子樹的所有端末結(jié)點(diǎn)自左至右排列成一個(gè)相對子樹根的短語。直接短語：只有父子兩代結(jié)點(diǎn)形成的短語。句柄：最左子樹的直接短語。,從語法樹可以看出：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的語法樹如圖：,對下述文法，求句型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í),給定右邊的文法，用句柄對符號串a(chǎn)bbcde進(jìn)行歸約,用句柄對句子進(jìn)行歸約的過程與用移進(jìn)-歸約過程是一致的，使用歸約的產(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是文法的開始符號(3)對任何i,0b...或R=>Qb...(注意ab相鄰)③ab,G中有P?...Rb...的產(chǎn)生式,且R=>...a或R=>...aQ(注意ab相鄰),算符優(yōu)先文法的定義,例：E→E+E|E*E|(E)|i證明不是算符優(yōu)先文法。因?yàn)椋篍→E+E，E?E*E則有+*(由規(guī)則2)又因?yàn)椋篍→E*E,E?E+E則有+*(由規(guī)則3)所以不是算符優(yōu)先文法。,3.算符優(yōu)先文法算符文法G的任何終結(jié)符a,b之間要么沒有優(yōu)先關(guān)系，若有優(yōu)先關(guān)系,至多有=,中的一種成立,則G為一算符優(yōu)先文法。,練習(xí),對右邊的文法G，計(jì)算終結(jié)符+，*，?和)之間的優(yōu)先關(guān)系：,E?E+TT?T*FF?P?FP?(E),因?yàn)椋篍?E+T，T=>T*F，所以：+E+T，所以：+>+(規(guī)則3)因?yàn)椋篢?T*F，F(xiàn)=>P?F，所以：*T*F，所以：*>*(規(guī)則3)因?yàn)椋篜?(E)，E=>E+T，所以：+>)(規(guī)則3)因?yàn)椋篎?P?F,P=>(E)，所以：）>?(規(guī)則3)因?yàn)椋篎?P?F，F(xiàn)=>P?F，所以：?a...或P=>Qa...,a為終結(jié)符,P，Q為非終結(jié)符},由優(yōu)先性低于的定義和firstVT集合的定義可以得出：若存在某個(gè)產(chǎn)生式：Q->…aP…，對所有：b∈FirstVT(P)都有：a...a或P=>...aQ,a為終結(jié)符,P，Q為非終結(jié)符},+,+,構(gòu)造LastVT集算法：自己練習(xí),3.構(gòu)造優(yōu)先關(guān)系表的算法如果每個(gè)非終結(jié)符的FirstVT和LastVT集均已知,則可根據(jù)定義構(gòu)造優(yōu)先關(guān)系表。,,構(gòu)造思路：(1)若產(chǎn)生式是形如：P→…ab…或P→…aQb…的形式，則有ab(2)若產(chǎn)生式右部是...aR...的形式,則對于每個(gè)b∈FirstVT(R)都有ab(3)若產(chǎn)生式右部有...Rb的形式,則對于每個(gè)a∈LastVT(R)集,都有ab,for每個(gè)形如P?X1X2…Xn的產(chǎn)生式dofori=1ton-1dobeginifXi和Xi+1都是終結(jié)符thenXi=Xi+1ifiXi+1;end;,優(yōu)先關(guān)系表構(gòu)造算法,同一產(chǎn)生式中的相鄰符號1,同一產(chǎn)生式中的相鄰符號2,a出現(xiàn)在其它產(chǎn)生式中，通過計(jì)算得到,練習(xí),FirstVT(S)={a,(}FirstVT(T)={a,(,,}LastVT(S)={a,)}LastVT(T)={a,),,},的FirstVT和LastVT集,構(gòu)造優(yōu)先關(guān)系表。,給定文法G[S]：,S?a|(T)T?T,S|S,算符優(yōu)先分析方法,原理：通過比較相鄰終結(jié)符間的優(yōu)先關(guān)系來實(shí)現(xiàn)實(shí)現(xiàn)機(jī)制：仍然采用“移進(jìn)-歸約”方式，不斷移進(jìn)輸入符號，識別可歸約串，并進(jìn)行歸約。分析方法：根據(jù)優(yōu)先性“低于”來識別句柄的頭，根據(jù)優(yōu)先性“高于”來識別句柄的尾。各種優(yōu)先關(guān)系已經(jīng)存于優(yōu)先關(guān)系表中。,幾個(gè)定義,1.算符優(yōu)先分析過程，不是嚴(yán)格的規(guī)范歸約，每次歸約的符號串，不一定是規(guī)范歸約中的“句柄”，不能識別只由一個(gè)非終結(jié)符組成的句柄，是當(dāng)前句型的最左素短語.2.素短語：是一個(gè)短語，至少含有一個(gè)終結(jié)符,且除自身外,不再包含任何其它更小的素短語。3.最左素短語：是指位于句型最左邊的那個(gè)素短語。,例：給定右邊文法的一個(gè)句型：T*F+i求其短語、素短語、最左素短語？,E?T|E+TT?F|T*FF?i|(E),短語有：i,T*F,T*F+i素短語有：i,T*F最左素短語是：T*F,練習(xí):給定文法G[E]:求句型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為最左素短語。,E?E+T|TT?T*F|FF?(E)|i,,設(shè)算符文法G的句型的一般形式為#N1a1N2a2…Nnan#(Ni∈VN∪{ε},ai∈VT）它的最左素短語是滿足下列條件的最左子串：NiaiNi+1ai+1…NjajNj+1其中：ai-1≮ai,ai≡ai+1≡…..≡aj-1≡aj，aj≯aj+1,說明了最左素短語與周圍符號之間的關(guān)系,定理,符號棧內(nèi)容+輸入緩沖區(qū)內(nèi)容＝#當(dāng)前句型#,#N1a1N2a2…NnanNn+1#(ai為終結(jié)符,Ni為可有可無的非終結(jié)符),句型的一般形式：,分析時(shí)句型表示：,3.算符優(yōu)先分析,分析模型,,過程：(1)從左向右掃描輸入符號并移入堆棧,并查優(yōu)先矩陣,直至找到滿足aj>aj+1時(shí)為止.(2)再從aj開始往左掃描堆棧,直至找到某個(gè)i,滿足ai-1aDOBEGINREPEATq:=s[j];IFs[j-1]∈VtTHENj:=j-1elsej:=j-2;UNTILs[j]=b，就從fa畫箭弧到gb，如果a<=b，就從gb畫箭弧到fa；(2)對每個(gè)結(jié)點(diǎn)都賦予一個(gè)數(shù)，此數(shù)值等于從該結(jié)點(diǎn)出發(fā)(含該結(jié)點(diǎn))，能夠到達(dá)的所有不相同的結(jié)點(diǎn)的個(gè)數(shù)，即不記重復(fù)數(shù)；(3)檢查所構(gòu)造的函數(shù)f和g，看是否同原來的優(yōu)先關(guān)系表相矛盾。如果不矛盾，f和g就是所要求的優(yōu)先函數(shù)；如果有矛盾，則不存在優(yōu)先關(guān)系函數(shù)。(因?yàn)榇嬖趦?yōu)先關(guān)系表沒有對應(yīng)的優(yōu)先函數(shù)的情況),例：根據(jù)優(yōu)先關(guān)系表構(gòu)造優(yōu)先函數(shù)：,練習(xí),對下邊的文法，有優(yōu)先關(guān)系表如右：為其構(gòu)造優(yōu)先函數(shù)：,S?a|(T)T?T,S|S,算符優(yōu)先分析中的錯(cuò)誤處理,使用算符優(yōu)先分析法時(shí)，可在兩種情況下發(fā)現(xiàn)語法錯(cuò)誤：1.若棧頂終結(jié)符號與下一個(gè)輸入符號之間不存在任何優(yōu)先關(guān)系2.若找到某一可歸約串，但不存在任一產(chǎn)生式，其右部與其匹配。,設(shè)文法為：E→#E#T→FE→E+TF→P↑F|PE→TP→(E)T→T*FP→i求算符優(yōu)先關(guān)系表。,練習(xí),解:(1)求firstVT和lastVT集firstVT(E)={#}firstVT(E)={+,*,↑,(,i)firstVT(T)={*,↑,(,i)firstVT(F)={↑,(,i)firstVT(P)={(,i)lastVT(E’)={#}lastVT(E)={+,*,↑,),i}lastVT(T)={*,↑,),i}lastVT(F)={),↑,i}lastVT(P)={i,)},firstVT(B)={b|B?b…或B?Cb…},E=#E#E?#…,E?E+TE?T?T*FE?T?F?P↑FE?T?P?(E)?i,lastVT(B)={a|B?…a或B?…aC},(2)求=關(guān)系E→#E##=#P→(E)(=),(3)求<關(guān)系E→#E#則##所以+>#,*>#，↑>#,)>#,i>#E→E+T則lastVT(E)>+所以+>+,*>+,↑>+,)>+,i>+T→T*F則lastVT(T)>*所以*>*,↑>*,i>*,)>*F→P↑F則lastVT(P)>↑所以i>↑,)>↑P→(E)則lastVT(E)>)所以+>),*>),↑>),i>),)>),算符優(yōu)先關(guān)系表,