資源描述:
《ch6自底向上算符優(yōu)先語(yǔ)法分析_(張素琴).ppt》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、自底向上算符優(yōu)先語(yǔ)法分析第6章1主要內(nèi)容:規(guī)范歸約,自上而下的算符優(yōu)先分析方法及其相關(guān)概念。重點(diǎn)掌握:掌握自下而上分析的基本思想,規(guī)范規(guī)約的概念及過(guò)程;算符優(yōu)先文法、算符優(yōu)先關(guān)系的判定,最左素短語(yǔ)、句柄的定義與判定;構(gòu)造算符優(yōu)先關(guān)系表;能用算符優(yōu)先分析法進(jìn)行表達(dá)式分析。6.1自底向上優(yōu)先分析概述2自下而上的語(yǔ)法分析實(shí)現(xiàn)思想:“移進(jìn)-歸約”方法輸入:待分析的句子(終結(jié)符號(hào)串)。輸出:語(yǔ)法樹(shù)。從樹(shù)葉開(kāi)始,逐步向上歸約構(gòu)造分析樹(shù),直到形成根結(jié)點(diǎn)。核心尋找句柄進(jìn)行規(guī)約。設(shè)置一個(gè)棧,將輸入符號(hào)逐個(gè)移進(jìn)棧中,棧頂形成某產(chǎn)生式的右部時(shí)(句柄)
2、,就用左部去代替,稱為歸約。重復(fù)這一過(guò)程,直到棧中只剩下文法的開(kāi)始符號(hào),就確認(rèn)輸入串是文法的句子,分析成功,否則出錯(cuò)。3最左推導(dǎo)(Left-mostDerive)每一步推導(dǎo)都替換當(dāng)前句型的最左邊的非終結(jié)符?!淠孢^(guò)程稱為最右歸約最右推導(dǎo)(Right-mostDerive)每一步推導(dǎo)都替換當(dāng)前句型的最右邊的非終結(jié)符?!淠孢^(guò)程稱為最左歸約(規(guī)范歸約),得規(guī)范句型例:設(shè)有文法G[S]:(1)S?aAcBe(2)A?b(3)A?Ab(4)B?d最右推導(dǎo):SaAcBeaAcdeaAbcdeabbcdeabbcde是文法G的句子
3、。4步驟動(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)為止。abAcS1移進(jìn)aAa移進(jìn)b4a歸約35cAa移進(jìn)d7cAa歸約48BcAa移進(jìn)e910歸約1移進(jìn)b2a歸約23ab移進(jìn)c6AadBeA5語(yǔ)法分析樹(shù)的生成演示abbcdeAABSA→bA→AbB→dS→aAcBe(1)S?aAcBe(2)A?b(3)A?Ab(4)B?d6規(guī)范歸約分析過(guò)程具有如下特點(diǎn):從輸入串的
4、開(kāi)始依次讀入單詞(移進(jìn)棧中)。一旦發(fā)現(xiàn)可歸約串(某個(gè)產(chǎn)生式的右端)就立即歸約。歸約就是將棧頂?shù)囊淮?hào)用文法產(chǎn)生式的左部代替,歸約可能重復(fù)多次。若最終能歸約成文法的開(kāi)始符號(hào),則分析成功。由于總是將句型的最左邊的可歸約串替換成非終結(jié)符,該方法與最右推導(dǎo)對(duì)應(yīng)。關(guān)鍵是如何判斷可歸約串?7問(wèn)題的提出:①在構(gòu)造語(yǔ)法樹(shù)的過(guò)程中,何時(shí)歸約?當(dāng)可歸約串出現(xiàn)在棧頂時(shí)就進(jìn)行歸約。②如何知道在棧頂符號(hào)串中已經(jīng)形成可歸約串?如何進(jìn)行歸約?不同的自下而上的分析方法對(duì)可歸約串的定義是不同的,但分析過(guò)程的一個(gè)共同特點(diǎn)是:邊移進(jìn)邊歸約。規(guī)范歸約:使用句柄來(lái)定義
5、,如簡(jiǎn)單優(yōu)先分析算符優(yōu)先分析:使用最左素短語(yǔ)來(lái)定義LR分析方法:使用活前綴來(lái)定義8規(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ǔ)稱為句柄.**+*注意:規(guī)范規(guī)約中每次歸約的部分必須是句柄(最右推導(dǎo))。關(guān)鍵的問(wèn)題是如何識(shí)別句柄9例:求句型i1*i2+i3的短語(yǔ)、直接短語(yǔ)和句柄。E?T
6、E+TT?F
7、T*F
8、F?i
9、(E)因此:短語(yǔ)有:i1,i2,i3,i1*i2,i1*i2+i3直接短語(yǔ)有:i1,i2,i3句柄是:i1E=>F*i2+i3E=>i1*F+i3E=>i1*i2+FE=>T+i3(T=>T*F=>i1*i2)E=>i1*i2+i3F?ii2+i3不是短語(yǔ),因?yàn)镋=>i1*E(E=>i2+i3)*++++++10從語(yǔ)法分析樹(shù)來(lái)識(shí)別:一棵子樹(shù)是由樹(shù)的某個(gè)結(jié)點(diǎn)連同它的所有子孫組成的。子樹(shù)的所有端末結(jié)點(diǎn)自左至右排列成一個(gè)相對(duì)子樹(shù)根的短語(yǔ)。直接短語(yǔ):只有父子兩代結(jié)點(diǎn)形成的短語(yǔ)。句柄:最左子樹(shù)的直接短語(yǔ)。EE+TTFi3i2i1T
10、*FF從語(yǔ)法樹(shù)可以看出:i1,i2,i3,i1*i2,i1*i2+i3是句型i1*i2+i3的短語(yǔ)直接短語(yǔ)有:i1,i2,i3句柄是:i1E?T
11、E+TT?F
12、T*FF?i
13、(E)句型i1*i2+i3的語(yǔ)法樹(shù)如圖:11對(duì)下述文法,求句型E+T*F+i的短語(yǔ)、直接短語(yǔ)、句柄E?T
14、E+TT?F
15、T*FF?i
16、(E)EE+TFiE+TT*F短語(yǔ)有:i,T*F,E+T*F,E+T*F+i直接短語(yǔ)有:i,T*F句柄是:T*F練習(xí)12給定右邊的文法,用句柄對(duì)符號(hào)串a(chǎn)bbcde進(jìn)行歸約用句柄對(duì)句子進(jìn)行歸約的過(guò)程與用移進(jìn)-歸約過(guò)程是一致的,使
17、用歸約的產(chǎn)生式及其順序是一致的。符號(hào)串(句型)歸約規(guī)則abbcde(1)S?aAcBe(2)A?b(3)A?Ab(4)B?d(2)A?b(3)A?AbaAbcdeaAcde(4)B?d(1)S?aAcBeaAcBeSbAABSacdeb13規(guī)范歸約分析中棧