編譯原理張晶版第五章自底向上優(yōu)先分析法

1、第五章第五章 優(yōu)先分析法優(yōu)先分析法第五章第五章 優(yōu)先分析法（優(yōu)先分析法（1 1） 語法分析語法分析 推導(dǎo)：推導(dǎo)：自上而下的語法分析過程自上而下的語法分析過程預(yù)測分析程序，遞歸下降分析法（最左推導(dǎo)）預(yù)測分析程序，遞歸下降分析法（最左推導(dǎo)）注：要求文法是注：要求文法是LL(1)LL(1)文法文法 歸約：歸約：自下而上的語法分析過程自下而上的語法分析過程簡單優(yōu)先分析法，算符優(yōu)先分析法、簡單優(yōu)先分析法，算符優(yōu)先分析法、LRLR分析法分析法第五章第五章 優(yōu)先分析法（優(yōu)先分析法（2 2）一、自下而上的語法分析過程一、自下而上的語法分析過程 1.1.自下而上的語法分析過程思想自下而上的語法分析過程思想自下而

2、上的語法分析過程是一個最左歸約的過程，自下而上的語法分析過程是一個最左歸約的過程，從輸入串開始。朝著文法的開始符號進(jìn)行歸約，直從輸入串開始。朝著文法的開始符號進(jìn)行歸約，直到到達(dá)文法的開始符號為止的過程到到達(dá)文法的開始符號為止的過程注意：輸入串在這里是指從詞法分析器送來的單詞注意：輸入串在這里是指從詞法分析器送來的單詞符號組成的二元式的有限序列符號組成的二元式的有限序列 2.2.自下而上分析的自下而上分析的PDAPDA 第五章第五章 優(yōu)先分析法（優(yōu)先分析法（3 3）a+b# 語法分析程序語法分析程序 語法表語法表輸出帶輸出帶#工作方式：工作方式：“移進(jìn)移進(jìn)歸約歸約”方式方式即：自左至右把輸入串的

3、符號一個一個移進(jìn)棧，在移進(jìn)過程即：自左至右把輸入串的符號一個一個移進(jìn)棧，在移進(jìn)過程中不斷查看棧頂符號串，一旦形成某個句型的句柄時，就將此中不斷查看棧頂符號串，一旦形成某個句型的句柄時，就將此句柄用相應(yīng)的產(chǎn)生式左部替換（歸約），若再形成句柄，就繼句柄用相應(yīng)的產(chǎn)生式左部替換（歸約），若再形成句柄，就繼續(xù)替換，直到棧頂不再形成句柄為止，然后繼續(xù)移進(jìn)符號，重續(xù)替換，直到棧頂不再形成句柄為止，然后繼續(xù)移進(jìn)符號，重復(fù)上面的過程直到棧頂只剩下文法的開始符號，輸入串讀完為復(fù)上面的過程直到棧頂只剩下文法的開始符號，輸入串讀完為止，這樣就認(rèn)為識別了一個句子。止，這樣就認(rèn)為識別了一個句子。第五章第五章 優(yōu)先分析法（

4、優(yōu)先分析法（4 4）注：注：1 1）初態(tài)時棧內(nèi)僅有棧底符）初態(tài)時棧內(nèi)僅有棧底符“#”#”，讀頭指在最左邊的單詞，讀頭指在最左邊的單詞符號上符號上 . . 2 2）語法分析程序執(zhí)行的動作：）語法分析程序執(zhí)行的動作： a) a)移進(jìn)：讀入一個單詞并壓入棧內(nèi)，讀頭后移；移進(jìn)：讀入一個單詞并壓入棧內(nèi)，讀頭后移； b) b)歸約：檢查棧頂若干個符號能否進(jìn)行歸約，若能，就以歸約：檢查棧頂若干個符號能否進(jìn)行歸約，若能，就以產(chǎn)生式左部替代該符號串，同時輸出產(chǎn)生式編號產(chǎn)生式左部替代該符號串，同時輸出產(chǎn)生式編號. . c) c)識別成功：移進(jìn)識別成功：移進(jìn)歸約的結(jié)局是棧內(nèi)只剩下棧底符號和歸約的結(jié)局是棧內(nèi)只剩下棧底

5、符號和文法開始符號，讀頭也指向語句的結(jié)束符文法開始符號，讀頭也指向語句的結(jié)束符. . d) d)識別失敗識別失敗. .一、自下而上的語法分析過程一、自下而上的語法分析過程第五章第五章 優(yōu)先分析法（優(yōu)先分析法（5 5）例如：有文法如下：例如：有文法如下： (1) S aAcBe (2) A b (3) A Ab (4) B d問語句問語句abbcdeabbcde是不是該文法的合法語句是不是該文法的合法語句? ?一、自下而上的語法分析過程一、自下而上的語法分析過程第五章第五章 優(yōu)先分析法（優(yōu)先分析法（6 6）步驟步驟棧棧輸入串輸入串輸出串輸出串動作動作0#abbcde#1#abbcde#移進(jìn)移進(jìn)2

6、#abbcde#移進(jìn)移進(jìn)3#aAbcde#2歸約歸約4#aAbcde#移進(jìn)移進(jìn)5#aA cde#2,3歸約歸約6#aAcde#移進(jìn)移進(jìn)7#aAcde#移進(jìn)移進(jìn)8#aAcBe#2,3,4歸約歸約9#aAcBe#移進(jìn)移進(jìn)10#S#2,3,4,1歸約歸約11識別成功識別成功Sa A c B eA bdb第五章第五章 優(yōu)先分析法（優(yōu)先分析法（7 7）二、確定的自下而上語法分析二、確定的自下而上語法分析1.1.優(yōu)先分析器（優(yōu)先分析器（Precedence Parser)Precedence Parser) 簡單優(yōu)先分析法簡單優(yōu)先分析法 算符優(yōu)先分析法算符優(yōu)先分析法2.LR2.LR分析器分析器第五章第五章

