語(yǔ)法分析-自下而上分析

1、第五章 語(yǔ)法分析-自下而上分析,5.1自底向上分析的一般過(guò)程：移進(jìn)-歸約分析5.1.1 規(guī)范歸約5.2 算符優(yōu)先分析5.3 LR分析法5.4 語(yǔ)法分析器的自動(dòng)產(chǎn)生,主要內(nèi)容,自底向上分析算法的基本思想：,存在主要問(wèn)題: 可歸約串的識(shí)別問(wèn)題,主要方法: 算法優(yōu)先分析法 LR分析法,5.1 自底向上分析的一般過(guò)程,所謂自頂向上分析法就是從輸入串開始，利用有關(guān)規(guī)則逐步進(jìn)行“歸約”，又稱為移進(jìn)-歸約分析法。特點(diǎn)

2、：邊移進(jìn)邊歸約。,移進(jìn)—?dú)w約分析結(jié)構(gòu),,,,,要點(diǎn)：建立符號(hào)棧，用來(lái)紀(jì)錄分析的歷史和現(xiàn)狀，并根據(jù)所面臨的情況，確定下一步動(dòng)作是移進(jìn)還是歸約。,,,,,分析過(guò)程：把輸入符號(hào)串按描述順序一一地移進(jìn)符號(hào)棧（一次移一個(gè)），檢查棧中符號(hào)，當(dāng)在棧頂?shù)娜舾煞?hào)形成當(dāng)前句型的句柄時(shí)，就根據(jù)規(guī)則進(jìn)行規(guī)約，將句柄從符號(hào)棧中彈出，并將相應(yīng)的非終結(jié)符號(hào)壓入棧內(nèi)（即規(guī)則的左部符號(hào)），然后再檢查棧內(nèi)符號(hào)串是否形成新的句柄，若有就再進(jìn)行規(guī)約，否則移進(jìn)符號(hào)。分析一直

3、進(jìn)行到讀到輸入串的右界符為止。最后，若棧中僅含有左界符號(hào)和識(shí)別符號(hào)，則表示分析成功，否則失敗。,歸約 （回顧）,推導(dǎo)定義1.直接推導(dǎo) “?” α→β是文法G的產(chǎn)生式，若有v,w滿足：v=γαδ,w= γβδ, 其中γ∈V*,δ∈V*(V代表字母表) 則稱v直接推導(dǎo)到w,記作 v ? w 也稱w直接歸約到v例：G： S→0S1， S→01 0S1 ?00S11 00S11 ?000S111

4、 000S111 ?00001111 S ?0S1,如果移進(jìn)－歸約過(guò)程是自頂向下最右推導(dǎo)的逆過(guò)程，則稱為規(guī)范歸約。如對(duì)最右推導(dǎo)S ?αAδ ?αβδ來(lái)說(shuō)，一定有A →β規(guī)則存在，將句型αβδ中的β用產(chǎn)生式的左部符號(hào)代替便得到新句型αAδ，這是一次規(guī)范歸約，恰好與規(guī)范推導(dǎo)相反。,5.1.1 規(guī)范歸約,*,對(duì)應(yīng)的規(guī)范歸約過(guò)程: abbcdeA→b aAbcdeA→Ab aAc

5、deB→d aAcBeS→aAcBe S歸約為開始符號(hào)，是合法句子。,S,a,A,c,B,c,A,b,b,d,,,,,,,,,,句子abbcde的最右推導(dǎo)過(guò)程：S ? aAcBe ? aAcde ? aAbcde ? abbcde,文法G[S]:S→aAcBe A→Ab|b B→d,例,對(duì)應(yīng)的自下而上分析過(guò)程,在移進(jìn)-歸約過(guò)程中，何時(shí)歸約？何時(shí)移進(jìn)？,不能只看到棧頂

