【正文】 b|a 要判斷 “ cad”是否為該文法的句子 ， 可以分別用 A∷ ＝ ab和 A∷ ＝ a代入第一個(gè)產(chǎn)生式中試探 。 自頂向下語(yǔ)法分析 一、自頂向下分析方法的問(wèn)題及其解決辦法 （ 2） 回溯問(wèn)題的解決 1） 路標(biāo)法 定義：設(shè)有規(guī)則 U∷ ＝ a1V1|a2V2|…|a nVn 若 ai為互不相同的終結(jié)符時(shí)，將 ai作為路標(biāo)，當(dāng)被分析符號(hào)串為 ai時(shí)，便可按規(guī)則 U∷ ＝ aiVi往下分析，這樣可以消除回溯。 if在這里就是路標(biāo) 因此，我們?cè)谠O(shè)計(jì)程序設(shè)計(jì)語(yǔ)言時(shí)，要考慮語(yǔ)法規(guī)則各選擇項(xiàng)開始符號(hào)互不相同 22 167。 這樣 ， 就可能 根據(jù)當(dāng)時(shí)讀進(jìn)的符號(hào)是屬于哪個(gè)選擇的 FIRST（ α i ） ， 來(lái)唯一地確定該選用哪個(gè)選擇來(lái)匹配輸入串 。 23 一般地 ， 設(shè) U為文法Ｇ的任意非終結(jié)符號(hào) ， 若 U U∷ ＝ α１ ｜ α２ ｜ … ｜ αn α i ∈ Ｖ + 若定義任一個(gè)選擇 α i的所有可能推出終結(jié)符號(hào)串的首符號(hào)集 FIRST（ α i ）FIRST（ α i） ＝ ｛ a｜ α i?*a… ， a∈ Ｖ Ｔ ｝ 顯然 FIRST （ α i） ?Ｖ Ｔ 167。 24 2) 提取左因子法 當(dāng)文法不滿足上述路標(biāo)法條件 ， 即右部各規(guī)則首符號(hào)相同時(shí) ， 我們可以 采用提取左因子法對(duì)文法進(jìn)行改寫 。 自頂向下語(yǔ)法分析 一、自頂向下分析方法的問(wèn)題及其解決辦法 25 注意 ： U∷ ＝ xy | x,可寫成 U∷ ＝ x(y | ?)， 當(dāng)分析符號(hào)串遇到 ? 時(shí) ， 認(rèn)為總能匹配 ， 可以一直分析下去 。 167。 可見沒(méi)出現(xiàn)回溯現(xiàn)象。 為避免分析時(shí)回溯 ， 可以將文法改寫成： 167。 自頂向下語(yǔ)法分析 一、自頂向下分析方法的問(wèn)題及其解決辦法 消除左遞歸 28 （ 1） 問(wèn)題的提出 在自頂向下分析過(guò)程中 ， 假定現(xiàn)在輪到要用非終結(jié)符 U去匹配輸入串 ， U∷ ＝ U… 它是一條直接左遞歸規(guī)則 ， 這種左遞歸文法將使上述自頂向下的分析過(guò) 程陷入無(wú)限循環(huán) ， 即： 當(dāng)試圖用 U去匹配輸入串時(shí)會(huì)發(fā)現(xiàn) ， 在沒(méi)有吃進(jìn)任何輸入符號(hào)的情況下 ， 又得重新要求 U去匹配 ， 如此循環(huán)下去而無(wú)終止 。 167。 其分析過(guò)程如下： S ?AB ?bBB ?bSbB ? bABbB ? bbBBbB(得第二個(gè)字符與輸入串不匹配） S ?AB ?bBB ?bSbB ? bABbB ? bAaBbB (只能用 A ∷ ＝ Aa推導(dǎo)，又遇 A，出現(xiàn)了死循環(huán) ) 由于文法規(guī)則中有左 遞歸 A ∷ ＝ Aa，所以無(wú)法分析下去 167。 自頂向下語(yǔ)法分析 一、自頂向下分析方法的問(wèn)題及其解決辦法 31 E E T ＋ E T ＋ E T ＋ T 等價(jià) E T + T + T + T T + T + T + T 167。 可以證明 ， 改寫前后的文法 是等價(jià)的 。 自頂向下語(yǔ)法分析 一、自頂向下分析方法的問(wèn)題及其解決辦法 33 2） 消除直接左遞歸 還可用另一種方法來(lái)改寫形如文法規(guī)則Ａ ∷ ＝Ａ α｜ β的直接左遞歸 。 同樣可以證明這種形式和原來(lái)形式是等價(jià)的 。 自頂向下語(yǔ)法分析 一、自頂向下分析方法的問(wèn)題及其解決辦法 34 A A α β A α A α β α α α 等價(jià) A β A’ α A’ α A’ α A’ ε β α α α 167。 自頂向下語(yǔ)法分析 一、自頂向下分析方法的問(wèn)題及其解決辦法 36 例如： A ∷ ＝ Ac|Aad|bd|e 等價(jià)于 A ∷ ＝ A（ c|ad） |bd|e ， 所以可以改 寫成： A ∷ ＝ （ bd|e） A’ （ 即 A ∷ ＝ bdA’ |eA’) A’ ∷ ＝ （ c|ad） A’| ε （ 即 A’ ∷ ＝ cA’|adA’|ε ） ∷ ， Ｔ ∷ ＝ T*Ｆ｜Ｆ ， Ｆ ∷ ＝ （ Ｅ ） ｜ i ∷ ＝ＴＥ ′ ， Ｅ ′∷ ＝＋ＴＥ ′｜ ε Ｔ ∷ ＝ＦＴ ′ ， Ｔ ′∷ ＝ *ＦＴ ′｜ ε ， Ｆ ∷ ＝ （ Ｅ ） ｜ i 167。 例如 ， 有文法Ｇ ［ Ｓ ］ Ｓ ∷ ＝Ｑ c｜ c Ｑ ∷ ＝Ｒ b｜ b Ｒ ∷ ＝Ｓ a｜ a 該文法無(wú)直接左遞歸 ， 但有間接左遞歸 ， Ｓ ? Ｑ c ? Ｒ bc ? Ｓ abc 即 Ｓ ?＋Ｓ abc 37 167。 自頂向下語(yǔ)法分析 一、自頂向下分析方法的問(wèn)題及其解決辦法 4) 消除文法遞歸的一般算法 要求：文法不含形如Ａ ? ＋Ａ的推導(dǎo) ， 也不存在Ａ ∷ ＝ ε這樣規(guī)則 算法思想如下： ①將文法Ｇ的所有非終結(jié)符整理成某種順序Ｕ１，Ｕ２， … Ｕ n ② 從 U1開始消除 U1規(guī)則的直接左遞歸 ③用左部為 U1的所有規(guī)則右部替換左部為 U2，右部以 U1開始的規(guī)則中的 U1，并消除 U2規(guī)則的直接左遞歸。 ⑤重復(fù)上一步，直到最后把左部為 U1， U2， …Un 1的右部帶入 Un規(guī)則中，并消除 Un中的直接左遞歸。 自頂向下語(yǔ)法分析 一、自頂向下分析方法的問(wèn)題及其解決辦法 ① 將文法Ｇ的所有非終結(jié)符整理成某種順序Ｕ １ ， Ｕ ２ ， … Ｕ n， 然后 ② ＦＯＲ i:＝１ ＴＯ n ＦＯＲ j∶ ＝１ ＴＯ i1 把形如 Ｕ i∷ ＝Ｕ jy Ui∷ ＝ x１ y｜ x２ y｜ … ｜ xky 其中 Uj∷ ＝ x１ ｜ x２ ｜ … ｜ xk 是 Uj 消除關(guān)于 Ui ③ 去掉多余規(guī)則（如果有的話） 40 消除左遞歸算法 167。 ＦＯＲ i∶ ＝１ ＴＯ 2 ＦＯＲ j∶ ＝１ ＴＯ i１ … 消除 Ui 41 167。 當(dāng) i＝２時(shí) ， 應(yīng)改寫規(guī)則Ａ ∷ ＝Ｓ d， 因?yàn)椋?∷ ＝Ａ a｜ b， 所以Ａ ∷ ＝Ａ ad｜ bd， Ｓ ∷ ＝Ａ a｜ b Ａ ∷ ＝Ａ c ｜Ａ ad｜ bd｜ e 消除關(guān)于Ａ的直接左遞歸即可 。 42 167。 自頂向下語(yǔ)法分析 二、遞歸子程序分析法 一個(gè)子程序以直接或間接方式調(diào)用本身，稱為遞歸子程序。 自頂向下語(yǔ)法分析 二、遞歸子程序分析法 一、自頂向下分析方法的問(wèn)題及其解決辦法 二、遞歸子程序分析法（遞歸下降分析法） 三、 LL（ 1）分析法 （ 1）分析方法 （ 1）文法 45 167。 （ 2） 構(gòu)造遞歸子程序的方法 程序語(yǔ)言的許多語(yǔ)法成分是遞歸定義的，在對(duì)程序語(yǔ)言進(jìn)行不帶回溯自頂向下語(yǔ)法分析時(shí)，就可以采用遞歸子程序法。 自頂向下語(yǔ)法分析 二、遞歸子程序分析法 1)對(duì)文法中每個(gè)非終結(jié)符號(hào) U（ 它們都分別代表一種語(yǔ)法成分 ） 都編出一個(gè)子程序 P（ U） 2)對(duì)于遞歸出現(xiàn)的非終結(jié)符 ， 其相應(yīng)的子程序中應(yīng)有遞歸入口部分 （ 遞歸入口子程序 ， 取名 SＣＩＮ ） ， 以便將返回地址壓入棧中 。 以便從地址壓入棧中取返回地址 3)對(duì)于規(guī)則 U∷ ＝ x１｜ x２｜ … ｜ xn， 可用下列方法構(gòu)造Ｐ （ U） ＩＦ ch ＩＮ ＦＩ RＳＴ （ Ｘ１ ） ＴＨＥＮ Ｐ （ Ｘ１ ） ＥＬＳＥ ＩＦ ch ＩＮ ＦＩＲＳＴ （ Ｘ２ ） ＴＨＥＮ Ｐ （ Ｘ２ ） ＥＬＳ E … ＩＦ ch ＩＮ ＦＩＲＳＴ （ Ｘ n） ＴＨＥＮ Ｐ （ Ｘ n） ＥＬＳＥ 47 167。 當(dāng)輸入符號(hào)遇選擇項(xiàng)為 ε時(shí) ， 就自動(dòng)認(rèn)為獲得 了匹配 。 如果 yi∈ Ｖ Ｎ ， 則Ｐ （ yi） 就 代表調(diào)用與 yi相應(yīng)的子程序 。 自頂向下語(yǔ)法分析 二、遞歸子程序分析法 一、自頂向下分析方法的問(wèn)題及其解決辦法 二、遞歸子程序分析法（遞歸下降分析法） 三、 LL（ 1）分析法 （ 1）分析方法 （ 1）文法 49 167。 在第一次執(zhí)行前 ， ch中已存有輸入串中首字符 。 自頂向下語(yǔ)法分析 二、遞歸子程序分析法 (1)構(gòu)造遞歸子程序：Ｐ (E) 51 SCIN ch=e? 1 2 READ P(B) ch=a? ERROR READ P(A) ERROR SCOUT Ｅ ∷ ＝ eBaA （ 用方法 4） ） = ≠ = ≠ 3 4 5 6 7 8 (1)構(gòu)造遞歸子程序 Ｐ (A) 52 Ａ ∷ ＝ a｜ bAcB （ 用方法 3） 和 4） ） SCIN ch=a? 1 2 READ ch=c? P(A) ERROR SCOUT ≠ = ≠ 3 4 7 6 10 ch=b? READ 5 = ERROR ≠ READ 8 P(B) 9 (1)構(gòu)造遞歸子程序 Ｐ (B) 53 SCIN ch=d? 1 2 READ P(E) ch=d? READ P(C) ERROR Ｂ ∷ ＝ dEd｜ aC （ 用方法 3） 和 4） ） = ≠ = ≠ 3 4 5 6 7 9 ERROR ≠ READ 8 = ch=a? SCOUT 10 (1)構(gòu)造遞歸子程序 Ｐ (C) 54 Ｃ ∷ ＝ e｜ dC （ 用方法 3） 和 4） ） SCIN ch=e? 1 2 READ P(C) ERROR SCOUT ≠ ＝ ≠ 3 4 6 7 ch=d? READ 5 = 55 ch （ 2） 分析實(shí)例 判別字符串 eadeaa 是否是文法Ｇ［Ｅ］的句子。并設(shè)一個(gè)返回地址棧用于存放返回地址 棧底 TOP→ 56 ch e a d e a a 1） 開始時(shí)，在全程變量 ch中存放了輸入串中的首字符 e，故分析與識(shí)別從符號(hào)‘ e’開始。e39。 SCIN ch=e? 1 2 READ P(B) ch=a? ERROR READ P(A) ERROR SCOUT = ≠ = ≠ 3 4 5 6 7 8 子程序 P(E) 主返 TOP→ 59 ch e a d e a a 4) 讀入下一個(gè)字符 a，即 ch＝ a SCIN ch=e? 1 2 READ P(B) ch=a? ERROR READ P(A) ERROR SCOUT = ≠ = ≠ 3 4 5 6 7 8 子程序 P(E) 主返 TOP→ 60 ch e a d e a a 5) P(E)子程序調(diào)用子程序 P(B)， P(B)調(diào)用遞歸入口 子程序 SCIN，將 P(B)在 P(E)中的返回地址 P(E):5送入返回棧中 SCIN ch=e? 1 2 READ P(B) ch=a? ERROR READ P(A) ERROR SCOUT = ≠ = ≠ 3 4 5 6 7 8 子程序 P(E) 主返 P(E):5 TOP→ 61 ch e a d e a a