編譯原理語法分析

1、第四章第四章 語法分析語法分析 貴州大學(xué)貴州大學(xué) 計算機(jī)科學(xué)與信息學(xué)院計算機(jī)科學(xué)與信息學(xué)院 第四章第四章 語法分析語法分析 v本章內(nèi)容本章內(nèi)容 自頂向下自頂向下分析和自底向上分析分析和自底向上分析 圍繞語法分析器的自動生成展開圍繞語法分析器的自動生成展開 第四章第四章 語法分析語法分析 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)化器 源程序源程序 表表 格格 管管 理理 出出 錯錯 處處 理理 目標(biāo)代碼生成器目標(biāo)代碼生成器 4.1 4.1 語法分析器概述語法分析器概述 v 語法分析器是編譯器語法分析器是編譯器前端前端的重要組成部分，許多編的重要組成部分，許多編 譯器，特別是由自動生成工具構(gòu)造的編譯器，往往其譯器，特別是由自動生成工具構(gòu)造的編譯器，往往其 前端的中心部件就是語法分析器。前端的中心部件就是語法分析器。

3、語法分析器在編語法分析器在編 譯器中的位置和作用如下：譯器中的位置和作用如下： 詞詞 法法 分析器分析器 記記 號號 取下一個取下一個 記號記號 源程序源程序 分析分析 樹樹 前端的前端的 其余部分其余部分 分析器分析器 中間中間 表示表示 符號表符號表 語法分析器概述語法分析器概述 v語法分析器的主要作用有兩點：語法分析器的主要作用有兩點： 檢查詞法分析器輸出的單詞序列是否是源語言中檢查詞法分析器輸出的單詞序列是否是源語言中 的句子，亦即是否符合源語言的語法規(guī)則的句子，亦即是否符合源語言的語法規(guī)則 檢查輸入中的語法（可能包括詞法）錯誤，并調(diào)檢查輸入中的語法（可能包括詞法）錯誤，并調(diào) 用出錯處

4、理器進(jìn)行適當(dāng)處理用出錯處理器進(jìn)行適當(dāng)處理 v兩大類分析方法：兩大類分析方法： 自頂向下分析自頂向下分析 自底向上分析自底向上分析 存在主要問題存在主要問題: 左遞歸問題左遞歸問題 回溯問題回溯問題 主要方法主要方法: 遞歸子程序法遞歸子程序法 預(yù)測分析法預(yù)測分析法 (LL(1) 自頂向下分析算法的基本思想為：自頂向下分析算法的基本思想為： 有符號串有符號串S 若若Z S 則則 S L(GZ) 否則否則 S L(GZ) Gz + 從文法產(chǎn)生語言的角度從文法產(chǎn)生語言的角度 A S aS bSA a a b a aSbAS aabAS aabbaS aabbaa aAS S P: SaAS a A

5、SbA SS ba 句子句子：aabbaa 自底向上分析算法的基本思想為：自底向上分析算法的基本思想為： + 若若Z S 則則 S L(GZ) 否則否則 S L(GZ) Gz 存在主要問題存在主要問題: 句柄的識別問題句柄的識別問題 主要方法主要方法: 算法優(yōu)先分析法算法優(yōu)先分析法 LR分析法分析法 從自動機(jī)識別語言的角從自動機(jī)識別語言的角 度度 A S aS bSA a a b a aAa aSbAa aSbbaa aabbaa aAS S P: SaAS a A SbA SS ba 句子句子：aabbaa 4.2 書寫文法書寫文法 v定義定義：如果一個文法有非終結(jié)符：如果一個文法有非終結(jié)符

6、A，對某個串，對某個串，存，存 在推導(dǎo)在推導(dǎo)A +A ，則稱該文法是則稱該文法是左遞歸左遞歸的。形式為的。形式為 AA的產(chǎn)生式引起的左遞歸稱為的產(chǎn)生式引起的左遞歸稱為直接左遞歸直接左遞歸。 v直接左遞歸直接左遞歸AAa |b 串的特點串的特點 ba . . . a v消除直接左遞歸消除直接左遞歸 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 其中，每個其中，每個 都不等于都不等于 ，每

7、個，每個 都不以都不以P開頭開頭 那么，消除那么，消除P的直接左遞歸就是把這些規(guī)則改的直接左遞歸就是把這些規(guī)則改 寫成：寫成： P 1P | 2P | | nP P 1P | 2P | | mP | 左遞歸變右左遞歸變右 遞歸遞歸 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 ) | id 4.2.1 消除左遞歸消除左遞歸 v非直接左

