編譯5語(yǔ)法—自下而上_zss_

1、編譯原理編譯原理(第三版第三版) 陳火旺等編著22022-3-20第五章第五章 語(yǔ)法分析語(yǔ)法分析自下而上分析自下而上分析n自上而下分析法自上而下分析法(Top-down)(Top-down)n自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)32022-3-20n語(yǔ)法分析的方法：語(yǔ)法分析的方法：自上而下分析法自上而下分析法(Top-down)(Top-down)n基本思想：它基本思想：它從文法的開(kāi)始符號(hào)出發(fā)從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)，反復(fù)使用各種產(chǎn)生式，尋找使用各種產(chǎn)生式，尋找 匹配匹配 的的推導(dǎo)推導(dǎo)。n遞歸下降分析法：對(duì)每一語(yǔ)法變量遞歸下降分析法：對(duì)每一語(yǔ)法變量( (非

2、終結(jié)非終結(jié)符符) )構(gòu)造一個(gè)相應(yīng)的子程序，每個(gè)子程序識(shí)構(gòu)造一個(gè)相應(yīng)的子程序，每個(gè)子程序識(shí)別一定的語(yǔ)法單位，通過(guò)子程序間的信息反別一定的語(yǔ)法單位，通過(guò)子程序間的信息反饋和聯(lián)合作用實(shí)現(xiàn)對(duì)輸入串的識(shí)別。饋和聯(lián)合作用實(shí)現(xiàn)對(duì)輸入串的識(shí)別。n預(yù)測(cè)分析程序預(yù)測(cè)分析程序F優(yōu)點(diǎn)：直觀、簡(jiǎn)單和宜于手工實(shí)現(xiàn)。優(yōu)點(diǎn)：直觀、簡(jiǎn)單和宜于手工實(shí)現(xiàn)。42022-3-20n語(yǔ)法分析的方法：語(yǔ)法分析的方法：自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)n基本思想：從輸入串開(kāi)始，逐步進(jìn)行基本思想：從輸入串開(kāi)始，逐步進(jìn)行“歸約歸約”，直到文法的開(kāi)始符號(hào)。即從樹(shù)末端開(kāi)始，構(gòu)造直到文法的開(kāi)始符號(hào)。即從樹(shù)末端開(kāi)始

3、，構(gòu)造語(yǔ)法樹(shù)。所謂語(yǔ)法樹(shù)。所謂歸約歸約，是指根據(jù)文法的產(chǎn)生式規(guī)，是指根據(jù)文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換成左部符號(hào)。則，把產(chǎn)生式的右部替換成左部符號(hào)。n算符優(yōu)先分析法：按照算符的優(yōu)先關(guān)系和結(jié)合算符優(yōu)先分析法：按照算符的優(yōu)先關(guān)系和結(jié)合性質(zhì)進(jìn)行語(yǔ)法分析。適合分析表達(dá)式。性質(zhì)進(jìn)行語(yǔ)法分析。適合分析表達(dá)式。nLRLR分析法：規(guī)范歸約分析法：規(guī)范歸約52022-3-2062022-3-20例：例： G(E)： E i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E Ei+ +* *EiiEEEE72022-3-205.1.1 5.1.1

4、歸約歸約n采用采用“移進(jìn)歸約移進(jìn)歸約”思想進(jìn)行自下而上分析。思想進(jìn)行自下而上分析。n基本思想：用一個(gè)寄存符號(hào)的后進(jìn)先出棧，基本思想：用一個(gè)寄存符號(hào)的后進(jìn)先出棧，把輸入符號(hào)一個(gè)一個(gè)地移進(jìn)到棧里，當(dāng)棧頂把輸入符號(hào)一個(gè)一個(gè)地移進(jìn)到棧里，當(dāng)棧頂形成某個(gè)產(chǎn)生式的候選式時(shí)，即把棧頂?shù)倪@形成某個(gè)產(chǎn)生式的候選式時(shí)，即把棧頂?shù)倪@一部分替換成一部分替換成( (歸約歸約為為) )該產(chǎn)生式的左部符該產(chǎn)生式的左部符號(hào)。號(hào)。82022-3-20n例：例：設(shè)文法設(shè)文法G(S)： (1) S aAcBe (2) A b (3) A Ab (4) B d試對(duì)試對(duì)abbcdeabbcde進(jìn)行進(jìn)行“移進(jìn)歸約移進(jìn)歸約”分析。分析。a