7、 優(yōu)先分析法（優(yōu)先分析法（8 8）5.1 5.1 簡單優(yōu)先分析法簡單優(yōu)先分析法一、基本思想一、基本思想1.1.相鄰文法符號之間的優(yōu)先關(guān)系相鄰文法符號之間的優(yōu)先關(guān)系 在句型中，句柄內(nèi)各相鄰符號之間具有相同的優(yōu)先級，相同在句型中，句柄內(nèi)各相鄰符號之間具有相同的優(yōu)先級，相同優(yōu)先級用優(yōu)先級用“ “ ” 由于句柄要先歸約由于句柄要先歸約, ,所以規(guī)定句柄兩端符號的優(yōu)先級要比位所以規(guī)定句柄兩端符號的優(yōu)先級要比位于句柄之外的相鄰符號的優(yōu)先級高于句柄之外的相鄰符號的優(yōu)先級高, ,優(yōu)先級低于表示為優(yōu)先級低于表示為“”,”,優(yōu)先級高于表示為優(yōu)先級高于表示為“ ” 某句型中某句型中: :N N1 1.N.Ni-1i

8、-1 N Ni i N Nj j N Nj+1j+1.N Nn n. .第五章第五章 優(yōu)先分析法（優(yōu)先分析法（9 9）5.1 5.1 簡單優(yōu)先分析法簡單優(yōu)先分析法一、基本思想一、基本思想2 2 優(yōu)先分析法的基本思想優(yōu)先分析法的基本思想 句型中的句型中的N Ni i.N Nj j是句柄，語法分析程序可以通過尋找是句柄，語法分析程序可以通過尋找 N Ni-i-1 1N Ni i和和N Nj j N Nj+1j+1來確定句柄的頭尾，從而確定句柄進(jìn)行歸來確定句柄的頭尾，從而確定句柄進(jìn)行歸約。約。.第五章第五章 優(yōu)先分析法（優(yōu)先分析法（1010）5.1 5.1 簡單優(yōu)先分析法簡單優(yōu)先分析法二、簡單優(yōu)先文

9、法二、簡單優(yōu)先文法1. 定義：一個文法定義：一個文法G G，如果它不含，如果它不含e e產(chǎn)生式，也不含任何右部相產(chǎn)生式，也不含任何右部相同的不同產(chǎn)生式，并且它的任何符號對（同的不同產(chǎn)生式，并且它的任何符號對（X X，Y Y）X X，Y Y是終結(jié)符或非終結(jié)符是終結(jié)符或非終結(jié)符或者沒有關(guān)系，或者存在優(yōu)先級或者沒有關(guān)系，或者存在優(yōu)先級相同或低于、高于等關(guān)系之一，則這是一個簡單優(yōu)先文法相同或低于、高于等關(guān)系之一，則這是一個簡單優(yōu)先文法。 2. 優(yōu)先級別定義：優(yōu)先級別定義： X Y 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G G中含有形如中含有形如P .XY. X Y當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G G中含有形如中含有形如P .XQ.的產(chǎn)生

10、式的產(chǎn)生式,其中其中Q Y X Y,當(dāng)且僅當(dāng)文法當(dāng)且僅當(dāng)文法G G的終結(jié)符的終結(jié)符,G中中P QR,且且Q .X,Yfirst(R).第五章第五章 優(yōu)先分析法（優(yōu)先分析法（1111）對任何對任何X,X,若文法開始符號若文法開始符號S X,則則# X;若有若有S .X,則則X # 5.1 5.1 簡單優(yōu)先分析法簡單優(yōu)先分析法二、簡單優(yōu)先文法二、簡單優(yōu)先文法+三、簡單優(yōu)先分析的思想三、簡單優(yōu)先分析的思想1 1、簡單優(yōu)先矩陣：根據(jù)優(yōu)先關(guān)系的定義，、簡單優(yōu)先矩陣：根據(jù)優(yōu)先關(guān)系的定義，將簡單優(yōu)先文法中各文法符號之間的這種關(guān)將簡單優(yōu)先文法中各文法符號之間的這種關(guān)系用一個矩陣表示，稱作簡單優(yōu)先矩陣系用一個矩

11、陣表示，稱作簡單優(yōu)先矩陣第五章第五章 優(yōu)先分析法（優(yōu)先分析法（1212） PDA PDA讀入一個單詞后，比較棧頂符號和該單詞讀入一個單詞后，比較棧頂符號和該單詞 的優(yōu)先級，若棧頂符號優(yōu)先級低于該單詞，繼續(xù)讀入；若棧的優(yōu)先級，若棧頂符號優(yōu)先級低于該單詞，繼續(xù)讀入；若棧頂符號優(yōu)先級高于或等于讀入符號，則找句柄進(jìn)行歸約，找頂符號優(yōu)先級高于或等于讀入符號，則找句柄進(jìn)行歸約，找不到句柄就繼續(xù)讀入，直到最后棧內(nèi)只剩下開始符號，輸入不到句柄就繼續(xù)讀入，直到最后棧內(nèi)只剩下開始符號，輸入串讀到串讀到“#”#”為止，此時識別正確。為止，此時識別正確。四四、簡單優(yōu)先分析法的優(yōu)缺點(diǎn)簡單優(yōu)先分析法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：算法理解

