編譯原理語法分析

1、第四章第四章語法分析語法分析貴州大學(xué)貴州大學(xué)計(jì)算機(jī)科學(xué)與信息學(xué)院計(jì)算機(jī)科學(xué)與信息學(xué)院第四章第四章 語法分析語法分析v本章內(nèi)容本章內(nèi)容自頂向下自頂向下分析和自底向上分析分析和自底向上分析圍繞語法分析器的自動(dòng)生成展開圍繞語法分析器的自動(dòng)生成展開第四章第四章 語法分析語法分析v4.1 4.1 語法分析器概述語法分析器概述v4.2 4.2 書寫文法書寫文法v4.3 4.3 自頂向下分析自頂向下分析v4.4 4.4 自底向上分析概述自底向上分析概述v4.5 4.5 算符優(yōu)先分析法算符優(yōu)先分析法v4.6 LR4.6 LR分析器分析器v4.7 4.7 二義文法的應(yīng)用二義文法的應(yīng)用語法分析器語法分析器中間代碼

2、中間代碼單詞符號單詞符號語法單位語法單位中間代碼中間代碼目標(biāo)代碼目標(biāo)代碼詞法分析器詞法分析器語義分析與中間代碼語義分析與中間代碼生成器生成器代碼優(yōu)化器代碼優(yōu)化器源程序源程序表表格格管管理理出出錯(cuò)錯(cuò)處處理理目標(biāo)代碼生成器目標(biāo)代碼生成器4.1 4.1 語法分析器概述語法分析器概述v 語法分析器是編譯器語法分析器是編譯器前端前端的重要組成部分，許多編的重要組成部分，許多編譯器，特別是由自動(dòng)生成工具構(gòu)造的編譯器，往往其譯器，特別是由自動(dòng)生成工具構(gòu)造的編譯器，往往其前端的中心部件就是語法分析器。前端的中心部件就是語法分析器。 語法分析器在編語法分析器在編譯器中的位置和作用如下：譯器中的位置和作用如下：詞

3、詞 法法分析器分析器記記 號號取下一個(gè)取下一個(gè)記號記號源程序源程序分析分析樹樹前端的前端的其余部分其余部分分析器分析器中間中間表示表示符號表符號表語法分析器概述語法分析器概述v語法分析器的主要作用有兩點(diǎn)：語法分析器的主要作用有兩點(diǎn)： 檢查詞法分析器輸出的單詞序列是否是源語言中檢查詞法分析器輸出的單詞序列是否是源語言中的句子，亦即是否符合源語言的語法規(guī)則的句子，亦即是否符合源語言的語法規(guī)則 檢查輸入中的語法（可能包括詞法）錯(cuò)誤，并調(diào)檢查輸入中的語法（可能包括詞法）錯(cuò)誤，并調(diào)用出錯(cuò)處理器進(jìn)行適當(dāng)處理用出錯(cuò)處理器進(jìn)行適當(dāng)處理v兩大類分析方法：兩大類分析方法：自頂向下分析自頂向下分析自底向上分析自底向

4、上分析存在主要問題存在主要問題: 左遞歸問題左遞歸問題 回溯問題回溯問題 主要方法主要方法: 遞歸子程序法遞歸子程序法 預(yù)測分析法預(yù)測分析法 (LL(1)自頂向下分析算法的基本思想為：自頂向下分析算法的基本思想為：有符號串有符號串S若若Z S 則則 S L(GZ) 否則否則 S L(GZ) Gz+從文法產(chǎn)生語言的角度從文法產(chǎn)生語言的角度ASaSbSAaaba aSbAS aabAS aabbaS aabbaa aAS SP: SaAS a A SbA SS ba句子句子：aabbaa自底向上分析算法的基本思想為：自底向上分析算法的基本思想為：+若若Z S 則則 S L(GZ) 否則否則 S L

5、(GZ) Gz存在主要問題存在主要問題: 句柄的識別問題句柄的識別問題主要方法主要方法: 算法優(yōu)先分析法算法優(yōu)先分析法 LR分析法分析法從自動(dòng)機(jī)識別語言的角從自動(dòng)機(jī)識別語言的角度度ASaSbSAaaba aAa aSbAa aSbbaa aabbaa aAS SP: SaAS a A SbA SS ba句子句子：aabbaa4.2 書寫文法書寫文法v定義定義：如果一個(gè)文法有非終結(jié)符：如果一個(gè)文法有非終結(jié)符A，對某個(gè)串，對某個(gè)串，存，存在推導(dǎo)在推導(dǎo)A +A ，則稱該文法是則稱該文法是左遞歸左遞歸的。形式為的。形式為AA的產(chǎn)生式引起的左遞歸稱為的產(chǎn)生式引起的左遞歸稱為直接左遞歸直接左遞歸。v直接左

6、遞歸直接左遞歸AAa |b 串的特點(diǎn)串的特點(diǎn) ba . . . av消除直接左遞歸消除直接左遞歸A b A A a A | 左遞歸變右左遞歸變右遞歸遞歸4.2.1 消除左遞歸消除左遞歸4.2.1 消除左遞歸消除左遞歸v一般而言，假定關(guān)于一般而言，假定關(guān)于P的全部產(chǎn)生式是的全部產(chǎn)生式是 PP 1 | P 2 | | P m | 1 | 2| n其中，每個(gè)其中，每個(gè) 都不等于都不等于 ，每個(gè)，每個(gè) 都不以都不以P開頭開頭 那么，消除那么，消除P的直接左遞歸就是把這些規(guī)則改的直接左遞歸就是把這些規(guī)則改寫成：寫成： P 1P | 2P | | nP P 1P | 2P | | mP | 左遞歸變右左遞

7、歸變右遞歸遞歸4.2.1 消除左遞歸消除左遞歸v例例 算術(shù)表達(dá)式文法算術(shù)表達(dá)式文法E E + T | T（ T + T . . . + T ）T T F | F（ F F . . . F ）F ( E ) | id消除左遞歸后文法消除左遞歸后文法 E TE E + TE | T FT T F T | F ( E ) | id4.2.1 消除左遞歸消除左遞歸v非直接左遞歸非直接左遞歸S Aa | b A Sd | v先變換成直接左遞歸先變換成直接左遞歸S Aa | bA Aad | bd | v再消除左遞歸再消除左遞歸S Aa | bA bd A | A A adA | 4.2.1 消除左遞歸消

8、除左遞歸v例例 考慮文法考慮文法G(S)SQc|cQRb|b (3.1)RSa|av令它的非終結(jié)符的排序?yàn)榱钏姆墙K結(jié)符的排序?yàn)镽、Q、S。v對于對于R，不存在直接左遞歸。，不存在直接左遞歸。v把把R代入到代入到Q的有關(guān)候選后，把的有關(guān)候選后，把Q的的規(guī)則變?yōu)橐?guī)則變?yōu)?QSab | ab | b4.2.1 消除左遞歸消除左遞歸v例例 考慮文法考慮文法G(S)SQc|cQRb|bRSa|av令它的非終結(jié)符的排序?yàn)榱钏姆墙K結(jié)符的排序?yàn)镽、Q、S。vQ的規(guī)則變?yōu)榈囊?guī)則變?yōu)?QSab | ab | bv現(xiàn)在的現(xiàn)在的Q不含直接左遞歸，把它代入到不含直接左遞歸，把它代入到S的有的有關(guān)候選后，關(guān)候選后，S