6、出現(xiàn)某一產(chǎn)生式的右部就用相應(yīng)產(chǎn)生式歸約，如在第5步時(shí)，棧中符號(hào)是＃aAb，棧頂符號(hào)串b,Ab都是產(chǎn)生式的右部符號(hào)，這時(shí)到底用A→b 還是A→Ab歸約不能確定。為此引入了 可歸約串的概念。,自下而上分析主要問(wèn)題,主要問(wèn)題識(shí)別“可歸約串”。對(duì)“可歸約串”概念的不同定義，就形成了不同的自下而上的分析方法。在“規(guī)范歸約”中，則用“句柄”來(lái)刻畫“可歸約串”。在算符優(yōu)先分析法中我們用“最左素短語(yǔ)”來(lái)刻畫“可歸約串”；,短語(yǔ)令G是一個(gè)文

7、法，S是文法的開始符，假定???是文法G的一個(gè)句型，如果有：S??A? 且 A ? ? 則稱?是句型???相對(duì)于非終結(jié)符A的短語(yǔ)。直接短語(yǔ)特別是，如果有 A ? ?（即有A→ ?的產(chǎn)生式）則稱?是句型???相對(duì)于規(guī)則A? ?的直接短語(yǔ)。句柄一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。,相關(guān)概念,*,+,子樹與短語(yǔ)的關(guān)系,子樹語(yǔ)法樹的某個(gè)結(jié)點(diǎn)連同它的所有后代組成了一棵子樹，只含有單層分枝的子樹稱為簡(jiǎn)單子樹。短語(yǔ)在語(yǔ)法樹中的識(shí)別

8、：短語(yǔ)：子樹的末端結(jié)點(diǎn)(即樹葉)組成的符號(hào)串是相對(duì)于子樹根的短語(yǔ)；直接短語(yǔ)：簡(jiǎn)單子樹的末端結(jié)點(diǎn)組成的符號(hào)串是相對(duì)于簡(jiǎn)單子樹根的直接短語(yǔ)；句柄：最左簡(jiǎn)單子樹的末端結(jié)點(diǎn)組成的符號(hào)串為句柄。顯然從語(yǔ)法樹出發(fā)尋找短語(yǔ)、直接短語(yǔ)、句柄要直觀得多。,解: (1) 該句型的推導(dǎo)過(guò)程為 E ? E+T ? T+T ? T*F+T ? F*F+T ? i*F+T ? i*i+F ? i*i+i

9、 i+i 并不是該句型的一個(gè)短語(yǔ)。,文法： E ? T|E+T T ?F|T*F F ?i | (E) 對(duì)于句型i*i+i，判斷i＋i是否是該句型的一個(gè)短語(yǔ)。,例1,從語(yǔ)法樹中看，i+i不構(gòu)成一棵子樹的所有葉子結(jié)點(diǎn),例2 上題文法的另一個(gè)句型E+T*F+I, 求其含有的短語(yǔ)、直接短語(yǔ)和句柄,短語(yǔ)： E+T*F+i ,E

10、+T*F, T*F,和i。直接短語(yǔ)：T*F和i。句柄為： T*F。,注意:一個(gè)句型的直接短語(yǔ)可能不只一個(gè)，但最左直接短語(yǔ)(即句柄)是惟一的。,規(guī)范規(guī)約就是句柄歸約可歸約串是句柄。歸約過(guò)程：裁剪句柄。即把A的子節(jié)點(diǎn)從分析樹中刪除。,規(guī)范規(guī)約的特點(diǎn),句柄為什么可作為可歸約串？,句柄具有“最左”特性，句柄的“最左”性和分析棧的棧頂兩者是相關(guān)的。對(duì)于規(guī)范句型(規(guī)范推導(dǎo)所得的句型)來(lái)說(shuō)，句柄的后面不會(huì)出現(xiàn)非終結(jié)符(也即句柄的后

11、面只能出現(xiàn)終結(jié)符)。即句柄一定在棧內(nèi)并在棧頂部分。基于這一點(diǎn)，我們可用句柄來(lái)刻畫“移進(jìn)－歸約”過(guò)程的“可歸約串”。歸約實(shí)質(zhì)：在移進(jìn)過(guò)程中，當(dāng)發(fā)現(xiàn)棧頂呈現(xiàn)句柄時(shí)就用相應(yīng)產(chǎn)生式的左部符號(hào)進(jìn)行替換(即歸約)。,例,文法 G[S]:S→aAcBe A→Ab|b B→d句子abbcde的規(guī)范歸約過(guò)程：,,書中[例5.3]：對(duì)于文法（5.2）輸入串i1*i2+i3

