編譯原理語(yǔ)法分析

1、第四章第四章語(yǔ)法分析語(yǔ)法分析貴州大學(xué)貴州大學(xué)計(jì)算機(jī)科學(xué)與信息學(xué)院計(jì)算機(jī)科學(xué)與信息學(xué)院第四章第四章 語(yǔ)法分析語(yǔ)法分析v本章內(nèi)容本章內(nèi)容自頂向下自頂向下分析和自底向上分析分析和自底向上分析圍繞語(yǔ)法分析器的自動(dòng)生成展開(kāi)圍繞語(yǔ)法分析器的自動(dòng)生成展開(kāi)第四章第四章 語(yǔ)法分析語(yǔ)法分析v4.1 4.1 語(yǔ)法分析器概述語(yǔ)法分析器概述v4.2 4.2 書(shū)寫(xiě)文法書(shū)寫(xiě)文法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)用語(yǔ)法分析器語(yǔ)法分析器中間代碼

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

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

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

5、(GZ) Gz存在主要問(wèn)題存在主要問(wèn)題: 句柄的識(shí)別問(wèn)題句柄的識(shí)別問(wèn)題主要方法主要方法: 算法優(yōu)先分析法算法優(yōu)先分析法 LR分析法分析法從自動(dòng)機(jī)識(shí)別語(yǔ)言的角從自動(dòng)機(jī)識(shí)別語(yǔ)言的角度度ASaSbSAaaba aAa aSbAa aSbbaa aabbaa aAS SP: SaAS a A SbA SS ba句子句子：aabbaa4.2 書(shū)寫(xiě)文法書(shū)寫(xiě)文法v定義定義：如果一個(gè)文法有非終結(jié)符：如果一個(gè)文法有非終結(jié)符A，對(duì)某個(gè)串，對(duì)某個(gè)串，存，存在推導(dǎo)在推導(dǎo)A +A ，則稱(chēng)該文法是則稱(chēng)該文法是左遞歸左遞歸的。形式為的。形式為AA的產(chǎn)生式引起的左遞歸稱(chēng)為的產(chǎn)生式引起的左遞歸稱(chēng)為直接左遞歸直接左遞歸。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開(kāi)頭開(kāi)頭 那么，消除那么，消除P的直接左遞歸就是把這些規(guī)則改的直接左遞歸就是把這些規(guī)則改寫(xiě)成：寫(xiě)成： 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對(duì)于對(duì)于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ī)則已是多余的，化簡(jiǎn)為：的規(guī)則已是多余的，化簡(jiǎn)為：SabcS | bcS | cS S a

10、bcS | (3.2)4.2.1 消除左遞歸消除左遞歸v注意，由于對(duì)非終結(jié)符排序的不同，最后所得的文注意，由于對(duì)非終結(jié)符排序的不同，最后所得的文法在形式上可能不一樣。但不難證明，它們都是等法在形式上可能不一樣。但不難證明，它們都是等價(jià)的。價(jià)的。v例如，若對(duì)文法例如，若對(duì)文法(3.1)的非終結(jié)符排序選為的非終結(jié)符排序選為S、Q、R，那么，最后所得的無(wú)左遞歸文法是：那么，最后所得的無(wú)左遞歸文法是：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自頂向下分析就是從文法的自頂向下分析就是從文法的開(kāi)始符號(hào)開(kāi)始符號(hào)出發(fā)，向下出發(fā)，向下推推導(dǎo)導(dǎo)，推出句子。，推出句子。帶帶“回溯回溯”