9、變成變成 SSabc | abc | bc | c4.2.1 消除左遞歸消除左遞歸v例例 考慮文法考慮文法G(S)SQc|cQRb|bRSa|avS變成變成 SSabc | abc | bc | cv消除消除S的直接左遞歸后：的直接左遞歸后：SabcS | bcS | cS S abcS | QSab |ab | bRSa|a4.2.1 消除左遞歸消除左遞歸v消除消除S的直接左遞歸后：的直接左遞歸后：SabcS | bcS | cS S abcS | QSab |ab | bRSa|av關(guān)于關(guān)于Q和和R的規(guī)則已是多余的，化簡為：的規(guī)則已是多余的，化簡為：SabcS | bcS | cS S a

10、bcS | (3.2)4.2.1 消除左遞歸消除左遞歸v注意，由于對非終結(jié)符排序的不同，最后所得的文注意，由于對非終結(jié)符排序的不同，最后所得的文法在形式上可能不一樣。但不難證明，它們都是等法在形式上可能不一樣。但不難證明，它們都是等價(jià)的。價(jià)的。v例如，若對文法例如，若對文法(3.1)的非終結(jié)符排序選為的非終結(jié)符排序選為S、Q、R，那么，最后所得的無左遞歸文法是：那么，最后所得的無左遞歸文法是：SQc | cQRb | bRbcaR | caR |a R (3.3)R bca R | v文法文法(3.2)和和(3.3)的等價(jià)性是顯然的。的等價(jià)性是顯然的。4.2.2 提左因子提左因子v有左因子的文

11、法有左因子的文法A 1 | 2v提左因子提左因子A A A 1 | 2 4.2.2 提左因子提左因子v例例 懸空懸空else的文法的文法 stmt if expr then stmt else stmt | if expr then stmt | otherv提左因子提左因子stmtif expr then stmt optional_else_part | otheroptional_else_part else stmt | 4.3 自頂向下分析自頂向下分析v自頂向下分析就是從文法的自頂向下分析就是從文法的開始符號開始符號出發(fā)，向下出發(fā)，向下推推導(dǎo)導(dǎo)，推出句子。，推出句子。帶帶“回溯回溯”

12、的分析方法的分析方法不帶回溯的遞歸子程序不帶回溯的遞歸子程序( (遞歸下降遞歸下降) )分析方法分析方法v自頂向下分析的主旨：對任何輸入串，試圖用一切自頂向下分析的主旨：對任何輸入串，試圖用一切可能的辦法，從文法開始符號可能的辦法，從文法開始符號( (根結(jié)點(diǎn)根結(jié)點(diǎn)) )出發(fā)，自上出發(fā)，自上而下、而下、從左到右從左到右地為輸入串建立一棵地為輸入串建立一棵分析樹分析樹?；蛘?。或者說，為輸入串尋找一個(gè)說，為輸入串尋找一個(gè)最左推導(dǎo)最左推導(dǎo)。v分析是一種試探的過程，是反復(fù)使用不同產(chǎn)生式謀分析是一種試探的過程，是反復(fù)使用不同產(chǎn)生式謀求與輸入序列匹配的過程。求與輸入序列匹配的過程。4.3.1 自頂向下分析的

13、一般方法自頂向下分析的一般方法v例例 假定有文法假定有文法G(S): (1) SxAy (2) A*|* 分析輸入串分析輸入串x*y(記為記為 )。Sx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*Sx*yIPAxySx*yIPAxySx*yIP分析成功！分析成功！4.3.1 自頂向下分析的一般方法自頂向下分析的一般方法v困難和缺點(diǎn)：困難和缺點(diǎn)：不能處理左遞歸（分析陷入無限循環(huán)）不能處理左遞歸（分析陷入無限循環(huán)）分析過程中，當(dāng)一個(gè)非終結(jié)符用某一個(gè)候選匹配分析過程中，當(dāng)一個(gè)非終結(jié)符用某一個(gè)候選匹配成功時(shí)，這種匹配可能是成功時(shí)，這種匹配可能是暫時(shí)暫時(shí)的的。出錯(cuò)時(shí)出錯(cuò)時(shí)

14、，不得，不得不不“回溯回溯”?；厮輰?dǎo)致語義工作推倒重來回溯導(dǎo)致語義工作推倒重來分析器難以報(bào)告輸入串出錯(cuò)的確切位置分析器難以報(bào)告輸入串出錯(cuò)的確切位置效率低，代價(jià)高，只有理論意義效率低，代價(jià)高，只有理論意義4.3.2 LL(1)文法文法v構(gòu)造不帶回溯的自上而下分析算法構(gòu)造不帶回溯的自上而下分析算法要消除文法的左遞歸性要消除文法的左遞歸性克服回溯克服回溯v為了消除回溯就必須保證：對文法的任何非為了消除回溯就必須保證：對文法的任何非終結(jié)符，當(dāng)要用它去匹配輸入串時(shí)，能夠根終結(jié)符，當(dāng)要用它去匹配輸入串時(shí)，能夠根據(jù)它所面臨的輸入符號準(zhǔn)確地指派它的一個(gè)據(jù)它所面臨的輸入符號準(zhǔn)確地指派它的一個(gè)候選去執(zhí)行任務(wù)，并且

15、此候選的工作結(jié)果應(yīng)候選去執(zhí)行任務(wù)，并且此候選的工作結(jié)果應(yīng)是確信無疑的。是確信無疑的。v例例 文法文法G(S): (1) SxAy (2) A*|*v例如例如, 對于下面文法，面臨對于下面文法，面臨a時(shí)不知用什么時(shí)不知用什么規(guī)則規(guī)則S A BA a b | B a CC 4.3.2 LL(1)文法文法v先定義兩個(gè)和文法有關(guān)的函數(shù)：先定義兩個(gè)和文法有關(guān)的函數(shù)：令令G是一個(gè)不含是一個(gè)不含左遞歸左遞歸的文法，對的文法，對G的所有非終結(jié)符的每個(gè)的所有非終結(jié)符的每個(gè)候選候選 定義它的終結(jié)首符集定義它的終結(jié)首符集FIRST( )為：為：特別是，若特別是，若 * ，則規(guī)定，則規(guī)定FIRST( )如果非終結(jié)符如