12、的分析（規(guī)范歸約）如下：步驟 符號(hào)棧 輸入串 動(dòng)作0 # i1*i2+i3# 預(yù)備 #i1 *i2+i3# 讀入i1 #F

13、 *i2+i3# 歸約，F(xiàn)?i #T *i2+i3 # 歸約，T ?F #T* i2+i3# 讀入 #T*i2 +i3# 讀入

14、 #T*F +i3# 歸約，F(xiàn) ?i #T +i3# 歸約，T ?T*F #E +i3# 歸約，E ?T # E+

15、 i3# 讀入 #E+i3 # 讀入 #E+F # 歸約, F ?i #E+T #

16、 歸約, T ?F #E # 歸約，E ?E+T #E # 接受,1) 這是一種經(jīng)典的自底向上分析法，簡(jiǎn)單直觀，并被廣泛使 用，開始主要是對(duì)表達(dá)式的分析，現(xiàn)在已不限于此?？梢?

17、 用于一大類上下無(wú)關(guān)的文法.,運(yùn)算法則:,1.乘除的優(yōu)先大于加減 2.同優(yōu)先級(jí)的運(yùn)算符左大于右 3.括號(hào)內(nèi)的優(yōu)先級(jí)大于括號(hào)外 于是： 4+8-6/2*3 運(yùn)算過(guò)程和結(jié)果唯一。,2) 稱為算符優(yōu)先分析是因?yàn)檫@種方法是仿效算術(shù)式的四則運(yùn)算 而建立起來(lái)的，作算術(shù)式的四則運(yùn)算時(shí)，為了保證計(jì)算結(jié)果 和過(guò)程的唯一性，規(guī)定了一個(gè)統(tǒng)一的四則運(yùn)算法則，規(guī)定運(yùn) 算符之間的優(yōu)先關(guān)系。,5.2 算符優(yōu)先分析法,3)算符優(yōu)先分

18、析的特點(diǎn):,仿效四則運(yùn)算過(guò)程，預(yù)先規(guī)定相鄰終結(jié)符之間的優(yōu) 先關(guān)系，然后利用這種優(yōu)先關(guān)系來(lái)確定句型的“可歸約串”，并進(jìn)行規(guī)約。,4)分析器結(jié)構(gòu):,#,,分析程序,優(yōu)先關(guān)系矩陣,,,,,,,,,#,,,,符號(hào)棧,輸入串,前提條件算符優(yōu)先文法可歸約串最左素短語(yǔ)特點(diǎn)非規(guī)范歸約，即不是句柄歸約,算符文法,一個(gè)文法，如果它的任何產(chǎn)生式的右部都不含兩個(gè)相繼（并列）的非終結(jié)符，即不含如下形式的產(chǎn)生式右部： …QR…

19、 則我們稱該文法為算符文法。,假定 a、b代表任意終結(jié)符；P、Q、R代表任意非終結(jié)符；‘…’代表有終結(jié)符和非終結(jié)符組成的任意序列，包括空字。 假定G是一個(gè)不含?-產(chǎn)生式的算符文法。對(duì)于任何一對(duì)終結(jié)符a、b，我們說(shuō)： (1) a??b 當(dāng)且僅當(dāng)文法G中含有形如P ?…ab…或P ?…aQb…的產(chǎn)生式; (2) ab 當(dāng)且僅當(dāng)G中含有形如P ?…Rb…的產(chǎn)生式，R而R?+…a或R ?+…aQ;,優(yōu)先關(guān)系,優(yōu)先關(guān)系的意

20、義,a??b a,b同時(shí)出現(xiàn)在同一產(chǎn)生式的右部，在子樹中是同一層葉子結(jié)點(diǎn)。aba在b的下一層子樹中，a至少歸約一次后產(chǎn)生的非終結(jié)符可與b同層。,如果一個(gè)算符文法G中的任何終結(jié)符對(duì)（a, b ）至多只滿足下述三關(guān)系之一： a=·b, ab 則稱G是一個(gè)算符優(yōu)先文法。優(yōu)先關(guān)系的特點(diǎn)：有序性。,算符優(yōu)先文法,試說(shuō)明下述算術(shù)表達(dá)式文法G[E]是一個(gè)算符文法，但不是算符優(yōu)先文法。

