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

《ch6自底向上算符優(yōu)先語法分析(張素琴)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、自底向上算符優(yōu)先語法分析第6章1主要內(nèi)容：規(guī)范歸約，自上而下的算符優(yōu)先分析方法及其相關(guān)概念。重點(diǎn)掌握：掌握自下而上分析的基本思想，規(guī)范規(guī)約的概念及過程；算符優(yōu)先文法、算符優(yōu)先關(guān)系的判定，最左素短語、句柄的定義與判定;構(gòu)造算符優(yōu)先關(guān)系表;能用算符優(yōu)先分析法進(jìn)行表達(dá)式分析。6.1自底向上優(yōu)先分析概述2自下而上的語法分析實(shí)現(xiàn)思想：“移進(jìn)-歸約”方法輸入：待分析的句子(終結(jié)符號(hào)串)。輸出：語法樹。從樹葉開始，逐步向上歸約構(gòu)造分析樹，直到形成根結(jié)點(diǎn)。核心尋找句柄進(jìn)行規(guī)約。設(shè)置一個(gè)棧，將輸入符號(hào)逐個(gè)移進(jìn)棧中

2、，棧頂形成某產(chǎn)生式的右部時(shí)(句柄)，就用左部去代替，稱為歸約。重復(fù)這一過程，直到棧中只剩下文法的開始符號(hào)，就確認(rèn)輸入串是文法的句子，分析成功，否則出錯(cuò)。3最左推導(dǎo)(Left-mostDerive)每一步推導(dǎo)都替換當(dāng)前句型的最左邊的非終結(jié)符?！淠孢^程稱為最右歸約最右推導(dǎo)(Right-mostDerive)每一步推導(dǎo)都替換當(dāng)前句型的最右邊的非終結(jié)符?！淠孢^程稱為最左歸約(規(guī)范歸約)，得規(guī)范句型例：設(shè)有文法G[S]：(1)S?aAcBe(2)A?b(3)A?Ab(4)B?d最右推導(dǎo)：Sa

3、AcBeaAcdeaAbcdeabbcdeabbcde是文法G的句子。4步驟動(dòng)作(1)S?aAcBe(2)A?b(3)A?Ab(4)B?d最左歸約過程是最右推導(dǎo)的逆過程，對輸入串a(chǎn)bbcde的歸約過程如下：該分析過程反復(fù)執(zhí)行“移進(jìn)”和“歸約”兩個(gè)動(dòng)作，直到棧中只有開始符號(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語法分析樹的生成演示abbcdeAABSA→bA→AbB→dS→aAcBe(1

4、)S?aAcBe(2)A?b(3)A?Ab(4)B?d6規(guī)范歸約分析過程具有如下特點(diǎn)：從輸入串的開始依次讀入單詞(移進(jìn)棧中)。一旦發(fā)現(xiàn)可歸約串（某個(gè)產(chǎn)生式的右端）就立即歸約。歸約就是將棧頂?shù)囊淮?hào)用文法產(chǎn)生式的左部代替，歸約可能重復(fù)多次。若最終能歸約成文法的開始符號(hào)，則分析成功。由于總是將句型的最左邊的可歸約串替換成非終結(jié)符，該方法與最右推導(dǎo)對應(yīng)。關(guān)鍵是如何判斷可歸約串？7問題的提出：①在構(gòu)造語法樹的過程中，何時(shí)歸約？當(dāng)可歸約串出現(xiàn)在棧頂時(shí)就進(jìn)行歸約。②如何知道在棧頂符號(hào)串中已經(jīng)形成可歸

5、約串？如何進(jìn)行歸約？不同的自下而上的分析方法對可歸約串的定義是不同的，但分析過程的一個(gè)共同特點(diǎn)是：邊移進(jìn)邊歸約。規(guī)范歸約：使用句柄來定義,如簡單優(yōu)先分析算符優(yōu)先分析：使用最左素短語來定義LR分析方法：使用活前綴來定義8規(guī)范歸約的概念有文法G，開始符號(hào)為S,如果有S=>xβy,則xβy是文法G的句型，x,y是任意的符號(hào)串如果有S=>xAy,且有A=>β,則β是句型xβy相對于非終結(jié)符A的短語如果有S=>xAy,且有A->β,則β是句型xβy相對于A->β的直接短語位于一個(gè)句型最左邊的直接短語稱為句

6、柄.**+*注意:規(guī)范規(guī)約中每次歸約的部分必須是句柄(最右推導(dǎo))。關(guān)鍵的問題是如何識(shí)別句柄9例：求句型i1*i2+i3的短語、直接短語和句柄。E?T

7、E+TT?F

8、T*FF?i

9、(E)因此：短語有：i1,i2,i3,i1*i2,i1*i2+i3直接短語有：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àn)镋=>i1*E（E=>i2+i3）*++++++10從語法分

10、析樹來識(shí)別：一棵子樹是由樹的某個(gè)結(jié)點(diǎn)連同它的所有子孫組成的。子樹的所有端末結(jié)點(diǎn)自左至右排列成一個(gè)相對子樹根的短語。直接短語：只有父子兩代結(jié)點(diǎn)形成的短語。句柄：最左子樹的直接短語。EE+TTFi3i2i1T*FF從語法樹可以看出：i1,i2,i3,i1*i2,i1*i2+i3是句型i1*i2+i3的短語直接短語有：i1,i2,i3句柄是：i1E?T

11、E+TT?F

12、T*FF?i

13、(E)句型i1*i2+i3的語法樹如圖：11對下述文法，求句型E+T*F+i的短語、直接短語、句柄E?T

14、E+TT?F

15、T

16、*FF?i

17、(E)EE+TFiE+TT*F短語有：i,T*F,E+T*F,E+T*F+i直接短語有：i,T*F句柄是：T*F練習(xí)12給定右邊的文法，用句柄對符號(hào)串a(chǎn)bbcde進(jìn)行歸約用句柄對句子進(jìn)行歸約的過程與用移進(jìn)-歸約過程是一致的，使用歸約的產(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ī)范歸約分析中棧