16、果非終結(jié)符A的所有候選首符集兩兩不相交，即的所有候選首符集兩兩不相交，即A的任何的任何兩個(gè)不同候選兩個(gè)不同候選 i和和 j FIRST( i)FIRST( j) 當(dāng)要求當(dāng)要求A匹配輸入串時(shí)，匹配輸入串時(shí)，A就能根據(jù)它所面臨的第一個(gè)輸入符就能根據(jù)它所面臨的第一個(gè)輸入符號號a，準(zhǔn)確地指派某一個(gè)候選前去執(zhí)行任務(wù)。這個(gè)候選就是，準(zhǔn)確地指派某一個(gè)候選前去執(zhí)行任務(wù)。這個(gè)候選就是那個(gè)終結(jié)首符集含那個(gè)終結(jié)首符集含a的的 。v經(jīng)過經(jīng)過反復(fù)提取左因子反復(fù)提取左因子，能夠把每個(gè)非終結(jié)符的所有候選首符集，能夠把每個(gè)非終結(jié)符的所有候選首符集變成為兩兩不相交。變成為兩兩不相交。.,|=)(*TVaaaFIRST問題：對文

17、法加什么樣的限制可以保證沒有回溯？問題：對文法加什么樣的限制可以保證沒有回溯？構(gòu)造構(gòu)造FIRST( )v對文法對文法G的任何符號串的任何符號串 =X1X2Xn構(gòu)造集合構(gòu)造集合FIRST( )。1. 置置FIRST( )FIRST(X1)；2. 若對任何若對任何1 j i-1，F(xiàn)IRST(Xj)，則把，則把FIRST(Xi)加至加至FIRST( )中；特別是，若所有中；特別是，若所有的的FIRST(Xj)均含有均含有 ，1 j n，則把，則把 也加至也加至FIRST( )中。顯然，若中。顯然，若 則則FIRST( ) 。4.3.2 LL(1)文法文法例：例： ETE E +TE | TFT T

18、*FT | F(E) | i 分析輸入串：分析輸入串：i + ii + i IPEnG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEnG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTnG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTinG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTinG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEF

19、Ti nG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEnG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEnG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEFTnG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEFTinG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEFTinG(E

20、): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEFTi nG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEFTi nG(E): ETE E +TE | TFT T *FT | F(E) | iE T+對于對于+ +的匹配只能依賴于在可能的推的匹配只能依賴于在可能的推導(dǎo)過程中導(dǎo)過程中TT的后面的字符的后面的字符4.3.2 LL(1)文法文法v若若FIRST ( i ) 或或 FIRST ( j )含含 ，還需增加條，還需增加條件件v假定假定S是文法是文法G的開始符號，對于的開

21、始符號，對于G的任何非的任何非終結(jié)符終結(jié)符A的的后繼符號后繼符號集合是所有在句型中直集合是所有在句型中直接出現(xiàn)在接出現(xiàn)在A后面的終結(jié)符的集合，即后面的終結(jié)符的集合，即 FOLLOW (A) = a | S * Aa，a VT 4.3.2 LL(1)文法文法v構(gòu)造構(gòu)造FOLLOW (B ) 的算法歸納為如下三條：的算法歸納為如下三條：對于文法的開始符號對于文法的開始符號S，令，令$屬于屬于FOLLOW (S) 如果文法中有形如如果文法中有形如AB的規(guī)則，則的規(guī)則，則FIRST()中中非非 元素元素屬于屬于FOLLOW (B ) 如果文法中有形如如果文法中有形如AB或或AB且且FIRST()含有含

22、有 元素這樣的規(guī)則，則元素這樣的規(guī)則，則FOLLOW (A) 的元素的元素屬于屬于FOLLOW (B ) v例例 E TE E + TE | T FT T FT | F (E) | idFIRST(E) = FIRST(T) = FIRST(F) = ( , id FIRST(E ) = +, FRIST(T ) = , FOLLOW(E) = ), $FOLLOW(E ) = FOLLOW(E) FOLLOW(T) = FIRST(E ) U FOLLOW(E) = +, ), $FOLLOW (T ) = FOLLOW(T) FOLLOW(F) = FRIST(T ) U FOLLOW(T

23、) = , +，), $ v練習(xí)：已知文法練習(xí)：已知文法GS: SeTRT T DR RdR D ab (1)FIRST(S)=_, FIRST(T)=_ FIRST(R)=_, FIRST(D)=_ a.d, b.a,b,d,e, c.a,b d.a,b,$ e.a,b, f.$ (2)FOLLOW(S)=_, FOLLOW(T)=_ FOLLOW(R)=_, FOLLOW(D)=_ a.d b.a,b c.a,b,$ d.$ e.d,$beacddce4.3.2 LL(1)文法文法v構(gòu)造不帶回溯的自上而下分析的文法條件構(gòu)造不帶回溯的自上而下分析的文法條件1. 文法不含左遞歸，文法不含左遞歸

24、，2. 對于文法中每一個(gè)非終結(jié)符對于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，若兩兩不相交。即，若 A 1| 2| n 則則 FIRST( i)FIRST( j) (i j)3. 對文法中的每個(gè)非終結(jié)符對文法中的每個(gè)非終結(jié)符A，若它存在某個(gè)候選首符集包，若它存在某個(gè)候選首符集包含含 ，則，則 FIRST( i)FOLLOW(A)= i=1,2,.,nv如果一個(gè)文法如果一個(gè)文法G滿足以上條件，則稱該文法滿足以上條件，則稱該文法G為為LL(1)文法文法。第一個(gè)第一個(gè)L代表從代表從左向右掃描左向右掃描輸入符號串，第二個(gè)輸入符號串，第二個(gè)L代表產(chǎn)生代表產(chǎn)生最

25、最左推導(dǎo)左推導(dǎo)，1代表在分析過程中執(zhí)行每步推導(dǎo)都要代表在分析過程中執(zhí)行每步推導(dǎo)都要向前查看一向前查看一個(gè)輸入符號個(gè)輸入符號 4.3.2 LL(1)文法文法v例例1：G1A: AaABe B BbbG1A不是不是LL(1)文法，因?yàn)槲姆ǎ驗(yàn)镕IRST(Bb) FIRST(b)=b v例例2：G2A: AaABeBa B dB G2A不是不是LL(1)文法，因?yàn)槲姆ǎ驗(yàn)镕IRST(aABe) FIRST(Ba)=a v例例3：G3S: SaAbDed A BSDe BSAccD D Se G3S不是不是LL(1)文法，因?yàn)槲姆ǎ驗(yàn)镕IRST(SAc) FOLLOW(B)=a,d 4.3.2

