1、溫故知新溫故知新3.3 自上而下分析3.3.6 預測分析的錯誤恢復預測分析的錯誤恢復編譯器的錯誤概述編譯器的錯誤概述 : 詞法錯誤，如標識符、關鍵字或算符拼寫錯誤詞法錯誤，如標識符、關鍵字或算符拼寫錯誤 語法錯誤，如算術表達式的括號不配對語法錯誤，如算術表達式的括號不配對 語義錯誤，如算符作用于不相容的運算對象語義錯誤，如算符作用于不相容的運算對象 邏輯錯誤，如無窮的遞歸調用邏輯錯誤，如無窮的遞歸調用3.3 自上而下分析分析器對錯誤處理的基本目標分析器對錯誤處理的基本目標 清楚而準確地報告錯誤的出現清楚而準確地報告錯誤的出現 迅速地從每個錯誤中恢復過來，以便診斷后迅速地從每個錯誤中恢復過來，以

2、便診斷后面的錯誤，并盡量少出現面的錯誤，并盡量少出現偽錯誤偽錯誤 它不應該使正確程序的處理速度降低太多它不應該使正確程序的處理速度降低太多 3.3 自上而下分析非遞歸預測分析在什么場合下發現錯誤非遞歸預測分析在什么場合下發現錯誤棧頂的終結符和下一個輸入符號不匹配棧頂的終結符和下一個輸入符號不匹配棧頂是非終結符棧頂是非終結符A，輸入符號是，輸入符號是a，而，而MA , a是是空白空白3.3 自上而下分析非遞歸預測分析：采用非遞歸預測分析：采用緊急方式的錯誤恢復緊急方式的錯誤恢復 發現錯誤時，分析器每次拋棄一個輸入記發現錯誤時，分析器每次拋棄一個輸入記號，直到輸入記號屬于某個指定的號，直到輸入記號

3、屬于某個指定的同步同步記號記號集合為止。集合為止。同步同步詞法分析器當前提供的記號流能構成的語詞法分析器當前提供的記號流能構成的語法結構，正是語法分析器所期望的。法結構，正是語法分析器所期望的。3.3 自上而下分析同步記號集合的選擇同步記號集合的選擇把把FOLLOW(A)的所有終結符放入非終結符的所有終結符放入非終結符A的的同步記號集合。同步記號集合。if expr then（then是是expr的一個同步記號）的一個同步記號）3.3 自上而下分析同步記號集合的選擇同步記號集合的選擇把把FOLLOW(A)的所有終結符放入非終結符的所有終結符放入非終結符A的的同步記號集合。同步記號集合。把高層結

4、構的開始符號加到低層結構的同步記號把高層結構的開始符號加到低層結構的同步記號集合中。集合中。a := expr ; if （語句的開始符號作為表達式的同步符號，以（語句的開始符號作為表達式的同步符號，以免遺漏分號時忽略一大段程序。）免遺漏分號時忽略一大段程序。）3.3 自上而下分析同步記號集合的選擇同步記號集合的選擇把把FOLLOW(A)的所有終結符放入非終結符的所有終結符放入非終結符A的的同步記號集合。同步記號集合。把高層結構的開始符號加到低層結構的同步記號把高層結構的開始符號加到低層結構的同步記號集合中。集合中。把把FIRST(A)的終結符加入的終結符加入A的同步記號集合。的同步記號集合。

5、3.3 自上而下分析同步記號集合的選擇同步記號集合的選擇把把FOLLOW(A)的所有終結符放入非終結符的所有終結符放入非終結符A的的同步記號集合。同步記號集合。把高層結構的開始符號加到低層結構的同步記號把高層結構的開始符號加到低層結構的同步記號集合中。集合中。把把FIRST(A)的終結符加入的終結符加入A的同步記號集合。的同步記號集合。如果非終結符可以產生空串，若出錯時棧頂是這如果非終結符可以產生空串，若出錯時棧頂是這樣的非終結符，則可以使用產生空串的產生式。樣的非終結符，則可以使用產生空串的產生式。3.3 自上而下分析同步記號集合的選擇同步記號集合的選擇把把FOLLOW(A)的所有終結符放入

