【正文】 LOW(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)造文法Ｇ的ＬＬ （ １ ） 分析表 ， 對于Ｇ中每一個(gè)規(guī)則Ａ ∷ ＝α ， 可按如下算法確定表中各元素 ① 對ＦＩＲＳＴ （ α ） 中每一終結(jié)符 a， 置Ｍ ［ A,a］ ＝“ Ａ → α ” ② 若 ε ∈ ＦＩＲＳＴ （ α ） ， 則對屬于ＦＯＬＬＯＷ（ Ａ ） 中的每一符號 b(b為終結(jié)符或＃ )， 置Ｍ ［ Ａ ， b］＝ “ Ａ → α ”； ③ 把Ｍ中所有不能按規(guī)則 ① 、 ② 定義的元素均置為出錯(cuò) 。 109 2)構(gòu)造分析表 M過程 （ 以文法Ｇ ［ Ｅ ］ 為例 ） 下面列出文法Ｇ ［ Ｅ ］ 符號串頭終結(jié)符號集合和非終結(jié)符后繼終結(jié)符號集合 文法Ｇ ［ Ｅ ］ : ① Ｅ → ＴＥ ′ ② Ｅ ′ → ＋ＴＥ ′ ｜ ε ③ Ｔ → FT′ ④ Ｔ ′ →* ＦＴ ′ ｜ ε ⑤ Ｆ → （ Ｅ ） ｜ i 110 對下述文法Ｇ［Ｅ］求出符號串頭終結(jié)符號集合和非終結(jié)符后繼終結(jié)符號集合整理得： 文法Ｇ［Ｅ］ : ① Ｅ → ＴＥ ′ ② Ｅ ′ → ＋ＴＥ ′ ｜ ε ③ Ｔ → FT′ ④ Ｔ ′ →* ＦＴ ′ ｜ ε ⑤ Ｆ → （ Ｅ ） ｜ i FIRST（ TE’） =={（ ， i} FIRST（ +TE’） ={+} FIRST（ FT’） ={（ ， i} FIRST（ *FT’） ={*} FIRST（（ E）） =={（ } FIRST（ ε ） ={ε } FOLLOW（ E） =FOLLOW（ E’） ={）， } FOLLOW（ E’） ＝ { ＃ ,） } FOLLOW（ T） =FOLLOW（ T’） ={）， ， +} FOLLOW（ T’)＝ { +,＃ ,） } FOLLOW（ F） ={）， ， +， *} 111 2)構(gòu)造分析表 M過程 （ 以文法 Ｇ ［ Ｅ ］ 為例 ） ① Ｅ → ＴＥ ′ ② Ｅ ′ → ＋ＴＥ ′ ｜ ε ③ Ｔ → FT′ ④ Ｔ ′ →* ＦＴ ′ ｜ ε ⑤ Ｆ → （ Ｅ ） ｜ i ① Ｅ → ＴＥ ′ 由于 FIRST（ TE?） ={(， i}， 由算法步驟 ① 于是置 M[E,（ ] = “Ｅ → ＴＥ ” M[E， i] = “Ｅ → ＴＥ ” i + * ( ) ＃ E E→TE? E→TE? E? T T? F 112 2)構(gòu)造分析表 M過程 （ 以文法 Ｇ ［ Ｅ ］ 為例 ） ① Ｅ → ＴＥ ′ ② Ｅ ′ → ＋ＴＥ ′ ｜ ε ③ Ｔ → FT′ ④ Ｔ ′ →* ＦＴ ′ ｜ ε ⑤ Ｆ → （ Ｅ ） ｜ i ② Ｅ ′→ ＋ＴＥ ′ ｜ ε 由于 FIRST（ +TE?） ={+} ， 由算法步驟 ① 于是置 M[Ｅ ′ ,+]= “Ｅ ′→ ＋ＴＥ ’” 由于Ｅ ′→ ε ，則 FIRST（ ε ） ={ε }，而 FOLLOW（ E’） ={ )， } 由算法步驟 ② 于是置 M[Ｅ ′ ，） ]= “Ｅ ′→ ε ” M[Ｅ ′ ， ]= “Ｅ ′→ ε ” i + * ( ) ＃ E E→TE? E→TE? E? E→+TE? E? → ε E? → ε T T? F 113 2)構(gòu)造分析表 M過程 （ 以文法 Ｇ ［ Ｅ ］ 為例 ） ① Ｅ → ＴＥ ′ ② Ｅ ′ → ＋ＴＥ ′ ｜ ε ③ Ｔ → FT′ ④ Ｔ ′ →* ＦＴ ′ ｜ ε ⑤ Ｆ → （ Ｅ ） ｜ i ③ Ｔ → FT′ 由于 FIRST（ FT’） ={(， i}， 由算法步驟 ① 于是置 M[T，（ ] = “Ｔ → FT?” M [T， i] = “Ｔ → FT?” i + * ( ) ＃ E E→TE? E→TE? E? E→+TE? E? → ε E? → ε T Ｔ → FT? Ｔ → FT? T? F 114 2)構(gòu)造分析表 M過程 （ 以文法 Ｇ ［ Ｅ ］ 為例 ） ① Ｅ → ＴＥ ′ ② Ｅ ′ → ＋ＴＥ ′ ｜ ε ③ Ｔ → FT′ ④ Ｔ ′ →* ＦＴ ′ ｜ ε ⑤ Ｆ → （ Ｅ ） ｜ i ④ Ｔ ′→* ＦＴ ′ ｜ ε 由于 FIRST(*FT’)={*} ， 由算法步驟 ① 于是置 M[Ｔ ′ ， *]=“Ｔ ′→* ＦＴ ′ ” 由于 T′→ ε ，則 FIRST（ ε ） ={ε }，而 FOLLOW（ T’） ={）， ， +}， 由算法步驟 ② 于是置 M[T?，） ] = “T′→ ε ” M[T?， ] = “T′→ ε ” M[T?， +] = “T′→ ε ” i + * ( ) ＃ E E→TE? E→TE? E? E→+TE? E? → ε E? → ε T Ｔ → FT? Ｔ → FT? T? T?→ε T →*FT? T?→ε T?→ε F 115 2)構(gòu)造分析表 M過程 （ 以文法 Ｇ ［ Ｅ ］ 為例 ） ① Ｅ → ＴＥ ′ ② Ｅ ′ → ＋ＴＥ ′ ｜ ε ③ Ｔ → FT′ ④ Ｔ ′ →* ＦＴ ′ ｜ ε ⑤ Ｆ → （ Ｅ ） ｜ i ⑤ Ｆ → （Ｅ）｜ i 由于 FIRST（（ E）） ={（ } ， 由算法步驟 ① 于是置 M[F， (]= = “Ｆ → （Ｅ） ” 由于 FIRST（ i） ={i} ， 由算法步驟 ① 于是置 M[F， i] = “Ｆ → i” i + * ( ) ＃ E E→TE? E→TE? E? E→+TE? E? → ε E? → ε T Ｔ → FT? T→FT? T? T?→ε T →*FT? T?→ε T?→ε F F→i F→(E) 116 三、 LL（ 1）分析法 4. LL（ 1）文法 (1)定義 一個(gè)文法 G，如果它的 LL(1)分析表 M不含多重定義入口，則稱該文法是 LL（ 1）文法 ，可以證明 ,一個(gè)LL(1)文法所定義的語言 ,恰好是它分析表Ｍ所識別全部句子。 所謂 多重定義入口 是指分析表中某 M[A， a]有兩個(gè)或兩個(gè)以上產(chǎn)生式。 LL（ 1） 文法是 2型文法 ， 但并不是所有 2型文法都是 LL（ 1） 文法 。 對 LL（ 1） 文法進(jìn)行 LL（ 1）分析才是有意義的 。 117 例如 ： 文法Ｇ ［ Ｓ ］ ： Ｓ ∷ ＝ iＣ tＳＳ ′ ｜ a Ｓ ′ ∷ ＝ eＳ｜ ε Ｃ ∷ ＝ b 它是 2型文法卻不是 LL（ 1） 文法 。 我們可以按照上述方法構(gòu)造它的分析表 ,從該表可以看出 ,元素 M[S’,e]有兩條規(guī)則 ,即 M[S’,e]有多重定義入口 ,所以該文法不是 LL（ 1） 文法 . a b e i t S S? C S::=a C::=b S?::Es,S?::=ε S::=iCtSS? S?::=ε 118 (2) LL(1)文法性質(zhì) LL（ 1） 文法有一些明顯的性質(zhì) ， 它 不是二義的 ， 也 不含左遞歸 。 還可以證明 Ｇ是 LL（ 1） 的 ， 當(dāng)且僅當(dāng) Ｇ的任何兩個(gè)規(guī)則Ａ ∷ ＝ α ｜ β 滿足下面條件： 1) FIRST(α ) ∩ FIRST(β )＝ ?， 也就是 α 和 β 推導(dǎo)不出 以某個(gè)同一終結(jié)符 a為首的符號串 。 2) α 和 β 中最多只有一個(gè)可能推出空串 。 3) 如果 β ? *ε ， 那么 α 推出任何串不會(huì)以 FOLLOW(A)中的 終結(jié)符開始 ， 即若 β ? *ε 則 FIRST(α ) ∩FOLLOW(A) ＝ ? 注意：對于某些文法可以通過消除左遞歸和提取左因子 （ 消除回溯 ） 變成 LL（ 1） 文法 119 167。 自底向上語法分析 120 例 設(shè)有文法 G=(VN,VT,P,S),其中 VN={A,B,S} VT={a,b,c,d,e} P: S∷=aAcBe A∷=Ab|b B∷=d 試分析 w=abbcde是否為此文法的句子。 121 為了具體實(shí)現(xiàn)方便，我們統(tǒng)一以符號“ ”作為待分析符號串左右分界符，作為初始狀態(tài)，先將符號串的左分界符壓入符號棧，作為棧底符號。對符號串 abbcde分析過程如下所示。 步驟 符號棧 輸入符號串 動(dòng)作 (1) abbcde 左界符進(jìn)棧 (2) a bbcde a進(jìn)棧 (3) ab bcde b進(jìn)棧 (4) aA bcde 用 A→ b歸約 (5) aAb cde b進(jìn)棧 (6) aA cde 用 A→Ab 歸約 (7) a