第三章語法分析PPT課件

1、第三章第三章 語法分析語法分析 本章內(nèi)容本章內(nèi)容 上下文無關(guān)文法上下文無關(guān)文法 自上而下自上而下分析和自下而上分析分析和自下而上分析 圍繞分析器的自動生成展開圍繞分析器的自動生成展開詞詞 法法分析器分析器記記 號號取下一個取下一個記號記號源程序源程序分析分析樹樹前端的前端的其余部分其余部分分析器分析器中間中間表示表示符號表符號表3.1 上下文無關(guān)文法上下文無關(guān)文法3.1.1 上下文無關(guān)文法的定義上下文無關(guān)文法的定義正規(guī)式能定義一些簡單的語言正規(guī)式能定義一些簡單的語言，能表示給定結(jié)構(gòu)能表示給定結(jié)構(gòu)的固定次數(shù)的重復(fù)或者沒有指定次數(shù)的重復(fù)的固定次數(shù)的重復(fù)或者沒有指定次數(shù)的重復(fù)例：例：a (ba)5,

2、 a (ba)*正規(guī)式不能用于描述配對或嵌套的結(jié)構(gòu)正規(guī)式不能用于描述配對或嵌套的結(jié)構(gòu)例例1：配對括號串的集合配對括號串的集合例例2：wcw | w是是a和和b的串的串 3.1 上下文無關(guān)文法上下文無關(guān)文法 上下文無關(guān)文法上下文無關(guān)文法是四元組（是四元組（VT , VN , S, P）VT : : 終結(jié)符終結(jié)符集合集合VN : : 非非終結(jié)符終結(jié)符集合集合S : : 開始符號，非終結(jié)符中的一個開始符號，非終結(jié)符中的一個P : :產(chǎn)生式產(chǎn)生式集合，集合， 產(chǎn)生式形式產(chǎn)生式形式 : : A 例例 ( id, +, , , (, ), expr, op, expr, P )expr expr op e

3、xpr expr (expr)expr expr expr idop + op 3.1 上下文無關(guān)文法上下文無關(guān)文法 簡化表示簡化表示expr expr op expr | (expr) | expr | idop + | 簡化表示簡化表示E E A E | (E ) | E | idA + | 3.1 上下文無關(guān)文法上下文無關(guān)文法3.1.2 推導(dǎo)推導(dǎo) 把產(chǎn)生式看成重寫規(guī)則，把符號串中的非終結(jié)符把產(chǎn)生式看成重寫規(guī)則，把符號串中的非終結(jié)符用其產(chǎn)生式右部的串來代替用其產(chǎn)生式右部的串來代替 例例 E E + E | E E | (E ) | E | id E E (E) (E + E) (id +

4、E) (id + id) 概念概念 上下文無關(guān)語言上下文無關(guān)語言、等價的等價的文法、文法、句型句型 記號記號S * 、 S + w 3.1 上下文無關(guān)文法上下文無關(guān)文法 例例 E E + E | E E | (E ) | E | id 最左最左推導(dǎo)推導(dǎo)E lm E lm (E) lm (E + E) lm (id + E) lm (id + id) 最右最右推導(dǎo)（規(guī)范推導(dǎo)）推導(dǎo)（規(guī)范推導(dǎo)）E rm E rm (E) rm (E + E) rm (E + id) rm (id + id)3.1 上下文無關(guān)文法上下文無關(guān)文法3.1.3 分析樹分析樹 例例 E E + E | E E | (E )

5、| E | idEE ()EEE+idid3.1 上下文無關(guān)文法上下文無關(guān)文法3.1.4 二義性二義性E E E E E + E id E E E +E id E + E id E + E id id + E id id + E id id + id id id + id兩個不同的最左推導(dǎo)兩個不同的最左推導(dǎo)3.1 上下文無關(guān)文法上下文無關(guān)文法3.1.4 二義性二義性E E E E E + E id E E E +E id E + E id E + E id id + E id id + E id id + id id id + id兩棵不同的語法樹兩棵不同的語法樹EEE*+EEidididEE

6、idE*+EEidid3.2 語言和文法語言和文法 文法的優(yōu)點(diǎn)文法的優(yōu)點(diǎn) 文法給出了精確的，易于理解的語法說明文法給出了精確的，易于理解的語法說明自動產(chǎn)生高效的分析器自動產(chǎn)生高效的分析器可以給語言定義出層次結(jié)構(gòu)可以給語言定義出層次結(jié)構(gòu)以文法為基礎(chǔ)的語言的實(shí)現(xiàn)以文法為基礎(chǔ)的語言的實(shí)現(xiàn)便于語言的修改便于語言的修改 文法的問題文法的問題文法只能描述編程語言的大部分語法，不能描述文法只能描述編程語言的大部分語法，不能描述語言中上下文有關(guān)的語法特征語言中上下文有關(guān)的語法特征3.2 語言和文法語言和文法 3.2.1 正規(guī)式和上下文無關(guān)文法的比較正規(guī)式和上下文無關(guān)文法的比較 正規(guī)式正規(guī)式(a|b)*ab 文

7、法文法A0 a A0 | b A0 | a A1A1 b A2A2 12開始開始a0abb3.2 語言和文法語言和文法 3.2.2 分離詞法分析器理由分離詞法分析器理由 為什么要用正規(guī)式定義詞法為什么要用正規(guī)式定義詞法 詞法規(guī)則非常簡單，不必用上下文無關(guān)文法詞法規(guī)則非常簡單，不必用上下文無關(guān)文法對于詞法記號，正規(guī)式描述簡潔且易于理解對于詞法記號，正規(guī)式描述簡潔且易于理解從正規(guī)式構(gòu)造出的詞法分析器效率高從正規(guī)式構(gòu)造出的詞法分析器效率高3.2 語言和文法語言和文法 從軟件工程角度看，詞法分析和語法分析的從軟件工程角度看，詞法分析和語法分析的分離有如下好處分離有如下好處簡化設(shè)計簡化設(shè)計編譯器的效率會