26、LL(1)文法文法vLL(1)LL(1)文法有一些明顯的性質(zhì)文法有一些明顯的性質(zhì)沒有公共左因子沒有公共左因子不含左遞歸不含左遞歸不是二義的不是二義的4.3.2 LL(1)文法文法v對于一個(gè)滿足上述條件的文法，可以對其輸入串進(jìn)對于一個(gè)滿足上述條件的文法，可以對其輸入串進(jìn)行有效的無回溯的自上而下分析。假設(shè)要用非終結(jié)行有效的無回溯的自上而下分析。假設(shè)要用非終結(jié)符符A進(jìn)行匹配，面臨的輸入符號為進(jìn)行匹配，面臨的輸入符號為a，A的所有產(chǎn)生的所有產(chǎn)生式為式為 A 1 | 2 | | n1. 若若a FIRST( i)，則指派，則指派 i執(zhí)行匹配任務(wù)；執(zhí)行匹配任務(wù)；2. 若若a不屬于任何一個(gè)候選首符集，則：不

27、屬于任何一個(gè)候選首符集，則： (1) 若若 屬于某個(gè)屬于某個(gè)FIRST( i )且且 a FOLLOW(A)， 則讓則讓A與與 自動(dòng)匹配。自動(dòng)匹配。 (2) 否則，否則，a的出現(xiàn)是一種語法錯(cuò)誤。的出現(xiàn)是一種語法錯(cuò)誤。4.3.3 遞歸的預(yù)測分析遞歸的預(yù)測分析v預(yù)測分析預(yù)測分析是指能根據(jù)當(dāng)前的輸入符號為非終結(jié)符確定用哪一是指能根據(jù)當(dāng)前的輸入符號為非終結(jié)符確定用哪一個(gè)選擇個(gè)選擇,LL(1),LL(1)文法滿足此要求文法滿足此要求v遞歸的預(yù)測分析是為遞歸的預(yù)測分析是為每一個(gè)非終結(jié)符每一個(gè)非終結(jié)符寫一個(gè)分析過程寫一個(gè)分析過程, ,這些這些過程可能是遞歸的過程可能是遞歸的v在處理輸入串時(shí)在處理輸入串時(shí),

28、,首先執(zhí)行的是對應(yīng)開始符號的過程首先執(zhí)行的是對應(yīng)開始符號的過程, ,然后根然后根據(jù)產(chǎn)生式右部出現(xiàn)的非終結(jié)符據(jù)產(chǎn)生式右部出現(xiàn)的非終結(jié)符, ,依次調(diào)用相應(yīng)的過程依次調(diào)用相應(yīng)的過程, ,這種逐這種逐步下降的過程調(diào)用序列隱含地定義了輸入串的分析樹步下降的過程調(diào)用序列隱含地定義了輸入串的分析樹例例：type simple | id | array simple of typesimple integer | char | num dotdot num4.3.3 遞歸的預(yù)測分析遞歸的預(yù)測分析一個(gè)輔助過程一個(gè)輔助過程procedure match (t : token);beginif lookahead

29、= t thenlookahead := nexttoken( )else error( )end;proccdure type;beginif lookahead in integer, char, num thensimple( )else if lookahead = then beginmatch (); match (id) endelse if lookahead = array then beginmatch (array); match ( ); simple( ); match ( ); match (of ); type( )endelse error( )end;type

30、 simple | id | array simple of typeprocedure simple;beginif lookahead = integer then match (integer)else if lookahead = char then match (char)else if lookahead = num then begin match (num); match (dotdot); match (num)endelse error( )end;simple integer | char | num dotdot num4.3.4 非遞歸的預(yù)測分析非遞歸的預(yù)測分析v如果

31、顯式地維持一個(gè)狀態(tài)棧如果顯式地維持一個(gè)狀態(tài)棧, ,而不是隱式地通過遞而不是隱式地通過遞歸調(diào)用歸調(diào)用, ,則可以構(gòu)造非遞歸的預(yù)測分析器則可以構(gòu)造非遞歸的預(yù)測分析器v預(yù)測分析的關(guān)鍵問題是決定取哪個(gè)產(chǎn)生式運(yùn)用于預(yù)測分析的關(guān)鍵問題是決定取哪個(gè)產(chǎn)生式運(yùn)用于非終結(jié)符（通過查分析表來決定產(chǎn)生式）非終結(jié)符（通過查分析表來決定產(chǎn)生式）v預(yù)測分析器組成：輸入緩沖區(qū)（存放要分析的串，預(yù)測分析器組成：輸入緩沖區(qū)（存放要分析的串，以以$ $作為結(jié)束標(biāo)記）、棧（存放文法符號，棧底符作為結(jié)束標(biāo)記）、棧（存放文法符號，棧底符號是號是$)$)、分析表（兩維數(shù)組、分析表（兩維數(shù)組MA,a,AMA,a,A是非終結(jié)符，是非終結(jié)符，a

32、 a是終結(jié)符或是終結(jié)符或$)$)和輸出流。和輸出流。4.3.4 非遞歸的預(yù)測分析非遞歸的預(yù)測分析a + b $輸入輸入預(yù)測分析程序預(yù)測分析程序分析表分析表M輸出輸出 XYZ$棧棧分析器工作過程分析器工作過程v預(yù)測分析程序根據(jù)現(xiàn)行棧頂符號預(yù)測分析程序根據(jù)現(xiàn)行棧頂符號X X和當(dāng)前輸入和當(dāng)前輸入符號符號a a，執(zhí)行下列四種動(dòng)作之一，執(zhí)行下列四種動(dòng)作之一: :1. 1. 若若X Xa a$，則宣布分析成功，停止分析。，則宣布分析成功，停止分析。2. 2. 若若X Xa a $，則把，則把X X從棧頂逐出，推進(jìn)輸入從棧頂逐出，推進(jìn)輸入指針，指向下一個(gè)輸入符號。指針，指向下一個(gè)輸入符號。3. 3. 若若X

33、 X是終結(jié)符但不是是終結(jié)符但不是a a，則分析器報(bào)告出錯(cuò)，調(diào)，則分析器報(bào)告出錯(cuò)，調(diào)用錯(cuò)誤恢復(fù)例程。用錯(cuò)誤恢復(fù)例程。分析器工作過程分析器工作過程4. 4. 若若X X是非終結(jié)符，程序訪問分析表是非終結(jié)符，程序訪問分析表若若MXMX，aa中存放著關(guān)于中存放著關(guān)于X X的一個(gè)產(chǎn)生式，把的一個(gè)產(chǎn)生式，把X X逐逐出出STACKSTACK棧頂，棧頂，把產(chǎn)生式的右部符號串按反序一把產(chǎn)生式的右部符號串按反序一一推進(jìn)一推進(jìn)STACKSTACK棧棧( (若右部符號為若右部符號為 ，則意味不推什，則意味不推什么東西進(jìn)棧么東西進(jìn)棧) )。若若MXMX，aa中存放著中存放著“出錯(cuò)標(biāo)志出錯(cuò)標(biāo)志”，則調(diào)用錯(cuò)誤，則調(diào)用錯(cuò)誤