8、遞歸非直接左遞歸 S Aa | b A Sd | v先變換成直接左遞歸先變換成直接左遞歸 S Aa | b A Aad | bd | v再消除左遞歸再消除左遞歸 S Aa | b A bd A | A A adA | 4.2.1 消除左遞歸消除左遞歸 v例例 考慮文法考慮文法G(S) SQc|c QRb|b (3.1) RSa|a v令它的非終結(jié)符的排序為令它的非終結(jié)符的排序為R、Q、S。 v對于對于R，不存在直接左遞歸。，不存在直接左遞歸。 v把把R代入到代入到Q的有關(guān)候選后，把的有關(guān)候選后，把Q的的 規(guī)則變?yōu)橐?guī)則變?yōu)?QSab | ab | b 4.2.1 消除左遞歸消除左遞歸 v例例 考

9、慮文法考慮文法G(S) SQc|c QRb|b RSa|a v令它的非終結(jié)符的排序為令它的非終結(jié)符的排序為R、Q、S。 vQ的規(guī)則變?yōu)榈囊?guī)則變?yōu)?QSab | ab | b v現(xiàn)在的現(xiàn)在的Q不含直接左遞歸，把它代入到不含直接左遞歸，把它代入到S的有的有 關(guān)候選后，關(guān)候選后，S變成變成 SSabc | abc | bc | c 4.2.1 消除左遞歸消除左遞歸 v例例 考慮文法考慮文法G(S) SQc|c QRb|b RSa|a vS變成變成 SSabc | abc | bc | c v消除消除S的直接左遞歸后：的直接左遞歸后： SabcS | bcS | cS S abcS | QSab |a

10、b | b RSa|a 4.2.1 消除左遞歸消除左遞歸 v消除消除S的直接左遞歸后：的直接左遞歸后： SabcS | bcS | cS S abcS | QSab |ab | b RSa|a v關(guān)于關(guān)于Q和和R的規(guī)則已是多余的，化簡為：的規(guī)則已是多余的，化簡為： SabcS | bcS | cS S abcS | (3.2) 4.2.1 消除左遞歸消除左遞歸 v注意，由于對非終結(jié)符排序的不同，最后所得的文注意，由于對非終結(jié)符排序的不同，最后所得的文 法在形式上可能不一樣。但不難證明，它們都是等法在形式上可能不一樣。但不難證明，它們都是等 價的。價的。 v例如，若對文法例如，若對文法(3.1)

11、的非終結(jié)符排序選為的非終結(jié)符排序選為S、Q、R， 那么，最后所得的無左遞歸文法是：那么，最后所得的無左遞歸文法是： SQc | c QRb | b RbcaR | caR |a R (3.3) R bca R | v文法文法(3.2)和和(3.3)的等價性是顯然的。的等價性是顯然的。 4.2.2 提左因子提左因子 v有左因子的文法有左因子的文法 A 1 | 2 v提左因子提左因子 A A A 1 | 2 4.2.2 提左因子提左因子 v例例 懸空懸空else的文法的文法 stmt if expr then stmt else stmt | if expr then stmt | other v

12、提左因子提左因子 stmtif expr then stmt optional_else_part | other optional_else_part else stmt | 4.3 自頂向下分析自頂向下分析 v自頂向下分析就是從文法的自頂向下分析就是從文法的開始符號開始符號出發(fā)，向下出發(fā)，向下推推 導(dǎo)導(dǎo)，推出句子。，推出句子。 帶帶“回溯回溯”的分析方法的分析方法 不帶回溯的遞歸子程序不帶回溯的遞歸子程序( (遞歸下降遞歸下降) )分析方法分析方法 v自頂向下分析的主旨：對任何輸入串，試圖用一切自頂向下分析的主旨：對任何輸入串，試圖用一切 可能的辦法，從文法開始符號可能的辦法，從文法開始符

13、號( (根結(jié)點根結(jié)點) )出發(fā)，自上出發(fā)，自上 而下、而下、從左到右從左到右地為輸入串建立一棵地為輸入串建立一棵分析樹分析樹。或者?；蛘?說，為輸入串尋找一個說，為輸入串尋找一個最左推導(dǎo)最左推導(dǎo)。 v分析是一種試探的過程，是反復(fù)使用不同產(chǎn)生式謀分析是一種試探的過程，是反復(fù)使用不同產(chǎn)生式謀 求與輸入序列匹配的過程。求與輸入序列匹配的過程。 4.3.1 自頂向下分析的一般方法自頂向下分析的一般方法 v例例 假定有文法假定有文法G(S): (1) SxAy (2) A*|* 分析輸入串分析輸入串x*y(記為記為 )。 Sx*y IP Axy * Sx*y IPAxy * Sx*y IP Axy *

14、Sx*y IPAxy * Sx*y IPAxy Sx*y IP Axy Sx*y IP 分析成功！分析成功！ 4.3.1 自頂向下分析的一般方法自頂向下分析的一般方法 v困難和缺點：困難和缺點： 不能處理左遞歸（分析陷入無限循環(huán)）不能處理左遞歸（分析陷入無限循環(huán)） 分析過程中，當(dāng)一個非終結(jié)符用某一個候選匹配分析過程中，當(dāng)一個非終結(jié)符用某一個候選匹配 成功時，這種匹配可能是成功時，這種匹配可能是暫時暫時的的。出錯時出錯時，不得，不得 不不“回溯回溯”。 回溯導(dǎo)致語義工作推倒重來回溯導(dǎo)致語義工作推倒重來 分析器難以報告輸入串出錯的確切位置分析器難以報告輸入串出錯的確切位置 效率低，代價高，只有理論