21、G[E]: E→E+E∣E*E∣(E)∣i,例：,解：由于文法G[E]中的任何產(chǎn)生式右部都不含兩個(gè)相鄰的非終 結(jié)符，所以G[E]是算符文法。此外，因?yàn)?(1) 由于存在E→E+E，而E+E中的第二個(gè)E可推出 E →E*E，即有+?*； (2) 由于存在E→E*E，而E*E中的第一個(gè)E可推出 E →E+E，即有+?*。 即運(yùn)算符+和*之間同時(shí)存在著兩種不同的優(yōu)先關(guān)系，故文法G

22、[E]不是一個(gè)算符優(yōu)先文法。,算符優(yōu)先表的構(gòu)造,為了找出所有滿足關(guān)系””的終結(jié)符對(duì)，首先需要對(duì)文法的每個(gè)非終結(jié)符P構(gòu)造兩個(gè)集合FIRSTVT(P)和LASTVT(P):　　FIRSTVT(P)={a | P?a…或P ?Qa…,a?VT而 Q ?VN }　　 LASTVT(P)={a | P?…a或P ?…aQ,a?VT而 Q ?VN } 有了這兩個(gè)集合后，就可以通過(guò)檢查每個(gè)產(chǎn)生式的候選式確定滿足關(guān)系的所有終結(jié)符對(duì)。

23、,注意：與前FRIST集相區(qū)別，前FIRST是句子的首個(gè)非終結(jié)符，而此處是所有可推導(dǎo)出的句型的首個(gè)非終結(jié)符。,+,+,+,+,構(gòu)造FIRSTVT和LASTVT集,構(gòu)造集合FIRSTVT(P)的算法：若有產(chǎn)生式P?a…或P ?Qa…,則a?FIRSTVT(P)若a?FIRSTVT(Q)，且有產(chǎn)生式P ?Q… 則a?FIRSTVT(P)構(gòu)造LASTVT(P)的算法。若有產(chǎn)生式P? … a或P ?…

24、aQ,則a?LASTVT(P)若a?LASTVT(Q)，且有產(chǎn)生式P ? … Q 則a?LASTVT(P)其程序?qū)崿F(xiàn)見(jiàn)P91,其程序?qū)崿F(xiàn)采用棧，見(jiàn)P91 以G[E]: ?E→E+T∣T ?T→T*F∣F F→(E)∣i 為例理解程序。,檢查一個(gè)算符優(yōu)先文法G[S]的每個(gè)產(chǎn)生式的每個(gè)侯選式，找出所有一個(gè)算符優(yōu)先文法相鄰的終結(jié)符對(duì)的優(yōu)先關(guān)系。

25、 (1) 對(duì)形如P→…ab…或P→…aQb…的產(chǎn)生式， 有a =· b； (2) 對(duì)形如P→…aR…的產(chǎn)生式，有b∈FIRSTVT(R)， 則a?b； (3) 對(duì)形如P→…Rb…的產(chǎn)生式，有a∈LASTVT(R)， 則a?b。 (4)特別,語(yǔ)句括號(hào)“#”作為終結(jié)符對(duì)待，S是文法開始符號(hào)，則應(yīng)有 #S# 存在；可由上述構(gòu)造方法得到：

26、 # =· # ；#?FIRSTVT(S)；LASTVT(S)?# 即“#”與FIRSTVT(S)或LASTVT(S)集合中的元素即終結(jié)符之間的優(yōu)先關(guān)系。,試構(gòu)造下述算術(shù)表達(dá)式文法G[E]的算符優(yōu)先關(guān)系表。 G[E]: ?E→E+T∣T ?T→T*F∣F F→(E)∣i,例,解：(1) 構(gòu)造FIRSTVT集。① 根據(jù)構(gòu)造規(guī)則(1)：由E→E+…