12、的分析方法的分析方法不帶回溯的遞歸子程序不帶回溯的遞歸子程序( (遞歸下降遞歸下降) )分析方法分析方法v自頂向下分析的主旨：對(duì)任何輸入串，試圖用一切自頂向下分析的主旨：對(duì)任何輸入串，試圖用一切可能的辦法，從文法開(kāi)始符號(hào)可能的辦法，從文法開(kāi)始符號(hào)( (根結(jié)點(diǎn)根結(jié)點(diǎn)) )出發(fā)，自上出發(fā)，自上而下、而下、從左到右從左到右地為輸入串建立一棵地為輸入串建立一棵分析樹(shù)分析樹(shù)?；蛘??；蛘哒f(shuō)，為輸入串尋找一個(gè)說(shuō)，為輸入串尋找一個(gè)最左推導(dǎo)最左推導(dǎo)。v分析是一種試探的過(guò)程，是反復(fù)使用不同產(chǎn)生式謀分析是一種試探的過(guò)程，是反復(fù)使用不同產(chǎn)生式謀求與輸入序列匹配的過(guò)程。求與輸入序列匹配的過(guò)程。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)：不能處理左遞歸（分析陷入無(wú)限循環(huán)）不能處理左遞歸（分析陷入無(wú)限循環(huán)）分析過(guò)程中，當(dāng)一個(gè)非終結(jié)符用某一個(gè)候選匹配分析過(guò)程中，當(dāng)一個(gè)非終結(jié)符用某一個(gè)候選匹配成功時(shí)，這種匹配可能是成功時(shí)，這種匹配可能是暫時(shí)暫時(shí)的的。出錯(cuò)時(shí)出錯(cuò)時(shí)

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

15、此候選的工作結(jié)果應(yīng)候選去執(zhí)行任務(wù)，并且此候選的工作結(jié)果應(yīng)是確信無(wú)疑的。是確信無(wú)疑的。v例例 文法文法G(S): (1) SxAy (2) A*|*v例如例如, 對(duì)于下面文法，面臨對(duì)于下面文法，面臨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è)不含左遞歸左遞歸的文法，對(duì)的文法，對(duì)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è)輸入符號(hào)號(hào)a，準(zhǔn)確地指派某一個(gè)候選前去執(zhí)行任務(wù)。這個(gè)候選就是，準(zhǔn)確地指派某一個(gè)候選前去執(zhí)行任務(wù)。這個(gè)候選就是那個(gè)終結(jié)首符集含那個(gè)終結(jié)首符集含a的的 。v經(jīng)過(guò)經(jīng)過(guò)反復(fù)提取左因子反復(fù)提取左因子，能夠把每個(gè)非終結(jié)符的所有候選首符集，能夠把每個(gè)非終結(jié)符的所有候選首符集變成為兩兩不相交。變成為兩兩不相交。.,|=)(*TVaaaFIRST問(wèn)題：對(duì)文

17、法加什么樣的限制可以保證沒(méi)有回溯？問(wèn)題：對(duì)文法加什么樣的限制可以保證沒(méi)有回溯？構(gòu)造構(gòu)造FIRST( )v對(duì)文法對(duì)文法G的任何符號(hào)串的任何符號(hào)串 =X1X2Xn構(gòu)造集合構(gòu)造集合FIRST( )。1. 置置FIRST( )FIRST(X1)；2. 若對(duì)任何若對(duì)任何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+對(duì)于對(duì)于+ +的匹配只能依賴(lài)于在可能的推的匹配只能依賴(lài)于在可能的推導(dǎo)過(guò)程中導(dǎo)過(guò)程中TT的后面的字符的后面的字符4.3.2 LL(1)文法文法v若若FIRST ( i ) 或或 FIRST ( j )含含 ，還需增加條，還需增加條件件v假定假定S是文法是文法G的開(kāi)始符號(hào)，對(duì)于的開(kāi)

21、始符號(hào)，對(duì)于G的任何非的任何非終結(jié)符終結(jié)符A的的后繼符號(hào)后繼符號(hào)集合是所有在句型中直集合是所有在句型中直接出現(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 ) 的算法歸納為如下三條：的算法歸納為如下三條：對(duì)于文法的開(kāi)始符號(hào)對(duì)于文法的開(kāi)始符號(hào)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. 對(duì)于文法中每一個(gè)非終結(jié)符對(duì)于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，若兩兩不相交。即，若 A 1| 2| n 則則 FIRST( i)FIRST( j) (i j)3. 對(duì)文法中的每個(gè)非終結(jié)符對(duì)文法中的每個(gè)非終結(jié)符A，若它存在某個(gè)候選首符集包，若它存在某個(gè)候選首符集包含含 ，則，則 FIRST( i)FOLLOW(A)= i=1,2,.,nv如果一個(gè)文法如果一個(gè)文法G滿(mǎn)足以上條件，則稱(chēng)該文法滿(mǎn)足以上條件，則稱(chēng)該文法G為為L(zhǎng)L(1)文法文法。第一個(gè)第一個(gè)L代表從代表從左向右掃描左向右掃描輸入符號(hào)串，第二個(gè)輸入符號(hào)串，第二個(gè)L代表產(chǎn)生代表產(chǎn)生最

25、最左推導(dǎo)左推導(dǎo)，1代表在分析過(guò)程中執(zhí)行每步推導(dǎo)都要代表在分析過(guò)程中執(zhí)行每步推導(dǎo)都要向前查看一向前查看一個(gè)輸入符號(hào)個(gè)輸入符號(hào) 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ì)沒(méi)有公共左因子沒(méi)有公共左因子不含左遞歸不含左遞歸不是二義的不是二義的4.3.2 LL(1)文法文法v對(duì)于一個(gè)滿(mǎn)足上述條件的文法，可以對(duì)其輸入串進(jìn)對(duì)于一個(gè)滿(mǎn)足上述條件的文法，可以對(duì)其輸入串進(jìn)行有效的無(wú)回溯的自上而下分析。假設(shè)要用非終結(jié)行有效的無(wú)回溯的自上而下分析。假設(shè)要用非終結(jié)符符A進(jìn)行匹配，面臨的輸入符號(hào)為進(jìn)行匹配，面臨的輸入符號(hào)為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)是一種語(yǔ)法錯(cuò)誤。的出現(xiàn)是一種語(yǔ)法錯(cuò)誤。4.3.3 遞歸的預(yù)測(cè)分析遞歸的預(yù)測(cè)分析v預(yù)測(cè)分析預(yù)測(cè)分析是指能根據(jù)當(dāng)前的輸入符號(hào)為非終結(jié)符確定用哪一是指能根據(jù)當(dāng)前的輸入符號(hào)為非終結(jié)符確定用哪一個(gè)選擇個(gè)選擇,LL(1),LL(1)文法滿(mǎn)足此要求文法滿(mǎn)足此要求v遞歸的預(yù)測(cè)分析是為遞歸的預(yù)測(cè)分析是為每一個(gè)非終結(jié)符每一個(gè)非終結(jié)符寫(xiě)一個(gè)分析過(guò)程寫(xiě)一個(gè)分析過(guò)程, ,這些這些過(guò)程可能是遞歸的過(guò)程可能是遞歸的v在處理輸入串時(shí)在處理輸入串時(shí),