34、恢復(fù)例程?；謴?fù)例程。分析表分析表非終非終結(jié)符結(jié)符輸輸 入入 符符 號號 id + . . .E E TE E E +TE T T FT T T T FT F F id 預(yù)測分析器接受輸入預(yù)測分析器接受輸入id + id * id的動(dòng)作的動(dòng)作 棧棧 輸輸 入入 輸輸 出出 $E id + id * id$ 非終非終結(jié)符結(jié)符輸輸 入入 符符 號號 id + E E TE E E +TE T T FT T T T FT F F id $E Tid + id * id$E TE $E T F id + id * id$id + id * id$ + id * id$ + id * id$ + id *

35、 id$ id * id$E T id$E T $E $E T +$E T T FT F idT E +TE 4.3.5 構(gòu)造預(yù)測分析表構(gòu)造預(yù)測分析表算法算法4.3(1)對文法的每個(gè)產(chǎn)生式對文法的每個(gè)產(chǎn)生式A ，執(zhí)行，執(zhí)行(2)和和(3)(2)對對FIRST( )的每個(gè)終結(jié)符的每個(gè)終結(jié)符a，把，把A 加入加入MA, a(3)如果如果 在在FIRST( )中，對中，對FOLLOW(A)的每的每個(gè)終結(jié)符個(gè)終結(jié)符b（包括（包括$）, 把把A 加入加入MA, b(4)M 的其它沒有定義的條目都是的其它沒有定義的條目都是error例例 E TE E + TE | T FT T FT | F (E) |

36、i FIRST(E) = FIRST(T) = FIRST(F) = ( , i FIRST(E ) = +, FRIST(T ) = , FOLLOW(E) = FOLLOW(E ) = ), $ FOLLOW(T) = FOLLOW (T ) = +, ), $ FOLLOW(F) = , +，), $ i+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)$4.3.5 構(gòu)造預(yù)測分析表構(gòu)造預(yù)測分析表v如果如果G是左遞歸或二義的，那么，是左遞歸或二義的，那么，M至少含至少含有一個(gè)有一個(gè)多重定義條目多重定義條目。因此，消除左遞歸和。

37、因此，消除左遞歸和提取左因子將有助于獲得無多重定義的分析提取左因子將有助于獲得無多重定義的分析表表M。v可以證明，一個(gè)文法可以證明，一個(gè)文法G的預(yù)測分析表的預(yù)測分析表M不含不含多重定義條目，當(dāng)且僅當(dāng)該文法為多重定義條目，當(dāng)且僅當(dāng)該文法為LL(1)的。的。G(S):S iCtS | iCtSeS | aC b提取左因子之后，改寫成：提取左因子之后，改寫成：G(S):S iCtSS | aS eS | C babeit#SSaSiCtSS S S S eSS CCbF (E)最近匹配原則最近匹配原則 FIRST(S)=i,a FIRST(S)=e, FIRST(C)=bFOLLOW(S)=e,$

38、FOLLOW(S)=e,$FOLLOW(C)=t$4.3.6 預(yù)測分析的錯(cuò)誤恢復(fù)預(yù)測分析的錯(cuò)誤恢復(fù)v程序可能的錯(cuò)誤程序可能的錯(cuò)誤: : 詞法錯(cuò)誤，如標(biāo)識符、關(guān)鍵字或算符的拼寫錯(cuò)詞法錯(cuò)誤，如標(biāo)識符、關(guān)鍵字或算符的拼寫錯(cuò) 語法錯(cuò)誤，如算術(shù)表達(dá)式的括號不配對語法錯(cuò)誤，如算術(shù)表達(dá)式的括號不配對 語義錯(cuò)誤，如算符作用于不相容的運(yùn)算對象語義錯(cuò)誤，如算符作用于不相容的運(yùn)算對象 邏輯錯(cuò)誤，如無窮的遞歸調(diào)用邏輯錯(cuò)誤，如無窮的遞歸調(diào)用v大多數(shù)錯(cuò)誤的診斷和恢復(fù)集中在語法分析階段。一個(gè)大多數(shù)錯(cuò)誤的診斷和恢復(fù)集中在語法分析階段。一個(gè)原因是大多數(shù)錯(cuò)誤是語法錯(cuò)誤，另一個(gè)原因是語法分原因是大多數(shù)錯(cuò)誤是語法錯(cuò)誤，另一個(gè)原因是語

39、法分析方法的準(zhǔn)確性，它們能以非常有效的方法診斷語法析方法的準(zhǔn)確性，它們能以非常有效的方法診斷語法錯(cuò)誤。錯(cuò)誤。v在編譯的時(shí)侯，想要準(zhǔn)確診斷語義或邏輯錯(cuò)誤有時(shí)是在編譯的時(shí)侯，想要準(zhǔn)確診斷語義或邏輯錯(cuò)誤有時(shí)是很困難的很困難的4.3.6 預(yù)測分析的錯(cuò)誤恢復(fù)預(yù)測分析的錯(cuò)誤恢復(fù)v分析器對錯(cuò)誤處理的基本目標(biāo)分析器對錯(cuò)誤處理的基本目標(biāo)清楚而準(zhǔn)確地報(bào)告錯(cuò)誤的出現(xiàn)清楚而準(zhǔn)確地報(bào)告錯(cuò)誤的出現(xiàn)迅速地從每個(gè)錯(cuò)誤中恢復(fù)過來，以便診斷后面迅速地從每個(gè)錯(cuò)誤中恢復(fù)過來，以便診斷后面的錯(cuò)誤，并盡量少出現(xiàn)偽錯(cuò)誤的錯(cuò)誤，并盡量少出現(xiàn)偽錯(cuò)誤它不應(yīng)該使正確程序的處理速度降低太多它不應(yīng)該使正確程序的處理速度降低太多v非遞歸預(yù)測分析在什么場