6、非終結符的所有終結符放入非終結符A的的同步記號集合。同步記號集合。把高層結構的開始符號加到低層結構的同步記號把高層結構的開始符號加到低層結構的同步記號集合中。集合中。把把FIRST(A)的終結符加入的終結符加入A的同步記號集合。的同步記號集合。如果非終結符可以產生空串，若出錯時棧頂是這如果非終結符可以產生空串，若出錯時棧頂是這樣的非終結符，則可以使用產生空串的產生式。樣的非終結符，則可以使用產生空串的產生式。如果終結符在棧頂而不能匹配，彈出此終結符。如果終結符在棧頂而不能匹配，彈出此終結符。 同步記號加到表同步記號加到表3.1的分析表上的分析表上非終非終結符結符輸輸 入入 符符 號號 id +

7、 * ( ) $E E TE E TE synch synchE E +TE E E T T FT synchT FT synch synchT T T * *FT T T F F id synch synchF (E) synch synch總結一下出錯的三種情況：總結一下出錯的三種情況：1 查表，表項是空白，棧頂不變，輸入串指查表，表項是空白，棧頂不變，輸入串指針后移；（相當于拋棄記號）針后移；（相當于拋棄記號）2 查表，表項是查表，表項是synch，彈棧，并且彈出的是，彈棧，并且彈出的是一個非終結符一個非終結符3 棧頂終結符和輸入串終結符不匹配，彈棧，棧頂終結符和輸入串終結符不匹配，彈棧

8、，將棧頂終結符彈出將棧頂終結符彈出棧輸入輸出$E+id*+id$出錯，跳過（用戶多輸入了+）$Eid*+id$id屬于first（E）$E Tid*+id$E T Fid*+id$E T idid*+id$E T *+id$E T F* *+id$E T F+id$出錯：“”正好在F的同步記號集合中，無須跳過任何記號；F被彈出；（用戶少輸入了id）$E T +id$E +id$E T+id$E Tid$E T Fid$E T idid$E T $E $文法文法G: S-aSb | P P-bPc | bQc Q-Qa | a（1）它是）它是chomsky哪一型文法？哪一型文法？（2）它生成的語

9、言是什么？）它生成的語言是什么？（3）給出提取左因子、消除左遞歸之后的文法）給出提取左因子、消除左遞歸之后的文法G（4）求出文法）求出文法G每個非終結符的每個非終結符的First集和集和Follow集集（5）構建文法）構建文法G的的LL（1）預測分析表）預測分析表（6）文法）文法G是否是是否是LL（1）文法）文法（7）利用非遞歸預測分析程序，驗證）利用非遞歸預測分析程序，驗證abacb是否是是否是文法文法G描述的語言的句子描述的語言的句子文法文法G: S-aSb | P P-bPc | bQc Q-Qa | a（1）它是）它是chomsky哪一型文法？哪一型文法？答：它是答：它是2型文法，即上

10、下文無關文法。型文法，即上下文無關文法。（2）它生成的語言是什么？）它生成的語言是什么？答：答：aibjakcjbi | i=0; j,k=1文法文法G: S-aSb | P P-bPc | bQc Q-Qa | a（3）給出提取左因子、消除左遞歸之后的文法）給出提取左因子、消除左遞歸之后的文法答：答： S-aSb | P P-bP P-Pc | Qc Q-aQ Q-aQ | S-aSb | PP-bPP-Pc | QcQ-aQQ-aQ | First(S)=a,bFirst(P)=bFirst(P)=a,bFirst(Q)=aFirst(Q)=a, Follow(S)=$,bFollow(P)=$,b,cFollow(P)=$,b,cFollow(Q)=cFollow(Q)=c （4）求出每個非終結符的）求出每個非終結符的First集和集和Follow集集（5）構建）構建LL（1）預測分析表）預測分析表 輸入符號輸入符號非終結符非終結符abc$SS-aSbS-PPP-bPPP-QcP-PcQQ-aQQQ-aQQ-（6）文法）文法G是否是是否是LL（1）文法）文法答：構建出的答：構建出的LL（1）分析表不含有多重定）分析表不含有多重定義的條目，因此文法義的條目，因此文法G是是LL（1）文法。）文法。（7）利用非遞歸預測分析程序，驗證）利用非遞歸預測分析