8、改進(jìn)編譯器的效率會改進(jìn)編譯器的可移植性加強(qiáng)編譯器的可移植性加強(qiáng)便于編譯器前端的模塊劃分便于編譯器前端的模塊劃分 3.2 語言和文法語言和文法 能否把詞法分析并入到語法分析中，直接從能否把詞法分析并入到語法分析中，直接從字符流進(jìn)行語法分析字符流進(jìn)行語法分析 若把詞法分析和語法分析合在一起，則必須將語若把詞法分析和語法分析合在一起，則必須將語言的注解和空白的規(guī)則反映在文法中，文法將大言的注解和空白的規(guī)則反映在文法中，文法將大大復(fù)雜大復(fù)雜 注解和空白由自己來處理的分析器，比注解和空注解和空白由自己來處理的分析器，比注解和空格已由詞法分析器刪除的分析器要復(fù)雜得多格已由詞法分析器刪除的分析器要復(fù)雜得多3

9、.2 語言和文法語言和文法 3.2.3 驗(yàn)證文法產(chǎn)生的語言驗(yàn)證文法產(chǎn)生的語言G : S (S) S | L(G) = 配對的括號串的集合配對的括號串的集合3.2 語言和文法語言和文法 3.2.3 驗(yàn)證文法產(chǎn)生的語言驗(yàn)證文法產(chǎn)生的語言G : S (S) S | L(G) = 配對的括號串的集合配對的括號串的集合 按推導(dǎo)步數(shù)進(jìn)行歸納按推導(dǎo)步數(shù)進(jìn)行歸納：推出的是：推出的是配對括號串配對括號串歸納基歸納基礎(chǔ)：礎(chǔ)： S 歸納假設(shè)：歸納假設(shè)：少于少于n步的推導(dǎo)都產(chǎn)生配對的括號串步的推導(dǎo)都產(chǎn)生配對的括號串 歸納步驟：歸納步驟：n步的最左推導(dǎo)步的最左推導(dǎo)如下：如下：S (S)S * (x) S * (x) y

10、3.2 語言和文法語言和文法 3.2.3 驗(yàn)證文法產(chǎn)生的語言驗(yàn)證文法產(chǎn)生的語言G : S (S) S | L(G) = 配對的括號串的集合配對的括號串的集合 按串長進(jìn)行歸納按串長進(jìn)行歸納：配對括號串可由配對括號串可由S推出推出歸納基歸納基礎(chǔ)：礎(chǔ)： S 歸納假設(shè)：歸納假設(shè)：長度小于長度小于2n的都可以從的都可以從S推導(dǎo)出來推導(dǎo)出來 歸納步驟：歸納步驟：考慮長度為考慮長度為2n(n 1)的的w = (x) yS (S)S * (x) S * (x) y3.2 語言和文法語言和文法 3.2.4 適當(dāng)?shù)谋磉_(dá)式文法適當(dāng)?shù)谋磉_(dá)式文法 用一種層次觀點(diǎn)看待表達(dá)式用一種層次觀點(diǎn)看待表達(dá)式id id (id+id

11、) + id id + id3.2 語言和文法語言和文法 3.2.4 適當(dāng)?shù)谋磉_(dá)式文法適當(dāng)?shù)谋磉_(dá)式文法 用一種層次觀點(diǎn)看待表達(dá)式用一種層次觀點(diǎn)看待表達(dá)式id id (id+id) + id id + idid id (id+id) 文法文法expr expr + term | termterm term factor | factor factor id | (expr)3.2 語言和文法語言和文法 expr expr + term | termterm term factor | factor factor id | (expr)expridtermfactorididterm*termfa

12、ctorfactor*exprexpr+idfactortermididterm*termfactorfactorid + id id分析樹分析樹 id id id分析樹分析樹 3.2 語言和文法語言和文法 3.2.5 消除二義性消除二義性stmt if expr then stmt | if expr then stmt else stmt | other 句型句型：if expr then if expr then stmt else stmt 兩個最左推導(dǎo)：兩個最左推導(dǎo)：stmt if expr then stmt if expr then if expr then stmt else

13、stmtstmt if expr then stmt else stmt if expr then if expr then stmt else stmt 3.2 語言和文法語言和文法 無二義的文法無二義的文法stmt matched _stmt | unmatched_stmtmatched_stmt if expr then matched_stmt else matched_stmt | otherunmatched_stmt if expr then stmt | if expr then matched_stmt else unmatched_stmt3.2 語言和文法語言和文法 3

14、.2.6 消除左遞歸消除左遞歸 文法文法左遞歸左遞歸A+A 直接左遞歸直接左遞歸AA | |b b 串的特點(diǎn)串的特點(diǎn) bb . . . . . . 消除直接左遞歸消除直接左遞歸A b b A A A | 3.2 語言和文法語言和文法 例例 算術(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 ) | id3.2 語言和文法語言和文法 非直接左遞歸非直接左遞歸S Aa | b A Sd | 先變換

15、成直接左遞歸先變換成直接左遞歸S Aa | bA Aad | bd | 再消除左遞歸再消除左遞歸S Aa | bA bd A | A A adA | 3.2 語言和文法語言和文法 3.2.7 提左因子提左因子 有左因子的文法有左因子的文法A bb1 | bb2 提左因子提左因子A A A b b1 | b b2 3.2 語言和文法語言和文法 例例 懸空懸空else的文法的文法 stmt if expr then stmt else stmt | if expr then stmt | other提左因子提左因子stmt if expr then stmt optional_else_part