27、得FIRSTVT(E)={+}；由T→T*…得FIRSTVT(T)={*}；由F→(…和F→i得FIRSTVT(F)={(，i}。② 根據(jù)構(gòu)造規(guī)則(2)： 由FIRSTVT(F)={(,i}和T→F得 FIRSTVT(T)={*，(，i}；由FIRSTVT(T)和E→T得 FIRSTVT(E)={+，*，(，i}。,G[E]: ?E→E+T∣T

28、 T→T*F∣F F→(E)∣i,(2) 構(gòu)造LASTVT集。① 根據(jù)構(gòu)造規(guī)則(1)：由E→…+T得LASTVT(E)={+}；由T→…*F得LASTVT(T)={*}；由F→…)和F→i得LASTVT(F)={)，i}。 ② 根據(jù)構(gòu)造規(guī)則(2)： 由LASTVT(F)和T→F得 LASTVT(T)={*，)，i}； 由LASTVT(T)和E→T得

29、 LASTVT(E)={+，*，)，i}。,G[E]: ?E→E+T∣T T→T*F∣F F→(E)∣i,(3) 構(gòu)造優(yōu)先關(guān)系表。① 根據(jù)規(guī)則(1)：由“(E)”得( =· )。② 根據(jù)規(guī)則(2)知：由E→…+T得+?FIRSTVT(T)，即： +?*，+?(，+?i；由T→…*F得*?FIRSTVT(F)，即：

30、 *?(，*?i；由F→(E…得(?FIRSTVT(E)，即： (?+，(?*，(?(，(?i。,G[E]: ?E→E+T∣T T→T*F∣F F→(E)∣i,③ 根據(jù)規(guī)則(3)知：由E→E+…得LASTVT(E)?+，即： +?+，*?+，)?+，i?+；由T→T*…得LASTVT(T)?*，即：

31、 *?*，)?*，i?*；由F→…E)得LASTVT(E)?),即： +?)，*?)，)?)，i?)。 ④此外，由#E#得 # =· #； #?FIRSTVT(E)，即#?+，#?*，#?(，#?i；LASTVT(E)?#，即+?#，*?#，)?#，i?#,G[E]: ?E→E+T∣T T→T*F∣F F→(E

32、)∣i,得到的優(yōu)先關(guān)系表,G[E]: ?E→E+T∣T T→T*F∣F F→(E)∣i,構(gòu)造文法G的優(yōu)先表的程序?qū)崿F(xiàn)：其算法如下（書P92）： FOR 每一條產(chǎn)生式P?X1X2…Xn FOR i:=1 TO n-1 DO BEGIN IF Xi 和 Xi+1 均為終結(jié)符 THEN

33、置 Xi=·Xi+1 IF i Xi＋1 END,文法 G[S]:S→aAcBe A→Ab|b B→d句子abbcde的歸約過(guò)程：（與規(guī)范歸約同）,用優(yōu)先關(guān)系構(gòu)造可歸約串,算符優(yōu)先文法句型的一般形式# N1a1N2a2…NnanNn+1# 每個(gè)ai都是終結(jié)符，Ni則是可有可無(wú)的

34、非終結(jié)符。算符文法的特點(diǎn)決定了該句型這n個(gè)終結(jié)符的任何兩個(gè)相鄰的終結(jié)符之間頂多只有一個(gè)非終結(jié)符。句型中的素短語(yǔ)每個(gè)素短語(yǔ)要素(指僅包含終結(jié)符的序列)都具有下述形式： aj-1??aj =· aj+1… =· ai ?ai+1,算符優(yōu)先分析算法的設(shè)計(jì),,最左素短語(yǔ),句型的素短語(yǔ)是指這樣一種短語(yǔ)，它至少包含一個(gè)終結(jié)符，并且除自身之外，不再包含其它更小的素短語(yǔ)。最左素短語(yǔ)句型最左邊的那個(gè)素短語(yǔ)。 子樹和素