5、 bbcdeba bcdeAa bcdebAa cdeAa cdecAa dedcAa eabbcdeeBcAa S BcAa e92022-3-20步驟步驟: :1 12 23 34 45 56 67 78 89 91010動(dòng)作動(dòng)作: : 進(jìn)進(jìn)a a進(jìn)進(jìn)b b 歸歸(2)(2) 進(jìn)進(jìn)b b 歸歸(3)(3) 進(jìn)進(jìn)c c進(jìn)進(jìn)d d 歸歸(4)(4) 進(jìn)進(jìn)e e 歸歸(1)(1)e ed dB BB Bb bc cc cc cc cb bA AA AA AA AA AA AA Aa aa aa aa aa aa aa aa aa aS S102022-3-20bdbaceSABA 最終的最終的語(yǔ)

6、法分析樹(shù)語(yǔ)法分析樹(shù)自下而上分析過(guò)程：自下而上分析過(guò)程：邊輸入單詞符號(hào)，邊邊輸入單詞符號(hào)，邊歸約。歸約。 核心問(wèn)題核心問(wèn)題：如何如何識(shí)別可歸約串識(shí)別可歸約串112022-3-205.1.2 5.1.2 規(guī)范歸約規(guī)范歸約n定義：令定義：令G G是一個(gè)文法，是一個(gè)文法，S S是文法的開(kāi)始符是文法的開(kāi)始符號(hào)，假定號(hào)，假定是文法是文法G G的一個(gè)句型，如果有的一個(gè)句型，如果有 且且 AS*A則則 稱是句型稱是句型相對(duì)于非終結(jié)符相對(duì)于非終結(jié)符A A的的短語(yǔ)短語(yǔ)。 特別是，如果有特別是，如果有A A, ,則稱則稱 是句型是句型相對(duì)于規(guī)則相對(duì)于規(guī)則A A 的的直接短語(yǔ)直接短語(yǔ)。一個(gè)句型的。一個(gè)句型的最左直接短

7、語(yǔ)稱為該句型的最左直接短語(yǔ)稱為該句型的句柄句柄。三個(gè)重要三個(gè)重要概念概念122022-3-20考慮文法考慮文法G(E)： E T | E+T T F | T*F F (E) | i 以及句型以及句型 i1*i2+i3 ：E E+T E+F E+i3 T+i3 T*F+i3 T*i2+i3 F*i2+i3 i1*i2+i3n短語(yǔ)：短語(yǔ)： i1，i2，i3， i1*i2， i1*i2+i3n直接短語(yǔ)：直接短語(yǔ)： i1，i2，i3n句柄：句柄： i1132022-3-20n在一個(gè)句型對(duì)應(yīng)的在一個(gè)句型對(duì)應(yīng)的語(yǔ)法樹(shù)中，以語(yǔ)法樹(shù)中，以某非某非終結(jié)符終結(jié)符為根的兩代為根的兩代以上的子樹(shù)的以上的子樹(shù)的所有所有

8、末端結(jié)點(diǎn)從左到右末端結(jié)點(diǎn)從左到右排列就是相對(duì)于排列就是相對(duì)于該該非終結(jié)符非終結(jié)符的一個(gè)的一個(gè)短短語(yǔ)語(yǔ)，如果子樹(shù)只有如果子樹(shù)只有兩代，則該短語(yǔ)就兩代，則該短語(yǔ)就是是直接短語(yǔ)直接短語(yǔ)。EFFTTTi1+*EFi3i2142022-3-20n可用可用句柄句柄來(lái)對(duì)句子進(jìn)行歸約來(lái)對(duì)句子進(jìn)行歸約句型句型 歸約規(guī)則歸約規(guī)則abbcde (2) A baAbcde (3) A AbaAcde (4) B daAcBe (1) S aAcBe SbdbaceSABA152022-3-20bdbaceSABAdbaceSABAdaceSABaceSABS162022-3-20n定義定義：假定：假定 是文法是文法G