16、| otheroptional_else_part else stmt | 3.2 語言和文法語言和文法 3.2.8 非上下文無關(guān)的語言構(gòu)造非上下文無關(guān)的語言構(gòu)造 L1 = wcw | w屬于屬于(a | b)*標(biāo)識符的聲明應(yīng)先于其引用的抽象標(biāo)識符的聲明應(yīng)先于其引用的抽象 L2 = anbmcndm | n 0, m 0 形參個數(shù)和實(shí)參個數(shù)應(yīng)該相同的抽象形參個數(shù)和實(shí)參個數(shù)應(yīng)該相同的抽象 L3 = anbncn | n 0 早先排版描述的一個現(xiàn)象的抽象早先排版描述的一個現(xiàn)象的抽象b e g i n：5個字母鍵，個字母鍵，5個回退鍵，個回退鍵，5個下劃線鍵個下劃線鍵3.2 語言和文法語言和文法 L

17、1 = wcwR | w (a|b)* S aSa | bSb | c L2 = anbmcmdn | n 1, m 1S aSd | aAdA bAc | bc L 2 = anbncmdm | n 1，m 1S ABA aAb | abB cBd | cd3.2 語言和文法語言和文法 L3 =anbn | n 1S aSb | ab L3 是不能用正規(guī)式描述的語言的一個范例是不能用正規(guī)式描述的語言的一個范例 若存在接受若存在接受L3 的的DFA D，狀態(tài)數(shù)為狀態(tài)數(shù)為k個個 設(shè)設(shè)D讀完讀完 , a, aa, , ak 分別到達(dá)狀態(tài)分別到達(dá)狀態(tài)s0, s1, , sk至少有兩個狀態(tài)相同，例如是

18、至少有兩個狀態(tài)相同，例如是si和和sj，則則ajbi屬于屬于L3 sifs0標(biāo)記為標(biāo)記為ai的路徑的路徑標(biāo)記為標(biāo)記為bi的路徑的路徑標(biāo)記為標(biāo)記為aj i的路徑的路徑 3.2 語言和文法語言和文法 3.2.9 形式語言鳥瞰形式語言鳥瞰 文法文法 G = (VT , VN, S, P) 0型文法：型文法： b b， , b b (VN VT)*, | | 13.2 語言和文法語言和文法 3.2.9 形式語言鳥瞰形式語言鳥瞰 文法文法 G = (VT , VN, S, P) 0型文法：型文法： b b， , b b (VN VT)*, | | 1 短語文法短語文法3.2 語言和文法語言和文法 3.2

19、.9 形式語言鳥瞰形式語言鳥瞰 文法文法 G = (VT , VN, S, P) 0型文法：型文法： b b， , b b (VN VT)*, | | 1 1型文法：型文法：| | |b b |，但但S 可以例外可以例外 短語文法短語文法3.2 語言和文法語言和文法 3.2.9 形式語言鳥瞰形式語言鳥瞰 文法文法 G = (VT , VN, S, P) 0型文法：型文法： b b， , b b (VN VT)*, | | 1 1型文法：型文法：| | |b b |，但但S 可以例外可以例外 短語文法、上下文有關(guān)文法短語文法、上下文有關(guān)文法3.2 語言和文法語言和文法 3.2.9 形式語言鳥瞰形

20、式語言鳥瞰 文法文法 G = (VT , VN, S, P) 0型文法：型文法： b b， , b b (VN VT)*, | | 1 1型文法：型文法：| | |b b |，但但S 可以例外可以例外 2型文法：型文法：A b b，A VN , b b (VN VT)* 短語文法、上下文有關(guān)文法短語文法、上下文有關(guān)文法3.2 語言和文法語言和文法 3.2.9 形式語言鳥瞰形式語言鳥瞰 文法文法 G = (VT , VN, S, P) 0型文法：型文法： b b， , b b (VN VT)*, | | 1 1型文法：型文法：| | |b b |，但但S 可以例外可以例外 2型文法：型文法：A

21、b b，A VN , b b (VN VT)* 短語文法、上下文有關(guān)文法、上下文無關(guān)文短語文法、上下文有關(guān)文法、上下文無關(guān)文法法3.2 語言和文法語言和文法 3.2.9 形式語言鳥瞰形式語言鳥瞰 文法文法 G = (VT , VN, S, P) 0型文法：型文法： b b， , b b (VN VT)*, | | 1 1型文法：型文法：| | |b b |，但但S 可以例外可以例外 2型文法：型文法：A b b，A VN , b b (VN VT)* 3型文法：型文法：A aB或或A a，A, B VN , a VT 短語文法、上下文有關(guān)文法、上下文無關(guān)文短語文法、上下文有關(guān)文法、上下文無關(guān)文

22、法法3.2 語言和文法語言和文法 3.2.9 形式語言鳥瞰形式語言鳥瞰 文法文法 G = (VT , VN, S, P) 0型文法：型文法： b b， , b b (VN VT)*, | | 1 1型文法：型文法：| | |b b |，但但S 可以例外可以例外 2型文法：型文法：A b b，A VN , b b (VN VT)* 3型文法：型文法：A aB或或A a，A, B VN , a VT 短語文法、上下文有關(guān)文法、上下文無關(guān)文短語文法、上下文有關(guān)文法、上下文無關(guān)文法、正規(guī)文法法、正規(guī)文法3.2 語言和文法語言和文法 例例 L3anbncn| n 1的上下文有關(guān)文法的上下文有關(guān)文法S a

23、SBC S aBC CB BCaB ab bB bbbC bccC ccanbncn的推導(dǎo)過程如下：的推導(dǎo)過程如下：S * an-1S(BC)n 1用用S aSBC n-1次次S + an(BC)n 用用S aBC 1次次S + anBnCn用用CB BC交換相鄰的交換相鄰的CBS + anbBn 1Cn用用aB ab 1次次S + anbnCn 用用bB bb n-1次次S + anbncCn-1用用bC bc 1次次S + anbncn用用cC cc n-1次次3.3 自上而下分析自上而下分析 3.3.1 自上而下分析的一般方法自上而下分析的一般方法 例例 文法文法 S aCb C cd

