第4章自下而上語法分析

1、自下而上語法分析方法自下而上語法分析方法第四章（第四章（2） 本節(jié)要求本節(jié)要求o 主要內(nèi)容主要內(nèi)容：自下而上語法分析的概念，規(guī)范自下而上語法分析的概念，規(guī)范歸約，算符優(yōu)先分析方法及其相關(guān)概念。歸約，算符優(yōu)先分析方法及其相關(guān)概念。o 重點掌握：重點掌握：掌握自下而上分析的基本思想，掌握自下而上分析的基本思想，規(guī)范規(guī)約的概念及過程；算符優(yōu)先文法、算規(guī)范規(guī)約的概念及過程；算符優(yōu)先文法、算符優(yōu)先關(guān)系的判定，最左素短語、句柄的定符優(yōu)先關(guān)系的判定，最左素短語、句柄的定義與判定，構(gòu)造算符優(yōu)先關(guān)系表，能用算符義與判定，構(gòu)造算符優(yōu)先關(guān)系表，能用算符優(yōu)先分析法進行表達式分析優(yōu)先分析法進行表達式分析G = (E,

2、i, +, *, (, ) , P , E) P： E E + E E E * E E ( E ) E i 使用最左推導(dǎo)：E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i例：判定輸入串(i+i)*i是否是下述文法的句子？結(jié)論結(jié)論：自上而下語法分析自上而下語法分析采用最左推導(dǎo)，每一步推導(dǎo)使用哪個產(chǎn)生式要視當(dāng)前非終結(jié)符匹配輸入字符串中的哪個符號來確定。自下而上語法分析自下而上語法分析是最右推導(dǎo)的逆過程，由輸入符號串反向歸約到文法的開始符號。自下而上的語法分析自下而上的語法分析o 實現(xiàn)思想：實現(xiàn)思想：“移進移進- -歸約歸約”方法方法n 設(shè)置一個

3、棧，將輸入符號逐個移進移進棧中，棧頂形成某某產(chǎn)生式的右部時，就用左部去代替，稱為歸約歸約。重復(fù)這一過程，直到棧中只剩下文法的開始符號，就確認輸入串是文法的句子，分析成功，否則出錯。n 語法樹：從樹葉開始，逐步向上歸約構(gòu)造分析樹，直到形成根結(jié)。是推導(dǎo)的逆過程。o 核心核心n 尋找尋找句柄句柄（這是關(guān)鍵）（這是關(guān)鍵）進行規(guī)約。用不同的方法尋找句柄，就可獲得不同的分析方法。o 最左推導(dǎo)最左推導(dǎo)(Left-most Derive)n每一步推導(dǎo)都替換當(dāng)前句型的最左邊的非終結(jié)符。n其逆過程稱為最右歸約最右歸約o 最右推導(dǎo)最右推導(dǎo)(Right-most Derive)n每一步推導(dǎo)都替換當(dāng)前句型的最右邊的非終

4、結(jié)符。n其逆過程稱為最左歸約最左歸約(規(guī)范歸約規(guī)范歸約)，得規(guī)范句型規(guī)范句型例：例：設(shè)有文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d 使用最右推導(dǎo)：因為S aAcBe aAcde aAbcde abbcde，所以 abbcde是文法G的句子。)1(rm)2(rm)3(rm)4(rm步驟步驟動作動作(1)S aAcBe(2)A b (3)A Ab(4)B d最左歸約過程是最右推導(dǎo)的逆過程， 對輸入串a(chǎn)bbcde的歸約過程如下：該分析過程反復(fù)執(zhí)行該分析過程反復(fù)執(zhí)行“移進移進”和和“歸約歸約”兩個動作，直到棧中只有開始符號為止。兩個動作，直到棧中只有開始符號為

5、止。ab AcS1移進aAa移進b4 a歸約35c A a移進d7c A a歸約48Bc A a移進e910歸約1移進b2a歸約23ab移進c6AadBeA語法分析樹的生成演示語法分析樹的生成演示a b b c d ea b b c d eAABSAbAbAAbAAbBdBdSaAcBeSaAcBe(1)S aAcBe(2)A b (3)A Ab(4)B do 規(guī)范歸約分析過程具有如下特點：n 從輸入串的開始依次讀入單詞(移進移進棧中) 。n 一旦發(fā)現(xiàn)可歸約串可歸約串（某個產(chǎn)生式的右端）就立即歸約歸約。n 歸約歸約就是將棧頂?shù)囊淮栍梦姆óa(chǎn)生式的左部代替，歸約可能重復(fù)多次重復(fù)多次。n 若最終