9、的一個(gè)句子，我們的一個(gè)句子，我們稱序列稱序列 n， n-1， ， 0 是是 的一個(gè)的一個(gè)規(guī)范歸約規(guī)范歸約，如果此序列滿足：，如果此序列滿足： 1 n= ； 2 0為文法的開(kāi)始符號(hào)，即為文法的開(kāi)始符號(hào)，即 0=S； 3 對(duì)任何對(duì)任何i，0 i n， i-1是從是從 i經(jīng)把經(jīng)把句句柄柄替換成為相應(yīng)產(chǎn)生式左部符號(hào)而得到替換成為相應(yīng)產(chǎn)生式左部符號(hào)而得到的。的。172022-3-20把上例倒過(guò)來(lái)寫(xiě)，則得到：把上例倒過(guò)來(lái)寫(xiě)，則得到：S S aAcBeaAcBe aAcde aAcde aAbcde aAbcde abbcde abbcde 顯然這是一個(gè)最右推導(dǎo)。顯然這是一個(gè)最右推導(dǎo)。規(guī)范歸約規(guī)范歸約是關(guān)于

10、是關(guān)于 的的一個(gè)一個(gè)最右推導(dǎo)最右推導(dǎo)的逆過(guò)程的逆過(guò)程最左歸約最左歸約 規(guī)范推導(dǎo)規(guī)范推導(dǎo)由規(guī)范推導(dǎo)推出的句型稱為由規(guī)范推導(dǎo)推出的句型稱為規(guī)范句型規(guī)范句型。182022-3-205.1.3 符號(hào)棧的使用和分析樹(shù)的表示符號(hào)棧的使用和分析樹(shù)的表示n棧是語(yǔ)法分析的一種基本數(shù)據(jù)結(jié)構(gòu)。棧是語(yǔ)法分析的一種基本數(shù)據(jù)結(jié)構(gòu)。 首先將首先將 # # 作為棧底符號(hào)作為棧底符號(hào)n考慮文法考慮文法G(E)： E T | E+T T F | T*F F (E) | i輸入串為輸入串為i1*i2+i3 ，分析步驟為：，分析步驟為：192022-3-20步驟步驟 符號(hào)棧符號(hào)棧輸入串輸入串動(dòng)作動(dòng)作0 #i1*i2+i3#預(yù)備預(yù)備1

11、 #i1*i2+i3#進(jìn)進(jìn)2 #F*i2+i3#歸，用歸，用Fi3 #T*i2+i3#歸，用歸，用TF4 #T*i2+i3#進(jìn)進(jìn)nG(E)： E T | E+T T F | T*F F (E) | i202022-3-20步驟步驟 符號(hào)棧符號(hào)棧輸入串輸入串動(dòng)作動(dòng)作4 #T*i2+i3#進(jìn)進(jìn)5 #T*i2+i3#進(jìn)進(jìn)6 #T*F+i3#歸，用歸，用Fi7 #T+i3#歸，用歸，用TT*F8 #E+i3# 歸，用歸，用ET9 #E+i3# 進(jìn)進(jìn)nG(E)： E T | E+T T F | T*F F (E) | i212022-3-20步驟步驟 符號(hào)棧符號(hào)棧輸入串輸入串動(dòng)作動(dòng)作9 #E+ i3#進(jìn)