15、意義效率低，代價高，只有理論意義 4.3.2 LL(1)文法文法 v構(gòu)造不帶回溯的自上而下分析算法構(gòu)造不帶回溯的自上而下分析算法 要消除文法的左遞歸性要消除文法的左遞歸性 克服回溯克服回溯 v為了消除回溯就必須保證：對文法的任何非為了消除回溯就必須保證：對文法的任何非 終結(jié)符，當(dāng)要用它去匹配輸入串時，能夠根終結(jié)符，當(dāng)要用它去匹配輸入串時，能夠根 據(jù)它所面臨的輸入符號準(zhǔn)確地指派它的一個據(jù)它所面臨的輸入符號準(zhǔn)確地指派它的一個 候選去執(zhí)行任務(wù)，并且此候選的工作結(jié)果應(yīng)候選去執(zhí)行任務(wù)，并且此候選的工作結(jié)果應(yīng) 是確信無疑的。是確信無疑的。 v例例 文法文法G(S): (1) SxAy (2) A*|* v

16、例如例如, 對于下面文法，面臨對于下面文法，面臨a時不知用什么時不知用什么 規(guī)則規(guī)則 S A B A a b | B a C C 4.3.2 LL(1)文法文法 v先定義兩個和文法有關(guān)的函數(shù)：先定義兩個和文法有關(guān)的函數(shù)： 令令G是一個不含是一個不含左遞歸左遞歸的文法，對的文法，對G的所有非終結(jié)符的每個的所有非終結(jié)符的每個 候選候選 定義它的終結(jié)首符集定義它的終結(jié)首符集FIRST( )為：為： 特別是，若特別是，若 * ，則規(guī)定，則規(guī)定FIRST( ) 如果非終結(jié)符如果非終結(jié)符A的所有候選首符集兩兩不相交，即的所有候選首符集兩兩不相交，即A的任何的任何 兩個不同候選兩個不同候選 i和和 j FI