40、合下發(fā)現(xiàn)錯(cuò)誤非遞歸預(yù)測分析在什么場合下發(fā)現(xiàn)錯(cuò)誤棧頂?shù)慕K結(jié)符和下一個(gè)輸入符號不匹配棧頂?shù)慕K結(jié)符和下一個(gè)輸入符號不匹配棧頂是非終結(jié)符棧頂是非終結(jié)符A A，輸入符號是，輸入符號是a a，而，而M M A A , , a a 是空白是空白4.3.6 預(yù)測分析的錯(cuò)誤恢復(fù)預(yù)測分析的錯(cuò)誤恢復(fù)v非遞歸預(yù)測分析：采用緊急方式的錯(cuò)誤恢復(fù)非遞歸預(yù)測分析：采用緊急方式的錯(cuò)誤恢復(fù) 發(fā)現(xiàn)錯(cuò)誤時(shí)，分析器每次拋棄一個(gè)輸入記號，直發(fā)現(xiàn)錯(cuò)誤時(shí)，分析器每次拋棄一個(gè)輸入記號，直到輸入記號屬于某個(gè)指定的到輸入記號屬于某個(gè)指定的同步記號同步記號集合為止集合為止v例：下述兩條是有語法錯(cuò)誤的語句，其中第一條賦例：下述兩條是有語法錯(cuò)誤的語句，

41、其中第一條賦值句結(jié)束時(shí)忘記加分號，采用緊急恢復(fù)方式的可能值句結(jié)束時(shí)忘記加分號，采用緊急恢復(fù)方式的可能結(jié)果如下所示。結(jié)果如下所示。 x := a + b y := c + d;緊急方式：緊急方式： x := a + b + d; - 丟棄丟棄b之后的若干記號，之后的若干記號，直到遇到直到遇到同步記號同步記號+為止。為止。4.3.6 預(yù)測分析的錯(cuò)誤恢復(fù)預(yù)測分析的錯(cuò)誤恢復(fù)v同步記號一般是定界符，如分號或同步記號一般是定界符，如分號或endend等。等。v緊急方式的錯(cuò)誤恢復(fù)的效果依賴于同步記號緊急方式的錯(cuò)誤恢復(fù)的效果依賴于同步記號集合的選擇：集合的選擇：把把FOLLOW(FOLLOW(A A) )的所

42、有終結(jié)符放入非終結(jié)符的所有終結(jié)符放入非終結(jié)符A A的同步的同步記號集合記號集合if if expr expr thenthen（thenthen是是exprexpr的一個(gè)同步記號）的一個(gè)同步記號） 把高層結(jié)構(gòu)的開始符號加到低層結(jié)構(gòu)的同步記號把高層結(jié)構(gòu)的開始符號加到低層結(jié)構(gòu)的同步記號集合中集合中a a := := exprexpr ; if ; if （語句的開始符號作為表達(dá)式的同步符號，以免遺（語句的開始符號作為表達(dá)式的同步符號，以免遺漏分號時(shí)忽略漏分號時(shí)忽略ifif語句等一大段程序）語句等一大段程序） 把把FIRST(FIRST(A A) )的終結(jié)符加入的終結(jié)符加入A A的同步記號集合的同步

43、記號集合a a := := exprexpr ; , if ; , if （語句的開始符號作為語句的同步符號，以免多（語句的開始符號作為語句的同步符號，以免多出一個(gè)逗號時(shí)會把出一個(gè)逗號時(shí)會把ifif語句忽略了）語句忽略了）錯(cuò)誤處理錯(cuò)誤處理 如果非終結(jié)符可以產(chǎn)生空串，若出錯(cuò)時(shí)棧頂如果非終結(jié)符可以產(chǎn)生空串，若出錯(cuò)時(shí)棧頂是這樣的非終結(jié)符，則可以使用產(chǎn)生空串的是這樣的非終結(jié)符，則可以使用產(chǎn)生空串的產(chǎn)生式產(chǎn)生式錯(cuò)誤處理錯(cuò)誤處理v棧頂為棧頂為T ，面臨，面臨id時(shí)出錯(cuò)時(shí)出錯(cuò)非終非終結(jié)符結(jié)符 輸輸 入入 符符 號號 id+ . . .EETE E E +TE TTFT T 出錯(cuò)出錯(cuò)T T FT . . .

44、錯(cuò)誤處理錯(cuò)誤處理vT 可以產(chǎn)生空串，報(bào)錯(cuò)并用可以產(chǎn)生空串，報(bào)錯(cuò)并用T 非終非終結(jié)符結(jié)符 輸輸 入入 符符 號號 id+ . . .EETE E E +TE TTFT T 報(bào)錯(cuò)，用報(bào)錯(cuò)，用T T T FT . . . 錯(cuò)誤處理錯(cuò)誤處理v如果終結(jié)符在棧頂而不能匹配，彈出如果終結(jié)符在棧頂而不能匹配，彈出此終結(jié)符此終結(jié)符 例例 E TE E + TE | T FT T FT | F (E) | id FOLLOW(E) = FOLLOW(E ) = ), $ FOLLOW(T) = FOLLOW (T ) = +, ), $ FOLLOW(F) = , +，), $ 注：注：synchsynch用來指

45、示從非終結(jié)符的用來指示從非終結(jié)符的FOLLOWFOLLOW集合中得到集合中得到的同步記號。的同步記號。i+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)synchsynchsynchsynchsynchsynchsynchsynchsynch$4.3.6 預(yù)測分析的錯(cuò)誤恢復(fù)預(yù)測分析的錯(cuò)誤恢復(fù)v如果分析器查找條目如果分析器查找條目MA,aMA,a并發(fā)現(xiàn)它是空的，并發(fā)現(xiàn)它是空的，則跳過輸入符號則跳過輸入符號a a；如果條目是；如果條目是synchsynch，則調(diào)，則調(diào)用同步過程并把棧頂?shù)姆墙K結(jié)符彈出，恢復(fù)用同步過程并把棧頂?shù)姆墙K結(jié)符

46、彈出，恢復(fù)分析；如果棧頂?shù)挠浱柌黄ヅ漭斎敕?，則分析；如果棧頂?shù)挠浱柌黄ヅ漭斎敕?，則從棧頂彈出該記號。從棧頂彈出該記號。vP136,P136,表表4.44.44.4 自底向上分析概述自底向上分析概述v基本思想：從輸入串開始，逐步進(jìn)行基本思想：從輸入串開始，逐步進(jìn)行“歸歸約約”，如果最后能得到文法的如果最后能得到文法的開始符號開始符號，則，則輸入串是合乎語法的句子，否則輸入串有語輸入串是合乎語法的句子，否則輸入串有語法錯(cuò)誤。法錯(cuò)誤。即從樹末端開始，即從樹末端開始，構(gòu)造分析構(gòu)造分析樹樹。v核心：尋找句型中的核心：尋找句型中的“句柄句柄”進(jìn)行歸約，用進(jìn)行歸約，用不同的方法尋找句柄，就可獲得不同的分

