ch6自底向上算符優(yōu)先語(yǔ)法分析_(張素琴).ppt

ch6自底向上算符優(yōu)先語(yǔ)法分析_(張素琴).ppt

ID:49411531

大小:2.35 MB

頁(yè)數(shù):72頁(yè)

時(shí)間:2020-02-06

ch6自底向上算符優(yōu)先語(yǔ)法分析_(張素琴).ppt_第1頁(yè)
ch6自底向上算符優(yōu)先語(yǔ)法分析_(張素琴).ppt_第2頁(yè)
ch6自底向上算符優(yōu)先語(yǔ)法分析_(張素琴).ppt_第3頁(yè)
ch6自底向上算符優(yōu)先語(yǔ)法分析_(張素琴).ppt_第4頁(yè)
ch6自底向上算符優(yōu)先語(yǔ)法分析_(張素琴).ppt_第5頁(yè)
資源描述:

《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ī)范歸約分析中棧

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫(huà)的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無(wú)此問(wèn)題,請(qǐng)放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫(kù)負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭(zhēng)議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無(wú)法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請(qǐng)聯(lián)系客服處理。