35、短語(yǔ)子樹的末端結(jié)點(diǎn)組成的符號(hào)串含終結(jié)符，且在該子樹中不再有包含含有終結(jié)符的更小子樹。,最左素短語(yǔ)的三個(gè)特點(diǎn)：至少包含一個(gè)終結(jié)符除自身外不包含其它素短語(yǔ)(最小性)；在句型中具有最左性。最左素短語(yǔ)與句柄的區(qū)別：最左素短語(yǔ)：有終結(jié)符句柄：直接短語(yǔ)（一層子樹）,查找最左素短語(yǔ)的兩個(gè)方法： (1) 最左子串法找出句型中最左子串且終結(jié)符由左至右的對(duì)應(yīng)關(guān)系滿足aj-1?aj =· aj+1… =· ai?a

36、i+1；檢查文法中是否存在一個(gè)候選式，該候選式中的所有終結(jié)符由左至右的排列恰為ajaj+1…ai，即每一位終結(jié)符均對(duì)應(yīng)相等，而非終結(jié)符僅對(duì)應(yīng)位置存在即可；如果存在這樣的候選式，則該候選式(包括其中的非終結(jié)符)即為該句型的最左素短語(yǔ)。,,(2) 語(yǔ)法樹法設(shè)句型為ω，先畫出對(duì)應(yīng)句型ω的語(yǔ)法樹，然后找出該語(yǔ)法樹中所有相鄰終結(jié)符之間的優(yōu)先關(guān)系。語(yǔ)法樹確定相鄰終結(jié)符之間優(yōu)先關(guān)系的原則如下：,,① 同層的優(yōu)先關(guān)系為“=· ”；

37、 ②不同層時(shí)，層次在下的優(yōu)先級(jí)高，層次在上的優(yōu)先級(jí)低； ③在句型ω兩側(cè)加上語(yǔ)句括號(hào)“#”，即#ω#，則有#?FIRSTVT（ω）和LASTVT（ω）?#。最后，按最左素短語(yǔ)必須具備的三個(gè)條件來(lái)確定最左素短語(yǔ)。,,F+T*i的語(yǔ)法樹及其優(yōu)先關(guān)系,求句型F+T*i的最左素短語(yǔ)。[解] 畫出對(duì)應(yīng)句型F+T*i的語(yǔ)法樹并根據(jù)語(yǔ)法樹確定相鄰終結(jié)符之間的優(yōu)先關(guān)系(見(jiàn)圖3–17)。,得到最左素短語(yǔ)為i,,該句型的最左直接短語(yǔ)(句柄)為F,

38、例,文法G[E] ：E ? T|E+T T ?F|T*F F ?i | (E)的句型E+T*F+i，求其含有的素短語(yǔ)、最左素短語(yǔ)（復(fù)習(xí)短語(yǔ)、直接短語(yǔ)和句柄）解：語(yǔ)法樹為,素短語(yǔ)為：T*F，i最左素短語(yǔ)為： T*F,例,算符優(yōu)先分析器,例：已知文法G[E] E→E+T∣T ?T→T*

39、F∣F F→(E)∣i和優(yōu)先關(guān)系，試給出輸入串i+i*i的算符優(yōu)先分析過(guò)程。[解] 其優(yōu)先關(guān)系表前已求出。,算符優(yōu)先分析過(guò)程,i+i*i算符優(yōu)先分析過(guò)程,,算符優(yōu)先歸約時(shí)i+i的語(yǔ)法樹,規(guī)范歸約時(shí)i+i的語(yǔ)法樹,由上例可知，算符優(yōu)先分析的歸約只關(guān)心句型中由左至右終結(jié)符序列的優(yōu)先關(guān)系，而不涉及終結(jié)符之間可能存在的非終結(jié)符，即實(shí)際上可認(rèn)為這些非終結(jié)符只是占位符。,算符優(yōu)先分析不考慮非終結(jié)符的形式(即認(rèn)為所有

40、非終結(jié)符都是一樣的)，即跳過(guò)了所有形如P→Q的單非終結(jié)符產(chǎn)生式(即右部?jī)H含一個(gè)非終結(jié)符的產(chǎn)生式)所對(duì)應(yīng)的歸約步驟。帶來(lái)的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：算符優(yōu)先分析比規(guī)范歸約要快得多；缺點(diǎn)：有可能把本來(lái)不成句子的輸入串也誤認(rèn)為是句子。（這種缺點(diǎn)可在技術(shù)上給予彌補(bǔ)）。,k=1; S[k]=‘#’;do{把下一個(gè)輸入符號(hào)讀進(jìn)a中；if (S[k]∈VT) j=k; else j=k?1; /* 任何兩終結(jié)符之間最多只