28、,首先執(zhí)行的是對(duì)應(yīng)開(kāi)始符號(hào)的過(guò)程首先執(zhí)行的是對(duì)應(yīng)開(kāi)始符號(hào)的過(guò)程, ,然后根然后根據(jù)產(chǎn)生式右部出現(xiàn)的非終結(jié)符據(jù)產(chǎn)生式右部出現(xiàn)的非終結(jié)符, ,依次調(diào)用相應(yīng)的過(guò)程依次調(diào)用相應(yīng)的過(guò)程, ,這種逐這種逐步下降的過(guò)程調(diào)用序列隱含地定義了輸入串的分析樹(shù)步下降的過(guò)程調(diào)用序列隱含地定義了輸入串的分析樹(shù)例例：type simple | id | array simple of typesimple integer | char | num dotdot num4.3.3 遞歸的預(yù)測(cè)分析遞歸的預(yù)測(cè)分析一個(gè)輔助過(guò)程一個(gè)輔助過(guò)程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ù)測(cè)分析非遞歸的預(yù)測(cè)分析v如果

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

32、 a是終結(jié)符或是終結(jié)符或$)$)和輸出流。和輸出流。4.3.4 非遞歸的預(yù)測(cè)分析非遞歸的預(yù)測(cè)分析a + b $輸入輸入預(yù)測(cè)分析程序預(yù)測(cè)分析程序分析表分析表M輸出輸出 XYZ$棧棧分析器工作過(guò)程分析器工作過(guò)程v預(yù)測(cè)分析程序根據(jù)現(xiàn)行棧頂符號(hào)預(yù)測(cè)分析程序根據(jù)現(xiàn)行棧頂符號(hào)X X和當(dāng)前輸入和當(dāng)前輸入符號(hào)符號(hào)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è)輸入符號(hào)。指針，指向下一個(gè)輸入符號(hào)。3. 3. 若若X

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

