【正文】 經(jīng)過反復(fù)提取公因子即可將每個非終結(jié)符的所有選擇首符號集變成兩兩不相交 。 2) 提取左因子法 當(dāng)文法不滿足上述路標(biāo)法條件 ， 即右部各規(guī)則首符號相同時 ， 我們可以采用提取左因子法對文法進行改寫 。 35 例如 ： U∷ ＝ xy|x, 可寫成 U∷ ＝ xU’ U’ ::=y|? 當(dāng)分析符號串遇到 ? 時 ， 認(rèn)為總能匹配 ， 可以一直分析下去 。 36 為避免分析時回溯 ， 可以將文法改寫成： S ∷ ＝ xAy , A ∷ ＝ *（ *|?） 進一步改寫成 S ∷ ＝ xAy , A ∷ ＝ *B ， B ∷ ＝ *|? 例如： 有文法 S ∷ ＝ xAy , A ∷ ＝ **|* 分析 x*y是否是該文法的句子 。 從開始符號出發(fā) ， 得自頂向下語法分析： S?xAy S?xAy ?x*By S?xAy ?x*By?x*?y S?xAy ?x*By ?x*?y ?x*y 37 S x y A * B ? 38 三、遞歸下降分析法 / 遞歸子程序分析法 39 一個子程序以直接或間接方式調(diào)用本身，稱為遞歸子程序。如： PASCAL語言中的遞歸函數(shù)就是遞歸子程序。 40 （ 1） 處理基本思想 對于遞歸子程序調(diào)用，用棧存放返回地址，當(dāng)調(diào)用該子程序時，由遞歸入口部分將返回地址壓入棧中，當(dāng)返回時，遞歸出口部分從棧中取出返回地址。返回到調(diào)用點后繼續(xù)執(zhí)行。 41 （ 2） 構(gòu)造遞歸子程序的方法 1)對文法中每個非終結(jié)符號 U（ 它們都分別代表一種語法成分 ） 都編出一個子程序 P（ U） 2)子程序包含： ① 遞歸入口部分 SＣＩＮ； ② 子程序處理部分； ② 遞歸出口部分 SＣＯＵＴ 。 42 3)對于規(guī)則 U∷ ＝ x１｜ x２｜ …｜ xn， 可用下列方法構(gòu)造Ｐ （ U） 的處理流程： IF ch IN FRIST(X1) THEN …… ELSE IF ch IN FRIST(X2) THEN …… ELSE … ELSE IF ch IN FRIST(Xn) THEN …… ELSE ERROR 其中全程變量 ch中存放了當(dāng)前輸入字符； ERROR為出錯信息 ,表示源程序中語法有錯 。 當(dāng)輸入符號遇選擇項為 ε 時 ， 就自動認(rèn)為獲得了匹配 。 43 4)對于符號串 x＝ y１ y２ …ym， 如果 yi∈ Ｖ Ｔ ， 則Ｐ （ yi） 為 IF ch＝ yi THEN READ(ch) ELSE ERROR 這就是說 ， 如果當(dāng)前文法中的符號與輸入符號匹配 ， 則繼續(xù)讀入下一個字符至 ch中；否則表明源程序有錯 。 44 設(shè)有文法Ｇ ［ Ｅ ］ Ｅ ∷ ＝ eBaA Ａ ∷ ＝ a｜ bAcB Ｂ ∷ ＝ dEd｜ aC Ｃ ∷ ＝ e｜ dC 此文法共有四個非終結(jié)符 ， 編寫四個相應(yīng)的遞歸子程序：Ｐ （ E） 、 Ｐ （ Ａ ） 、 Ｐ （ Ｂ ） 、Ｐ （ Ｃ ） 。 在第一次執(zhí)行前 ， ch中已存有輸入串中首字符 。 45 遞歸子程序：Ｐ（ E） SCIN ch=?e?? 1 2 READ P(B) ch=?a?? ERROR READ P(A) ERROR SCOUT Ｅ ∷ ＝ eBaA = ≠ = ≠ 3 4 5 6 7 8 46 遞歸子程序：Ｐ（ A） Ａ ∷ ＝ a｜ bAcB 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 47 遞歸子程序：Ｐ（ B） SCIN ch=?d?? 1 2 READ P(E) ch=?d?? READ P(C) ERROR Ｂ ∷ ＝ dEd｜ aC = ≠ = ≠ 3 4 5 6 7 9 ERROR ≠ READ 8 = ch=?a?? SCOUT 10 48 遞歸子程序：Ｐ（ C） Ｃ ∷ ＝ e｜ dC SCIN ch=?e?? 1 2 READ P(C) ERROR SCOUT ≠ ＝ ≠ 3 4 6 7 ch=?d?? READ 5 = 49 ch 例：判別字符串 eadeaa 是否是文法Ｇ［Ｅ］的句子。 e a d e a a 分析步驟從識別符號 E開始，掃描字符串eadeaa ，設(shè)一個全程變量 ch用于存放存放輸入串中的字符。并設(shè)一個返回地址棧用于存放返回地址 棧底 TOP→ 50 ch e a d e a a （ 1）開始時，在全程變量 ch中存放了輸入串中的首字符 e，故分析與識別從符號‘ e?開始。 此時主程序調(diào)用子程序 P(E) 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→ 51 ch e a d e a a （ 2）進入 P(E)后，執(zhí)行 P(E)子程序，首先通過遞歸入口子程序 SCIN將 P(E)在主程序中的返回地址送入返回棧中 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→ 52 ch e a d e a a （ 3）根據(jù) P(E)子程序，首先判斷 ch?＝’ e?，如果是 39。e39。，接著讀入下一個字符 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→ 53 ch e a d e a a （ 4） P(E)子程序調(diào)用子程序 P(B)， P(B)調(diào)用遞歸入口子程序 SCIN，將 P(B)在 P(E)中的返回地址送入返回棧中 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→ 54 ch e a d e a a （ 4） P(E)子程序調(diào)用子程序 P(B)， P(B)調(diào)用遞歸入口子程序 SCIN，將 P(B)在 P(E)中的返回地址送入返回棧中 子程序 P(B) 主返 P(E):5 TOP→ SCIN ch=?d?? 1 2 READ P(E) ch=?d?? READ P(C) ERROR = ≠ = ≠ 3 4 5 6 7 9 ERROR ≠ READ 8 = ch=?a?? SCOUT 10 55 ch e a d e a a （ 5）然后 子程序 P(B)中將分析 ch?＝’ d?，如果不是，再判定 ch？＝’ a?。 子程序 P(B) 主返 P(E):5 TOP→ SCIN ch=?d?? 1 2 READ P(E) ch=?d?? READ P(C) ERROR = ≠ = ≠ 3 4 5 6 7 9 ERROR ≠ READ 8 = ch=?a?? SCOUT 10 56 ch e a d e a a （ 6）現(xiàn)在的情況輸入的第二個字符是‘ a?，再讀入下一個字符‘ d?，再調(diào)用子程序 P(C) 子程序 P(B) 主返 P(E):5 TOP→ SCIN ch=?d?? 1 2 READ P(E) ch=?d?? READ P(C) ERROR = ≠ = ≠ 3 4 5 6 7 9 ERROR ≠ READ 8 = ch=?a?? SCOUT 10 57 ch e a d e a a （ 7） P(B)子程序調(diào)用子程序 P(C)， P(C)調(diào)用遞歸入口子程序 SCIN，將 P(C)在 P(B)中的返回地址送入返回棧中 子程序 P(B) 主返 P(E):5 P(B):10 TOP→ SCIN ch=?d?? 1 2 READ P(E) ch=?d?? READ P(C) ERROR = ≠ = ≠ 3 4 5 6 7 9 ERROR ≠ READ 8 = ch=?a?? SCOUT 10 58 ch e a d e a a （ 8）接著應(yīng)該判定 ch?＝’ e?。如果不是字符’ e?，再接著判定 ch?＝’ d?。 子程序 P(C) 主返 P(E):5 P(B):10 TOP→ SCIN ch=?e?? 1 2 READ P(C) ERROR SCOUT ≠ ＝ ≠ 3 4 6 7 ch=?d?? READ 5 = 59 ch e a d e a a （ 9）現(xiàn)在第三個字符是 d，于是再讀入一個字符‘ e?。 子程序 P(C) 主返 P(E):5 P(B):10 TOP→ SCIN ch=?e?? 1 2 READ P(C) ERROR SCOUT ≠ ＝ ≠ 3 4 6 7 ch=?d?? READ 5 = 60 ch e a d e a a （ 10） P(C)子程序調(diào)用新子程序 P(C)，新 P(C)調(diào)用遞歸入口子程序 SCIN，將新 P(C)在原 P(C)中的返回地址送入返回棧中。 原子程序 P(C) 主返 P(E):5 P(B):10 P(C):7 TOP→ SCIN ch=?e?? 1 2 READ P(C) ERROR SCOUT ≠ ＝ ≠ 3 4 6 7 ch=?d?? READ 5 = 61 ch e a d e a a （ 11） P(C)子程序調(diào)用新子程序 P(C)，新 P(C)調(diào)用遞歸入口子程序 SCIN，將新 P(C)在原 P(C)中的返回地址送入返回棧中。 新子程序 P(C) 主返 P(E):5 P(B):10 P(C):7 TOP→ SCIN ch=?e?? 1 2 READ P(C) ERROR SCOUT ≠ ＝ ≠ 3 4 6 7 ch=?d?? READ 5 = 62 ch e a d e a a （ 12）這時要判定 ch?＝’ e?。 子程序 P(C) 主返 P(E):5 P(B):10 P(C):7 TOP→ SCIN ch=?e?? 1 2 READ P(C) ERROR SCOUT ≠ ＝ ≠ 3 4 6 7 ch=?d?? READ 5