[理學(xué)]第四章2自下而上語法分析-文庫吧資料
2024-10-22 22:57本頁面
【正文】 ..的產(chǎn)生式 ,且 R=...a或R=...aQ (注意 ab相鄰 ) 算符優(yōu)先文法的定義 + + + + 例： E→E+E | E*E | (E) | i 證明不是算符優(yōu)先文法 。 如果以上四種關(guān)系中的任意兩種都不會(huì)同時(shí)成立，則可以根據(jù)終結(jié)符號(hào)之間的歸約關(guān)系進(jìn)行語法分析。 (3) a優(yōu)先性低于 b ，記作 a b。 ? 顯然，在一個(gè)符號(hào)串中，任意兩個(gè)相鄰終結(jié)符號(hào) a和 b之間，只可能存在以下四種優(yōu)先關(guān)系： (1) a, b優(yōu)先性相同，記作 a b。 ? 各種分析方法中處理沖突的技術(shù)不同 算符優(yōu)先分析 ? 算符優(yōu)先分析法的思想源于表達(dá)式的分析，即利用相鄰終結(jié)符號(hào)之間的關(guā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 動(dòng)作 棧 輸入緩沖區(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) 歸約 F→id E+F *id 3 9) 歸約 T→F E+T *id 3 10) 移進(jìn) E+T* id3 11) 移進(jìn) E+T*id3 12) 歸約 F→id E+T*F 13) 歸約 T→T*F E+T 14) 歸約 E→E+T E 15) 接受 所得的結(jié)果是：用產(chǎn)生式序列表示語法分析樹 (1) EE+T|T (2) TT*F|F (3) F(E)|id id1 + id2 * id3 F T E F T F T E 移進(jìn)歸約分析中的問題 ? 1) 移進(jìn) 歸約沖突 – 在分析到某一步時(shí)，既可以移進(jìn)，又可以歸約 – 上例第 10)步可以移進(jìn) *，也可以按產(chǎn)生式E→E+T 進(jìn)行歸約。 在規(guī)范歸約中， 關(guān)鍵問題就轉(zhuǎn)化為 如何識(shí)別句柄 ? 回到上例用 句柄 對(duì)句子 abbcde進(jìn)行歸約有： ? 用句柄對(duì)句子進(jìn)行歸約的過程與用移進(jìn) 歸約過程是一致的，使用歸約的產(chǎn)生式及其順序是一致的。 ② 如何知道在棧頂符號(hào)串中已經(jīng)形成可歸約串？ 如何進(jìn)行歸約？ 通過不同的自底向上的分析算法來解釋，不同的算法對(duì)可歸約串的定義是不同的，但分析過程都有一個(gè)共同的特點(diǎn)： 邊移進(jìn)邊歸約 。 – 由于總是將句型的最左邊的可歸約串替換成非終結(jié)符，該方法通常得到是最右推導(dǎo)。 – 歸約就是將棧頂?shù)囊淮?hào)用文法產(chǎn)生式的左部代替，歸約可能重復(fù)多次，然后繼續(xù)移進(jìn)。 ? ―移進(jìn) —?dú)w約”語法分析小結(jié)： – 從輸入串的開始依次讀入單詞 (移進(jìn) 棧中 ) 。 ? 4) 出錯(cuò) ： 棧頂?shù)膬?nèi)容與輸入符號(hào)相悖，即當(dāng)識(shí)別程序發(fā)現(xiàn)輸入符號(hào)串不是句子時(shí)，進(jìn)行出錯(cuò)處理。 ? 2) 歸約 ： 當(dāng)棧頂符號(hào)串形成一個(gè)可歸約的串（如： 句柄 ）時(shí)，直接進(jìn)行歸約，即用產(chǎn)生式左側(cè)的非終結(jié)符替換棧頂?shù)木浔?。?shí)際上，不同的找可歸約串的方法，構(gòu)成了不同的分析算法。} while (在棧里符號(hào)串中找到一個(gè)可歸約串 )； 歸約可歸約串 while （文法開始符號(hào)出現(xiàn)在棧頂或者發(fā)現(xiàn)錯(cuò)誤）； ? 分析成功的條件 ：棧頂為文法符號(hào)，輸入串為空。 )1(rm?)2(rm? )3(rm?)4(rm? 步驟 動(dòng)作 (1)S ?aABe (2)A ?b (3)A ?Abc (4)B ?d 最左歸約過程是最右推導(dǎo)的逆過程， 對(duì)輸入串 abbcde的移進(jìn) —?dú)w約過程如下： 該分析過程反復(fù)執(zhí)行“移進(jìn)”和“歸約”兩個(gè)動(dòng)作，直到棧中只有開始符號(hào)為止。 – 與最左歸約 (規(guī)范歸約 )對(duì)應(yīng)，得規(guī)范句型。 – 與最右歸約對(duì)應(yīng)。 是推導(dǎo) 的逆過程 。 重復(fù)這一過程 ， 直到歸約到棧中只剩下文法的開始符號(hào)時(shí) ， 則分析成功 ， 稱為 “ 移進(jìn) 歸約 ”方法 。第四章 (2) 自下向上語法分析 本章要求 : 1. 掌握自下向上語法分析的基本思想和基本概念 2. 了解算符優(yōu)先語法分析；求 FIRSTVT集和LASTVT集，構(gòu)造算符優(yōu)先關(guān)系表；能運(yùn)用算符優(yōu)先分析方法進(jìn)行表達(dá)式分析（選學(xué)） 3. 掌握句柄的定義與判定 4. 理解規(guī)范歸
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1