12、進(jìn)10#E+i3#進(jìn)進(jìn)11#E+F#歸，用歸，用Fi12#E+T#歸，用歸，用TF13#E#歸，用歸，用EE+T14#E#接受接受nG(E)： E T | E+T T F | T*F F (E) | i222022-3-205.2 5.2 算符優(yōu)先分析算符優(yōu)先分析n四則運(yùn)算的優(yōu)先規(guī)則：四則運(yùn)算的優(yōu)先規(guī)則： 先乘除后加減，同級(jí)從左到右先乘除后加減，同級(jí)從左到右n考慮二義文法考慮二義文法G(E)：G(E)： E i| E+E|E-E|E*E|E/E|(E)n它的句子有幾種它的句子有幾種不同的規(guī)范規(guī)約不同的規(guī)范規(guī)約。n歸約即計(jì)算表達(dá)式的值。歸約順序不同，歸約即計(jì)算表達(dá)式的值。歸約順序不同，則計(jì)算的順

13、序也不同，結(jié)果也不一樣。則計(jì)算的順序也不同，結(jié)果也不一樣。n如果規(guī)定算符的優(yōu)先次序，并按這種規(guī)定如果規(guī)定算符的優(yōu)先次序，并按這種規(guī)定進(jìn)行歸約，則歸約過(guò)程是進(jìn)行歸約，則歸約過(guò)程是唯一唯一的。的。232022-3-20例如：句子例如：句子i+i-ii+i-i* *(i+i)(i+i)Ei( () )i* *EiEE+ +EEE-ii+ +EEE242022-3-20Ei( () )i* *EiEE+ +EEE-ii+ +EEE返回例如：句子例如：句子i+i-ii+i-i* *(i+i)(i+i)252022-3-20句子句子i+i-i*(i+i)的歸約過(guò)程是：的歸約過(guò)程是：(1) i+i-i*(i

14、+i)(2) E+i-i*(i+i)(3) 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)(8) E-E*(E)(9) E-E*E(10) E-E(11) E262022-3-20n起決定作用的是相鄰的兩個(gè)起決定作用的是相鄰的兩個(gè)算符算符之間的之間的優(yōu)優(yōu)先關(guān)系先關(guān)系。n所謂所謂算符優(yōu)先分析法算符優(yōu)先分析法就是定義算符之間的就是定義算符之間的某種優(yōu)先關(guān)系，借助于這種關(guān)系尋找某種優(yōu)先關(guān)系，借助于這種關(guān)系尋找“可歸可歸約串約串”和進(jìn)行歸約和進(jìn)行歸約。272022-3-20n首先必須定義任何兩個(gè)可能相繼出現(xiàn)的終結(jié)首先必須定

15、義任何兩個(gè)可能相繼出現(xiàn)的終結(jié)符符a a與與b b的優(yōu)先關(guān)系的優(yōu)先關(guān)系 三種關(guān)系三種關(guān)系a a b a b a的優(yōu)先級(jí)高于的優(yōu)先級(jí)高于b bn注意：與數(shù)學(xué)上的注意：與數(shù)學(xué)上的 “ ”、“= =” 不同不同a a a aa a b b 并不意味著并不意味著 b b a a282022-3-205.2.1 算符優(yōu)先文法及優(yōu)先表構(gòu)造算符優(yōu)先文法及優(yōu)先表構(gòu)造n一個(gè)文法，如果它的任一產(chǎn)生式的右部都一個(gè)文法，如果它的任一產(chǎn)生式的右部都不含兩個(gè)相繼不含兩個(gè)相繼(并列并列)的非終結(jié)符，即不含的非終結(jié)符，即不含如下形式的產(chǎn)生式右部：如下形式的產(chǎn)生式右部：QR 則我們稱該文法為則我們稱該文法為算符文法算符文法。n約