12、簡單，技術(shù)簡單優(yōu)點(diǎn)：算法理解簡單，技術(shù)簡單缺點(diǎn)：適用范圍小，分析尺寸太大缺點(diǎn)：適用范圍小，分析尺寸太大5.1 5.1 簡單優(yōu)先分析法簡單優(yōu)先分析法第五章第五章 優(yōu)先分析法（優(yōu)先分析法（1313）5.2 5.2 算符優(yōu)先分析法算符優(yōu)先分析法一、一、什么是算符優(yōu)先分析法什么是算符優(yōu)先分析法1.1.算符優(yōu)先分析法：算符優(yōu)先分析法： 所謂算符優(yōu)先分析法是仿效四則運(yùn)算的計算過程而構(gòu)造的一所謂算符優(yōu)先分析法是仿效四則運(yùn)算的計算過程而構(gòu)造的一種語法分析方法種語法分析方法. .2.2.算符優(yōu)先分析法的特點(diǎn)：算符優(yōu)先分析法的特點(diǎn)： 簡單直觀，特別方便于表達(dá)式分析，易于手工實現(xiàn)，是自下簡單直觀，特別方便于表達(dá)式分

13、析，易于手工實現(xiàn)，是自下而上的歸約過程，但未必按照句柄歸約而上的歸約過程，但未必按照句柄歸約. .3.3.算符優(yōu)先分析法的關(guān)鍵：算符優(yōu)先分析法的關(guān)鍵： 規(guī)定算符（終結(jié)符）的優(yōu)先級及結(jié)合性質(zhì)規(guī)定算符（終結(jié)符）的優(yōu)先級及結(jié)合性質(zhì) 例如：例如：8+7-68+7-6* *5/35/3的運(yùn)算的運(yùn)算第五章第五章 優(yōu)先分析法（優(yōu)先分析法（1414）5.2 5.2 算符優(yōu)先分析法算符優(yōu)先分析法 例如：表達(dá)式文法：例如：表達(dá)式文法： E E+E|E-E|E*E|E/E|(E)|i 對這個二義文法可能會有好幾個規(guī)范推導(dǎo)和歸約，對這個二義文法可能會有好幾個規(guī)范推導(dǎo)和歸約，真正運(yùn)算時也有幾種不同結(jié)果，但若按算符優(yōu)先順

14、真正運(yùn)算時也有幾種不同結(jié)果，但若按算符優(yōu)先順序和結(jié)合規(guī)則的規(guī)定進(jìn)行歸約，句子的歸約過程就序和結(jié)合規(guī)則的規(guī)定進(jìn)行歸約，句子的歸約過程就是唯一的，運(yùn)算結(jié)果也唯一是唯一的，運(yùn)算結(jié)果也唯一. .注：對所有的終結(jié)符定義某種優(yōu)先關(guān)系，借助這種關(guān)注：對所有的終結(jié)符定義某種優(yōu)先關(guān)系，借助這種關(guān)系找出可歸約的串，進(jìn)行歸約，達(dá)到自下而上分析系找出可歸約的串，進(jìn)行歸約，達(dá)到自下而上分析的目的的目的. .第五章第五章 優(yōu)先分析法（優(yōu)先分析法（1515）如：如：i+i-i*(i+i) 歸約過程如下：歸約過程如下：1）i+i-i*(i+i) 設(shè)算數(shù)級別最高，最先歸約設(shè)算數(shù)級別最高，最先歸約2）E+i-i*(i+i)3)

15、E+E-i*(i+i) +,-同級，先歸約左邊同級，先歸約左邊“+”4）E-i*(i+i)5) E-E*(i+i) -, 不同級，先歸約右邊不同級，先歸約右邊“”6) E-E*(E+i)7) E-E*(E+E) 先算括號內(nèi)，再算括號外先算括號內(nèi)，再算括號外8) E-E*(E)9) E-E*E 先歸約先歸約“”，再歸約，再歸約“+”+”10) E-E11) E第五章第五章 優(yōu)先分析法（優(yōu)先分析法（1616）1 1、確定運(yùn)算符的優(yōu)先級、確定運(yùn)算符的優(yōu)先級 算符優(yōu)先分析法的關(guān)鍵是比較兩個相繼出現(xiàn)的終結(jié)算符優(yōu)先分析法的關(guān)鍵是比較兩個相繼出現(xiàn)的終結(jié)符的優(yōu)先級而決定應(yīng)采取的動作符的優(yōu)先級而決定應(yīng)采取的動作

16、 要完成運(yùn)算符間優(yōu)先級的比較，可以先定義各種可要完成運(yùn)算符間優(yōu)先級的比較，可以先定義各種可能相繼出現(xiàn)的運(yùn)算符的優(yōu)先級，并表示為矩陣的形能相繼出現(xiàn)的運(yùn)算符的優(yōu)先級，并表示為矩陣的形式，使得能夠在分析中通過查詢矩陣元素而得到算式，使得能夠在分析中通過查詢矩陣元素而得到算符之間的優(yōu)先關(guān)系符之間的優(yōu)先關(guān)系5.2 5.2 算符優(yōu)先分析法算符優(yōu)先分析法二、算符優(yōu)先分析技術(shù)的改進(jìn)二、算符優(yōu)先分析技術(shù)的改進(jìn)第五章第五章 優(yōu)先分析法（優(yōu)先分析法（1717）2.對于任何兩個可能相繼出現(xiàn)的終結(jié)符對于任何兩個可能相繼出現(xiàn)的終結(jié)符a,b，若具有以下形式若具有以下形式：“.ab.”, “.aQb.”,其中其中Q Q是某非

