【正文】 對(duì)符號(hào)串 abbcde分析過程如下所示。 2) α 和 β 中最多只有一個(gè)可能推出空串 。 對(duì) LL（ 1） 文法進(jìn)行 LL（ 1）分析才是有意義的 。 ∷ ＝ α B或Ａ ∷ ＝ α Bβ 的規(guī)則 ，且 β ?*ε ， 則ＦＯＬＬＯＷ （ Ａ ） 中全部終結(jié)符均屬于ＦＯＬＬＯＷ （ Ｂ ） 104 考慮文法Ｇ ［ Ｅ ］ : ① Ｅ → ＴＥ ′ ② Ｅ ′ → ＋ＴＥ ′ ｜ ε ③ Ｔ → FT′ ④ Ｔ ′ →* ＦＴ ′ ｜ ε ⑤ Ｆ → （ Ｅ ） ｜ i FOLLOW（ E） ＝ { ＃ ,） } 由算法步驟 ： ∈ FOLLOW（ E） (E是文法開始符號(hào) ） 由算法步驟 ⑤ 得： ） ∈ FOLLOW（ E） 所以 FOLLOW（ E） ＝ { ＃ ,） } FOLLOW（ E’） ＝ { ＃ ,） } 由算法步驟 ① 得： FOLLOW(E)? FOLLOW(E’) 所以 FOLLOW（ E’） ＝ { ＃ ,） } 105 考慮文法Ｇ ［ Ｅ ］ : ① Ｅ → ＴＥ ′ ② Ｅ ′ → ＋ＴＥ ′ ｜ ε ③ Ｔ → FT′ ④ Ｔ ′ →* ＦＴ ′ ｜ ε ⑤ Ｆ → （ Ｅ ） ｜ i FOLLOW（ T） ＝ { +,＃ ,） } 1)由算法步驟 ① 、 ② 得： +∈ FOLLOW（ T） (因?yàn)? FIRST(E’) {ε }={+}) 2)由算法步驟 ① 得： FOLLOW（ E） ?FOLLOW（ T） 即 {） ， } ?FOLLOW(T)} (由規(guī)則 ② 得：Ｅ ′ ?*ε ,所以由算法 ① 得： FOLLOW（ E） ?FOLLOW（ T） 即 {） ， } ?FOLLOW(T)}) 所以 FOLLOW（ T） ＝ { +,＃ ,） } 106 考慮文法Ｇ ［ Ｅ ］ : ① Ｅ → ＴＥ ′ ② Ｅ ′ → ＋ＴＥ ′ ｜ ε ③ Ｔ → FT′ ④ Ｔ ′ →* ＦＴ ′ ｜ ε ⑤ Ｆ → （ Ｅ ） ｜ i FOLLOW（ T’)＝ { +,＃ ,） } 由算法步驟 ③ 得： FOLLOW（ T） ?FOLLOW（ T’)即 {+， ,） } ?FOLLOW(T’) 所以 FOLLOW（ T’)＝ {+， ,） } 107 考慮文法Ｇ ［ Ｅ ］ : ① Ｅ → ＴＥ ′ ② Ｅ ′ → ＋ＴＥ ′ ｜ ε ③ Ｔ → FT′ ④ Ｔ ′ →* ＦＴ ′ ｜ ε ⑤ Ｆ → （ Ｅ ） ｜ i FOLLOW（ F)＝ { +,*， ＃ ,） } 1)由算法步驟 ③ 、 ④ 得： * ∈ FOLLOW（ F） (因?yàn)? FIRST(T’) {ε }={*}) 2)由算法步驟 ③ 得： FOLLOW（ T） ?FOLLOW（ F） 即 {+,） ， } ?FOLLOW(F)} (由規(guī)則 ④ 得：Ｔ ′ ?*ε ,所以由算法 ③ 得： FOLLOW（ T’） ?FOLLOW（ F） 即 {+,） ， } ?FOLLOW(F)} 所以 FOLLOW（ T） ＝ { +,*,＃ ,） } 108 (2)構(gòu)造分析表 M 1)構(gòu)造分析表 M算法 求出ＦＩＲＳＴ集和ＦＯＬＬＯＷ集后 ， 就可以構(gòu)造文法Ｇ的ＬＬ （ １ ） 分析表 ， 對(duì)于Ｇ中每一個(gè)規(guī)則Ａ ∷ ＝α ， 可按如下算法確定表中各元素 ① 對(duì)ＦＩＲＳＴ （ α ） 中每一終結(jié)符 a， 置Ｍ ［ A,a］ ＝“ Ａ → α ” ② 若 ε ∈ ＦＩＲＳＴ （ α ） ， 則對(duì)屬于ＦＯＬＬＯＷ（ Ａ ） 中的每一符號(hào) b(b為終結(jié)符或＃ )， 置Ｍ ［ Ａ ， b］＝ “ Ａ → α ”； ③ 把Ｍ中所有不能按規(guī)則 ① 、 ② 定義的元素均置為出錯(cuò) 。最后，若對(duì)于１ ≤ i≤n ， ε ∈ ＦＩＲＳＴ（Ｘ i），則再將 ε 加進(jìn)ＦＩＲＳＴ（ α ）中。 ∷ ＝Ｙ １ Ｙ ２ …YＫ 的規(guī)則 ， 若Ｙ １ ∈ Ｖ Ｎ ， 則將 FIRST（ Ｙ １ ） 中一切非 ε 符號(hào)加進(jìn)ＦＩＲＳＴ （ Ｘ ） 中 ， 對(duì)于一切 2≤i≤k ， 若Ｙ １ ?*ε ， 則把Ｙ 2中首符號(hào)集 （ 除 ε 外 ） 也加進(jìn) FIRST（ Ｘ ）中 ， 如此繼續(xù)下去 ， 直到Ｙ k1 ? *ε ， 則把 YK中首符號(hào)集 (除 ε 外 )也入FIRST(X)中 。 96 3. 構(gòu)造分析表 （ 1） 頭終結(jié)符號(hào)集合和后繼終結(jié)符號(hào)集合 1） 頭終結(jié)符號(hào)集合 ① 定義 為了構(gòu)造分析表 ， 我們引進(jìn)與文法有關(guān)的集合FIRST集和 FOLLOW集 。 然后反復(fù)執(zhí)行第 （ 2） 步 2） 設(shè)在分析的某一步 ， 分析棧及余留的輸入符號(hào)串處于如下格局 X1X2… Xm1Xm aiai+1… 其中 ， Ｘ １ ， Ｘ ２ ， …， Ｘ m為分析過程中所得的文法符號(hào) ， 此時(shí) ， 可視棧頂符號(hào)Ｘ m的不同情況 ，分別做如下的動(dòng)作 : 93 ① 若Ｘ m∈ Ｖ Ｎ ， 則以Ｘ m及 ai組成符號(hào)對(duì) （ Ｘ m， ai）查分析表Ｍ ， 設(shè)Ｍ ［ Ｘ m,ai］ 為一產(chǎn)生式 ， 譬如說Xm→ ＵＶＷ ， 此時(shí)將Ｘ m從分析棧中退出 ， 并將ＵＶＷ按反序推入棧中 （ 即用該產(chǎn)生式推導(dǎo)一步 ） ，從而得到新的格局 : X1X2… Xm1WVU aiai+1… 但若Ｍ ［ Ｘ m， ai］ ＝ “ ＥＲＲＯＲ ” ， 則調(diào)用出錯(cuò)處理程序進(jìn)行處理 。 我們通常把按 LL（ 1） 方法執(zhí)行語(yǔ)法分析任務(wù)的程序稱為 LL（ 1） 分析程序或 LL（ 1） 分析器 ， 它由一個(gè)總控程序 、 一張分析表和一個(gè)分析棧組成 ， 如下 圖 所示 。 （ 3）可以加入語(yǔ)義加工子程序 ? 缺點(diǎn) （ 1）編寫程序和調(diào)試工作量大 （ 2）對(duì)上下文無關(guān)文法需要改寫 86 四、 LL（ 1）分析法 （ 1）分析方法 （ 1）文法 87 1. 定義 LL（ 1） 分析方法也是一種自頂向下不帶回溯的分析方法， LL的意思是：從左（ Left）到右掃描輸入符號(hào)串并建立它的最左推導(dǎo)（ Left most derivations）。 BEGIN IF CH=‘(‘ THEN BEGIN getch(ch)。 T’ END 規(guī)則 T’::=*FT’|ε PROCEDURE T’。 E’ END END 規(guī)則 E::=TE’ PROCEDURE E。 也就是說 ， 字符串 eadeaa被語(yǔ)法分析程序 所接受 ， 這表明字符串 ‘ eadeaa’是文法Ｇ （ Ｅ ）的句子 。 主返 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 77 ch e a d e a a （ 21） P(A)調(diào)用遞歸出口子程序 SCOUT，將返回棧中 P(A)在 P(E)中的返回地址 P(E):8取出。 子程序 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 69 ch e a d e a a （ 16） P(B)調(diào)用遞歸出口子程序 SCOUT，將返回棧中 P(B)在 P(E)中的返回地址 P(E):5取出。 子程序 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 = 65 ch e a d e a a （ 14）新 P(C)調(diào)用遞歸出口子程序 SCOUT，將返回棧中新 P(C)在原 P(C)中的返回地址 P(C):7取出。 原子程序 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(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)在的情況輸入的第二個(gè)字符是‘ a?，再讀入下一個(gè)字符‘ 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?。并設(shè)一個(gè)返回地址棧用于存放返回地址 棧底 TOP→ 50 ch e a d e a a （ 1）開始時(shí)，在全程變量 ch中存放了輸入串中的首字符 e，故分析與識(shí)別從符號(hào)‘ e?開始。 44 設(shè)有文法Ｇ ［ Ｅ ］ Ｅ ∷ ＝ eBaA Ａ ∷ ＝ a｜ bAcB Ｂ ∷ ＝ dEd｜ aC Ｃ ∷ ＝ e｜ dC 此文法共有四個(gè)非終結(jié)符 ， 編寫四個(gè)相應(yīng)的遞歸子程序：Ｐ （ E） 、 Ｐ （ Ａ ） 、 Ｐ （ Ｂ ） 、Ｐ （ Ｃ ） 。 41 （ 2） 構(gòu)造遞歸子程序的方法 1)對(duì)文法中每個(gè)非終結(jié)符號(hào) U（ 它們都分別代表一種語(yǔ)法成分 ） 都編出一個(gè)子程序 P（ U） 2)子程序包含： ① 遞歸入口部分 SＣＩＮ； ② 子程序處理部分； ② 遞歸出口部分 SＣＯＵＴ 。 從開始符號(hào)出發(fā) ， 得自頂向下語(yǔ)法分析： 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 一個(gè)子程序以