16、定：約定：a、b代表任意終結(jié)符；代表任意終結(jié)符；P、Q、R代表任意非終結(jié)符；代表任意非終結(jié)符；代表由終結(jié)符和非終結(jié)符組成的任意序代表由終結(jié)符和非終結(jié)符組成的任意序列，包括空字。列，包括空字。292022-3-20n假定假定G是一個(gè)不含是一個(gè)不含 -產(chǎn)生式的算符文法。產(chǎn)生式的算符文法。對(duì)于任何一對(duì)終結(jié)符對(duì)于任何一對(duì)終結(jié)符a、b，我們說(shuō)：，我們說(shuō)：1. a b當(dāng)且僅當(dāng)文法當(dāng)且僅當(dāng)文法G中含有形如中含有形如Pab或或PaQb的產(chǎn)生式；的產(chǎn)生式；n如果一個(gè)算符文法如果一個(gè)算符文法G中的任何終結(jié)符對(duì)中的任何終結(jié)符對(duì)(a，b)至多只滿足下述三關(guān)系之一：至多只滿足下述三關(guān)系之一：a b，a b 則稱則稱G是

17、一個(gè)是一個(gè)算符優(yōu)先文法算符優(yōu)先文法。2. a b 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G中含有形如中含有形如PRb的產(chǎn)生式，而的產(chǎn)生式，而 R a或或R aQ。302022-3-20n例例:考慮下面的文法考慮下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | in由第由第(4)條規(guī)則，有條規(guī)則，有 ( )；n由規(guī)則由規(guī)則EET和和TT*F， 有有 *；n由由(2) TT*F 和和(3) FP F ，可得，可得* +；n由由(3)FP F 和和 F P F，可得，可得 。n由由(4)P(E)和和 EE+TT+TT*F+TF*F+TPF*F+TiF

