語法分析-自下而上分析

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

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

3、進(jìn)行到讀到輸入串的右界符為止。最后，若棧中僅含有左界符號和識別符號，則表示分析成功，否則失敗。,歸約 （回顧）,推導(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)－歸約過程是自頂向下最右推導(dǎo)的逆過程，則稱為規(guī)范歸約。如對最右推導(dǎo)S ?αAδ ?αβδ來說，一定有A →β規(guī)則存在，將句型αβδ中的β用產(chǎn)生式的左部符號代替便得到新句型αAδ，這是一次規(guī)范歸約，恰好與規(guī)范推導(dǎo)相反。,5.1.1 規(guī)范歸約,*,對應(yīng)的規(guī)范歸約過程: abbcdeA→b aAbcdeA→Ab aAc

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

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

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

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

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

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

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

12、的分析（規(guī)范歸約）如下：步驟 符號棧 輸入串 動作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)典的自底向上分析法，簡單直觀，并被廣泛使 用，開始主要是對表達(dá)式的分析，現(xiàn)在已不限于此?？梢?

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

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

19、 則我們稱該文法為算符文法。,假定 a、b代表任意終結(jié)符；P、Q、R代表任意非終結(jié)符；‘…’代表有終結(jié)符和非終結(jié)符組成的任意序列，包括空字。 假定G是一個不含?-產(chǎn)生式的算符文法。對于任何一對終結(jié)符a、b，我們說： (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同時出現(xiàn)在同一產(chǎn)生式的右部，在子樹中是同一層葉子結(jié)點(diǎn)。aba在b的下一層子樹中，a至少歸約一次后產(chǎn)生的非終結(jié)符可與b同層。,如果一個算符文法G中的任何終結(jié)符對（a, b ）至多只滿足下述三關(guān)系之一： a=·b, ab 則稱G是一個算符優(yōu)先文法。優(yōu)先關(guān)系的特點(diǎn)：有序性。,算符優(yōu)先文法,試說明下述算術(shù)表達(dá)式文法G[E]是一個算符文法，但不是算符優(yōu)先文法。

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

22、[E]不是一個算符優(yōu)先文法。,算符優(yōu)先表的構(gòu)造,為了找出所有滿足關(guān)系””的終結(jié)符對，首先需要對文法的每個非終結(jié)符P構(gòu)造兩個集合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 } 有了這兩個集合后，就可以通過檢查每個產(chǎn)生式的候選式確定滿足關(guān)系的所有終結(jié)符對。

23、,注意：與前FRIST集相區(qū)別，前FIRST是句子的首個非終結(jié)符，而此處是所有可推導(dǎo)出的句型的首個非終結(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)見P91,其程序?qū)崿F(xiàn)采用棧，見P91 以G[E]: ?E→E+T∣T ?T→T*F∣F F→(E)∣i 為例理解程序。,檢查一個算符優(yōu)先文法G[S]的每個產(chǎn)生式的每個侯選式，找出所有一個算符優(yōu)先文法相鄰的終結(jié)符對的優(yōu)先關(guān)系。

25、 (1) 對形如P→…ab…或P→…aQb…的產(chǎn)生式， 有a =· b； (2) 對形如P→…aR…的產(chǎn)生式，有b∈FIRSTVT(R)， 則a?b； (3) 對形如P→…Rb…的產(chǎn)生式，有a∈LASTVT(R)， 則a?b。 (4)特別,語句括號“#”作為終結(jié)符對待，S是文法開始符號，則應(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ī)范歸約同）,用優(yōu)先關(guān)系構(gòu)造可歸約串,算符優(yōu)先文法句型的一般形式# N1a1N2a2…NnanNn+1# 每個ai都是終結(jié)符，Ni則是可有可無的

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

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

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

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

38、例,文法G[E] ：E ? T|E+T T ?F|T*F F ?i | (E)的句型E+T*F+i，求其含有的素短語、最左素短語（復(fù)習(xí)短語、直接短語和句柄）解：語法樹為,素短語為：T*F，i最左素短語為： 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)先分析過程。[解] 其優(yōu)先關(guān)系表前已求出。,算符優(yōu)先分析過程,i+i*i算符優(yōu)先分析過程,,算符優(yōu)先歸約時i+i的語法樹,規(guī)范歸約時i+i的語法樹,由上例可知，算符優(yōu)先分析的歸約只關(guān)心句型中由左至右終結(jié)符序列的優(yōu)先關(guān)系，而不涉及終結(jié)符之間可能存在的非終結(jié)符，即實(shí)際上可認(rèn)為這些非終結(jié)符只是占位符。,算符優(yōu)先分析不考慮非終結(jié)符的形式(即認(rèn)為所有

40、非終結(jié)符都是一樣的)，即跳過了所有形如P→Q的單非終結(jié)符產(chǎn)生式(即右部僅含一個非終結(jié)符的產(chǎn)生式)所對應(yīng)的歸約步驟。帶來的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：算符優(yōu)先分析比規(guī)范歸約要快得多；缺點(diǎn)：有可能把本來不成句子的輸入串也誤認(rèn)為是句子。（這種缺點(diǎn)可在技術(shù)上給予彌補(bǔ)）。,k=1; S[k]=‘#’;do{把下一個輸入符號讀進(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描述如下: 在算法中使用了一個符號棧S，用來存放終結(jié)符和非終結(jié)符,k代表符號棧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]歸約為某個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、#’); 此算法工作過程中若出現(xiàn)j減1后其值小于或等于0，則意味著輸入串有錯。在正確的情況下，算法工作完畢時符號棧將呈現(xiàn)#S#。,優(yōu)先函數(shù),引入原因：用優(yōu)先關(guān)系表來表示每對終結(jié)符之間的優(yōu)先關(guān)系存儲量大、查找費(fèi)時。引入方法：把每個終結(jié)符對應(yīng)兩個函數(shù)f和g，值的大小反映其優(yōu)先關(guān)系，則終結(jié)符對a、b之間的優(yōu)先關(guān)系就轉(zhuǎn)換為兩個優(yōu)先函數(shù)f(a)與g(b)值的比較。定義兩個函數(shù)是因?yàn)榻K結(jié)對是有序的。 例如，既存在

44、著+?)又存在著)?+。 因此，對一個終結(jié)符a而言，它應(yīng)該有一個左優(yōu)先數(shù)f(a)和一個右優(yōu)先數(shù)g(a)，這樣就定義了終結(jié)符的一對函數(shù)。使用優(yōu)先函數(shù)有兩個明顯的好處：一是節(jié)省空間；二是便于進(jìn)行比較運(yùn)算。,如果根據(jù)一個文法的算符優(yōu)先關(guān)系表，使得文法中的每個終結(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ù)。注意：一個優(yōu)先關(guān)系表對應(yīng)的優(yōu)先函數(shù)f和g不是惟一的；只要存在一對，就存在無窮多對。也有許多優(yōu)先關(guān)系表不存在對應(yīng)的優(yōu)先函數(shù)。,優(yōu)先函數(shù)的定義,一個不存在優(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)系圖法① 對所有終結(jié)符a(包括“#”)，用有下腳標(biāo)的fa、ga為結(jié)點(diǎn)名，畫出全部n個終結(jié)符所對應(yīng)的2n個結(jié)點(diǎn)；② 若a?b或a =· b，則畫一條以fa到gb的有向邊

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

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

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

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

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