6、能歸約成文法的開始符號，則分析成功。n 由于總是將句型的最左邊的可歸約串替換成非終結(jié)符，該方法與最右推導(dǎo)對應(yīng)。o 關(guān)鍵是如何判斷可歸約串可歸約串？問題的提出： 在構(gòu)造語法樹的過程中，何時歸約？ 當(dāng)可歸約串出現(xiàn)在棧頂時就進行歸約。 如何知道在棧頂符號串中已經(jīng)形成可歸約串？ 如何進行歸約？ 不同的自下而上的分析方法對可歸約串的定義是不同的，但分析過程的一個共同特點是：邊移邊移進邊歸約進邊歸約。規(guī)范歸約：使用句柄句柄來定義算符優(yōu)先分析：使用最左素短語最左素短語來定義LR分析方法：使用活前綴活前綴來定義規(guī)范歸約的概念o 有文法G，開始符號為S, 如果有S=xy,則xy是文法G的句型句型，x,y是任意的

7、符號串o 如果有S=xAy, 且有A=,則是句型xy相對于非終結(jié)符A的短語短語o 如果有S=xAy, 且有A-,則是句型xy相對于A-的直接短語直接短語o 位于一個一個句型最左邊的直接短語稱為句柄句柄.*+*注意: 每次歸約的部分必須是句柄句柄 (最右推導(dǎo))。 關(guān)鍵的問題是如何識別句柄如何識別句柄例：考慮如下文法：求句型 i1 * i2 + i3 的短語、直接短語和句柄。ET | E+TTF | T*FFi | (E)因此：因此： 短語有：i1, i2, i3, i1*i2, i1*i2+i3 直接短語有：i1, i2 , i3 句柄是： i1E = F * i2 + i3 E = i1 *

8、F + i3 E = i1 * i2 + F E = T + i3 （T =T*F =i1 * i2）E = i1 * i2 + i3 Fii2 + i3 不是短語，因為E = i1 * E （E =i2 +i3）*從語法分析樹來識別：o 一棵子樹子樹是由樹的某個結(jié)點連同它的所有子孫組成的。o 子樹的所有端末結(jié)點自左至右排列成一個相對子樹根的短語短語。o 直接短語直接短語：只有父子兩代結(jié)點形成的短語。o 句柄句柄：最左子樹的直接短語。EE + TTFi3i2i1T * FF從語法樹可以看出：i1, i2, i3, i1*i2, i1*i2+i3是句型i1*i2+i3的短語直接短語有：i1, i

9、2 , i3 句柄是： i1ET | E+TTF | T*FFi | (E)句型i1*i2+i3的語法樹如圖：對下述文法，求句型 E+T * F + i的短語、直接短語、句柄ET | E+TTF | T*FFi | (E)EE + TFiE + TT * F短語有：i, T * F, E+T * F, E + T * F + i直接短語有： i, T * F句柄是：T * F練 習(xí)給定右邊的文法，用句柄對符號串a(chǎn)bbcde進行歸約o 用句柄對句子進行歸約的過程與用移進-歸約過程是一致的，使用歸約的產(chǎn)生式及其順序是一致的。符號串歸約規(guī)則abbcde(1)S aAcBe(2)A b (3)A Ab

10、(4)B d(2)Ab(3)A AbaAbcdeaAcde(4)B d(1)S aAcBeaAcBeSbAABSacdeb規(guī)范歸約的定義：o 假定是文法G的一個句子，如果序列： n, n-1, , 0 (=S)滿足如下條件，則序列n, n-1, , 0是一個規(guī)范歸約規(guī)范歸約:(1) n = 是給定的句子(2) 0 =S 是文法的開始符號(3) 對任何i, 0b.或R=Qb. (注意ab相鄰)a b,G中有P.Rb.的產(chǎn)生式,且R=.a或R=.aQ (注意ab相鄰)算符優(yōu)先文法的定義+例：EE+E | E*E | (E) | i 證明不是算符優(yōu)先文法。因 為：EE+E ，EE*E 則有 + *(

11、由規(guī)則2)又因為：EE*E, EE+E 則有 + *(由規(guī)則3)所以不是算符優(yōu)先文法。o 3.算符優(yōu)先文法算符優(yōu)先文法n 算符文法G的任何終結(jié)符a,b之間要么沒有優(yōu)先關(guān)系，若有優(yōu)先關(guān)系,至多有 , , 中的一種成立,則G為一算符優(yōu)先文法符優(yōu)先文法。練 習(xí)o 對右邊的文法G，計算終結(jié)符+，*，和 )之間的優(yōu)先關(guān)系：EE + T TT * F FP FP(E) 因為： EE + T ，T=T*F，所以：+ E + T ，所以：+ + (規(guī)則規(guī)則3)因為： T T * F ，F(xiàn) = P F，所以：* T * F，所以：* * (規(guī)則規(guī)則3)因為： P(E) ， E = E + T ，所以：+ ) (

12、規(guī)則規(guī)則3) 因為：FP F, P = (E)，所以：） (規(guī)則規(guī)則3) 因為： FP F， F =P F，所以： i, 得 + T*F, 得 + (E), 得 + E+TE = i, 得i +E = E+T, 得+ + E = T*F, 得* + E = (E), 得 ) + +*i()#+*i()#例:P:EE+T|T TT*F|F F (E)|i 求算符優(yōu)先關(guān)系表終結(jié)符+#終結(jié)符+#對于結(jié)束符#和其它終結(jié)符a之間若有關(guān)系,則必有: # # ，計算方法是拓展成E#E#*注意：o a,b之間未必有優(yōu)先關(guān)系,在優(yōu)先表中，空白部分是一種錯誤關(guān)系o 相同的終結(jié)符之間的優(yōu)先關(guān)系不一定是o 如果有a