47、析不同的方法尋找句柄，就可獲得不同的分析方法。方法。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+ +* *EiiEEEE4.4 自底向上分析自底向上分析4.4.1 歸約歸約例例S aABe A Abc | bB d所謂所謂歸約歸約，是指根據(jù)，是指根據(jù)文法的產(chǎn)生式規(guī)則，文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換把產(chǎn)生式的右部替換成左部符號成左部符號4.4.1 歸約歸約例例S aABe A Abc | bB dabbcdeeabbdc所謂所謂歸約歸約，是指根據(jù)，是指根據(jù)文法的產(chǎn)生式規(guī)則，文法的產(chǎn)生式規(guī)則，把產(chǎn)生式

48、的右部替換把產(chǎn)生式的右部替換成左部符號成左部符號4.4.1 歸約歸約例例S aABe A Abc | bB dabbcdeaAbcdeeabAbdc所謂所謂歸約歸約，是指根據(jù)，是指根據(jù)文法的產(chǎn)生式規(guī)則，文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換把產(chǎn)生式的右部替換成左部符號成左部符號4.4.1 歸約歸約例例S aABe A Abc | bB dabbcdeaAbcdeaAdeeabAbdAc所謂所謂歸約歸約，是指根據(jù)，是指根據(jù)文法的產(chǎn)生式規(guī)則，文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換把產(chǎn)生式的右部替換成左部符號成左部符號4.4.1 歸約歸約例例S aABe A Abc | bB dabbcdeaAbcde

49、aAdeaABeeabAbdAcB所謂所謂歸約歸約，是指根據(jù)，是指根據(jù)文法的產(chǎn)生式規(guī)則，文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換把產(chǎn)生式的右部替換成左部符號成左部符號4.4.1 歸約歸約例例S aABe A Abc | bB dabbcdeaAbcdeaAdeaABeS SeabAbdAcB所謂所謂歸約歸約，是指根據(jù)，是指根據(jù)文法的產(chǎn)生式規(guī)則，文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換把產(chǎn)生式的右部替換成左部符號成左部符號4.4.1 歸約歸約例例S aABe A Abc | bB dabbcdeaAbcdeaAdeaABeS S rm aABe rm aAde rm aAbcde rm abbcdeSe

50、abAbdAcB所謂所謂歸約歸約，是指根據(jù)，是指根據(jù)文法的產(chǎn)生式規(guī)則，文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換把產(chǎn)生式的右部替換成左部符號成左部符號4.4.2 句柄句柄v定義定義 設(shè)設(shè)是文法是文法G的一個(gè)句型，若的一個(gè)句型，若 存在存在S *A，A +，則，則 稱稱是句型是句型相對于相對于A的的短語短語；特別的，若；特別的，若 有有A，則，則 稱稱是句型是句型相對于產(chǎn)生式相對于產(chǎn)生式A的的直接短語直接短語（簡單短語簡單短語）。一個(gè)句型的最左直接短語被稱為一個(gè)句型的最左直接短語被稱為句柄句柄。4.4.2 句柄句柄v用分析樹求用分析樹求短語短語、簡單短語簡單短語和和句柄句柄的方法：的方法：1 1）每個(gè)

51、句型都有一棵分析樹；）每個(gè)句型都有一棵分析樹；2 2）每棵分析樹的葉（從左到右）組成一）每棵分析樹的葉（從左到右）組成一句型句型；3 3）每個(gè)子樹的葉（從左到右）組成一）每個(gè)子樹的葉（從左到右）組成一短語短語；4 4）每個(gè)簡單子樹的葉（從左到右）組成一）每個(gè)簡單子樹的葉（從左到右）組成一簡簡單短語單短語；5 5）最左簡單子樹的葉（從左到右）組成一）最左簡單子樹的葉（從左到右）組成一句句柄柄。bdbaceSABAdbaceSABAdaceSABaceSABSS aAcBe A Ab | b B dabbcde規(guī)范歸約規(guī)范歸約v定義定義：假定：假定 是文法是文法G的一個(gè)句子，我們稱序列的一個(gè)句子，

52、我們稱序列 n， n-1， ， 0 是一個(gè)是一個(gè)規(guī)范歸約規(guī)范歸約（最左歸約最左歸約），如果此序列滿足：），如果此序列滿足： 1 n= 2 0為文法的開始符號，即為文法的開始符號，即 0=S 3 對任何對任何i，0 i n， i-1是從是從 i經(jīng)把經(jīng)把句柄句柄替換成為替換成為相應(yīng)產(chǎn)生式左部非終結(jié)符而得到的。相應(yīng)產(chǎn)生式左部非終結(jié)符而得到的。v提醒提醒：最左歸約最左歸約的逆過程是一個(gè)的逆過程是一個(gè)最右推導(dǎo)最右推導(dǎo)，分別，分別稱稱最右推導(dǎo)最右推導(dǎo)和和最左歸約最左歸約為為規(guī)范推導(dǎo)規(guī)范推導(dǎo)和和規(guī)范歸約規(guī)范歸約4.4.3 移進(jìn)移進(jìn) 歸約分析歸約分析v采用采用“移進(jìn)歸約移進(jìn)歸約”思想進(jìn)行自底向上分析。思想進(jìn)行

53、自底向上分析。v基本思想：用一個(gè)寄存符號的棧，基本思想：用一個(gè)寄存符號的棧，把輸入符把輸入符號號按從左到右的順序一個(gè)一個(gè)地移進(jìn)到棧里按從左到右的順序一個(gè)一個(gè)地移進(jìn)到棧里，邊移入邊分析，當(dāng)棧頂形成某個(gè)產(chǎn)生式的邊移入邊分析，當(dāng)棧頂形成某個(gè)產(chǎn)生式的句句柄柄（即為某產(chǎn)生式的右部）時(shí)，即把棧頂?shù)模礊槟钞a(chǎn)生式的右部）時(shí)，即把棧頂?shù)倪@一部分替換成這一部分替換成( (歸約歸約為為) )該產(chǎn)生式的左部符該產(chǎn)生式的左部符號號。最終如果棧頂為文法的開始符號，則所。最終如果棧頂為文法的開始符號，則所分析的輸入符號串為合法的符號串，報(bào)告分分析的輸入符號串為合法的符號串，報(bào)告分析成功析成功, ,否則，是不合格的符號串，

54、報(bào)告錯(cuò)誤。否則，是不合格的符號串，報(bào)告錯(cuò)誤。例：設(shè)文法例：設(shè)文法G(S)： (1) S aAcBe (2) A b (3) A Ab (4) B d試對試對abbcde進(jìn)行進(jìn)行“移進(jìn)歸約移進(jìn)歸約”分析。分析。a bbcdeba bcdeAa bcdebAa cdeAa cdecAa dedcAa eabbcdeeBcAa S BcAa e例：考慮文法例：考慮文法G(E)：EE +T |T TT*F | F Fi| (E)并假定輸入串為并假定輸入串為（i+i)*i，考察自底向上的分析過程。，考察自底向上的分析過程。步驟步驟 分析棧分析棧 輸入串輸入串 動(dòng)作動(dòng)作 $ (i+i)$ (i+i)* *

