【正文】 歸約 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)行歸約。實(shí)際上，不同的找可歸約串的方法，構(gòu)成了不同的分析算法。 例 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 自下而上的語法分析的一般過程 ? 實(shí)現(xiàn)思想 – 從輸入符號(hào)串開始 ， 從左到右進(jìn)行掃描 ， 將輸入符號(hào)逐個(gè)移入一個(gè)棧中 ， 邊移入邊分析 ， 一旦棧頂符號(hào)串形成某個(gè)產(chǎn)生式的右部時(shí) ， 就用該產(chǎn)生式的左部非終結(jié)符代替 ， 稱為 歸約 。 ? 3) 接受 ： 當(dāng)棧底只有 “ ‖和開始符號(hào)，而輸入也已經(jīng)到達(dá)右端標(biāo)志符號(hào) “ ‖時(shí)，識(shí)別出符號(hào)串是句子，執(zhí)行該動(dòng)作，表示分析成功，是歸約的一種特殊情況。 ? 將句型中的終結(jié)符號(hào)當(dāng)作 “ 算符 ” ，借助于算符之間的優(yōu)先關(guān)系確定句柄。步驟： ? 先用第一條規(guī)則進(jìn)行初始化 ? 使用第二條規(guī)則對(duì)數(shù)組 F進(jìn)行修改， 修改方法是： – (1) 用一個(gè)棧，將所有 F數(shù)組中值為真的元素 F[P,a]的符號(hào)對(duì) (P,a)壓入堆棧； – (2) 對(duì)棧施行如下操作：若棧不空，將棧頂符號(hào)對(duì)出棧，記為 (Q,a)，檢查所有的產(chǎn)生式，若有形為： P?Q… 的產(chǎn)生式，且 F[P,a]為假，則使 F[P,a]為真，且將 (P,a)壓入堆棧； – (3) 重復(fù)這一過程，直到?？? 求文法各非終結(jié)符的 firstVT： ? 定義數(shù)組： + * ( ) i E 1 T 1 F 1 1 E?E+T | T T?T*F | F F?(E) | i 1 1 1 1 1 從而得到： FirstVT(E) = { +, *,(, I} FirstVT(T) = {*,(,I} FirstVT(F) = {(,I} Begin For 對(duì)每個(gè)非終結(jié)符 P和終結(jié)符 a do F[P,a] = false For 對(duì)每個(gè)形如 P?a… 或 P?Qa… 的產(chǎn)生式 do Insert(P,a) While stack 非空 Begin 把棧頂項(xiàng)出棧，記為 (Q,a) For 對(duì)每條形如 P?Q… 的產(chǎn)生式 do insert(P,a) End。 ? ： (根據(jù)最左素短語的定義 ) – 句型 的一般形式 : N1a1N2a2...NnanNn+1(ai為終結(jié)符 ,Ni為可有可無的非終結(jié)符 ) – 從左向右掃描各符號(hào) ,依次查看算符優(yōu)先矩陣 ,直至找到滿足 ai ai+1的終結(jié)符為止 ,一直移進(jìn) .再從 ai開始往左掃描 ,直至找到滿足關(guān)系 aj1 aj的終結(jié)符為止 ,進(jìn)行歸約。 ? 算符優(yōu)先分析一般并不等價(jià)于規(guī)范規(guī)約 ? 并不對(duì)文法的