【正文】 1 2 READ ch=c? P(A) ERROR SCOUT ≠ = ≠ 3 4 7 6 10 ch=b? READ 5 = ERROR ≠ READ 8 P(B) 9 79 ch e a d e a a 24） 由于輸入串 eadeaa后面再也沒有其他字符 了，故讀入的是句子的終結(jié)符‘ ’ 主返 P(E):8 TOP→ 子程序 P(A) 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 80 ch e a d e a a 25） P(A)調(diào)用遞歸出口子程序 SCOUT，將返回 棧中中返回地址 P(E):8取出。 子程序 P(B) 主返 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 75 ch e a d e a a 20） P(E)執(zhí)行 P(E):5，即 P(E) 子程序判別 ch? ＝ a，現(xiàn)在是 a，接著讀入下一個(gè)字符。 子程序 P(C) 主返 P(E):5 TOP→ SCIN ch=e? 1 2 READ P(C) ERROR SCOUT ≠ ＝ ≠ 3 4 6 7 ch=d? READ 5 = 73 ch e a d e a a 18） P(B)執(zhí)行 P(B):10，即 P(B)調(diào)用遞歸出口子 程序 SCOUT，將返回棧返回地址 P(E):5取出。 子程序 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 = 71 ch e a d e a a 16） P(C)執(zhí)行 P(C):7，即 P(C)調(diào)用遞歸出口子程序 SCOUT，將返回棧中返回地址 P(B):10取出。 子程序 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 = 68 ch e a d e a a 13） 讀入下一個(gè)字符 a，即 ch＝ a 子程序 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 = 69 ch e a d e a a 14） P(C)調(diào)用遞歸出口子程序 SCOUT，將返 回棧中返回地址 P(C):7取出。 子程序 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 = 65 ch e a d e a a 10） 讀入下一個(gè)字符 e，即 ch＝ 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 = 66 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):7地址送入返回棧中。 子程序 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 62 ch e a d e a a 7） 讀入下一個(gè)字符 d，即 ch＝ d 子程序 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 63 ch e a d e a a 8） P(B)子程序調(diào)用子程序 P(C)， P(C)調(diào)用遞歸入口子程序 SCIN，將 P(C)在 P(B)中的返回地址P(B):10送入返回棧中 子程序 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 64 ch e a d e a a 9） 接著執(zhí)行 P(C)，分析 ch?＝ e。接著讀入下一個(gè)字符。 此時(shí)主程序調(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→ 57 ch e a d e a a 2) 進(jìn)入 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→ 58 ch e a d e a a 3) 執(zhí)行 P(E)子程序，首先判斷 ch?＝ e，現(xiàn)在 ch＝ 39。 e a d e a a 分析步驟從識(shí)別符號(hào) E開始，掃視字符串eadeaa ，設(shè)一個(gè)全程變量 ch用于存放輸入串中的字符。 167。 自頂向下語(yǔ)法分析 二、遞歸子程序分析法 50 設(shè)有文法Ｇ ［ Ｅ ］ Ｅ ∷ ＝ eBaA Ａ ∷ ＝ a｜ bAcB Ｂ ∷ ＝ dEd｜ aC Ｃ ∷ ＝ e｜ dC 此文法共有四個(gè)非終結(jié)符 ， 并且在規(guī)則中都是遞歸出現(xiàn) ， 故應(yīng)該編寫四個(gè)相應(yīng)的遞歸子程序：Ｐ （ E） 、 Ｐ （ Ａ ） 、 Ｐ （ Ｂ ） 、Ｐ （ Ｃ ） 。 48 167。 4)對(duì)于符號(hào)串 x＝ y１ y２ … ym， 如果 yi∈ Ｖ Ｔ ， 則Ｐ （ yi） ＩＦ ch＝ yi ＴＨＥＮ ＲＥＡＤ （ ch） ＥＬＳＥ 這就是說 ， 如果當(dāng)前文法中的符號(hào)與輸入符號(hào)匹配 ， 則繼續(xù)讀入下 一個(gè)字符至 ch中；否則表明源程序有錯(cuò) 。 自頂向下語(yǔ)法分析 二、遞歸子程序分析法 其中全程變量 ch中存放了當(dāng)前輸入字符；ＥＲＲＯＲ為出錯(cuò)信息 ， 表 示源程序中語(yǔ)法有錯(cuò) 。 此外 ， 還應(yīng)有遞歸出口部分 ， 設(shè)此子程序取名 SＣＯＵＴ 。其方法步驟如下： 46 167。 自頂向下語(yǔ)法分析 二、遞歸子程序分析法 （ 1） 處理基本思想 對(duì)于遞歸子程序調(diào)用，用棧存放返回地址，當(dāng)調(diào)用該子程序時(shí)，由遞歸入口子程序?qū)⒎祷氐刂穳喝霔Ｖ校?dāng)返回時(shí)，用遞歸出口子程序從棧中取出返回地址。 44 167。 自頂向下語(yǔ)法分析 一、自頂向下分析方法的問題及其解決辦法 一、自頂向下分析方法的問題及其解決辦法 二、遞歸子程序分析法（遞歸下降分析法） 三、 LL（ 1）分析法 （ 1）分析方法 （ 1）文法 43 167。 該文法沒有多余的規(guī)則 。 自頂向下語(yǔ)法分析 一、自頂向下分析方法的問題及其解決辦法 當(dāng) i＝１時(shí) ， 上述語(yǔ)句對(duì)文法Ｇ不產(chǎn)生影響 。 自頂向下語(yǔ)法分析 一、自頂向下分析方法的問題及其解決辦法 例 ［ Ｓ ］ Ｓ ∷ ＝Ａ a｜ b Ａ ∷ ＝Ａ c｜Ｓ d｜ e 應(yīng)用上述算法 ， 將非終結(jié)符排列Ｓ ， Ａ 。 ⑥消除多余規(guī)則 39 167。 ④用類似的方法把 U1， U2的右部替換左部為 U3，右部以 U1， U2開始的規(guī)則中，消除 U3規(guī)則中的直接左遞歸。 自頂向下語(yǔ)法分析 一、自頂向下分析方法的問題及其解決辦法 3） 消除間接左遞歸 對(duì)于間接左遞歸先將間接左遞歸變成直接左遞歸 ， 然后消除直接左遞歸 例如； A ∷ ＝ aB|Bb (1) B ∷ ＝ Ac|d (2) 先將（ 1）代入（ 2）中，得 B ∷ ＝ Bbc|aBc|d (3) 由此將 (3)改寫為； B ∷ ＝（ aBc|d)B’ B’∷ ＝ bcB’|? 加入文法開始符號(hào)的產(chǎn)生式得消除左遞歸后的等價(jià)文法為： A ∷ ＝ aB|Bb B ∷ ＝ (aBc|d)B’ B’∷ ＝ bcB’|? 38 167。 自頂向下語(yǔ)法分析 一、自頂向下分析方法的問題及其解決辦法 上述兩種方法可消除任意直接左遞歸 ， 但不能消除兩步或多步推導(dǎo)形成 的左遞歸 。 自頂向下語(yǔ)法分析 一、自頂向下分析方法的問題及其解決辦法 就一般而言 ， Ａ ∷ ＝Ａ α１ ｜Ａ α２ ｜ … ｜Ａ αn｜ β１ ｜ β２ ｜ … ｜ βn 這時(shí)可改寫成如下形式： Ａ ∷ ＝ A(α１ ｜ α２ ｜ … ｜ αn) ｜ β１ ｜ β２ ｜ … ｜ βn 由消除直接左遞歸方法 ， 得 Ａ ∷ ＝ (β１ ｜ β２ ｜ … ｜ βn)Ａ ′ Ａ ′∷ ＝ (α１ ｜ α２ ｜ … ｜ αn)Ａ ′｜ ε 35 167。 167。 對(duì)Ａ引入一個(gè)新的非終結(jié)符Ａ ′， 將Ａ ∷ ＝Ａ α｜ β Ａ ∷ ＝ βＡ ′ Ａ ′∷ ＝ αＡ ′｜ ε 由于 β不以Ａ開頭 ， α不以Ａ ′開頭 ， 因此改寫后兩條規(guī)則不是直接 左遞歸 。 167。 自頂向下語(yǔ)法分析 一、自頂向下分析方法的問題及其解決辦法 32 同樣 ， Ｔ ∷ ＝Ｔ * 等價(jià)于Ｔ ∷ ＝Ｔ（ *Ｆ｜／Ｆ）｜Ｆ Ｔ ∷ ＝Ｆ ｛ *Ｆ｜／Ｆ ｝ 這樣 ， 改寫后的文