24、| c為輸入串為輸入串w = acb建立分析樹建立分析樹SaCbSaCbcdSaCbc不能處理不能處理左遞歸左遞歸3.3 自上而下分析自上而下分析 不能處理左遞歸的例子不能處理左遞歸的例子 算術(shù)表達(dá)文法算術(shù)表達(dá)文法E E + T | TT T F | FF ( E ) | idEE+TE+TE+T 3.3 自上而下分析自上而下分析 3.3.1 自上而下分析的一般方法自上而下分析的一般方法 例例 文法文法 S aCb C cd | c為輸入串為輸入串w = acb建立分析樹建立分析樹SSSaCbaaCCbbcdc不能處理不能處理左遞歸左遞歸、復(fù)雜的回溯技術(shù)復(fù)雜的回溯技術(shù)3.3 自上而下分析自上而

25、下分析 3.3.1 自上而下分析的一般方法自上而下分析的一般方法 例例 文法文法 S aCb C cd | c為輸入串為輸入串w = acb建立分析樹建立分析樹SSSaCbaaCCbbcdc不能處理不能處理左遞歸左遞歸、復(fù)雜的回溯技術(shù)復(fù)雜的回溯技術(shù)、回溯導(dǎo)回溯導(dǎo)致語義工作推倒重來致語義工作推倒重來3.3 自上而下分析自上而下分析 3.3.1 自上而下分析的一般方法自上而下分析的一般方法 例例 文法文法 S aCb C cd | c為輸入串為輸入串w = acb建立分析樹建立分析樹SSSaCbaaCCbbcdc不能處理不能處理左遞歸左遞歸、復(fù)雜的回溯技術(shù)復(fù)雜的回溯技術(shù)、回溯導(dǎo)回溯導(dǎo)致語義工作推倒

26、重來致語義工作推倒重來、難以報告出錯的確切難以報告出錯的確切位置位置3.3 自上而下分析自上而下分析 3.3.1 自上而下分析的一般方法自上而下分析的一般方法 例例 文法文法 S aCb C cd | c為輸入串為輸入串w = acb建立分析樹建立分析樹SSSaCbaaCCbbcdc不能處理不能處理左遞歸左遞歸、復(fù)雜的回溯技術(shù)復(fù)雜的回溯技術(shù)、回溯導(dǎo)回溯導(dǎo)致語義工作推倒重來致語義工作推倒重來、難以報告出錯的確切難以報告出錯的確切位置位置、效率低效率低3.3 自上而下分析自上而下分析 3.3.2 LL(1)文法文法 對文法加什么樣的限制可以保證沒有對文法加什么樣的限制可以保證沒有回溯回溯？ 先定義

27、兩個和文法有關(guān)的函數(shù)先定義兩個和文法有關(guān)的函數(shù) FIRST( ) = a | * a, a VT 特別是，特別是， * 時，規(guī)定時，規(guī)定 FIRST( ) 對對A的任何兩個不同選擇的任何兩個不同選擇 i 和和 j，希望有希望有FIRST( i ) FIRST( j ) = 若若FIRST( i ) 或或 FIRST( j )含含 ，還需增加條件，還需增加條件3.3 自上而下分析自上而下分析 3.3.2 LL(1)文法文法 對文法加什么樣的限制可以保證沒有對文法加什么樣的限制可以保證沒有回溯回溯？ 先定義兩個和文法有關(guān)的函數(shù)先定義兩個和文法有關(guān)的函數(shù) FIRST( ) = a | * a, a

28、VT 特別是，特別是， * 時，規(guī)定時，規(guī)定 FIRST( ) FOLLOW(A) = a | S * Aa，a VT如果如果A是某個句型的最右符號，那么是某個句型的最右符號，那么$屬于屬于FOLLOW(A) 3.3 自上而下分析自上而下分析 LL(1)文法文法任何兩個產(chǎn)生式任何兩個產(chǎn)生式A | b b 都滿足下列條件：都滿足下列條件： FIRST( ) FIRST(b b ) = 若若b b * ，那么，那么FIRST( ) FOLLOW(A) = 例如例如, 對于下面文法，面臨對于下面文法，面臨a時，第時，第2步推導(dǎo)不步推導(dǎo)不知用哪個產(chǎn)生式知用哪個產(chǎn)生式S A BA a b | a FIR

29、ST(ab) FOLLOW(A) B a CC 3.3 自上而下分析自上而下分析 LL(1)文法文法任何兩個產(chǎn)生式任何兩個產(chǎn)生式A | b b 都滿足下列條件：都滿足下列條件： FIRST( ) FIRST(b b ) = 若若b b * ，那么，那么FIRST( ) FOLLOW(A) = LL(1)文法有一些明顯的性質(zhì)文法有一些明顯的性質(zhì)沒有公共左因子沒有公共左因子不是二義的不是二義的不含左遞歸不含左遞歸3.3 自上而下分析自上而下分析 例例 E TE E + TE | T FT T FT | F (E) | idFIRST(E) = FIRST(T) = FIRST(F) = ( , i

30、d FIRST(E ) = +, FRIST(T ) = , FOLLOW(E) = FOLLOW(E ) = ), $FOLLOW(T) = FOLLOW (T ) = +, ), $FOLLOW(F) = +, , ), $ 3.3 自上而下分析自上而下分析 3.3.3 遞歸下降的預(yù)測分析遞歸下降的預(yù)測分析為每一個非終結(jié)符寫一個分析過程為每一個非終結(jié)符寫一個分析過程這些過程可能是遞歸的這些過程可能是遞歸的 例例type simple | id | array simple of typesimple integer | char | num dotdot num3.3 自上而下分析自上而下

31、分析 一個輔助過程一個輔助過程void match (terminal t) if (lookahead = t) lookahead = nextToken( );else error( );3.3 自上而下分析自上而下分析 void type( ) if ( (lookahead = integer) | (lookahead = char) | (lookahead = num) )simple( );else if ( lookahead = ) match(); match(id);else if (lookahead = array) match(array); match( );