13、b,不一定有b a(不具對稱性) o 如果有a b,不一定有b a(不具對稱性)，因為只定義相鄰運算符之間的優(yōu)先關(guān)系，a,b相鄰時，不一定b,a相鄰。o 如果有a b, b c不一定有a c算符優(yōu)先關(guān)系表的自動構(gòu)造算法算符優(yōu)先關(guān)系表的自動構(gòu)造算法 o 1.FirstVT1.FirstVT集集n 定義定義：對每個非終結(jié)符P, FirstVT(P)FirstVT(P)=a|P=a.或P=Qa.,a為終結(jié)符,P，Q為非終結(jié)符+由優(yōu)先性低于的定義和FirstVT集合的定義可以得出：若存在某個產(chǎn)生式：Q-aP，對所有：bFirstVT(P) 都有：a .a或 P =.aQ,a為終結(jié)符,P，Q為非終結(jié)符+

14、構(gòu)造LastVT集算法算法 ： 自己練習(xí)練習(xí)練習(xí)o LastVT(S) = a,)o LastVT(T) = a,), , 計算LastVT給定文法GS：S a | (T)T T,S | S o3.3.構(gòu)造優(yōu)先關(guān)系表的算法構(gòu)造優(yōu)先關(guān)系表的算法n 如果每個非終結(jié)符的FirstVT和LastVT集均已知,則可根據(jù)定義構(gòu)造優(yōu)先關(guān)系表。構(gòu)造思路： (1) 若產(chǎn)生式是形如：Pab 或 PaQb的形式，則有a b (2)若產(chǎn)生式右部是.aR.的形式,則對于每個bFirstVT(R)都有a b (3)若產(chǎn)生式右部有.Rb的形式,則對于每個aLastVT(R)集,都有a bfor 每個每個形如形如PX1X2X

15、n的的產(chǎn)生式產(chǎn)生式 dofor i =1 to n-1 dobegin if Xi和和Xi+1都是終結(jié)符都是終結(jié)符 then Xi = Xi+1 if i= n-2, Xi和和Xi+2是終結(jié)符是終結(jié)符, 但但Xi+1為非終結(jié)符為非終結(jié)符 then Xi = Xi+2 if Xi為終結(jié)符為終結(jié)符, Xi+1為非終結(jié)符為非終結(jié)符 then for FirstVT中的每個元素中的每個元素a do Xi Xi+1 ;end;優(yōu)先關(guān)系表構(gòu)造算法同一產(chǎn)生式中同一產(chǎn)生式中的相鄰符號的相鄰符號1同一產(chǎn)生式中同一產(chǎn)生式中的相鄰符號的相鄰符號2a出現(xiàn)在其它產(chǎn)出現(xiàn)在其它產(chǎn)生式中，通過生式中，通過計算得到計算得到練習(xí)

16、練習(xí)o FirstVT(S) = a,(o FirstVT(T) = a,(, , o LastVT(S) = a,)o LastVT(T) = a,), , 的FirstVT和LastVT集,構(gòu)造優(yōu)先關(guān)系表。給定文法GS：S a | (T)T T,S | S a,()#a,(# aj+1時為止.n(2)(2)再從aj開始往左掃描堆棧,直至找到某個i,滿足ai-1 ai為止n(3)(3)Niai Ni+1ai+1 Njaj Nj+1形式的子串即為最左最左素短語素短語，應(yīng)被歸約。算符優(yōu)先分析過程算符優(yōu)先分析過程 開始開始： 分析棧中為：# #，輸入緩沖區(qū)為：輸入串輸入串# 結(jié)束結(jié)束：輸入緩沖區(qū)為