17、終結(jié)符，則是某非終結(jié)符，則a,ba,b之間的關(guān)系為之間的關(guān)系為：1） a b,a的優(yōu)先級低于的優(yōu)先級低于b2) a b,a的優(yōu)先級等于的優(yōu)先級等于b3) a b,a的優(yōu)先級高于的優(yōu)先級高于b4) 若若abab在任何情況下都不可能相繼出現(xiàn)，則在任何情況下都不可能相繼出現(xiàn)，則abab無關(guān)系無關(guān)系5.2 5.2 算符優(yōu)先分析法算符優(yōu)先分析法二、算符優(yōu)先分析技術(shù)的改進(jìn)二、算符優(yōu)先分析技術(shù)的改進(jìn).第五章第五章 優(yōu)先分析法（優(yōu)先分析法（1818）5.2 5.2 算符優(yōu)先分析法算符優(yōu)先分析法+（）i#+()i#右符右符左符左符.第五章第五章 優(yōu)先分析法（優(yōu)先分析法（1919） 注：）在此表中，包括，包括，注

18、：）在此表中，包括，包括，“”是一個特是一個特殊符號，用于語句的開始符號和結(jié)束符號殊符號，用于語句的開始符號和結(jié)束符號. . ）這張表滿足是通常數(shù)學(xué)上的習(xí)慣約定，值得注意的）這張表滿足是通常數(shù)學(xué)上的習(xí)慣約定，值得注意的是：是：1).1).運(yùn)算量運(yùn)算量i i的優(yōu)先級高于算符的優(yōu)先級高于算符2). 語句開始和結(jié)束符號語句開始和結(jié)束符號“”與終結(jié)符與終結(jié)符a a相繼出現(xiàn)時，應(yīng)該相繼出現(xiàn)時，應(yīng)該有有a a或或a #,a #,以此來保證語句內(nèi)先歸約以此來保證語句內(nèi)先歸約 （）表示括號是成對歸約的（）表示括號是成對歸約的 優(yōu)先關(guān)系和代數(shù)中的大于小于關(guān)系不同優(yōu)先關(guān)系和代數(shù)中的大于小于關(guān)系不同,a b,a b

19、并不意味著并不意味著b b a a終結(jié)符所處的左右位置很重要終結(jié)符所處的左右位置很重要. . 5.2 5.2 算符優(yōu)先分析法算符優(yōu)先分析法.第五章第五章 優(yōu)先分析法（優(yōu)先分析法（2020）3、直觀算符分析法直觀算符分析法5.2 5.2 算符優(yōu)先分析法算符優(yōu)先分析法二、算符優(yōu)先分析技術(shù)的改進(jìn)二、算符優(yōu)先分析技術(shù)的改進(jìn)a+b#直觀算符優(yōu)先法直觀算符優(yōu)先法 優(yōu)先表優(yōu)先表OPND操作數(shù)操作數(shù)Q Q#OPTR操作符操作符p p下推棧下推棧第五章第五章 優(yōu)先分析法（優(yōu)先分析法（2121）3、直觀算符分析法直觀算符分析法 1 1）直觀算符分析法使用兩個工作棧：一個算符棧）直觀算符分析法使用兩個工作棧：一個算

20、符棧（OPTROPTR）存放運(yùn)算符和括號，一個算量棧（）存放運(yùn)算符和括號，一個算量棧（OPND)OPND)用于存放操作數(shù)和運(yùn)算結(jié)果；用于存放操作數(shù)和運(yùn)算結(jié)果；OPTR的棧頂符號用的棧頂符號用Q表示，OPND的棧頂符號用的棧頂符號用p表示表示 2）初態(tài)時初態(tài)時，OPND為空為空，OPTR只有”#“ 直觀算符分析算法如下直觀算符分析算法如下：5.2 5.2 算符優(yōu)先分析法算符優(yōu)先分析法二、算符優(yōu)先分析技術(shù)的改進(jìn)二、算符優(yōu)先分析技術(shù)的改進(jìn)第五章第五章 優(yōu)先分析法（優(yōu)先分析法（2222）OPND=“”;OPND=“”;OPTR=“#”O(jiān)PTR=“#”flag=true;flag=true;advanc

21、e;/advance;/* *讀入一個單詞讀入一個單詞* */ /While flagWhile flagIf If Q Q=“#”and SYM=“#”then flag=false/=“#”and SYM=“#”then flag=false/* *成功成功* */ /else if else if Q Q=“(“and SYM=“)” then /=“(“and SYM=“)” then /* *匹配括號對匹配括號對* */ /OPTROPTR棧頂出棧；棧頂出棧；advanceadvanceelse if SYMelse if SYM是算量是算量 then /then /* *移進(jìn)算量移

22、進(jìn)算量* */ /第五章第五章 優(yōu)先分析法（優(yōu)先分析法（2323）SYMSYM入入OPNDOPND棧；棧；advanceadvance； else if Q SYM then /else if Q SYM then /* *移進(jìn)算符移進(jìn)算符* */ /SYMSYM入入OPTROPTR棧；棧；advanceadvance； else if Q SYM then /else if Q SYM then /* *歸約歸約* */ /OPNDOPND棧頂兩個元素棧頂兩個元素p p1,1,p p2 2彈出；彈出；彈出彈出OPTROPTR棧頂元素棧頂元素Q;Q;將將p p1Q1Qp p2 2的結(jié)果入的結(jié)果

23、入OPNDOPND棧；棧； else ERRORelse ERROR 第五章第五章 優(yōu)先分析法（優(yōu)先分析法（2424）4.此算法的優(yōu)缺點(diǎn)此算法的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)：優(yōu)點(diǎn)：1 1）簡單明了，易于手工實現(xiàn)，適于分析各種算術(shù)表）簡單明了，易于手工實現(xiàn)，適于分析各種算術(shù)表達(dá)式達(dá)式 2 2）使用此算法可以很方便地把表達(dá)式譯成目標(biāo)指令，）使用此算法可以很方便地把表達(dá)式譯成目標(biāo)指令，只要在歸約時把計算只要在歸約時把計算p1Qp2值改為生成相應(yīng)指令值改為生成相應(yīng)指令（Q,p p1,p p2,T)即可即可缺點(diǎn)：缺點(diǎn)：1 1）算法采用兩個棧，有時會把錯誤句子當(dāng)成合法句子；）算法采用兩個棧，有時會把錯誤句子當(dāng)成合法句子；

