[理學(xué)]第四章2 自下而上語法分析-文庫吧
2024-10-01 22:57 本頁面
【正文】 while (在棧里符號串中找到一個可歸約串 )； 歸約可歸約串 while （文法開始符號出現(xiàn)在棧頂或者發(fā)現(xiàn)錯誤）； ? 分析成功的條件 ：棧頂為文法符號，輸入串為空。 ? 注意： 該過程并未涉及如何在棧里找可歸約串。實際上，不同的找可歸約串的方法，構(gòu)成了不同的分析算法。 分析器的四種動作 ? 1) 移進(jìn) ： 讀入下一個輸入符號并把它下推進(jìn)棧。 ? 2) 歸約 ： 當(dāng)棧頂符號串形成一個可歸約的串（如： 句柄 ）時，直接進(jìn)行歸約，即用產(chǎn)生式左側(cè)的非終結(jié)符替換棧頂?shù)木浔? ? 3) 接受 ： 當(dāng)棧底只有 “ ‖和開始符號，而輸入也已經(jīng)到達(dá)右端標(biāo)志符號 “ ‖時，識別出符號串是句子，執(zhí)行該動作，表示分析成功，是歸約的一種特殊情況。 ? 4) 出錯 ： 棧頂?shù)膬?nèi)容與輸入符號相悖，即當(dāng)識別程序發(fā)現(xiàn)輸入符號串不是句子時，進(jìn)行出錯處理。 ? 注意：決定移進(jìn)和歸約的依據(jù)是什么？ 棧頂是否出現(xiàn)了可歸約的符號串。 ? ―移進(jìn) —?dú)w約”語法分析小結(jié)： – 從輸入串的開始依次讀入單詞 (移進(jìn) 棧中 ) 。 – 一旦發(fā)現(xiàn) 可歸約串 (某個產(chǎn)生式的右端 )就立即 歸約 。 – 歸約就是將棧頂?shù)囊淮栍梦姆óa(chǎn)生式的左部代替，歸約可能重復(fù)多次，然后繼續(xù)移進(jìn)。 – 若最終能歸約成文法的開始符號，則分析成功（ 接受 ）；否則 出錯 。 – 由于總是將句型的最左邊的可歸約串替換成非終結(jié)符，該方法通常得到是最右推導(dǎo)。 ? 關(guān)鍵是 如何識別可歸約的符號串 ？ 語法分析中問題的提出： ① 在構(gòu)造語法樹的過程中 ， 何時歸約 ？ 當(dāng)可歸約串出現(xiàn)在棧頂時就進(jìn)行歸約 。 ② 如何知道在棧頂符號串中已經(jīng)形成可歸約串？ 如何進(jìn)行歸約？ 通過不同的自底向上的分析算法來解釋，不同的算法對可歸約串的定義是不同的，但分析過程都有一個共同的特點： 邊移進(jìn)邊歸約 。 規(guī)范歸約：使用 句柄 來定義可歸約串 算符優(yōu)先：使用 最左素短語 來定義可歸約串 ? 自下而上語法分析主要有以下三種方法： ① 簡單優(yōu)先分析法 (規(guī)范歸約 )—— 文法按 一定原則規(guī)定文法符號的優(yōu)先關(guān)系 ②算符優(yōu)先分析法 (不規(guī)范歸約 )—— 規(guī)定 算符 之間的優(yōu)先關(guān)系 ③ LR分析法（規(guī)范歸約） —— LR(0)、LR(1)、 SLR(1)和 LALR(1) 語法分析樹的生成演示 a b b c d e A A B S A→b A→Abc B→d S→aABe (1)S ? aABe (2)A ? b (3)A ? Abc (4)B ? d S ? aABe ? aAde ? aAbcde ? abbcde 規(guī)范歸約相關(guān)概念復(fù)習(xí) ? 有文法 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ī)范歸約中， 關(guān)鍵問題就轉(zhuǎn)化為 如何識別句柄 ? 回到上例用 句柄 對句子 abbcde進(jìn)行歸約有： ? 用句柄對句子進(jìn)行歸約的過程與用移進(jìn) 歸約過程是一致的，使用歸約的產(chǎn)生式及其順序是一致的。 句型 歸約規(guī)則 abbcde (1)S ? aABe (2)A ? b (3)A ? Abc (4)B ? d (2) A?b (3)A ? Abc aAbcde aAde (4)B ? d (1)S ? aABe aABe S 練習(xí)：有文法如下 (1)EE+T|T (2)TT*F|F (3)F(E)|id 1）寫出輸入串 id1+id2*id3 的規(guī)范歸約過程； 2）給出該文法“移進(jìn) 歸約”語法分析的過程。 E=E+T =E+T*F =E+T*id =E+F*id =E+id*id =T+id*id =F+id*id =id+id*id 動作 棧 輸入緩沖區(qū) 1) 準(zhǔn)備 id1+id2*id3 2) 移進(jìn) id1 +id2*id3 3) 歸約 F→id F +id 2*id3 4) 歸約 T→F T +id 2*id3 5) 歸約 E→T E +id 2*id3 6) 移進(jìn) E+ id2*id3 7) 移進(jìn) E+id2 *id3 8) 歸約
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1