41、有一非終結(jié)符，故若S[k] ∈ VT則S[k?1]∈VT */while (S[j]?a){,算符優(yōu)先分析算法(P93 Pascal描述)C描述如下: 在算法中使用了一個(gè)符號(hào)棧S，用來(lái)存放終結(jié)符和非終結(jié)符,k代表符號(hào)棧S的使用深度：,\,do{ /*找出最左子串S[j]?S[j+1]…S[k]?a*/Q=S[j];if (S[j?1]∈VT) j=j?1;els

42、e j=j?2;}while (S[j] ? Q);把S[j+1]…S[k]歸約為某個(gè)N;k=j+1;S[k]=N; /*將歸約后的非終結(jié)符N置于原S[j+1]位置*/}if ((S[j]?a)││(S[j]=·a))/*如果棧頂S[j]?a或S[j]a則將a壓棧*/,{k=k+1;S[k]=a;}else error( );}while (a!=‘

43、#’); 此算法工作過(guò)程中若出現(xiàn)j減1后其值小于或等于0，則意味著輸入串有錯(cuò)。在正確的情況下，算法工作完畢時(shí)符號(hào)棧將呈現(xiàn)#S#。,優(yōu)先函數(shù),引入原因：用優(yōu)先關(guān)系表來(lái)表示每對(duì)終結(jié)符之間的優(yōu)先關(guān)系存儲(chǔ)量大、查找費(fèi)時(shí)。引入方法：把每個(gè)終結(jié)符對(duì)應(yīng)兩個(gè)函數(shù)f和g，值的大小反映其優(yōu)先關(guān)系，則終結(jié)符對(duì)a、b之間的優(yōu)先關(guān)系就轉(zhuǎn)換為兩個(gè)優(yōu)先函數(shù)f(a)與g(b)值的比較。定義兩個(gè)函數(shù)是因?yàn)榻K結(jié)對(duì)是有序的。 例如，既存在

44、著+?)又存在著)?+。 因此，對(duì)一個(gè)終結(jié)符a而言，它應(yīng)該有一個(gè)左優(yōu)先數(shù)f(a)和一個(gè)右優(yōu)先數(shù)g(a)，這樣就定義了終結(jié)符的一對(duì)函數(shù)。使用優(yōu)先函數(shù)有兩個(gè)明顯的好處：一是節(jié)省空間；二是便于進(jìn)行比較運(yùn)算。,如果根據(jù)一個(gè)文法的算符優(yōu)先關(guān)系表，使得文法中的每個(gè)終結(jié)符a和b滿足下述條件： (1) 如果存在a =· b，則有f(a)=g(b)； (2) 如果存在a?b，則有f(a)＞g(

45、b)； (3) 如果存在a?b，則有f(a)＜g(b)。 則稱f和g為優(yōu)先函數(shù)；其中 f稱為入棧優(yōu)先函數(shù)，g稱為比較優(yōu)先函數(shù)。注意：一個(gè)優(yōu)先關(guān)系表對(duì)應(yīng)的優(yōu)先函數(shù)f和g不是惟一的；只要存在一對(duì)，就存在無(wú)窮多對(duì)。也有許多優(yōu)先關(guān)系表不存在對(duì)應(yīng)的優(yōu)先函數(shù)。,優(yōu)先函數(shù)的定義,一個(gè)不存在優(yōu)先函數(shù)的優(yōu)先關(guān)系表。,在表中，假定存在f和g，則應(yīng)有：f(a)=g(a)； f(a)＞g(b)f(b)=g(a)；