24、而且。它也無法指出輸入串出錯位置而且。它也無法指出輸入串出錯位置 2 2）對于含有單目正負(fù)號的算術(shù)表達(dá)式不好處理。因為）對于含有單目正負(fù)號的算術(shù)表達(dá)式不好處理。因為負(fù)號的優(yōu)先級高于加減法，低于乘除法，但負(fù)號的形式與減負(fù)號的優(yōu)先級高于加減法，低于乘除法，但負(fù)號的形式與減號相同，不容易識別。號相同，不容易識別。5.2 5.2 算符優(yōu)先分析法算符優(yōu)先分析法二、算符優(yōu)先分析技術(shù)的改進(jìn)二、算符優(yōu)先分析技術(shù)的改進(jìn)第五章第五章 優(yōu)先分析法優(yōu)先分析法第五章第五章 優(yōu)先分析法（優(yōu)先分析法（2525）1.算符文法的定義算符文法的定義給定上下文無關(guān)文法給定上下文無關(guān)文法G G，若，若G G中所有產(chǎn)生式右部都不中所有

25、產(chǎn)生式右部都不包含兩個相繼的非終結(jié)符，則包含兩個相繼的非終結(jié)符，則G G為算符文法為算符文法注：算符文法保證了兩個運(yùn)算符之間只有一個操作注：算符文法保證了兩個運(yùn)算符之間只有一個操作數(shù)數(shù)2.2.算符優(yōu)先文法定義：算符優(yōu)先文法定義： 設(shè)設(shè)G G是一個不含有空串產(chǎn)生式的算符文法，是一個不含有空串產(chǎn)生式的算符文法，并并設(shè)設(shè)a,bVT;P.Q,RVN 定義關(guān)系定義關(guān)系：5.2 5.2 算符優(yōu)先分析法算符優(yōu)先分析法三、算符優(yōu)先文法及優(yōu)先表的構(gòu)造三、算符優(yōu)先文法及優(yōu)先表的構(gòu)造第五章第五章 優(yōu)先分析法（優(yōu)先分析法（2626）2.算符優(yōu)先文法定義：算符優(yōu)先文法定義： a b 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G中含有形如中含有形

26、如P .ab.產(chǎn)生式產(chǎn)生式，或者或者P aQb.產(chǎn)生式產(chǎn)生式； a b 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G中含有形如中含有形如P .aR產(chǎn)生式產(chǎn)生式, ,其中其中R b.或或R Qb.; a b 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G中含有形如中含有形如 P Rb,產(chǎn)生式產(chǎn)生式, ,其中其中R .a, 或或R .aQ. 若若G G中任何終結(jié)符序偶（中任何終結(jié)符序偶（a,ba,b) )至多滿足上述關(guān)系之至多滿足上述關(guān)系之一，則稱一，則稱G G為算符優(yōu)先文法（為算符優(yōu)先文法（OPG)OPG)5.2 5.2 算符優(yōu)先分析法算符優(yōu)先分析法三、算符優(yōu)先文法及優(yōu)先表的構(gòu)造三、算符優(yōu)先文法及優(yōu)先表的構(gòu)造.+ + + + +第五章第五章 優(yōu)先分

27、析法（優(yōu)先分析法（2727）3.算符文法和算符優(yōu)先文法定義的意義算符文法和算符優(yōu)先文法定義的意義 這兩個定義相當(dāng)于對文法的句型和可歸約的短語做這兩個定義相當(dāng)于對文法的句型和可歸約的短語做了如下規(guī)定了如下規(guī)定：設(shè)設(shè)A1A2Ai-1AiAi+1An是文法是文法G的一個句型的一個句型. .1.若若AiVN，則則Ai-1, Ai-1VT,即不允許出現(xiàn)相繼兩個即不允許出現(xiàn)相繼兩個非終結(jié)符非終結(jié)符；2.若若B1B2Bm是當(dāng)前可歸約短語，并可歸約為是當(dāng)前可歸約短語，并可歸約為Ai，則則：5.2 5.2 算符優(yōu)先分析法算符優(yōu)先分析法三、算符優(yōu)先文法及優(yōu)先表的構(gòu)造三、算符優(yōu)先文法及優(yōu)先表的構(gòu)造第五章第五章 優(yōu)先

28、分析法（優(yōu)先分析法（2828）a)B1B2Bm中不能有相繼兩個非終結(jié)符且相鄰的終結(jié)符優(yōu)中不能有相繼兩個非終結(jié)符且相鄰的終結(jié)符優(yōu)先級全相等；先級全相等；b)對于對于B1B2Bm中首終結(jié)符中首終結(jié)符b有有Ai-1 bc)對于對于B1B2Bm中尾終結(jié)符中尾終結(jié)符b b有有b Ai+1注：實際上，可歸約短語是某產(chǎn)生式右部符號串，所以通注：實際上，可歸約短語是某產(chǎn)生式右部符號串，所以通過檢查過檢查G G的每一個產(chǎn)生式的每個候選式?？梢圆檎页鋈我獾拿恳粋€產(chǎn)生式的每個候選式?？梢圆檎页鋈我鈨?yōu)先級相同的終結(jié)符序偶，優(yōu)先級相同的終結(jié)符序偶，要找出所有滿足關(guān)系要找出所有滿足關(guān)系 和和 的終結(jié)符序偶，就要找出各非終

