[理學(xué)]第四章2自下而上語法分析-wenkub
2022-10-31 22:57:41 本頁面
【正文】 ? b (3) A ? Abc (4) B ? d 使用最右推導(dǎo)： 因為 S aABe aAde aAbcde abbcde，所以 abbcde是文法 G的句子。 ? 最左推導(dǎo) (Leftmost Derive) – 每次推導(dǎo)都替換當(dāng)前句型的最左邊的非終結(jié)符。 例 S ? aABe A ? Abc | b B ? d abbcde 例 S ? aABe A ? Abc | b B ? d abbcde aAbcde aAbcde 例 S ? aABe A ? Abc | b B ? d abbcde aAbcde aAde 例 S ? aABe A ? Abc | b B ? d abbcde aAbcde aAde aABe 例 S ? aABe A ? Abc | b B ? d abbcde aAbcde aAde aABe S 例 S ? aABe A ? Abc | b B ? d abbcde aAbcde aAde aABe S S ?rm aABe ?rm aAde ?rm aAbcde ?rm abbcde 自下而上的語法分析的一般過程 ? 實現(xiàn)思想 – 從輸入符號串開始 ， 從左到右進行掃描 ， 將輸入符號逐個移入一個棧中 ， 邊移入邊分析 ， 一旦棧頂符號串形成某個產(chǎn)生式的右部時 ， 就用該產(chǎn)生式的左部非終結(jié)符代替 ， 稱為 歸約 。 重復(fù)這一過程 ， 直到歸約到棧中只剩下文法的開始符號時 ， 則分析成功 ， 稱為 “ 移進 歸約 ”方法 。 – 與最右歸約對應(yīng)。 )1(rm?)2(rm? )3(rm?)4(rm? 步驟 動作 (1)S ?aABe (2)A ?b (3)A ?Abc (4)B ?d 最左歸約過程是最右推導(dǎo)的逆過程， 對輸入串 abbcde的移進 —歸約過程如下： 該分析過程反復(fù)執(zhí)行“移進”和“歸約”兩個動作，直到棧中只有開始符號為止。實際上，不同的找可歸約串的方法，構(gòu)成了不同的分析算法。 ? 4) 出錯 ： 棧頂?shù)膬?nèi)容與輸入符號相悖，即當(dāng)識別程序發(fā)現(xiàn)輸入符號串不是句子時，進行出錯處理。 – 歸約就是將棧頂?shù)囊淮栍梦姆óa(chǎn)生式的左部代替，歸約可能重復(fù)多次，然后繼續(xù)移進。 ② 如何知道在棧頂符號串中已經(jīng)形成可歸約串？ 如何進行歸約？ 通過不同的自底向上的分析算法來解釋，不同的算法對可歸約串的定義是不同的，但分析過程都有一個共同的特點： 邊移進邊歸約 。 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) 移進 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) 移進 E+ id2*id3 7) 移進 E+id2 *id3 8) 歸約 F→id E+F *id 3 9) 歸約 T→F E+T *id 3 10) 移進 E+T* id3 11) 移進 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 移進歸約分析中的問題 ? 1) 移進 歸約沖突 – 在分析到某一步時，既可以移進，又可以歸約 – 上例第 10)步可以移進 *，也可以按產(chǎn)生式E→E+T 進行歸約。 ? 顯然，在一個符號串中，任意兩個相鄰終結(jié)符號
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1