[理學(xué)]第四章2自下而上語法分析(存儲(chǔ)版)
【正文】 入串的開始依次讀入單詞 (移進(jìn) 棧中 ) 。 在規(guī)范歸約中， 關(guān)鍵問題就轉(zhuǎn)化為 如何識(shí)別句柄 ? 回到上例用 句柄 對(duì)句子 abbcde進(jìn)行歸約有： ? 用句柄對(duì)句子進(jìn)行歸約的過程與用移進(jìn) 歸約過程是一致的，使用歸約的產(chǎn)生式及其順序是一致的。 (3) a優(yōu)先性低于 b ，記作 a b。 ? 構(gòu)造優(yōu)先關(guān)系表的方法： – ①按照定義手工計(jì)算 – ②使用算法 ? 由 F(E) 得 ( = ) T = i, 得 + i T = T*F, 得 + * T = (E), 得 + ( 由 EE+T E = i, 得 i + E = E+T, 得 + + E = T*F, 得 * + E = (E), 得 ) + + * i ( ) + * i ( ) 例 : P: EE+T|T TT*F|F F(E)|i 求算符優(yōu)先表。 (P,a)進(jìn)棧 end。 ? 柄。s[k] = ‘’。 END If s[j] a or s[j] = a THEN begin k:=k+1。 ? 可能將本來不是句子的輸入串誤認(rèn)為是句子。即無法使用單非產(chǎn)生式 (如： T?F)進(jìn)行歸約。 把 s[j+1]….s[k] 歸約為某個(gè) N； k:=j+1。 – 此時(shí) ,形如 :Nj aj Nj+1 aj+1.....Ni ai Ni+1的子串即為 最左素短語 ，應(yīng)被歸約。 ? 分析的方法 ：根據(jù)優(yōu)先性“高于”來識(shí)別句柄的頭，根據(jù)優(yōu)先性“低于”來識(shí)別句柄的尾。 End. PROCEDURE insert(P,a)。 ? – 算符文法 G的任何終結(jié)符 a,b之間要么沒有優(yōu)先關(guān)系，若有優(yōu)先關(guān)系 ,至多有 = , , 中的一種成立 ,則 G為一 算符優(yōu)先文法 。 ? 顯然，在一個(gè)符號(hào)串中，任意兩個(gè)相鄰終結(jié)符號(hào) a和 b之間，只可能存在以下四種優(yōu)先關(guān)系： (1) a, b優(yōu)先性相同，記作 a b。 ② 如何知道在棧頂符號(hào)串中已經(jīng)形成可歸約串？ 如何進(jìn)行歸約？ 通過不同的自底向上的分析算法來解釋，不同的算法對(duì)可歸約串的定義是不同的，但分析過程都有一個(gè)共同的特點(diǎn)： 邊移進(jìn)邊歸約 。 ? 4) 出錯(cuò) ： 棧頂?shù)膬?nèi)容與輸入符號(hào)相悖，即當(dāng)識(shí)別程序發(fā)現(xiàn)輸入符號(hào)串不是句子時(shí)，進(jìn)行出錯(cuò)處理。 )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)為止。 重復(fù)這一過程 ， 直到歸約到棧中只剩下文法的開始符號(hào)時(shí) ， 則分析成功 ， 稱為 “ 移進(jìn) 歸約 ”方法 。 ? 最左推導(dǎo) (Leftmost Derive) – 每次推導(dǎo)都替換當(dāng)前句型的最左邊的非終結(jié)符。 ? 注意： 該過程并未涉及如何在棧里找可歸約串。 – 一旦發(fā)現(xiàn) 可歸約串 (某個(gè)產(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) 歸約”語法分析的過程。 (4) a與 b不可能相鄰，即此符號(hào)串不是句型 (出錯(cuò) )。 終結(jié)符 +?‘ 終結(jié)符 +?‘ 對(duì)于結(jié)束符 和其它終結(jié)符 a有關(guān)系 : a 。 對(duì)數(shù)組初始化 應(yīng)用規(guī)則 1 應(yīng)用規(guī)則 2 ? 2. 求 LASTVT集 – 定義： LASTVT(P)={a|P = ...a或 P =... aQ,a為終結(jié)符 ,P， Q為非終結(jié)符 } + + ?構(gòu)造 LASTVT集 算法 : (思考？ ) ? – 如果每個(gè)非終結(jié)符的 FIRSTVT和 LASTVT集均已知 ,則 可構(gòu)造優(yōu)先關(guān)系表 。不能保證每次對(duì)句柄進(jìn)行歸約 ,在算符優(yōu)先分析過程中 ,每次歸約的符號(hào)串 ,是當(dāng)前句型的最左素短語 . ? ： 至少含有一個(gè)終結(jié)符 ,且除自身外 ,不再包含任何其它更小的素短語。 Repeat a := 下一個(gè)輸入符號(hào) 。 s[k]:=a。 ? 總結(jié)歸約的策略 : 在文法中尋找這樣的產(chǎn)生式 : 它的右部形如 :uj aj uj+1 aj+1... ui ai ui+1,其中每個(gè)終結(jié)符號(hào)與最左素短語對(duì)應(yīng)位置上的 終結(jié)符號(hào)完全相同 ,而每一個(gè) 非終結(jié)符
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1