55、i$ i$ 移進(jìn)移進(jìn) $( i+i)$( i+i)* *i$ i$ 移進(jìn)移進(jìn) $(i +i)$(i +i)* *i$ i$ 歸約歸約 $(F +i)$(F +i)* *i$ i$ 歸約歸約 $(T +i)$(T +i)* *i$ i$ 歸約歸約 $(E +i)$(E +i)* *i$ i$ 移進(jìn)移進(jìn) $(E+ i)$(E+ i)* *i$ i$ 移進(jìn)移進(jìn) $(E+i )$(E+i )* *i$ i$ 歸約歸約 $(E+F )$(E+F )* *i$ i$ 歸約歸約1 1 步驟步驟 分析棧分析棧 輸入串輸入串 動(dòng)作動(dòng)作10 $(E+T )10 $(E+T )* *i$ i$ 歸約歸約11 $(E

56、 )11 $(E )* *i$ i$ 移進(jìn)移進(jìn)12 $(E) 12 $(E) * *i$ i$ 歸約歸約13 $F 13 $F * *i$ i$ 歸約歸約14 $T 14 $T * *i$ i$ 移進(jìn)移進(jìn)15 $T15 $T* * i$ i$ 移進(jìn)移進(jìn)16 $T16 $T* *i $ i $ 歸約歸約17 $T17 $T* *F $ F $ 歸約歸約18 $T $ 18 $T $ 歸約歸約 $E $ $E $ 接受接受移進(jìn)移進(jìn) 歸約分析歸約分析v分析棧上的候選式不一定是句柄。例如，在第分析棧上的候選式不一定是句柄。例如，在第1414步步時(shí)棧頂為時(shí)棧頂為T T，它是，它是E E的一候選式，但它不

57、是的一候選式，但它不是句柄句柄，不，不能歸約成能歸約成E E。判定候選式是極為簡單的事情，但判。判定候選式是極為簡單的事情，但判定句柄就不那么容易。而不同的自底向上方法給出定句柄就不那么容易。而不同的自底向上方法給出不同的判定方法。不同的判定方法。v自底向上方法主要包括以下四個(gè)動(dòng)作：自底向上方法主要包括以下四個(gè)動(dòng)作：移進(jìn)移進(jìn)：把下一個(gè)輸入符號讀到分析棧中：把下一個(gè)輸入符號讀到分析棧中歸約歸約：把分析棧頂?shù)木浔鷼w約為一非終結(jié)符：把分析棧頂?shù)木浔鷼w約為一非終結(jié)符接受接受：分析成功：分析成功報(bào)錯(cuò)報(bào)錯(cuò)：處理錯(cuò)誤：處理錯(cuò)誤移進(jìn)移進(jìn) 歸約分析歸約分析v注意兩點(diǎn)：注意兩點(diǎn)：（1 1）棧內(nèi)符號串）棧內(nèi)符號串+

58、 + 未處理輸入符號串未處理輸入符號串 = = 當(dāng)當(dāng)前前句型句型（2 2）句柄都在）句柄都在棧頂棧頂v這一方法的關(guān)鍵是確定當(dāng)前句型的句柄這一方法的關(guān)鍵是確定當(dāng)前句型的句柄v實(shí)際上，以上分析過程并未真正解決句柄實(shí)際上，以上分析過程并未真正解決句柄的識別問題的識別問題 移進(jìn)移進(jìn) 歸約分析的沖突歸約分析的沖突v有些上下文無關(guān)文法不能使用移進(jìn)有些上下文無關(guān)文法不能使用移進(jìn)歸約分析。這歸約分析。這些文法的移進(jìn)些文法的移進(jìn)歸約分析器可能面臨兩種情況：歸約分析器可能面臨兩種情況：分析器根據(jù)棧中的所有內(nèi)容和下一個(gè)輸入符號不分析器根據(jù)棧中的所有內(nèi)容和下一個(gè)輸入符號不能決定是移進(jìn)還是歸約（能決定是移進(jìn)還是歸約（移

59、進(jìn)移進(jìn)歸約沖突歸約沖突）分析器不能決定按哪一個(gè)產(chǎn)生式進(jìn)行歸約（分析器不能決定按哪一個(gè)產(chǎn)生式進(jìn)行歸約（歸歸約約歸約沖突歸約沖突）2022-2-19944.4.4 優(yōu)先法優(yōu)先法v根據(jù)歸約的先后次序?yàn)榫湫椭邢噜彽奈姆ǚ柛鶕?jù)歸約的先后次序?yàn)榫湫椭邢噜彽奈姆ǚ栆?guī)定優(yōu)先關(guān)系規(guī)定優(yōu)先關(guān)系句柄內(nèi)相鄰符號同時(shí)歸約，是同優(yōu)先的句柄內(nèi)相鄰符號同時(shí)歸約，是同優(yōu)先的句柄兩端符號的優(yōu)先級要高于句柄外與之相鄰的句柄兩端符號的優(yōu)先級要高于句柄外與之相鄰的符號符號va1ai-1 aiai+1aj-1aj aj+1anv定義了這種優(yōu)先關(guān)系之后，語法分析程序就可定義了這種優(yōu)先關(guān)系之后，語法分析程序就可以通過以通過ai-1 ai

60、和和aj aj+1這兩個(gè)關(guān)系來確定句柄這兩個(gè)關(guān)系來確定句柄的頭和尾了的頭和尾了 2022-2-1995v根據(jù)句柄的識別狀態(tài)（根據(jù)句柄的識別狀態(tài)（句柄是逐步形成的句柄是逐步形成的）用狀態(tài)來描述不同時(shí)刻下形成的那部分句柄用狀態(tài)來描述不同時(shí)刻下形成的那部分句柄因?yàn)榫浔钱a(chǎn)生式的右部，可用產(chǎn)生式來表示句因?yàn)榫浔钱a(chǎn)生式的右部，可用產(chǎn)生式來表示句柄的不同識別狀態(tài)柄的不同識別狀態(tài)v例如：例如： SbBB可分解為如下識別狀態(tài)可分解為如下識別狀態(tài)S.bBB 移進(jìn)移進(jìn)bSbB.B 等待歸約出等待歸約出BSb.BB 等待歸約出等待歸約出BSbBB. 歸約歸約v采用這種方法，語法分析程序根據(jù)當(dāng)前的分析狀態(tài)采用這種方