34、恢復(fù)例程?；謴?fù)例程。分析表分析表非終非終結(jié)符結(jié)符輸輸 入入 符符 號(hào)號(hào) id + . . .E E TE E E +TE T T FT T T T FT F F id 預(yù)測(cè)分析器接受輸入預(yù)測(cè)分析器接受輸入id + id * id的動(dòng)作的動(dòng)作 棧棧 輸輸 入入 輸輸 出出 $E id + id * id$ 非終非終結(jié)符結(jié)符輸輸 入入 符符 號(hào)號(hào) 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ù)測(cè)分析表構(gòu)造預(yù)測(cè)分析表算法算法4.3(1)對(duì)文法的每個(gè)產(chǎn)生式對(duì)文法的每個(gè)產(chǎn)生式A ，執(zhí)行，執(zhí)行(2)和和(3)(2)對(duì)對(duì)FIRST( )的每個(gè)終結(jié)符的每個(gè)終結(jié)符a，把，把A 加入加入MA, a(3)如果如果 在在FIRST( )中，對(duì)中，對(duì)FOLLOW(A)的每的每個(gè)終結(jié)符個(gè)終結(jié)符b（包括（包括$）, 把把A 加入加入MA, b(4)M 的其它沒(méi)有定義的條目都是的其它沒(méi)有定義的條目都是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ù)測(cè)分析表構(gòu)造預(yù)測(cè)分析表v如果如果G是左遞歸或二義的，那么，是左遞歸或二義的，那么，M至少含至少含有一個(gè)有一個(gè)多重定義條目多重定義條目。因此，消除左遞歸和。

37、因此，消除左遞歸和提取左因子將有助于獲得無(wú)多重定義的分析提取左因子將有助于獲得無(wú)多重定義的分析表表M。v可以證明，一個(gè)文法可以證明，一個(gè)文法G的預(yù)測(cè)分析表的預(yù)測(cè)分析表M不含不含多重定義條目，當(dāng)且僅當(dāng)該文法為多重定義條目，當(dāng)且僅當(dāng)該文法為L(zhǎng)L(1)的。的。G(S):S iCtS | iCtSeS | aC b提取左因子之后，改寫(xiě)成：提取左因子之后，改寫(xiě)成：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ù)測(cè)分析的錯(cuò)誤恢復(fù)預(yù)測(cè)分析的錯(cuò)誤恢復(fù)v程序可能的錯(cuò)誤程序可能的錯(cuò)誤: : 詞法錯(cuò)誤，如標(biāo)識(shí)符、關(guān)鍵字或算符的拼寫(xiě)錯(cuò)詞法錯(cuò)誤，如標(biāo)識(shí)符、關(guān)鍵字或算符的拼寫(xiě)錯(cuò) 語(yǔ)法錯(cuò)誤，如算術(shù)表達(dá)式的括號(hào)不配對(duì)語(yǔ)法錯(cuò)誤，如算術(shù)表達(dá)式的括號(hào)不配對(duì) 語(yǔ)義錯(cuò)誤，如算符作用于不相容的運(yùn)算對(duì)象語(yǔ)義錯(cuò)誤，如算符作用于不相容的運(yùn)算對(duì)象 邏輯錯(cuò)誤，如無(wú)窮的遞歸調(diào)用邏輯錯(cuò)誤，如無(wú)窮的遞歸調(diào)用v大多數(shù)錯(cuò)誤的診斷和恢復(fù)集中在語(yǔ)法分析階段。一個(gè)大多數(shù)錯(cuò)誤的診斷和恢復(fù)集中在語(yǔ)法分析階段。一個(gè)原因是大多數(shù)錯(cuò)誤是語(yǔ)法錯(cuò)誤，另一個(gè)原因是語(yǔ)法分原因是大多數(shù)錯(cuò)誤是語(yǔ)法錯(cuò)誤，另一個(gè)原因是語(yǔ)

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

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

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

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