32、 simple( );match( ); match(of ); type( );else error( ); type simple | id | array simple of type3.3 自上而下分析自上而下分析 void simple( ) if ( lookahead = integer) match(integer);else if (lookahead = char) match(char);else if (lookahead = num) match(num); match(dotdot); match(num);else error( ); simple integer

33、 | char | num dotdot num3.3 自上而下分析自上而下分析3.3.4 非遞歸的預(yù)測分析非遞歸的預(yù)測分析a + b $輸入輸入預(yù)測分析程序預(yù)測分析程序分析表分析表M輸出輸出 XYZ$棧棧3.3 自上而下分析自上而下分析非終非終結(jié)符結(jié)符輸輸 入入 符符 號號 id + . . .E E TE E E +TE T T FT T T T FT F F id 分析表的一部分分析表的一部分3.3 自上而下分析自上而下分析棧棧 輸輸 入入 輸輸 出出 $E id id + id$ 預(yù)測預(yù)測分析器接受輸入分析器接受輸入id * id + id的前一部分動作的前一部分動作 3.3 自上而下

34、分析自上而下分析棧棧 輸輸 入入 輸輸 出出 $E id id + id$ $E T id id + id$ E TE 預(yù)測預(yù)測分析器接受輸入分析器接受輸入id * id + id的前一部分動作的前一部分動作 3.3 自上而下分析自上而下分析棧棧 輸輸 入入 輸輸 出出 $E id id + id$ $E T id id + id$ E TE $E T F id id + id$ T FT 預(yù)測預(yù)測分析器接受輸入分析器接受輸入id * id + id的前一部分動作的前一部分動作 3.3 自上而下分析自上而下分析棧棧 輸輸 入入 輸輸 出出 $E id id + id$ $E T id id +

35、 id$ E TE $E T F id id + id$ T FT $E T id id id + id$ F id 預(yù)測預(yù)測分析器接受輸入分析器接受輸入id * id + id的前一部分動作的前一部分動作 3.3 自上而下分析自上而下分析棧棧 輸輸 入入 輸輸 出出 $E id id + id$ $E T id id + id$ E TE $E T F id id + id$ T FT $E T id id id + id$ F id $E T id + id$ 預(yù)測預(yù)測分析器接受輸入分析器接受輸入id * id + id的前一部分動作的前一部分動作 3.3 自上而下分析自上而下分析棧棧 輸

36、輸 入入 輸輸 出出 $E id id + id$ $E T id id + id$ E TE $E T F id id + id$ T FT $E T id id id + id$ F id $E T id + id$ $E T F id + id$ T FT 預(yù)測預(yù)測分析器接受輸入分析器接受輸入id * id + id的前一部分動作的前一部分動作 3.3 自上而下分析自上而下分析棧棧 輸輸 入入 輸輸 出出 $E id id + id$ $E T id id + id$ E TE $E T F id id + id$ T FT $E T id id id + id$ F id $E T i

37、d + id$ $E T F id + id$ T FT $E T F id + id$ 預(yù)測預(yù)測分析器接受輸入分析器接受輸入id * id + id的前一部分動作的前一部分動作 3.3 自上而下分析自上而下分析棧棧 輸輸 入入 輸輸 出出 $E id id + id$ $E T id id + id$ E TE $E T F id id + id$ T FT $E T id id id + id$ F id $E T id + id$ $E T F id + id$ T FT $E T F id + id$ $E T id id + id$ F id 預(yù)測預(yù)測分析器接受輸入分析器接受輸入id

38、 * id + id的前一部分動作的前一部分動作 3.3 自上而下分析自上而下分析3.3.5 構(gòu)造預(yù)測分析表構(gòu)造預(yù)測分析表 （1）對文法的每個產(chǎn)生式對文法的每個產(chǎn)生式A ，執(zhí)行執(zhí)行(2)和和(3)（2）對）對FIRST( )的每個終結(jié)符的每個終結(jié)符a，把把A 加入加入MA, a（3）如果如果 在在FIRST( )中，對中，對FOLLOW(A)的每個終的每個終結(jié)符結(jié)符b（包括包括$）, 把把A 加入加入MA, b（4）M中中其它沒有定義的條目都是其它沒有定義的條目都是error3.3 自上而下分析自上而下分析非終非終結(jié)符結(jié)符 輸輸 入入 符符 號號 other b else . . .stmt

39、stmt other e_part e_part else stmte_part expr expr b 多重定義的條目多重定義的條目3.3 自上而下分析自上而下分析非終非終結(jié)符結(jié)符 輸輸 入入 符符 號號 other b else . . .stmt stmt other e_part e_part else stmtexpr expr b 消去多重定義消去多重定義3.3 自上而下分析自上而下分析3.3.6 預(yù)測分析的錯誤恢復(fù)預(yù)測分析的錯誤恢復(fù)1、先對編譯器的錯誤處理做一個概述先對編譯器的錯誤處理做一個概述 詞法錯誤，如標(biāo)識符、關(guān)鍵字或算符的拼寫詞法錯誤，如標(biāo)識符、關(guān)鍵字或算符的拼寫錯錯 語

40、法錯誤，如算術(shù)表達(dá)式的括號不配對語法錯誤，如算術(shù)表達(dá)式的括號不配對 語義錯誤，如算符作用于不相容的運(yùn)算對象語義錯誤，如算符作用于不相容的運(yùn)算對象 邏輯錯誤，如無窮的遞歸調(diào)用邏輯錯誤，如無窮的遞歸調(diào)用3.3 自上而下分析自上而下分析2、分析器對錯誤處理的基本目標(biāo)、分析器對錯誤處理的基本目標(biāo) 清楚而準(zhǔn)確地報告錯誤的出現(xiàn)，并盡量少出清楚而準(zhǔn)確地報告錯誤的出現(xiàn)，并盡量少出現(xiàn)現(xiàn)偽錯誤偽錯誤 迅速地從每個錯誤中恢復(fù)過來，以便診斷后迅速地從每個錯誤中恢復(fù)過來，以便診斷后面的錯誤面的錯誤 它不應(yīng)該使正確程序的處理速度降低太多它不應(yīng)該使正確程序的處理速度降低太多 3.3 自上而下分析自上而下分析3、非遞歸預(yù)測分