17、# #，分析棧中為#S#S，分析成功否則失敗表達式表達式 i+ii+i* *i i的算符優(yōu)先過程EE+T|T TT*F|FF(E)|i例:給定文法GE：棧棧輸入緩沖輸入緩沖 說明說明# #i+ii+i* *i#i#初始狀態(tài)#i+i+i* *i#i# #i, i入棧#F+i+i* *i#i# #+, 用Fi歸約#F+i i* *i#i# #+, +入棧#F+i* *i#i# +i, i入棧#F+F* *i#i# +*, 用Fi歸約#F+F*i#i# +*, *入棧#F+F*i# # *i, i入棧#F+F*F# # *#,用Fi歸約#F+T# # +#, 用TF*F歸約#E# # #, 用EF+

18、T歸約+*i()#+ * i ( # a DO BEGINREPEAT q:=sj; IF sj-1 Vt THEN j:=j-1 else j:=j-2;UNTIL sj q;把把sj+1.sk歸約為某個歸約為某個N，將，將N入棧；入棧；top:=j+1; END IF sj a OR sj = a THENBEGIN top:=top+1; stop:=a; END; ELSE error; a := 下一個輸入符號下一個輸入符號;while (a!=#) ;算法：P95棧頂符號sj與即將輸入的符號a進行比較棧頂符號優(yōu)先性低于或等于輸入符號a，則移進a向前查找最左素短語的頭， j記錄可歸約

19、串的頭進行歸約S表示堆棧，top記錄棧頂位置，j記錄棧頂符號位置Sj優(yōu)先性高于a,尋找可歸約串,進行歸約o 算符優(yōu)先分析不是嚴(yán)格的規(guī)范歸約o 不對文法的非終結(jié)符定義優(yōu)先關(guān)系，無法發(fā)現(xiàn)由單個非終結(jié)符組成的“可歸約串”。即無法使用單非產(chǎn)生式(如：TF)進行歸約。o 算符優(yōu)先分析比規(guī)范歸約過程要快，跳過了所有的單非終結(jié)產(chǎn)生式。o 可能將本來不是句子的輸入串誤認為是句子。o 總結(jié)歸約的策略: 在文法中尋找這樣的產(chǎn)生式:它的右部形如: Niai Ni+1ai+1 Njaj Nj+1,其中每個終結(jié)符號與最左素短語對應(yīng)位置上的終結(jié)符號完全相同終結(jié)符號完全相同,而每一個非終結(jié)非終結(jié)符號符號uk應(yīng)與相應(yīng)位置上的

20、非終結(jié)符號Nk相對應(yīng),不必完全相同不必完全相同。算符優(yōu)先分析法小結(jié)算符優(yōu)先分析法小結(jié)o 優(yōu)點優(yōu)點n 簡單、效率高簡單、效率高n 能夠處理部分二義性文法能夠處理部分二義性文法o 缺點缺點n 文法書寫限制大文法書寫限制大n 占用內(nèi)存空間大占用內(nèi)存空間大n 不規(guī)范、存在查不到的語法錯誤不規(guī)范、存在查不到的語法錯誤優(yōu)先函數(shù)優(yōu)先函數(shù)o 一般不直接用優(yōu)先關(guān)系表，構(gòu)造優(yōu)先函數(shù) 將每個終結(jié)符與兩個自然數(shù)f()和g()對應(yīng)，f()和g()的選擇滿足如下關(guān)系：1 2 , f(1) 2 , f(1)g(2)函數(shù)f為入棧優(yōu)先函數(shù)，g為比較優(yōu)先函數(shù)。給定一個文法，如果存在優(yōu)先函數(shù)，則一定存在多個，即f和g的選擇不是唯一

21、的。從優(yōu)先關(guān)系表構(gòu)造優(yōu)先函數(shù)的方法：o (1) 對應(yīng)于每個終結(jié)符a(包含#)，令其對應(yīng)兩個符號fa和ga，然后畫一張以所有這些符號為結(jié)點的方向圖，如果a = b，就從fa畫箭弧到gb ，如果a *(練習(xí)o 對下邊的文法，有優(yōu)先關(guān)系表如右：為其構(gòu)造優(yōu)先函數(shù)：S a | (T)T T,S | S a,()#a,(#=a,()#f64262g73722fagaf,g,f(g(f)g)f#g#算符優(yōu)先分析中的錯誤處理算符優(yōu)先分析中的錯誤處理o 使用算符優(yōu)先分析法時，可在兩種情況下發(fā)現(xiàn)語法錯誤：n 1. 若棧頂終結(jié)符號與下一個輸入符號之間不存在任何優(yōu)先關(guān)系n 2. 若找到某一可歸約串，但不存在任一產(chǎn)生式，其右部與其匹配。 設(shè)文法為： E #E# TF EE+T FPF | P ET P(E) TT*F Pi求算符優(yōu)先關(guān)系表。練習(xí)練習(xí)解: (1)求firstVT和lastVT集f