43、記號(hào)集合a a := := exprexpr ; , if ; , if （語(yǔ)句的開(kāi)始符號(hào)作為語(yǔ)句的同步符號(hào)，以免多（語(yǔ)句的開(kāi)始符號(hào)作為語(yǔ)句的同步符號(hào)，以免多出一個(gè)逗號(hào)時(shí)會(huì)把出一個(gè)逗號(hào)時(shí)會(huì)把ifif語(yǔ)句忽略了）語(yǔ)句忽略了）錯(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(mén) ，面臨，面臨id時(shí)出錯(cuò)時(shí)出錯(cuò)非終非終結(jié)符結(jié)符 輸輸 入入 符符 號(hào)號(hào) 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é)符 輸輸 入入 符符 號(hào)號(hào) 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用來(lái)指

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

46、彈出，恢復(fù)分析；如果棧頂?shù)挠浱?hào)不匹配輸入符號(hào)，則分析；如果棧頂?shù)挠浱?hào)不匹配輸入符號(hào)，則從棧頂彈出該記號(hào)。從棧頂彈出該記號(hào)。vP136,P136,表表4.44.44.4 自底向上分析概述自底向上分析概述v基本思想：從輸入串開(kāi)始，逐步進(jìn)行基本思想：從輸入串開(kāi)始，逐步進(jìn)行“歸歸約約”，如果最后能得到文法的如果最后能得到文法的開(kāi)始符號(hào)開(kāi)始符號(hào)，則，則輸入串是合乎語(yǔ)法的句子，否則輸入串有語(yǔ)輸入串是合乎語(yǔ)法的句子，否則輸入串有語(yǔ)法錯(cuò)誤。法錯(cuò)誤。即從樹(shù)末端開(kāi)始，即從樹(shù)末端開(kāi)始，構(gòu)造分析構(gòu)造分析樹(shù)樹(shù)。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)生式的右部替換成左部符號(hào)成左部符號(hào)4.4.1 歸約歸約例例S aABe A Abc | bB dabbcdeeabbdc所謂所謂歸約歸約，是指根據(jù)，是指根據(jù)文法的產(chǎn)生式規(guī)則，文法的產(chǎn)生式規(guī)則，把產(chǎn)生式

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

49、aAdeaABeeabAbdAcB所謂所謂歸約歸約，是指根據(jù)，是指根據(jù)文法的產(chǎn)生式規(guī)則，文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換把產(chǎn)生式的右部替換成左部符號(hào)成左部符號(hào)4.4.1 歸約歸約例例S aABe A Abc | bB dabbcdeaAbcdeaAdeaABeS SeabAbdAcB所謂所謂歸約歸約，是指根據(jù)，是指根據(jù)文法的產(chǎn)生式規(guī)則，文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換把產(chǎn)生式的右部替換成左部符號(hào)成左部符號(hào)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)生式的右部替換成左部符號(hào)成左部符號(hào)4.4.2 句柄句柄v定義定義 設(shè)設(shè)是文法是文法G的一個(gè)句型，若的一個(gè)句型，若 存在存在S *A，A +，則，則 稱(chēng)稱(chēng)是句型是句型相對(duì)于相對(duì)于A的的短語(yǔ)短語(yǔ)；特別的，若；特別的，若 有有A，則，則 稱(chēng)稱(chēng)是句型是句型相對(duì)于產(chǎn)生式相對(duì)于產(chǎn)生式A的的直接短語(yǔ)直接短語(yǔ)（簡(jiǎn)單短語(yǔ)簡(jiǎn)單短語(yǔ)）。一個(gè)句型的最左直接短語(yǔ)被稱(chēng)為一個(gè)句型的最左直接短語(yǔ)被稱(chēng)為句柄句柄。4.4.2 句柄句柄v用分析樹(shù)求用分析樹(shù)求短語(yǔ)短語(yǔ)、簡(jiǎn)單短語(yǔ)簡(jiǎn)單短語(yǔ)和和句柄句柄的方法：的方法：1 1）每個(gè)

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