29、結(jié)符的終結(jié)符序偶，就要找出各非終結(jié)符P P的首終結(jié)符集和尾的首終結(jié)符集和尾終結(jié)符集。終結(jié)符集。第五章第五章 優(yōu)先分析法（優(yōu)先分析法（2929）4 .求各非終結(jié)符求各非終結(jié)符P P的首終結(jié)符集和尾終結(jié)符集的首終結(jié)符集和尾終結(jié)符集1 1）定義）定義： 首終結(jié)符集首終結(jié)符集FIRSTVT(P)=a|P a. 或或P Qa.,aVT;P,QVN 尾終結(jié)符集尾終結(jié)符集LASTVT(P)=a|P .a或或P .aQ,aVT;P,QVN 有了這兩個集合后，就可以通過檢查每個產(chǎn)生式的每個候選有了這兩個集合后，就可以通過檢查每個產(chǎn)生式的每個候選式，確定滿足關(guān)系式，確定滿足關(guān)系 和和 的所有終結(jié)符序偶的所有終結(jié)符

30、序偶5.2 5.2 算符優(yōu)先分析法算符優(yōu)先分析法三、算符優(yōu)先文法及優(yōu)先表的構(gòu)造三、算符優(yōu)先文法及優(yōu)先表的構(gòu)造+第五章第五章 優(yōu)先分析法（優(yōu)先分析法（3030）5.2 5.2 算符優(yōu)先分析法算符優(yōu)先分析法 例如：假定產(chǎn)生式右部有形如：例如：假定產(chǎn)生式右部有形如：. .aPaP串，則對串，則對于任何于任何bFIRSTVT(P),有有a b; 假定產(chǎn)生式右部有形如假定產(chǎn)生式右部有形如：.Pb.的串，則的串，則 對于任何對于任何aLASTVT(P),有a b;例：設(shè)文法例：設(shè)文法G G的產(chǎn)生式為的產(chǎn)生式為： S aAcBe A Ab|b B d 計算每個非終結(jié)符的計算每個非終結(jié)符的FIRSTVTFIR

31、STVT與與LASTVTLASTVT及所有終結(jié)符及所有終結(jié)符之間的關(guān)系之間的關(guān)系第五章第五章 優(yōu)先分析法（優(yōu)先分析法（3131）解解：FIRSTVT(S)=a LASTVT(S)=eFIRSTVT(S)=a LASTVT(S)=e FIRSTVT(A)=b LASTVT(A)=b FIRSTVT(A)=b LASTVT(A)=b FIRSTVT(B)=d LASTVT(B)=d FIRSTVT(B)=d LASTVT(B)=dabcdeabcde左右.第五章第五章 優(yōu)先分析法（優(yōu)先分析法（3232）5. .構(gòu)造算法構(gòu)造算法1 1）構(gòu)造集合）構(gòu)造集合FIRSTVT(P)的算法的算法a)方法方法1

32、 1： 根據(jù)根據(jù)FIRSTVT(P)FIRSTVT(P)的定義，按下面的規(guī)則來構(gòu)造：的定義，按下面的規(guī)則來構(gòu)造： (1)若有產(chǎn)生式若有產(chǎn)生式P a.或或P Qa.,則則aFIRSTVT(P) (2)若若aFIRSTVT(Q)，且有產(chǎn)生式且有產(chǎn)生式P Q則aFIRSTVT(P).注：規(guī)則注：規(guī)則1 1是求是求FIRSTONE aFIRSTONE a的關(guān)系；規(guī)則的關(guān)系；規(guī)則2 2是求是求P FIRSTP FIRST* *Q Q的的關(guān)系關(guān)系. .5.2 5.2 算符優(yōu)先分析法算符優(yōu)先分析法三、算符優(yōu)先文法及優(yōu)先表的構(gòu)造三、算符優(yōu)先文法及優(yōu)先表的構(gòu)造第五章第五章 優(yōu)先分析法（優(yōu)先分析法（3333）5.

33、5.構(gòu)造算法構(gòu)造算法1 1）構(gòu)造集合）構(gòu)造集合FIRSTVT(P)FIRSTVT(P)的算法的算法a)a)方法方法2 2： 在此算法中使用了兩個數(shù)據(jù)結(jié)構(gòu)在此算法中使用了兩個數(shù)據(jù)結(jié)構(gòu)一個是二維布爾矩陣一個是二維布爾矩陣F F，行稱為非終結(jié)符，列稱為終結(jié)符，行稱為非終結(jié)符，列稱為終結(jié)符a a；FP,aFP,a=true,=true,當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)aFIRSTVT(PaFIRSTVT(P););另一個是堆棧另一個是堆棧STACK;STACK;棧中動態(tài)存放曾在棧中動態(tài)存放曾在FP,aFP,a 中為真的序偶中為真的序偶（P,aP,a).). 算法如下：算法如下：5.2 5.2 算符優(yōu)先分析法算符優(yōu)先分

34、析法三、算符優(yōu)先文法及優(yōu)先表的構(gòu)造三、算符優(yōu)先文法及優(yōu)先表的構(gòu)造第五章第五章 優(yōu)先分析法（優(yōu)先分析法（3434） (1)初始化：將布爾矩陣初始化：將布爾矩陣F F中各元素置為假；棧清空；中各元素置為假；棧清空； (2) (2)按規(guī)則按規(guī)則1 1，查看產(chǎn)生式，對于形如，查看產(chǎn)生式，對于形如P a或或 P Qa.的產(chǎn)生式，置相應(yīng)的的產(chǎn)生式，置相應(yīng)的FP,a為真，并將序偶為真，并將序偶( (P,aP,a) )入棧入棧； (3)按規(guī)則按規(guī)則2 2，對棧施加如下操作：，對棧施加如下操作： 彈出棧頂序偶并記為（彈出棧頂序偶并記為（Q,aQ,a) )，查看所有產(chǎn)生式，看有無形如，查看所有產(chǎn)生式，看有無形如P