46、 f(b)=g(b) 這將導(dǎo)致如下矛盾： f(a)＞g(b)=f(b)=g(a)=f(a),優(yōu)先函數(shù)的構(gòu)造,根據(jù)優(yōu)先關(guān)系表構(gòu)造優(yōu)先函數(shù)f和g的兩種方法： 1.關(guān)系圖法；2.由定義直接構(gòu)造。(1) 關(guān)系圖法① 對(duì)所有終結(jié)符a(包括“#”)，用有下腳標(biāo)的fa、ga為結(jié)點(diǎn)名，畫出全部n個(gè)終結(jié)符所對(duì)應(yīng)的2n個(gè)結(jié)點(diǎn)；② 若a?b或a =· b，則畫一條以fa到gb的有向邊

47、；若a?b或a =· b，則畫一條從gb到fa的有向邊；③ 對(duì)每個(gè)結(jié)點(diǎn)都賦予一個(gè)數(shù)，此數(shù)等于從該結(jié)點(diǎn)出發(fā)所能到達(dá)的結(jié)點(diǎn)(包括出發(fā)結(jié)點(diǎn)自身在內(nèi))的個(gè)數(shù)，賦給fa的數(shù)作為f(a)，賦給gb的數(shù)作為g(b)； ④ 檢查所構(gòu)造出來(lái)的函數(shù)f和g，看它們同原來(lái)的關(guān)系表是否有矛盾。如果沒(méi)有矛盾，則f和g就是所要的優(yōu)先函數(shù)；如果有矛盾，那么就不存在優(yōu)先函數(shù)。,(2) 由定義直接構(gòu)造 首先，對(duì)每個(gè)終結(jié)符a(包括“#

48、”)，令f(a)=g(a)=1(也可以是其它整數(shù))，則： ① 如果a?b而f(a)≤g(b)，則令f(a)=g(b)+1； ② 如果a?b而f(a)≥g(b)，則令g(b)=f(a)+1；③ 如果a=·b而f(a)≠g(b)，則令 f(a)=g(b)=max{f(a),g(b)}； ④重復(fù)①～③步直到過(guò)程收斂。 如果重復(fù)過(guò)程中有一個(gè)值大于2n，

49、則表明該算符優(yōu)先文法不存在優(yōu)先函數(shù)。,例:用關(guān)系圖法和直接定義法求出前例的優(yōu)先關(guān)系表所對(duì)應(yīng)的優(yōu)先函數(shù)(不含“#”)。[解] (1) 用關(guān)系圖法構(gòu)造的關(guān)系圖如圖所示。,4,優(yōu)先函數(shù)表,(2) 由定義直接計(jì)算出的優(yōu)先函數(shù)計(jì)算過(guò)程如表所示。,[例1] 設(shè)有文法G和輸入串$ G: S?aABe $: abbcde A ?Abc|b B ?

50、d 求其短語(yǔ)、直接短語(yǔ)、句柄和素短語(yǔ)。,解：畫其語(yǔ)法樹,短語(yǔ)：b,bbc,d,abbcde,直接短語(yǔ)：b,d,句柄：b,素短語(yǔ)：b,[例2] 對(duì)下列文法G: S’?#S# P ?S|i S ?D(R) D ?i R ?R; P|P 求出每個(gè)非終結(jié)符的FIRST

51、VT集和LASTVT集，并構(gòu)造算符優(yōu)先關(guān)系矩陣。解：文法G每個(gè)非終結(jié)符的FIRSTVT集合FIRSTVT(S’)= {#} FIRSTVT(P) ={i, ( }FIRSTVT(S)={ (, i } FIRSTVT(D) ={i }FIRSTVT(R) ={;, (, I } 文法G的每個(gè)非終結(jié)符的LASTVT集合LASTVT(S’) ={ #}

52、 LASTVT(P) = {i , ) }LASTVT(S) ={ ) } LASTVT(D) = {i }LASTVT(R) ={;, ) ,i },語(yǔ)法分析器的自動(dòng)產(chǎn)生,一個(gè)著名的編譯程序自動(dòng)產(chǎn)生工具YACC。,YACC程序的作用,小結(jié),自底向上語(yǔ)法分析——移進(jìn)-歸約分析規(guī)范歸約句柄、分析過(guò)程及程序算符優(yōu)先分析最左素短語(yǔ)、優(yōu)先分析表的構(gòu)造、分析過(guò)程及程序、優(yōu)先函數(shù)。自動(dòng)生成工具YACC