52、我們稱(chēng)序列 n， n-1， ， 0 是一個(gè)是一個(gè)規(guī)范歸約規(guī)范歸約（最左歸約最左歸約），如果此序列滿(mǎn)足：），如果此序列滿(mǎn)足： 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)生式左部非終結(jié)符而得到的。相應(yīng)產(chǎn)生式左部非終結(jié)符而得到的。v提醒提醒：最左歸約最左歸約的逆過(guò)程是一個(gè)的逆過(guò)程是一個(gè)最右推導(dǎo)最右推導(dǎo)，分別，分別稱(chēng)稱(chēng)最右推導(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è)寄存符號(hào)的棧，基本思想：用一個(gè)寄存符號(hào)的棧，把輸入符把輸入符號(hào)號(hào)按從左到右的順序一個(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)生式的左部符號(hào)號(hào)。最終如果棧頂為文法的開(kāi)始符號(hào)，則所。最終如果棧頂為文法的開(kāi)始符號(hào)，則所分析的輸入符號(hào)串為合法的符號(hào)串，報(bào)告分分析的輸入符號(hào)串為合法的符號(hào)串，報(bào)告分析成功析成功, ,否則，是不合格的符號(hào)串，

54、報(bào)告錯(cuò)誤。否則，是不合格的符號(hào)串，報(bào)告錯(cuò)誤。例：設(shè)文法例：設(shè)文法G(S)： (1) S aAcBe (2) A b (3) A Ab (4) B d試對(duì)試對(duì)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，考察自底向上的分析過(guò)程。，考察自底向上的分析過(guò)程。步驟步驟 分析棧分析棧 輸入串輸入串 動(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(mén) T，它是，它是E E的一候選式，但它不

57、是的一候選式，但它不是句柄句柄，不，不能歸約成能歸約成E E。判定候選式是極為簡(jiǎn)單的事情，但判。判定候選式是極為簡(jiǎn)單的事情，但判定句柄就不那么容易。而不同的自底向上方法給出定句柄就不那么容易。而不同的自底向上方法給出不同的判定方法。不同的判定方法。v自底向上方法主要包括以下四個(gè)動(dòng)作：自底向上方法主要包括以下四個(gè)動(dòng)作：移進(jìn)移進(jìn)：把下一個(gè)輸入符號(hào)讀到分析棧中：把下一個(gè)輸入符號(hào)讀到分析棧中歸約歸約：把分析棧頂?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)符號(hào)串）棧內(nèi)符號(hào)串+

58、 + 未處理輸入符號(hào)串未處理輸入符號(hào)串 = = 當(dāng)當(dāng)前前句型句型（2 2）句柄都在）句柄都在棧頂棧頂v這一方法的關(guān)鍵是確定當(dāng)前句型的句柄這一方法的關(guān)鍵是確定當(dāng)前句型的句柄v實(shí)際上，以上分析過(guò)程并未真正解決句柄實(shí)際上，以上分析過(guò)程并未真正解決句柄的識(shí)別問(wèn)題的識(shí)別問(wèn)題 移進(jìn)移進(jìn) 歸約分析的沖突歸約分析的沖突v有些上下文無(wú)關(guān)文法不能使用移進(jìn)有些上下文無(wú)關(guān)文法不能使用移進(jìn)歸約分析。這歸約分析。這些文法的移進(jìn)些文法的移進(jìn)歸約分析器可能面臨兩種情況：歸約分析器可能面臨兩種情況：分析器根據(jù)棧中的所有內(nèi)容和下一個(gè)輸入符號(hào)不分析器根據(jù)棧中的所有內(nèi)容和下一個(gè)輸入符號(hào)不能決定是移進(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)榫湫椭邢噜彽奈姆ǚ?hào)根據(jù)歸約的先后次序?yàn)榫湫椭邢噜彽奈姆ǚ?hào)規(guī)定優(yōu)先關(guān)系規(guī)定優(yōu)先關(guān)系句柄內(nèi)相鄰符號(hào)同時(shí)歸約，是同優(yōu)先的句柄內(nèi)相鄰符號(hào)同時(shí)歸約，是同優(yōu)先的句柄兩端符號(hào)的優(yōu)先級(jí)要高于句柄外與之相鄰的句柄兩端符號(hào)的優(yōu)先級(jí)要高于句柄外與之相鄰的符號(hào)符號(hào)va1ai-1 aiai+1aj-1aj aj+1anv定義了這種優(yōu)先關(guān)系之后，語(yǔ)法分析程序就可定義了這種優(yōu)先關(guān)系之后，語(yǔ)法分析程序就可以通過(guò)以通過(guò)ai-1 ai

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