35、 Q.的產(chǎn)生式，若有，且的產(chǎn)生式，若有，且aFIRSTVT(P)()(即即FP,aFP,a 為假），則將為假），則將FP,aFP,a 置為真，并把（置為真，并把（P,aP,a) )入棧入棧； (4)重復(fù)步驟重復(fù)步驟3 3，直到棧空為止，直到?？諡橹? . 那么，在那么，在FP,aFP,a 中，凡是中，凡是“真真”的元素即屬于的元素即屬于P P的首終結(jié)符集的首終結(jié)符集第五章第五章 優(yōu)先分析法（優(yōu)先分析法（3535）5.構(gòu)造算法構(gòu)造算法1 1）構(gòu)造算符優(yōu)先表算法）構(gòu)造算符優(yōu)先表算法 算法過程算法過程： FOR 每條產(chǎn)生式每條產(chǎn)生式P X1X2.Xn DO FOR (i=1,i=n-1,i+) if

36、 Xi 和和Xi+1均為終結(jié)符均為終結(jié)符 then置置Xi Xi+1 if i=n-2 and Xi和和Xi+2均為終結(jié)符均為終結(jié)符and Xi+1為非非 終結(jié)符終結(jié)符 then置置Xi Xi+2 if Xi為終結(jié)符而為終結(jié)符而Xi+1為非終結(jié)符為非終結(jié)符 then5.2 5.2 算符優(yōu)先分析法算符優(yōu)先分析法三、算符優(yōu)先文法及優(yōu)先表的構(gòu)造三、算符優(yōu)先文法及優(yōu)先表的構(gòu)造.第五章第五章 優(yōu)先分析法（優(yōu)先分析法（3636） for FIRSTVT(Xfor FIRSTVT(Xi+1i+1) )中的每個中的每個a DOa DO 置置X Xi i a a if Xi if Xi為非終結(jié)符而為非終結(jié)符而X

37、 Xi+1i+1為終結(jié)符為終結(jié)符 thenthen for for LASTVT(XLASTVT(Xi i) )中的每個中的每個a DOa DO 置置a Xa Xi+1i+1 算符優(yōu)先文法的另一個定義：算符優(yōu)先文法的另一個定義：如果文法如果文法G G按此算法構(gòu)造出的優(yōu)先表沒有重按此算法構(gòu)造出的優(yōu)先表沒有重定義項，則文法定義項，則文法G G是一個算符優(yōu)先文法是一個算符優(yōu)先文法第五章第五章 優(yōu)先分析法（優(yōu)先分析法（3737）例：構(gòu)造下面文法的算符優(yōu)先表例：構(gòu)造下面文法的算符優(yōu)先表S if S if E Eb b then E else E E E+T|T then E else E E E+T|T

38、T TT T* *F|F F i F|F F i E Eb b b b 解：解：1 1）求各非終結(jié)符的首終結(jié)符和尾終結(jié)符集，為了考率語句的）求各非終結(jié)符的首終結(jié)符和尾終結(jié)符集，為了考率語句的開始和結(jié)束符號開始和結(jié)束符號“#”,#”,對文法拓廣對文法拓廣, ,加一個產(chǎn)生式加一個產(chǎn)生式 S #S#S #S#FIRSTVT(S)=if LASTVT(S)=else ,+,FIRSTVT(S)=if LASTVT(S)=else ,+,* *,i,iFIRSTVT(E)=FIRSTVT(E)=+, +,* *, ,i LASTVT(E)=+,i LASTVT(E)=+,* *,i,iFIRSTVT(T

39、)=FIRSTVT(T)=* *,i LASTVT(T)=,i LASTVT(T)=* *,i,iFIRSTVT(F)=i LASTVT(F)=iFIRSTVT(F)=i LASTVT(F)=iFIRSTVT(EFIRSTVT(Eb b)=b )=b LASTVT(ELASTVT(Eb b)=b)=b2)2)填寫算符優(yōu)先表填寫算符優(yōu)先表第五章第五章 優(yōu)先分析法（優(yōu)先分析法（3838）ifthenelse+*ib#ifthenelse+*ib#左左右右.第五章第五章 優(yōu)先分析法（優(yōu)先分析法（3939）5.2 5.2 算符優(yōu)先分析法算符優(yōu)先分析法四、算符優(yōu)先分析的若干問題四、算符優(yōu)先分析的若干問題

40、1.1.優(yōu)先表構(gòu)造算法的討論優(yōu)先表構(gòu)造算法的討論 構(gòu)造優(yōu)先表的算法僅僅反映文法符號間關(guān)系，并不構(gòu)造優(yōu)先表的算法僅僅反映文法符號間關(guān)系，并不反映附加條件，對二義性文法構(gòu)造算符優(yōu)先表?？煞从掣郊訔l件，對二義性文法構(gòu)造算符優(yōu)先表?？赡軙霈F(xiàn)多重定義項。能會出現(xiàn)多重定義項。2 .2 .非規(guī)范分析非規(guī)范分析 （1 1）. .規(guī)范規(guī)約規(guī)范規(guī)約 嚴(yán)格按照句柄進(jìn)行歸約，終結(jié)符和非終結(jié)符一起嚴(yán)格按照句柄進(jìn)行歸約，終結(jié)符和非終結(jié)符一起考慮，只要棧頂形成句柄。不管句柄是否包含終結(jié)考慮，只要棧頂形成句柄。不管句柄是否包含終結(jié)符都要進(jìn)行歸約。符都要進(jìn)行歸約。第五章第五章 優(yōu)先分析法（優(yōu)先分析法（4040）5.2 5.2