18、*F+T 有有 ( +、( *、( 和和( i。312022-3-20 優(yōu)先關(guān)系表優(yōu)先關(guān)系表 + * i ( ) #+ * i ( ) # G結(jié)論結(jié)論: G是算符優(yōu)先文法是算符優(yōu)先文法 優(yōu)先關(guān)系表優(yōu)先關(guān)系表 + * i ( ) #+ * i ( ) # 322022-3-20n從算符優(yōu)先文法從算符優(yōu)先文法G構(gòu)造優(yōu)先關(guān)系表的算法。構(gòu)造優(yōu)先關(guān)系表的算法。n通過(guò)檢查通過(guò)檢查G的每個(gè)產(chǎn)生式的每個(gè)候選式，可的每個(gè)產(chǎn)生式的每個(gè)候選式，可找出所有滿足找出所有滿足 a b的終結(jié)符對(duì)。的終結(jié)符對(duì)。2. a b當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G中含有形如中含有形如PRb的產(chǎn)生式，而的產(chǎn)生式，而 R a或或R aQ。n確定滿足關(guān)系

19、確定滿足關(guān)系的所有終結(jié)符對(duì)：的所有終結(jié)符對(duì)：1. a b當(dāng)且僅當(dāng)文法當(dāng)且僅當(dāng)文法G中含有形如中含有形如Pab或或PaQb的產(chǎn)生式；的產(chǎn)生式；332022-3-20n確定滿足關(guān)系確定滿足關(guān)系的所有終結(jié)符對(duì)：的所有終結(jié)符對(duì)：首先需要對(duì)首先需要對(duì)G的的每個(gè)非終結(jié)符每個(gè)非終結(jié)符P構(gòu)造兩個(gè)集合構(gòu)造兩個(gè)集合FIRSTVT(P)和和LASTVT(P)：,|)(NTVQVaQaPaPaPFIRSTVT而或 a b 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G中含有形如中含有形如PRb的產(chǎn)生式，而的產(chǎn)生式，而 R a或或R aQ。342022-3-20FIRSTVT Pa PaPQaaVQVTN( ) |,或而 ,|)(NTVQVaaQ

20、PaPaPLASTVT而或.,|=)(*TVaaaFIRST比較.,.|)(*TVaAaSaAFOLLOW比較352022-3-20q有了這兩個(gè)集合之后，就可以通過(guò)檢查每有了這兩個(gè)集合之后，就可以通過(guò)檢查每個(gè)產(chǎn)生式的候選式確定滿足關(guān)系個(gè)產(chǎn)生式的候選式確定滿足關(guān)系 的所有終結(jié)符對(duì)。的所有終結(jié)符對(duì)。假定有個(gè)產(chǎn)生式的一個(gè)候選形為假定有個(gè)產(chǎn)生式的一個(gè)候選形為aP 那么，對(duì)任何那么，對(duì)任何b FIRSTVT(P)，有，有 a b。362022-3-20n首先討論構(gòu)造集合首先討論構(gòu)造集合FIRSTVT(P)的算法。的算法。n按其定義，可用下面兩條規(guī)則來(lái)構(gòu)造集合按其定義，可用下面兩條規(guī)則來(lái)構(gòu)造集合FIRST

21、VT(P)：1. 若有產(chǎn)生式若有產(chǎn)生式Pa或或PQa，則，則a FIRSTVT(P)；2. 若若a FIRSTVT(Q)，且有產(chǎn)生式，且有產(chǎn)生式PQ，則則a FIRSTVT(P)。FIRSTVT Pa PaPQaaVQVTN( ) |,或而 372022-3-20n數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：布爾數(shù)組布爾數(shù)組 FP，a，使得，使得 FP，a為真的條件為真的條件是，當(dāng)且僅當(dāng)是，當(dāng)且僅當(dāng)a FIRSTVT(P)。開(kāi)始時(shí)，按上。開(kāi)始時(shí)，按上述的規(guī)則述的規(guī)則(1)對(duì)每個(gè)數(shù)組元素對(duì)每個(gè)數(shù)組元素FP，a賦初值。賦初值。棧棧STACK，把所有初值為真的數(shù)組元素，把所有初值為真的數(shù)組元素FP，a的符號(hào)對(duì)的符號(hào)對(duì)(P，

22、a)全都放在全都放在STACK之中。之中。382022-3-20n運(yùn)算：運(yùn)算：如果棧如果棧STACK不空，就將頂項(xiàng)彈出，記此不空，就將頂項(xiàng)彈出，記此項(xiàng)為項(xiàng)為(Q，a)。對(duì)于每個(gè)形如。對(duì)于每個(gè)形如PQ 的產(chǎn)生式，若的產(chǎn)生式，若FP，a為假，則變其值為真為假，則變其值為真且將且將(P，a)推進(jìn)推進(jìn)STACK棧。棧。上述過(guò)程必須一直重復(fù)，直至棧上述過(guò)程必須一直重復(fù)，直至棧STACK拆拆空為止?？諡橹?。392022-3-20n如果把這個(gè)算法稍為形式化一點(diǎn)，我們?nèi)绻堰@個(gè)算法稍為形式化一點(diǎn)，我們可得如下所示的一個(gè)程序可得如下所示的一個(gè)程序(包括一個(gè)過(guò)程包括一個(gè)過(guò)程和主程序和主程序)：PROCEDURE

23、INSERT(P，a)；IF NOT FP，a THENBEGIN FP，a:=TRUE； 把把(P，a)下推進(jìn)下推進(jìn)STACK棧棧 END；402022-3-20主程序：主程序：BEGIN FOR 每個(gè)非終結(jié)符每個(gè)非終結(jié)符P和終結(jié)符和終結(jié)符a DO FP，a:=FALSE； FOR 每個(gè)形如每個(gè)形如Pa或或PQa的產(chǎn)生式的產(chǎn)生式 DO INSERT(P，a)； WHILE STACK 非空非空 DOBEGIN 把把STACK的頂項(xiàng)，記為的頂項(xiàng)，記為(Q，a)，上托出去；，上托出去； FOR 每條形如每條形如PQ的產(chǎn)生式的產(chǎn)生式 DOINSERT(P，a)；END OF WHILE；END41

24、2022-3-20n這個(gè)算法的工作結(jié)果得到一個(gè)二維數(shù)組這個(gè)算法的工作結(jié)果得到一個(gè)二維數(shù)組F，從它可得任何非終結(jié)符從它可得任何非終結(jié)符P的的FIRSTVT。FIRSTVT(P)a | FP，a=TRUEn同理，可構(gòu)造計(jì)算同理，可構(gòu)造計(jì)算LASTVT的算法。的算法。422022-3-20n構(gòu)造集合構(gòu)造集合LASTVT(P)的算法。的算法。n按其定義，可用下面兩條規(guī)則來(lái)構(gòu)造集合按其定義，可用下面兩條規(guī)則來(lái)構(gòu)造集合LASTVT(P)：1. 若有產(chǎn)生式若有產(chǎn)生式P a或或P aQ，則，則a LASTVT(P)；2. 若若a LASTVT(Q)，且有產(chǎn)生式，且有產(chǎn)生式P Q ，則則a LASTVT(P)。

25、,|)(NTVQVaaQPaPaPLASTVT而或432022-3-20n使用每個(gè)非終結(jié)符使用每個(gè)非終結(jié)符P的的FIRSTVT(P)和和LASTVT(P)，就能夠構(gòu)造文法，就能夠構(gòu)造文法G的優(yōu)先的優(yōu)先表。表。 構(gòu)造優(yōu)先表的算法是：構(gòu)造優(yōu)先表的算法是：442022-3-20FOR 每條產(chǎn)生式每條產(chǎn)生式PX1X2Xn DO FOR 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為終

26、結(jié)符而為終結(jié)符而Xi+1為非終結(jié)符為非終結(jié)符 THENFOR FIRSTVT(Xi+1)中的每個(gè)中的每個(gè)a DO 置置 Xi Xi+1 END構(gòu)造優(yōu)先表的算法是：構(gòu)造優(yōu)先表的算法是：452022-3-20n例例: 考慮下面的文法考慮下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i 計(jì)算文法計(jì)算文法G的的FIRSTVT和和LASTVT462022-3-20+ * ()iE TFP(,)(,*,)(,)(,*,)(iPFIRSTVTiEFIRSTVTiFFIRSTVTiTFIRSTVT+ * ()iE TFP),)(),*

27、,)(),)(),*,)(iPLASTVTiELASTVTiFLASTVTiTLASTVT472022-3-205.2.2 算符優(yōu)先分析算法算符優(yōu)先分析算法n可歸約串，句型，短語(yǔ)，直接短語(yǔ)，句柄，可歸約串，句型，短語(yǔ)，直接短語(yǔ)，句柄，規(guī)范歸約。規(guī)范歸約。n一個(gè)文法一個(gè)文法G G的句型的的句型的素短語(yǔ)素短語(yǔ)是指這樣一個(gè)短是指這樣一個(gè)短語(yǔ)，它至少含有一個(gè)終結(jié)符，并且，除它語(yǔ)，它至少含有一個(gè)終結(jié)符，并且，除它自身之外不再含任何更小的素短語(yǔ)。自身之外不再含任何更小的素短語(yǔ)。n最左素短語(yǔ)最左素短語(yǔ)是指處于句型最左邊的那個(gè)素是指處于句型最左邊的那個(gè)素短語(yǔ)。短語(yǔ)。482022-3-20n考慮下面的文法考慮下

28、面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | iEEF+*TiFTFTP+ETP句型：句型：T+F*P+i短語(yǔ)：短語(yǔ)：直接短語(yǔ)：直接短語(yǔ)：句柄：句柄：素短語(yǔ)：素短語(yǔ)：最左素短語(yǔ)：最左素短語(yǔ)：, T+F*P+iT, F, P, F*P, iT+F*PT, F, P, iTF*P, iF*P注意注意T+F*P不是，？不是，？492022-3-20n算符優(yōu)先文法句型算符優(yōu)先文法句型(括在兩個(gè)之間括在兩個(gè)之間)的一般的一般形式寫(xiě)成：形式寫(xiě)成： #N1a1N2a2NnanNn+1#其中，每個(gè)其中，每個(gè)ai都是終結(jié)符，都是終結(jié)符，N

29、i是可有可無(wú)的非是可有可無(wú)的非終結(jié)符。終結(jié)符。n定理定理：一個(gè)算符優(yōu)先文法：一個(gè)算符優(yōu)先文法G的任何句型的最的任何句型的最左素短語(yǔ)是滿足如下條件的最左子串左素短語(yǔ)是滿足如下條件的最左子串 NjajNiaiNi+1， aj-1 ai+1算符在同一層次上算符在同一層次上502022-3-20n算符優(yōu)先分析算法算符優(yōu)先分析算法n使用一個(gè)符號(hào)棧使用一個(gè)符號(hào)棧S，用它寄存終結(jié)符和非終結(jié)，用它寄存終結(jié)符和非終結(jié)符，符，k代表符號(hào)棧代表符號(hào)棧S的使用深度。的使用深度。 512022-3-20k:=1;Sk:=#;REPEAT 把下一個(gè)輸入符號(hào)讀進(jìn)把下一個(gè)輸入符號(hào)讀進(jìn)a中；中； IF Sk VT THEN j

30、:=k ELSE j:=k-1;WHILE Sj a DOBEGIN REPEAT Q:=Sj; IF Sj-1 VT THEN j:=j-1 ELSE j:=j-2 UNTIL Sj Q; 把把Sj+1Sk歸約為某個(gè)歸約為某個(gè)N； k:=j+1; Sk:=N END OF WHILE; IF Sj a OR Sj = a THEN BEGIN k:=k+1;Sk:=a END ELSE ERROR /*調(diào)用出錯(cuò)診察程序調(diào)用出錯(cuò)診察程序*/ UNTIL a=#自左至右，終結(jié)符對(duì)終結(jié)符，非自左至右，終結(jié)符對(duì)終結(jié)符，非終結(jié)符對(duì)非終結(jié)符，而且對(duì)應(yīng)的終結(jié)符對(duì)非終結(jié)符，而且對(duì)應(yīng)的終結(jié)符相同。終結(jié)符相同。

31、 N X1 X2 Xk-j Sj+1 Sj+2 Sk522022-3-20n在算法的工作過(guò)程中，若出現(xiàn)在算法的工作過(guò)程中，若出現(xiàn) j 減減1后的后的值小于等于值小于等于0時(shí)，則意味著輸入串有錯(cuò)。時(shí)，則意味著輸入串有錯(cuò)。在正確的情況下，算法工作完畢時(shí)，符號(hào)在正確的情況下，算法工作完畢時(shí)，符號(hào)棧棧S應(yīng)呈現(xiàn)：應(yīng)呈現(xiàn)：# N #。n由于非終結(jié)符對(duì)歸約沒(méi)有影響，因此，非由于非終結(jié)符對(duì)歸約沒(méi)有影響，因此，非終結(jié)符根本可以不進(jìn)符號(hào)棧終結(jié)符根本可以不進(jìn)符號(hào)棧S。532022-3-20n算符優(yōu)先分析一般并不等價(jià)于規(guī)范歸約。算符優(yōu)先分析一般并不等價(jià)于規(guī)范歸約。EE+*iTP+iPiPiPEEF+*TiFTFTP+

32、ETiFPiPiPn考慮下面的文法考慮下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i的句子的句子i+i*i+i542022-3-20n算符優(yōu)先分析法特點(diǎn)：算符優(yōu)先分析法特點(diǎn)：優(yōu)點(diǎn)優(yōu)點(diǎn): : 簡(jiǎn)單，快速簡(jiǎn)單，快速缺點(diǎn)缺點(diǎn): : 可能錯(cuò)誤接受非法句子，能力有限可能錯(cuò)誤接受非法句子，能力有限. .n算符優(yōu)先分析法是一種廣為應(yīng)用、行之算符優(yōu)先分析法是一種廣為應(yīng)用、行之有效的方法。有效的方法。用于分析各類表達(dá)式用于分析各類表達(dá)式ALGOL 60552022-3-205.2.3 5.2.3 優(yōu)先函數(shù)優(yōu)先函數(shù)n把每個(gè)終結(jié)符把每個(gè)終結(jié)符 與兩個(gè)自然數(shù)與兩