41、析在什么場合下發(fā)現(xiàn)錯誤、非遞歸預(yù)測分析在什么場合下發(fā)現(xiàn)錯誤棧頂?shù)慕K結(jié)符和下一個輸入符號不匹配棧頂?shù)慕K結(jié)符和下一個輸入符號不匹配a + b $輸入輸入預(yù)測分析程序預(yù)測分析程序分析表分析表M輸出輸出 XYZ$棧棧3.3 自上而下分析自上而下分析3、非遞歸預(yù)測分析在什么場合下發(fā)現(xiàn)錯誤、非遞歸預(yù)測分析在什么場合下發(fā)現(xiàn)錯誤棧頂是非終結(jié)符棧頂是非終結(jié)符A，輸入符號是輸入符號是a，而而MA , a是是空白空白a + b $輸入輸入預(yù)測分析程序預(yù)測分析程序分析表分析表M輸出輸出 XYZ$棧棧3.3 自上而下分析自上而下分析4、非遞歸預(yù)測分析：采用、非遞歸預(yù)測分析：采用緊急方式的錯誤恢復(fù)緊急方式的錯誤恢復(fù)發(fā)現(xiàn)錯

42、誤時，分析器每次拋棄一個輸入記號，直發(fā)現(xiàn)錯誤時，分析器每次拋棄一個輸入記號，直到輸入記號屬于某個指定的同步記號集合為止到輸入記號屬于某個指定的同步記號集合為止5、同步、同步詞法分析器當(dāng)前提供的記號流能夠構(gòu)成的語法構(gòu)詞法分析器當(dāng)前提供的記號流能夠構(gòu)成的語法構(gòu)造，正是語法分析器所期望的造，正是語法分析器所期望的不同步的例子不同步的例子語法分析器期望剩余的前綴構(gòu)成過程調(diào)用語句，語法分析器期望剩余的前綴構(gòu)成過程調(diào)用語句，而實(shí)際剩余的前綴形成賦值語句而實(shí)際剩余的前綴形成賦值語句3.3 自上而下分析自上而下分析6、同步記號集合的選擇、同步記號集合的選擇把把FOLLOW(A)的所有終結(jié)符放入非終結(jié)符的所有終

43、結(jié)符放入非終結(jié)符A的的同步記號集合同步記號集合3.3 自上而下分析自上而下分析6、同步記號集合的選擇、同步記號集合的選擇把把FOLLOW(A)的所有終結(jié)符放入非終結(jié)符的所有終結(jié)符放入非終結(jié)符A的的同步記號集合同步記號集合if expr then stmt（then和分號等記號是和分號等記號是expr的同步記號）的同步記號）3.3 自上而下分析自上而下分析6、同步記號集合的選擇、同步記號集合的選擇把把FOLLOW(A)的所有終結(jié)符放入非終結(jié)符的所有終結(jié)符放入非終結(jié)符A的的同步記號集合同步記號集合把高層構(gòu)造的開始符號加到低層構(gòu)造的同步記號把高層構(gòu)造的開始符號加到低層構(gòu)造的同步記號集合中集合中3.3

44、 自上而下分析自上而下分析6、同步記號集合的選擇、同步記號集合的選擇把把FOLLOW(A)的所有終結(jié)符放入非終結(jié)符的所有終結(jié)符放入非終結(jié)符A的的同步記號集合同步記號集合把高層構(gòu)造的開始符號加到低層構(gòu)造的同步記號把高層構(gòu)造的開始符號加到低層構(gòu)造的同步記號集合中集合中a = expr; if (語句的開始符號作為表達(dá)式的同步記號，以免表語句的開始符號作為表達(dá)式的同步記號，以免表達(dá)式出錯又遺漏分號時忽略達(dá)式出錯又遺漏分號時忽略if語句等一大段程序語句等一大段程序)3.3 自上而下分析自上而下分析6、同步記號集合的選擇、同步記號集合的選擇把把FOLLOW(A)的所有終結(jié)符放入非終結(jié)符的所有終結(jié)符放入非

45、終結(jié)符A的的同步記號集合同步記號集合把高層構(gòu)造的開始符號加到低層構(gòu)造的同步記號把高層構(gòu)造的開始符號加到低層構(gòu)造的同步記號集合中集合中把把FIRST(A)的終結(jié)符加入的終結(jié)符加入A的同步記號集合的同步記號集合a = expr; , if （語句的開始符號作為語句的同步符號，以免多出語句的開始符號作為語句的同步符號，以免多出一個逗號時會把一個逗號時會把if語句忽略了）語句忽略了）3.3 自上而下分析自上而下分析6、同步記號集合的選擇、同步記號集合的選擇把把FOLLOW(A)的所有終結(jié)符放入非終結(jié)符的所有終結(jié)符放入非終結(jié)符A的的同步記號集合同步記號集合把高層構(gòu)造的開始符號加到低層構(gòu)造的同步記號把高層

46、構(gòu)造的開始符號加到低層構(gòu)造的同步記號集合中集合中把把FIRST(A)的終結(jié)符加入的終結(jié)符加入A的同步記號集合的同步記號集合如果非終結(jié)符可以產(chǎn)生空串，若出錯時棧頂是這如果非終結(jié)符可以產(chǎn)生空串，若出錯時棧頂是這樣的非終結(jié)符，則可以使用推出空串的產(chǎn)生式樣的非終結(jié)符，則可以使用推出空串的產(chǎn)生式3.3 自上而下分析自上而下分析非終非終結(jié)符結(jié)符 輸輸 入入 符符 號號 id+ . . .EETE E E+TE TTFT T 出錯出錯T T FT . . . 例例 棧頂為棧頂為T ，面臨，面臨id時出錯時出錯3.3 自上而下分析自上而下分析非終非終結(jié)符結(jié)符 輸輸 入入 符符 號號 id+ . . .EETE

