【正文】 1 第四章 語法分析 167。 引言 167。 自頂向下語法分析 167。 自底向上語法分析 167。 語法分析程序的自動生成 2 167。 引言 一、語法分析任務 二、語法分析方法 語法 分析方法 語法 分析方法 3 一、語法分析任務 詞法分析階段，主要介紹了單詞符號的結(jié)構(gòu)、識別（用狀態(tài)轉(zhuǎn)換圖），描述（通過正規(guī)式）以及有限自動機 DFA和 NFA。 在一個編譯程序?qū)δ硞€源程序完成了詞法工作以后 ,就進入了語法分析階段。由詞法分析程序所產(chǎn)生的單詞符號流，作為語法分析程序的輸入串，按文法規(guī)則分析檢查是否構(gòu)成了合法的句子。 首先來了解一下語法分析的任務 。 4 根據(jù)語法規(guī)則對各種語法成分進行分析 ， 確定它們的語法關(guān)系以檢查語法上的正確和錯誤 ， 并指出錯誤的性質(zhì)和出錯位置 。 如： if B then S1 else S2 若寫成 if B then else S2 就錯了 （ then后少一個 S1） 5 2. 根據(jù)語法符號進行一定語義處理加工 如語法分析過程得到一個合法的句子時 ， 往往同時進行必要的語義分析等 如：當遇到處理表達式 a+b*c時 ， 若該表達式語法關(guān)系正確 ， 就可以進行語義處理加工 ， 可將該表達式變成中間語言 ， 以便以后生成目標程序 6 二、語法分析方法 語法分析方法很多，但能夠產(chǎn)生計算機程序并能得到廣泛應用的主要有兩大類，按照生成語法樹的順序，分別稱為 自頂向下和 自底向上 分析方法。 7 語法 分析方法 （ 1） 遞歸下降分析法 （ 2） LL（ 1） 分析法 8 語法 分析方法 （ 1） 簡單優(yōu)先分析法 （ 2） 算符優(yōu)先分析法 （ 3） LR分析法 9 167。 自頂向下語法分析 一、消除左遞歸 二、消除回溯 三、遞歸下降分析法 四、 LL(1)分析法 10 一、消除左遞歸 （ 1） 問題的提出 在自頂向下分析過程中 ， 假定現(xiàn)在輪到要用非終結(jié)符 U去匹配輸入串 ， 而在文法中第一條規(guī)則是 U∷ ＝ U… 這樣會產(chǎn)生什么問題呢 ？ 11 若文法具有間接左遞歸 ， 即有 U?＋ U… 那么 ， 也會發(fā)生上述問題 。 12 例如：已知文法 G[S] S ∷ ＝ AB A ∷ ＝ bB|Aa (存在直接左遞歸 ） B ∷ ＝ Sb|a 現(xiàn)分析符號串 baabaab是否是文法 G的句子 。 其分析過程如下： 13 （ 2） 消除左遞歸方法 1） 用重復表示法 （ 擴充的ＢＮＦ表示法 ） 改寫語法規(guī)則 假定一個文法中有關(guān)于非終結(jié)符的規(guī)則為 Ａ ∷ ＝Ａ α ｜ β 其中 α 非空 ， β 不以Ａ開頭 ， 則等價地改寫為 Ａ ∷ ＝ β ｛ α ｝ 14 例如 ， 下述直接左遞歸規(guī)則： Ｅ ∷ ＝Ｅ＋Ｔ｜Ｔ 可改寫為 Ｅ ∷ ＝Ｔ ｛ ＋Ｔ ｝ E E T ＋ E T ＋ E T ＋ T 等價 E T + T + T + T T + T + T + T 15 同樣 ， 規(guī)則 Ｔ ∷ ＝Ｔ *Ｆ｜Ｔ／Ｆ｜Ｆ 等價于Ｔ ∷ ＝Ｔ（ *Ｆ｜／Ｆ）｜Ｆ 可改寫為 Ｔ ∷ ＝Ｆ ｛ *Ｆ｜／Ｆ ｝ 這樣 ， 改寫后的文法消除了直接左遞歸 。 可以證明 ，改寫前后的文法 是等價的 。 16 2） 改寫方法規(guī)則消除直接左遞歸 還可用另一種方法來改寫形如文法規(guī)則Ａ ∷ ＝Ａα ｜ β 的直接左遞歸 。 對Ａ引入一個新的非終結(jié)符Ａ ′ ， 將Ａ ∷ ＝Ａ α ｜ β 等價寫成 Ａ ∷ ＝ β Ａ ′ Ａ ′ ∷ ＝ α Ａ ′ ｜ ε 由于 β 不以Ａ開頭 ， α 不以Ａ ′ 開頭 ， 因此改寫后兩條規(guī)則不是直接左遞歸 。 同樣可以證明這種形式和原來形式是等價的 。 17 A A α β A α A α β α α α 等價 A β A? α A? α A? α A? ε β α α α 18 就一般而言 ， 關(guān)于Ａ的規(guī)則具有下面形式： Ａ ∷ ＝Ａ α １ ｜Ａ α ２ ｜ …｜Ａ α n｜ β １ ｜ β ２ ｜ …｜ β n 這時可改寫成如下形式： Ａ ∷ ＝ A(α １ ｜ α ２ ｜ …｜ α n｜ ) ｜ β １ ｜ β ２ ｜ …｜ β n 由消除直接左遞歸方法 ， 得 Ａ ∷ ＝ (β １ ｜ β ２ ｜ …｜ β n)Ａ ′ Ａ ′ ∷ ＝ (α １ ｜ α ２ ｜ …｜ α n)Ａ ′ ｜ ε 19 例如： A ∷ ＝ Ac|Aad|bd|e 等價于 A ∷ ＝ A（ c|ad） |bd|e ， 所以可以改寫成： A ∷ ＝ （ bd|e） A’ A’ ∷ ＝ （ c|ad） A’ | ε 20 例如：有文法 Ｅ ∷ ＝Ｅ＋Ｔ｜Ｔ ， Ｔ ∷ ＝ T*Ｆ｜Ｆ ， Ｆ ∷ ＝ （ Ｅ ） ｜ i 用上述方法可改寫成： Ｅ ∷ ＝ＴＥ ′ ， Ｅ ′ ∷ ＝＋ＴＥ ′ ｜ ε Ｔ ∷ ＝ＦＴ ′ ， Ｔ ′ ∷ ＝ *ＦＴ ′ ｜ ε ， Ｆ ∷ ＝ （ Ｅ ） ｜ i 21 上述兩種方法可消除任意直接左遞歸 ， 但不能消除間接左遞歸 例如 ， 有文法Ｇ ［ Ｓ ］ Ｓ ∷ ＝Ｑ c｜ c Ｑ ∷ ＝Ｒ b｜ b Ｒ ∷ ＝Ｓ a｜ a 該文法無直接左遞歸 ， 但有間接左遞歸 ， 例如有 Ｓ ? Ｑ c ? Ｒ bc ? Ｓ abc 即Ｓ ?＋Ｓ abc 22 3） 消除間接左遞歸 對于間接左遞歸先將間接左遞歸變成直接左遞歸 ， 然后再消除直接左遞歸 例如； A ∷ ＝ aB|Bb (1) B ∷ ＝ Ac|d (2) 先將（ 1）代入（ 2）中，得 B ∷ ＝ Bbc|aBc|d (3) 由此將 (3)改寫為； B ∷ ＝（ aBc|d)B? B?∷ ＝ bcB?|? 加入文法開始符號的產(chǎn)生式得消除左遞歸后的等價文法為： A ∷ ＝ aB|Bb B ∷ ＝ (aBc|d)B? B?∷ ＝ bcB?|? 23 4) 消除文法遞歸的一般算法 要求：文法不含形如Ａ ? ＋Ａ的推導 ， 也不存在Ａ ∷ ＝ ε這樣規(guī)則 ， 算法思想如下： ①將文法Ｇ的所有非終結(jié)符整理成某種順序Ｕ１，Ｕ２， … Ｕ n ② 從 U1開始消除 U1規(guī)則的直接左遞歸 ③用左部為 U1的所有規(guī)則右部替換左部為 U2，右部以 U1開始的規(guī)則中的 U1，并消除 U2規(guī)則的直接左遞歸。 ④用類似的方法用 U1， U2的右部替換左部為 U3，右部以 U1，U2開始的規(guī)則中，消除 U3規(guī)則中的直接左遞歸。 ⑤重復上一步，直到最后把左部為 U1， U2， …Un1的右部帶入 Un規(guī)則中，并消除 Un中的直接左遞歸。 ⑥消除多余規(guī)則 24 ① 將文法Ｇ的所有非終結(jié)符整理成某種順序Ｕ １ ， Ｕ ２ ， …Ｕ n， 然后按此順序執(zhí)行下一步； ② 執(zhí)行循環(huán)語句： ＦＯＲ i:＝１ ＴＯ n ＤＯ ＢＥＧＩＮ ＦＯＲ j∶ ＝１ ＴＯ i1 ＤＯ ＢＥＧＩＮ 把形如 Ｕ i∷ ＝Ｕ jy的規(guī)則改寫成 Ui∷ ＝ x１ y｜ x２ y｜ …｜ xky 其中 Uj∷ ＝ x１ ｜ x２ ｜ …｜ xk 是 Uj的所有規(guī)則 ＥＮＤ 消除關(guān)于 Ui規(guī)則中直接左遞歸 ＥＮＤ ③ 去掉多余規(guī)則（如果有的話） 消除左遞歸算法 ： 25 例 ［ Ｓ ］ Ｓ ∷ ＝Ａ a｜ b Ａ ∷ ＝Ａ c｜Ｓ d｜ e 應用上述算法 ， 將非終結(jié)符排列Ｓ ， Ａ 。 然后執(zhí)行循環(huán)語句 ＦＯＲ i∶ ＝１ ＴＯ 2 ＤＯ ＢＥＧＩＮ ＦＯＲ j∶ ＝１ ＴＯ i１ ＤＯ ＢＥＧＩＮ … ＥＮＤ 消除 Ui規(guī)則中直接左遞歸 ＥＮＤ 26 當 i＝１時 ， 上述語句對文法Ｇ不產(chǎn)生影響 。 當 i＝２時 ， 應改寫規(guī)則Ａ ∷ ＝Ｓ d， 因為Ｓ ∷ ＝Ａ a｜ b， 所以Ａ ∷ ＝Ａ ad｜ bd， 此時文法Ｇ變換成為 Ｓ ∷ ＝Ａ a｜ b Ａ ∷ ＝Ａ c ｜Ａ ad｜ bd｜ e 消除關(guān)于Ａ的直接左遞歸即可 。 Ｓ ∷ ＝Ａ a｜ b Ａ ∷ ＝ bdＡ ’ ｜ eＡ ’ Ａ ’ ∷ ＝ cＡ ’ ｜ adＡ ’ ｜ ? 該文法沒有多余的規(guī)則 。 27 二、消除回溯 （ 1） 回溯分析方法定義 在進行自頂向下語法分析時 ， 對于文法規(guī)則中具有同一左部而右部有不同規(guī)則時 ， 在分析時按順序一個個試探 ， 若能分析下去則成 ， 否則在退回到出錯點換另一規(guī)則重新試探 。 這種方法稱回溯分析方法 。 其實質(zhì)就是使用不同規(guī)則反復試探 。 如： S∷ ＝ cAd A∷ ＝ ab|a 要判斷 “ cad”是否為該文法的句子 。 28 若按自上而下語法分析程序的步驟進行分析判斷，其過程如下： P: S∷=cAd A∷=ab|a S A d c S?cAd cad i 29 若按自上而下語法分析程序的步驟進行分析判斷，其過程如下： P: S∷=cAd A∷=ab|a S A d c S?cAd ?cabd cad i a b 30 若按自上而下語法分析程序的步驟進行分析判斷，其過程如下： P: S∷=cAd A∷=ab|a S A d c S?cAd ?cabd cad i a b ERROR! 31 （ 2） 回溯問題的解決 1） 路標法 定義：設有規(guī)則 U∷ ＝ a1V1|a2V2|…|a nVn 若 ai為互不相同的終結(jié)符時，將 ai作為路標，當被分析符號串為 ai時，便可按規(guī)則 U∷ ＝ aiVi往下分析，這樣可以消除回溯。 如： 語句 ∷ ＝ 變量 ： ＝ 表達式 |if 布爾表達式 then 語句 當分析語句： if AB then A:=B時，我們可以根據(jù)第二個產(chǎn)生式以 if開始直接選用它作判斷。 if在這里就是路標 32 一般地 ， 設 U為文法Ｇ的任意非終結(jié)符號 ， 若 U有如下規(guī)則 U∷ ＝ α １ ｜ α ２ ｜ …｜ α n α i ∈ Ｖ + 若定義任一個選擇 α i的所有可能推出終結(jié)符號串的首符號集 FIRST（ α i ） 為 FIRST（ α i） ＝ ｛ a｜ α i?*a… ， a∈ Ｖ Ｔ ｝ 顯然 FIRST （ α i） ?Ｖ Ｔ 33 為了避免回溯 ， 我們對文法要求是： FIRST(α i ） ∩ FIRST(α j ） ＝ ?（ i≠j ） 如：當前輸入符號為 b(b ∈ Ｖ Ｔ )， 如果 b ∈ FIRST(α i） ， 則可以選擇第 i個產(chǎn)生式去匹配輸入串 。 34 一般地說 ， 如果有規(guī)則 U∷ ＝ aβ １ ｜ aβ ２ ｜ …｜ aβ n｜ γ 則可以將這些規(guī)則寫成 U ∷ ＝ aU′ ｜ γ U′ ∷ ＝ β １ ｜ β ２ ｜ …｜ β n 其中 a稱為左公因子 ，