41、 算符優(yōu)先分析法算符優(yōu)先分析法 例如：考慮非二義的表達(dá)式文法例如：考慮非二義的表達(dá)式文法G(EG(E):E E+T|T T T*F|F F (E)|i識別句子識別句子i+ii+i* *i i的過程的過程 （1）規(guī)范歸約規(guī)范歸約 i+i*i#1.F+i*i# 2.T+i*i#3.E+i*i#4.E+F*i#5.E+T*i#6.E+T*F#7.E+T#8.E#第五章第五章 優(yōu)先分析法（優(yōu)先分析法（4141）2.非規(guī)范分析非規(guī)范分析(2).(2).算符優(yōu)先分析算符優(yōu)先分析 在算符優(yōu)先分析，僅研究終結(jié)符之間的優(yōu)先關(guān)系，而不考慮在算符優(yōu)先分析，僅研究終結(jié)符之間的優(yōu)先關(guān)系，而不考慮非終結(jié)符之間的優(yōu)先關(guān)系；

42、但句柄是由終結(jié)符和非終結(jié)符一非終結(jié)符之間的優(yōu)先關(guān)系；但句柄是由終結(jié)符和非終結(jié)符一起構(gòu)成的，所以算符優(yōu)先分析相對來說是非規(guī)范的分析。起構(gòu)成的，所以算符優(yōu)先分析相對來說是非規(guī)范的分析。 對上題的分析過程：對上題的分析過程： i+i*i# 1.E+i*i# 2.E+T*i# 3.E+T*F#5.2 5.2 算符優(yōu)先分析法算符優(yōu)先分析法四、算符優(yōu)先分析的若干問題四、算符優(yōu)先分析的若干問題4.E+T#5.E#第五章第五章 優(yōu)先分析法（優(yōu)先分析法（4242） 兩種分析的語法樹對比：兩種分析的語法樹對比：E EE + TE + TT TFiT * FFiiE EE + TiT * Fii第五章第五章 優(yōu)先分

43、析法（優(yōu)先分析法（4343）2.2.非規(guī)范分析非規(guī)范分析 (2).(2).算符優(yōu)先分析算符優(yōu)先分析 注：在算符優(yōu)先分析中，可歸約的短語不再稱為句柄，而稱注：在算符優(yōu)先分析中，可歸約的短語不再稱為句柄，而稱為最左素短語，素短語是指這樣一個短語，至少含有一個終為最左素短語，素短語是指這樣一個短語，至少含有一個終結(jié)符，且除它自身外不再包含其它素短語，最左邊的素短語結(jié)符，且除它自身外不再包含其它素短語，最左邊的素短語稱為最左素短語。稱為最左素短語。 例如：考慮非二義的表達(dá)式文法例如：考慮非二義的表達(dá)式文法G(E):G(E):E E+T|T T TE E+T|T T T* *F|F F (F|F F (

44、E)|iE)|i句型句型#T+T#T+T* *F+iF+i# #的素短語，為什么？的素短語，為什么？5.2 5.2 算符優(yōu)先分析法算符優(yōu)先分析法四、算符優(yōu)先分析的若干問題四、算符優(yōu)先分析的若干問題第五章第五章 優(yōu)先分析法（優(yōu)先分析法（4444）E EE + TE + TE + TE + TT T * * F FT TF Fi i由定義可知，素短語：由定義可知，素短語：T T* *F,IF,I 最左素短語：最左素短語：T T* *F F第五章第五章 優(yōu)先分析法（優(yōu)先分析法（4545）3.3.通用算符優(yōu)先分析通用算符優(yōu)先分析(1)(1)最左素短語的判斷最左素短語的判斷 假定文法的句型的一般形式為：

45、假定文法的句型的一般形式為：#N#N1 1a a1 1N N2 2a a2 2.N.Nn na an nN Nn+1n+1# #其中其中a ai i是終結(jié)符，是終結(jié)符，N Ni i是可有可無的非終結(jié)符，設(shè)最左素短語為是可有可無的非終結(jié)符，設(shè)最左素短語為a aj jN Ni ia ai iN Ni+1i+1, ,則必有：則必有： a aj-1j-1 a ai i a ai+1i+1 . . a ai i a ai+1i+1則，則， a aj jN Ni ia ai iN Ni+1i+1一定能歸約為某非終結(jié)符一定能歸約為某非終結(jié)符注意：在程序設(shè)計語言中會經(jīng)?？吹竭@種素短語注意：在程序設(shè)計語言中會經(jīng)?？吹竭@種素短語, ,當(dāng)棧頂形成當(dāng)棧頂形成某素短語時就可以進(jìn)行歸約，算符優(yōu)先分析中也要考慮到這某素短語時就可以進(jìn)行歸約，算符優(yōu)先分析中也要考慮到這種歸約種歸約5.2 5.2 算符優(yōu)先分析法算符優(yōu)先分析法四、算符優(yōu)先分析的若干問題四、算符優(yōu)先分析的若干問題.第五章第五章 優(yōu)先分析法（優(yōu)先分析法（4646）3.3.通用算符優(yōu)先分析通用算符優(yōu)先分析(2).(2).通用算符優(yōu)先分析算法通用算符優(yōu)先分析算法注：注：1).1).算法結(jié)束時，若棧內(nèi)只有算法結(jié)束時，若棧內(nèi)只有“#”“#”和某非終結(jié)符，讀頭下和某非終結(jié)符