47、 E E+TE TTFT T 出錯，出錯，用用T T T FT . . . T 可以產(chǎn)生空串，報錯并用可以產(chǎn)生空串，報錯并用T 3.3 自上而下分析自上而下分析同步記號集合的選擇同步記號集合的選擇把把FOLLOW(A)的所有終結(jié)符放入非終結(jié)符的所有終結(jié)符放入非終結(jié)符A的的同步記號集合同步記號集合把高層結(jié)構(gòu)的開始符號加到低層結(jié)構(gòu)的同步記號把高層結(jié)構(gòu)的開始符號加到低層結(jié)構(gòu)的同步記號集合中集合中把把FIRST(A)的終結(jié)符加入的終結(jié)符加入A的同步記號集合的同步記號集合如果非終結(jié)符可以產(chǎn)生空串，若出錯時棧頂是這如果非終結(jié)符可以產(chǎn)生空串，若出錯時棧頂是這樣的非終結(jié)符，則可以使用推出空串的產(chǎn)生式樣的非終結(jié)

48、符，則可以使用推出空串的產(chǎn)生式如果終結(jié)符在棧頂而不能匹配，彈出此終結(jié)符如果終結(jié)符在棧頂而不能匹配，彈出此終結(jié)符 3.4 自下而上分析自下而上分析 3.4.1 歸約歸約 例例 S aABe A Abc | bB d3.4 自下而上分析自下而上分析 3.4.1 歸約歸約 例例 S aABe A Abc | bB dabbcde（讀入（讀入ab）ab3.4 自下而上分析自下而上分析 3.4.1 歸約歸約 例例 S aABe A Abc | bB dabbcdeaAbcde（歸約）（歸約）abA3.4 自下而上分析自下而上分析 3.4.1 歸約歸約 例例 S aABe A Abc | bB dabbc

49、deaAbcde（再讀入（再讀入bc）abAbc3.4 自下而上分析自下而上分析 3.4.1 歸約歸約 例例 S aABe A Abc | bB dabbcdeaAbcdeaAde（歸約）（歸約）abAbAc3.4 自下而上分析自下而上分析 3.4.1 歸約歸約 例例 S aABe A Abc | bB dabbcdeaAbcdeaAde（再讀入（再讀入d）abAbdAc3.4 自下而上分析自下而上分析 3.4.1 歸約歸約 例例 S aABe A Abc | bB dabbcdeaAbcdeaAdeaABe（歸約）（歸約）abAbdAcB3.4 自下而上分析自下而上分析 3.4.1 歸約歸約

50、 例例 S aABe A Abc | bB dabbcdeaAbcdeaAdeaABe(再讀入再讀入e)eabAbdAcB3.4 自下而上分析自下而上分析 3.4.1 歸約歸約 例例 S aABe A Abc | bB dabbcdeaAbcdeaAdeaABeS（歸約）（歸約）SeabAbdAcB3.4 自下而上分析自下而上分析 3.4.1 歸約歸約 例例 S aABe A Abc | bB dabbcdeaAbcdeaAdeaABeS S rm aABe rm aAde rm aAbcde rm abbcdeSeabAbdAcB3.4 自下而上分析自下而上分析 3.4.2 句柄句柄句型的句

51、型的句柄句柄是和某產(chǎn)生式右部匹配的子串，是和某產(chǎn)生式右部匹配的子串，并且，把它歸約成該產(chǎn)生式左部的非終結(jié)符并且，把它歸約成該產(chǎn)生式左部的非終結(jié)符代表了最右推導(dǎo)過程的逆過程的一步代表了最右推導(dǎo)過程的逆過程的一步S aABe A Abc | bB dS rm aABe rm aAde rm aAbcde rm abbcde句柄的右邊僅含終結(jié)符句柄的右邊僅含終結(jié)符如果文法二義，那么句柄可能不唯一如果文法二義，那么句柄可能不唯一3.4 自下而上分析自下而上分析 例例 句柄不唯一句柄不唯一E E + E | E E | (E ) | id3.4 自下而上分析自下而上分析 例例 句柄不唯一句柄不唯一E E

52、 + E | E E | (E ) | idE rm E E rm E E + E rm E E + id3 rm E id2 + id3 rm id1 id2 + id3 3.4 自下而上分析自下而上分析 例例 句柄不唯一句柄不唯一E E + E | E E | (E ) | idE rm E E E rm E + E rm E E + Erm E + id3 rm E E + id3rm E E + id3 rm E id2 + id3 rm E id2 + id3 rm id1 id2 + id3 rm id1 id2 + id3 在句型在句型E E + id3中，句柄不唯一中，句柄不唯

53、一3.4 自下而上分析自下而上分析 3.4.3 用棧實(shí)現(xiàn)移進(jìn)用棧實(shí)現(xiàn)移進(jìn) 歸約分析歸約分析先通過先通過移進(jìn)移進(jìn) 歸約分析器在分析輸入串歸約分析器在分析輸入串id1 id2 + id3時時的動作序列的動作序列來了解移進(jìn)來了解移進(jìn) 歸約分析的工作方式歸約分析的工作方式3.4 自下而上分析自下而上分析 棧棧 輸輸 入入 動動 作作 $ id1 id2 + id3$ 3.4 自下而上分析自下而上分析 棧棧 輸輸 入入 動動 作作 $ id1 id2 + id3$ 移進(jìn)移進(jìn) 3.4 自下而上分析自下而上分析 棧棧 輸輸 入入 動動 作作 $ id1 id2 + id3$ 移進(jìn)移進(jìn) $ id1 id2 +