17、RST( i)FIRST( j) 當(dāng)要求當(dāng)要求A匹配輸入串時，匹配輸入串時，A就能根據(jù)它所面臨的第一個輸入符就能根據(jù)它所面臨的第一個輸入符 號號a，準(zhǔn)確地指派某一個候選前去執(zhí)行任務(wù)。這個候選就是，準(zhǔn)確地指派某一個候選前去執(zhí)行任務(wù)。這個候選就是 那個終結(jié)首符集含那個終結(jié)首符集含a的的 。 v經(jīng)過經(jīng)過反復(fù)提取左因子反復(fù)提取左因子，能夠把每個非終結(jié)符的所有候選首符集，能夠把每個非終結(jié)符的所有候選首符集 變成為兩兩不相交。變成為兩兩不相交。 .,|=)( * T VaaaFIRST 問題：對文法加什么樣的限制可以保證沒有回溯？問題：對文法加什么樣的限制可以保證沒有回溯？ 構(gòu)造構(gòu)造FIRST( ) v對

18、文法對文法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 *FT | F(E) | i 分析輸入串：分析輸入串：i + i i + i IP E n

19、G(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE nG(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE FT nG(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE FT i nG(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE FT i nG(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE FT i nG(E): ETE E

20、+TE | TFT T *FT | F(E) | i i + i IP E TE FT i +TE nG(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE FT i +TE nG(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE FT i +TE FT nG(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE FT i +TE FT i nG(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE

21、 FT i +TE FT i nG(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE FT i +TE FT i nG(E): ETE E +TE | TFT T *FT | F(E) | i i + i IP E TE FT i +TE FT i nG(E): ETE E +TE | TFT T *FT | F(E) | i E T+ 對于對于+ +的匹配只能依賴于在可能的推的匹配只能依賴于在可能的推 導(dǎo)過程中導(dǎo)過程中TT的后面的字符的后面的字符 4.3.2 LL(1)文法文法 v若若FIRST ( i ) 或或 FIRST ( j )含含

22、 ，還需增加條，還需增加條 件件 v假定假定S是文法是文法G的開始符號，對于的開始符號，對于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() 中中非非 元素元素屬于屬于F

23、OLLOW (B ) 如果文法中有形如如果文法中有形如AB或或AB且且FIRST() 含有含有 元素這樣的規(guī)則，則元素這樣的規(guī)則，則FOLLOW (A) 的元素的元素 屬于屬于FOLLOW (B ) v例例 E TE E + TE | T FT T FT | F (E) | id FIRST(E) = FIRST(T) = FIRST(F) = ( , id FIRST(E ) = +, FRIST(T ) = , FOLLOW(E) = ), $ FOLLOW(E ) = FOLLOW(E) FOLLOW(T) = FIRST(E ) U FOLLOW(E) = +, ), $ FOLLOW

24、 (T ) = FOLLOW(T) FOLLOW(F) = FRIST(T ) U FOLLOW(T) = , +，), $ 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,$ b e ac d d ce 4.3.2 LL(1)文法

25、文法 v構(gòu)造不帶回溯的自上而下分析的文法條件構(gòu)造不帶回溯的自上而下分析的文法條件 1. 文法不含左遞歸，文法不含左遞歸， 2. 對于文法中每一個非終結(jié)符對于文法中每一個非終結(jié)符A的各個產(chǎn)生式的候選首符集的各個產(chǎn)生式的候選首符集 兩兩不相交。即，若兩兩不相交。即，若 A 1| 2| n 則則 FIRST( i)FIRST( j) (i j) 3. 對文法中的每個非終結(jié)符對文法中的每個非終結(jié)符A，若它存在某個候選首符集包，若它存在某個候選首符集包 含含 ，則，則 FIRST( i)FOLLOW(A)= i=1,2,.,n v如果一個文法如果一個文法G滿足以上條件，則稱該文法滿足以上條件，則稱該文法

26、G為為LL(1)文法文法。 第一個第一個L代表從代表從左向右掃描左向右掃描輸入符號串，第二個輸入符號串，第二個L代表產(chǎn)生代表產(chǎn)生最最 左推導(dǎo)左推導(dǎo)，1代表在分析過程中執(zhí)行每步推導(dǎo)都要代表在分析過程中執(zhí)行每步推導(dǎo)都要向前查看一向前查看一 個輸入符號個輸入符號 4.3.2 LL(1)文法文法 v例例1：G1A: AaABe B Bbb G1A不是不是LL(1)文法，因為文法，因為 FIRST(Bb) FIRST(b)=b v例例2：G2A: AaABeBa B dB G2A不是不是LL(1)文法，因為文法，因為 FIRST(aABe) FIRST(Ba)=a v例例3：G3S: SaAbDed A

27、 BSDe BSAccD D Se G3S不是不是LL(1)文法，因為文法，因為 FIRST(SAc) FOLLOW(B)=a,d 4.3.2 LL(1)文法文法 vLL(1)LL(1)文法有一些明顯的性質(zhì)文法有一些明顯的性質(zhì) 沒有公共左因子沒有公共左因子 不含左遞歸不含左遞歸 不是二義的不是二義的 4.3.2 LL(1)文法文法 v對于一個滿足上述條件的文法，可以對其輸入串進(jìn)對于一個滿足上述條件的文法，可以對其輸入串進(jìn) 行有效的無回溯的自上而下分析。假設(shè)要用非終結(jié)行有效的無回溯的自上而下分析。假設(shè)要用非終結(jié) 符符A進(jìn)行匹配，面臨的輸入符號為進(jìn)行匹配，面臨的輸入符號為a，A的所有產(chǎn)生的所有產(chǎn)生

28、 式為式為 A 1 | 2 | | n 1. 若若a FIRST( i)，則指派，則指派 i執(zhí)行匹配任務(wù)；執(zhí)行匹配任務(wù)； 2. 若若a不屬于任何一個候選首符集，則：不屬于任何一個候選首符集，則： (1) 若若 屬于某個屬于某個FIRST( i )且且 a FOLLOW(A)， 則讓則讓A與與 自動匹配。自動匹配。 (2) 否則，否則，a的出現(xiàn)是一種語法錯誤。的出現(xiàn)是一種語法錯誤。 4.3.3 遞歸的預(yù)測分析遞歸的預(yù)測分析 v預(yù)測分析預(yù)測分析是指能根據(jù)當(dāng)前的輸入符號為非終結(jié)符確定用哪一是指能根據(jù)當(dāng)前的輸入符號為非終結(jié)符確定用哪一 個選擇個選擇,LL(1),LL(1)文法滿足此要求文法滿足此要求

29、v遞歸的預(yù)測分析是為遞歸的預(yù)測分析是為每一個非終結(jié)符每一個非終結(jié)符寫一個分析過程寫一個分析過程, ,這些這些 過程可能是遞歸的過程可能是遞歸的 v在處理輸入串時在處理輸入串時, ,首先執(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 type simple integer | char

30、| num dotdot num 4.3.3 遞歸的預(yù)測分析遞歸的預(yù)測分析 一個輔助過程一個輔助過程 procedure match (t : token); begin if lookahead = t then lookahead := nexttoken( ) else error( ) end; proccdure type; begin if lookahead in integer, char, num then simple( ) else if lookahead = then begin match (); match (id) end else if lookahead =

31、 array then begin match (array); match ( ); simple( ); match ( ); match (of ); type( ) end else error( ) end; type simple | id | array simple of type procedure simple; begin if lookahead = integer then match (integer) else if lookahead = char then match (char) else if lookahead = num then begin matc

32、h (num); match (dotdot); match (num) end else error( ) end; simple integer | char | num dotdot num 4.3.4 非遞歸的預(yù)測分析非遞歸的預(yù)測分析 v如果顯式地維持一個狀態(tài)棧如果顯式地維持一個狀態(tài)棧, ,而不是隱式地通過遞而不是隱式地通過遞 歸調(diào)用歸調(diào)用, ,則可以構(gòu)造非遞歸的預(yù)測分析器則可以構(gòu)造非遞歸的預(yù)測分析器 v預(yù)測分析的關(guān)鍵問題是決定取哪個產(chǎn)生式運用于預(yù)測分析的關(guān)鍵問題是決定取哪個產(chǎn)生式運用于 非終結(jié)符（通過查分析表來決定產(chǎn)生式）非終結(jié)符（通過查分析表來決定產(chǎn)生式） v預(yù)測分析器組成：輸入緩

33、沖區(qū)（存放要分析的串，預(yù)測分析器組成：輸入緩沖區(qū)（存放要分析的串， 以以$ $作為結(jié)束標(biāo)記）、棧（存放文法符號，棧底符作為結(jié)束標(biāo)記）、棧（存放文法符號，棧底符 號是號是$)$)、分析表（兩維數(shù)組、分析表（兩維數(shù)組MA,a,AMA,a,A是非終結(jié)符，是非終結(jié)符， a a是終結(jié)符或是終結(jié)符或$)$)和輸出流。和輸出流。 4.3.4 非遞歸的預(yù)測分析非遞歸的預(yù)測分析 a + b $ 輸入輸入 預(yù)測分析程序預(yù)測分析程序 分析表分析表M 輸出輸出 X Y Z $ 棧棧 分析器工作過程分析器工作過程 v預(yù)測分析程序根據(jù)現(xiàn)行棧頂符號預(yù)測分析程序根據(jù)現(xiàn)行棧頂符號X X和當(dāng)前輸入和當(dāng)前輸入 符號符號a a，執(zhí)行

34、下列四種動作之一，執(zhí)行下列四種動作之一: : 1. 1. 若若X Xa a$，則宣布分析成功，停止分析。，則宣布分析成功，停止分析。 2. 2. 若若X Xa a $，則把，則把X X從棧頂逐出，推進(jìn)輸入從棧頂逐出，推進(jìn)輸入 指針，指向下一個輸入符號。指針，指向下一個輸入符號。 3. 3. 若若X X是終結(jié)符但不是是終結(jié)符但不是a a，則分析器報告出錯，調(diào)，則分析器報告出錯，調(diào) 用錯誤恢復(fù)例程。用錯誤恢復(fù)例程。 分析器工作過程分析器工作過程 4. 4. 若若X X是非終結(jié)符，程序訪問分析表是非終結(jié)符，程序訪問分析表 若若MXMX，aa中存放著關(guān)于中存放著關(guān)于X X的一個產(chǎn)生式，把的一個產(chǎn)生式，

35、把X X逐逐 出出STACKSTACK棧頂，棧頂，把產(chǎn)生式的右部符號串按反序一把產(chǎn)生式的右部符號串按反序一 一推進(jìn)一推進(jìn)STACKSTACK棧棧( (若右部符號為若右部符號為 ，則意味不推什，則意味不推什 么東西進(jìn)棧么東西進(jìn)棧) )。 若若MXMX，aa中存放著中存放著“出錯標(biāo)志出錯標(biāo)志”，則調(diào)用錯誤，則調(diào)用錯誤 恢復(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的動作的動作 棧棧 輸輸 入入 輸輸 出出 $

36、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 * id$ id * id$ $E T id $E T $E $E T + $E T T FT F id T E +TE 4.3.5 構(gòu)造預(yù)測分析表構(gòu)造預(yù)測分析表 算法算法4.3 (1)對文法的每個產(chǎn)生式對文法的每個產(chǎn)生式A ，執(zhí)行，執(zhí)行(2)和和(3) (2)對對FI

37、RST( )的每個終結(jié)符的每個終結(jié)符a，把，把A 加入加入 MA, a (3)如果如果 在在FIRST( )中，對中，對FOLLOW(A)的每的每 個終結(jié)符個終結(jié)符b（包括（包括$）, 把把A 加入加入MA, b (4)M 的其它沒有定義的條目都是的其它沒有定義的條目都是error 例例 E TE E + TE | T FT T FT | F (E) | i FIRST(E) = FIRST(T) = FIRST(F) = ( , i FIRST(E ) = +, FRIST(T ) = , FOLLOW(E) = FOLLOW(E ) = ), $ FOLLOW(T) = FOLLOW (T

38、 ) = +, ), $ 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至少含至少含 有一個有一個多重定義條目多重定義條目。因此，消除左遞歸和。因此，消除左遞歸和 提取左因子將有助于獲得無多重定義的分析提取左因子將有助于獲得無多重定義的分析 表表M。 v可以證明，一個文法可以證明，一個文法G的預(yù)測分析表的預(yù)測分析表M不含不含 多重定義條目，當(dāng)且僅當(dāng)該文法為多重定義條目，當(dāng)且

39、僅當(dāng)該文法為LL(1)的。的。 G(S): S iCtS | iCtSeS | a C b 提取左因子之后，改寫成：提取左因子之后，改寫成： G(S): S iCtSS | a S eS | C b abeit# SSaSiCtSS S S S eS S CCbF (E) 最近匹配原則最近匹配原則 FIRST(S)=i,a FIRST(S)=e, FIRST(C)=b FOLLOW(S)=e,$ FOLLOW(S)=e,$ FOLLOW(C)=t $ 4.3.6 預(yù)測分析的錯誤恢復(fù)預(yù)測分析的錯誤恢復(fù) v程序可能的錯誤程序可能的錯誤: : 詞法錯誤，如標(biāo)識符、關(guān)鍵字或算符的拼寫錯詞法錯誤，如標(biāo)識

40、符、關(guān)鍵字或算符的拼寫錯 語法錯誤，如算術(shù)表達(dá)式的括號不配對語法錯誤，如算術(shù)表達(dá)式的括號不配對 語義錯誤，如算符作用于不相容的運算對象語義錯誤，如算符作用于不相容的運算對象 邏輯錯誤，如無窮的遞歸調(diào)用邏輯錯誤，如無窮的遞歸調(diào)用 v大多數(shù)錯誤的診斷和恢復(fù)集中在語法分析階段。一個大多數(shù)錯誤的診斷和恢復(fù)集中在語法分析階段。一個 原因是大多數(shù)錯誤是語法錯誤，另一個原因是語法分原因是大多數(shù)錯誤是語法錯誤，另一個原因是語法分 析方法的準(zhǔn)確性，它們能以非常有效的方法診斷語法析方法的準(zhǔn)確性，它們能以非常有效的方法診斷語法 錯誤。錯誤。 v在編譯的時侯，想要準(zhǔn)確診斷語義或邏輯錯誤有時是在編譯的時侯，想要準(zhǔn)確診斷

41、語義或邏輯錯誤有時是 很困難的很困難的 4.3.6 預(yù)測分析的錯誤恢復(fù)預(yù)測分析的錯誤恢復(fù) v分析器對錯誤處理的基本目標(biāo)分析器對錯誤處理的基本目標(biāo) 清楚而準(zhǔn)確地報告錯誤的出現(xiàn)清楚而準(zhǔn)確地報告錯誤的出現(xiàn) 迅速地從每個錯誤中恢復(fù)過來，以便診斷后面迅速地從每個錯誤中恢復(fù)過來，以便診斷后面 的錯誤，并盡量少出現(xiàn)偽錯誤的錯誤，并盡量少出現(xiàn)偽錯誤 它不應(yīng)該使正確程序的處理速度降低太多它不應(yīng)該使正確程序的處理速度降低太多 v非遞歸預(yù)測分析在什么場合下發(fā)現(xiàn)錯誤非遞歸預(yù)測分析在什么場合下發(fā)現(xiàn)錯誤 棧頂?shù)慕K結(jié)符和下一個輸入符號不匹配棧頂?shù)慕K結(jié)符和下一個輸入符號不匹配 棧頂是非終結(jié)符棧頂是非終結(jié)符A A，輸入符號是，

42、輸入符號是a a，而，而M M A A , , a a 是空白是空白 4.3.6 預(yù)測分析的錯誤恢復(fù)預(yù)測分析的錯誤恢復(fù) v非遞歸預(yù)測分析：采用緊急方式的錯誤恢復(fù)非遞歸預(yù)測分析：采用緊急方式的錯誤恢復(fù) 發(fā)現(xiàn)錯誤時，分析器每次拋棄一個輸入記號，直發(fā)現(xiàn)錯誤時，分析器每次拋棄一個輸入記號，直 到輸入記號屬于某個指定的到輸入記號屬于某個指定的同步記號同步記號集合為止集合為止 v例：下述兩條是有語法錯誤的語句，其中第一條賦例：下述兩條是有語法錯誤的語句，其中第一條賦 值句結(jié)束時忘記加分號，采用緊急恢復(fù)方式的可能值句結(jié)束時忘記加分號，采用緊急恢復(fù)方式的可能 結(jié)果如下所示。結(jié)果如下所示。 x := a + b

43、 y := c + d; 緊急方式：緊急方式： x := a + b + d; - 丟棄丟棄b之后的若干記號，之后的若干記號， 直到遇到直到遇到同步記號同步記號+為止。為止。 4.3.6 預(yù)測分析的錯誤恢復(fù)預(yù)測分析的錯誤恢復(fù) v同步記號一般是定界符，如分號或同步記號一般是定界符，如分號或endend等。等。 v緊急方式的錯誤恢復(fù)的效果依賴于同步記號緊急方式的錯誤恢復(fù)的效果依賴于同步記號 集合的選擇：集合的選擇： 把把FOLLOW(FOLLOW(A A) )的所有終結(jié)符放入非終結(jié)符的所有終結(jié)符放入非終結(jié)符A A的同步的同步 記號集合記號集合 if if expr expr thenthen （t

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

45、的開始符號作為語句的同步符號，以免多 出一個逗號時會把出一個逗號時會把ifif語句忽略了）語句忽略了） 錯誤處理錯誤處理 如果非終結(jié)符可以產(chǎn)生空串，若出錯時棧頂如果非終結(jié)符可以產(chǎn)生空串，若出錯時棧頂 是這樣的非終結(jié)符，則可以使用產(chǎn)生空串的是這樣的非終結(jié)符，則可以使用產(chǎn)生空串的 產(chǎn)生式產(chǎn)生式 錯誤處理錯誤處理 v棧頂為棧頂為T ，面臨，面臨id時出錯時出錯 非終非終 結(jié)符結(jié)符 輸輸 入入 符符 號號 id+ . . . EETE E E +TE TTFT T 出錯出錯T T FT . . . 錯誤處理錯誤處理 vT 可以產(chǎn)生空串，報錯并用可以產(chǎn)生空串，報錯并用T 非終非終 結(jié)符結(jié)符 輸輸 入入

46、符符 號號 id+ . . . EETE E E +TE TTFT T 報錯，用報錯，用 T T T FT . . . 錯誤處理錯誤處理 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用來指示從非終結(jié)符的用來指示從非終結(jié)符的FOLLOWFOLLOW集合中得到集合中得到 的同步記號。

47、的同步記號。 i+*()# EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E) synch synchsynch synch synch synch synch synch synch $ 4.3.6 預(yù)測分析的錯誤恢復(fù)預(yù)測分析的錯誤恢復(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é)符彈出，恢復(fù) 分析；如果棧頂?shù)挠浱柌黄ヅ漭斎敕?，則分析；如果

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

49、 方法。方法。 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 E i + + * * E i i E EE E 4.4 自底向上分析自底向上分析 4.4.1 歸約歸約 例例S aABe A Abc | b B d 所謂所謂歸約歸約，是指根據(jù)，是指根據(jù) 文法的產(chǎn)生式規(guī)則，文法的產(chǎn)生式規(guī)則， 把產(chǎn)生式的右部替換把產(chǎn)生式的右部替換 成左部符號成左部符號 4.4.1 歸約歸約 例例S aABe A Abc | b B d abbcde eabbdc 所謂所謂歸約歸約，是指根據(jù)，是指根據(jù) 文法的產(chǎn)生式規(guī)則，文法的產(chǎn)生式規(guī)

50、則， 把產(chǎn)生式的右部替換把產(chǎn)生式的右部替換 成左部符號成左部符號 4.4.1 歸約歸約 例例S aABe A Abc | b B d abbcde aAbcde eab A bdc 所謂所謂歸約歸約，是指根據(jù)，是指根據(jù) 文法的產(chǎn)生式規(guī)則，文法的產(chǎn)生式規(guī)則， 把產(chǎn)生式的右部替換把產(chǎn)生式的右部替換 成左部符號成左部符號 4.4.1 歸約歸約 例例S aABe A Abc | b B d abbcde aAbcde aAde eab A bd A c 所謂所謂歸約歸約，是指根據(jù)，是指根據(jù) 文法的產(chǎn)生式規(guī)則，文法的產(chǎn)生式規(guī)則， 把產(chǎn)生式的右部替換把產(chǎn)生式的右部替換 成左部符號成左部符號 4.4.1 歸

51、約歸約 例例S aABe A Abc | b B d abbcde aAbcde aAde aABe eab A bd A c B 所謂所謂歸約歸約，是指根據(jù)，是指根據(jù) 文法的產(chǎn)生式規(guī)則，文法的產(chǎn)生式規(guī)則， 把產(chǎn)生式的右部替換把產(chǎn)生式的右部替換 成左部符號成左部符號 4.4.1 歸約歸約 例例S aABe A Abc | b B d abbcde aAbcde aAde aABe S S eab A bd A c B 所謂所謂歸約歸約，是指根據(jù)，是指根據(jù) 文法的產(chǎn)生式規(guī)則，文法的產(chǎn)生式規(guī)則， 把產(chǎn)生式的右部替換把產(chǎn)生式的右部替換 成左部符號成左部符號 4.4.1 歸約歸約 例例S aABe A

52、 Abc | b B d abbcde aAbcde aAde aABe S S rm aABe rm aAde rm aAbcde rm abbcde S eab A bd A c B 所謂所謂歸約歸約，是指根據(jù)，是指根據(jù) 文法的產(chǎn)生式規(guī)則，文法的產(chǎn)生式規(guī)則， 把產(chǎn)生式的右部替換把產(chǎn)生式的右部替換 成左部符號成左部符號 4.4.2 句柄句柄 v定義定義 設(shè)設(shè)是文法是文法G的一個句型，若的一個句型，若 存在存在 S *A，A +，則，則 稱稱是句型是句型相對于相對于A的的 短語短語；特別的，若；特別的，若 有有A，則，則 稱稱是句型是句型 相對于產(chǎn)生式相對于產(chǎn)生式A的的直接短語直接短語（簡單短

53、語簡單短語）。 一個句型的最左直接短語被稱為一個句型的最左直接短語被稱為句柄句柄。 4.4.2 句柄句柄 v用分析樹求用分析樹求短語短語、簡單短語簡單短語和和句柄句柄的方法：的方法： 1 1）每個句型都有一棵分析樹；）每個句型都有一棵分析樹； 2 2）每棵分析樹的葉（從左到右）組成一）每棵分析樹的葉（從左到右）組成一句型句型； 3 3）每個子樹的葉（從左到右）組成一）每個子樹的葉（從左到右）組成一短語短語； 4 4）每個簡單子樹的葉（從左到右）組成一）每個簡單子樹的葉（從左到右）組成一簡簡 單短語單短語； 5 5）最左簡單子樹的葉（從左到右）組成一）最左簡單子樹的葉（從左到右）組成一句句 柄柄

54、。 b db ace S AB A d b ace S AB A d ace S AB ace S AB S S aAcBe A Ab | b B d abbcde 規(guī)范歸約規(guī)范歸約 v定義定義：假定：假定 是文法是文法G的一個句子，我們稱序列的一個句子，我們稱序列 n， n-1， ， 0 是一個是一個規(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

55、提醒提醒：最左歸約最左歸約的逆過程是一個的逆過程是一個最右推導(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)行自底向上分析。 v基本思想：用一個寄存符號的棧，基本思想：用一個寄存符號的棧，把輸入符把輸入符 號號按從左到右的順序一個一個地移進(jìn)到棧里按從左到右的順序一個一個地移進(jìn)到棧里， 邊移入邊分析，當(dāng)棧頂形成某個產(chǎn)生式的邊移入邊分析，當(dāng)棧頂形成某個產(chǎn)生式的句句 柄柄（即為某產(chǎn)生式的右部）時，即把棧頂?shù)模礊槟钞a(chǎn)生式的右部）時，即把棧頂?shù)?這

56、一部分替換成這一部分替換成( (歸約歸約為為) )該產(chǎn)生式的左部符該產(chǎn)生式的左部符 號號。最終如果棧頂為文法的開始符號，則所。最終如果棧頂為文法的開始符號，則所 分析的輸入符號串為合法的符號串，報告分分析的輸入符號串為合法的符號串，報告分 析成功析成功, ,否則，是不合格的符號串，報告錯誤。否則，是不合格的符號串，報告錯誤。 例：設(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 bbcde b a bcde A a bcde b A a cde A a cde c A a de

57、 d c A a eabbcde e B c A a S B c A a e 例：考慮文法例：考慮文法G(E)：EE +T |T TT*F | F Fi| (E) 并假定輸入串為并假定輸入串為（i+i)*i，考察自底向上的分析過程。，考察自底向上的分析過程。 步驟步驟 分析棧分析棧 輸入串輸入串 動作動作 $ (i+i)$ (i+i)* *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

58、)$(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 步驟步驟 分析棧分析棧 輸入串輸入串 動作動作 10 $(E+T )10 $(E+T )* *i$ i$ 歸約歸約 11 $(E )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$

59、移進(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步步 時棧頂為時棧頂為T T，它是，它是E E的一候選式，但它不是的一候選式，但它不是句柄句柄，不，不 能歸約成能歸約成E E。判定候選式是極為簡單的事情，但判。判定候選式是極為簡單的事情，但判 定句柄就不那么容易。而不同的自底向上方法給出定句柄就不那么容易。而不同的自底向上方法給出 不同的判定

60、方法。不同的判定方法。 v自底向上方法主要包括以下四個動作：自底向上方法主要包括以下四個動作： 移進(jìn)移進(jìn)：把下一個輸入符號讀到分析棧中：把下一個輸入符號讀到分析棧中 歸約歸約：把分析棧頂?shù)木浔鷼w約為一非終結(jié)符：把分析棧頂?shù)木浔鷼w約為一非終結(jié)符 接受接受：分析成功：分析成功 報錯報錯：處理錯誤：處理錯誤 移進(jìn)移進(jìn) 歸約分析歸約分析 v注意兩點：注意兩點： （1 1）棧內(nèi)符號串）棧內(nèi)符號串+ + 未處理輸入符號串未處理輸入符號串 = = 當(dāng)當(dāng) 前前句型句型 （2 2）句柄都在）句柄都在棧頂棧頂 v這一方法的關(guān)鍵是確定當(dāng)前句型的句柄這一方法的關(guān)鍵是確定當(dāng)前句型的句柄 v實際上，以上分析過程并未真正解