54、 id3$ 3.4 自下而上分析自下而上分析 棧棧 輸輸 入入 動動 作作 $ id1 id2 + id3$ 移進(jìn)移進(jìn) $ id1 id2 + id3$ 按按E id歸約歸約 3.4 自下而上分析自下而上分析 棧棧 輸輸 入入 動動 作作 $ id1 id2 + id3$ 移進(jìn)移進(jìn) $ id1 id2 + id3$ 按按E id歸約歸約 $E id2 + id3$ 3.4 自下而上分析自下而上分析 棧棧 輸輸 入入 動動 作作 $ id1 id2 + id3$ 移進(jìn)移進(jìn) $ id1 id2 + id3$ 按按E id歸約歸約 $E id2 + id3$移進(jìn)移進(jìn) 3.4 自下而上分析自下而上分析

55、 棧棧 輸輸 入入 動動 作作 $ id1 id2 + id3$ 移進(jìn)移進(jìn) $ id1 id2 + id3$ 按按E id歸約歸約 $E id2 + id3$移進(jìn)移進(jìn) $E id2 + id3$ 3.4 自下而上分析自下而上分析 棧棧 輸輸 入入 動動 作作 $ id1 id2 + id3$ 移進(jìn)移進(jìn) $ id1 id2 + id3$ 按按E id歸約歸約 $E id2 + id3$移進(jìn)移進(jìn) $E id2 + id3$ 移進(jìn)移進(jìn) 3.4 自下而上分析自下而上分析 棧棧 輸輸 入入 動動 作作 $ id1 id2 + id3$ 移進(jìn)移進(jìn) $ id1 id2 + id3$ 按按E id歸約歸約 $

56、E id2 + id3$移進(jìn)移進(jìn) $E id2 + id3$ 移進(jìn)移進(jìn) $E id2 + id3$ 3.4 自下而上分析自下而上分析 棧棧 輸輸 入入 動動 作作 $ id1 id2 + id3$ 移進(jìn)移進(jìn) $ id1 id2 + id3$ 按按E id歸約歸約 $E id2 + id3$移進(jìn)移進(jìn) $E id2 + id3$ 移進(jìn)移進(jìn) $E id2 + id3$ 按按E id歸約歸約 3.4 自下而上分析自下而上分析 棧棧 輸輸 入入 動動 作作 $ id1 id2 + id3$ 移進(jìn)移進(jìn) $ id1 id2 + id3$ 按按E id歸約歸約 $E id2 + id3$移進(jìn)移進(jìn) $E id2

57、 + id3$ 移進(jìn)移進(jìn) $E id2 + id3$ 按按E id歸約歸約 $E E + id3$ 3.4 自下而上分析自下而上分析 棧棧 輸輸 入入 動動 作作 $ id1 id2 + id3$ 移進(jìn)移進(jìn) $ id1 id2 + id3$ 按按E id歸約歸約 $E id2 + id3$移進(jìn)移進(jìn) $E id2 + id3$ 移進(jìn)移進(jìn) $E id2 + id3$ 按按E id歸約歸約 $E E + id3$ 移進(jìn)移進(jìn) 3.4 自下而上分析自下而上分析 棧棧 輸輸 入入 動動 作作 $ id1 id2 + id3$ 移進(jìn)移進(jìn) $ id1 id2 + id3$ 按按E id歸約歸約 $E id2

58、+ id3$移進(jìn)移進(jìn) $E id2 + id3$ 移進(jìn)移進(jìn) $E id2 + id3$ 按按E id歸約歸約 $E E + id3$ 移進(jìn)移進(jìn) $E E+ id3$ 3.4 自下而上分析自下而上分析 棧棧 輸輸 入入 動動 作作 $ id1 id2 + id3$ 移進(jìn)移進(jìn) $ id1 id2 + id3$ 按按E id歸約歸約 $E id2 + id3$移進(jìn)移進(jìn) $E id2 + id3$ 移進(jìn)移進(jìn) $E id2 + id3$ 按按E id歸約歸約 $E E + id3$ 移進(jìn)移進(jìn) $E E+ id3$ 移進(jìn)移進(jìn) 3.4 自下而上分析自下而上分析 棧棧 輸輸 入入 動動 作作 $ id1 id

59、2 + id3$ 移進(jìn)移進(jìn) $ id1 id2 + id3$ 按按E id歸約歸約 $E id2 + id3$移進(jìn)移進(jìn) $E id2 + id3$ 移進(jìn)移進(jìn) $E id2 + id3$ 按按E id歸約歸約 $E E + id3$ 移進(jìn)移進(jìn) $E E+ id3$ 移進(jìn)移進(jìn) $E E+id3 $ 3.4 自下而上分析自下而上分析 棧棧 輸輸 入入 動動 作作 $ id1 id2 + id3$ 移進(jìn)移進(jìn) $ id1 id2 + id3$ 按按E id歸約歸約 $E id2 + id3$移進(jìn)移進(jìn) $E id2 + id3$ 移進(jìn)移進(jìn) $E id2 + id3$ 按按E id歸約歸約 $E E + i

60、d3$ 移進(jìn)移進(jìn) $E E+ id3$ 移進(jìn)移進(jìn) $E E+id3 $按按E id歸約歸約 3.4 自下而上分析自下而上分析 棧棧 輸輸 入入 動動 作作 $ id1 id2 + id3$ 移進(jìn)移進(jìn) $ id1 id2 + id3$ 按按E id歸約歸約 $E id2 + id3$移進(jìn)移進(jìn) $E id2 + id3$ 移進(jìn)移進(jìn) $E id2 + id3$ 按按E id歸約歸約 $E E + id3$ 移進(jìn)移進(jìn) $E E+ id3$ 移進(jìn)移進(jìn) $E E+id3 $按按E id歸約歸約 $E E+E $ 3.4 自下而上分析自下而上分析 棧棧 輸輸 入入 動動 作作 $ id1 id2 + id3