【正文】 步驟 符號(hào)棧 輸入符號(hào)串 動(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) aA。 121 為了具體實(shí)現(xiàn)方便，我們統(tǒng)一以符號(hào)“ ”作為待分析符號(hào)串左右分界符，作為初始狀態(tài)，先將符號(hào)串的左分界符壓入符號(hào)棧，作為棧底符號(hào)。 3) 如果 β ? *ε ， 那么 α 推出任何串不會(huì)以 FOLLOW(A)中的 終結(jié)符開始 ， 即若 β ? *ε 則 FIRST(α ) ∩FOLLOW(A) ＝ ? 注意：對(duì)于某些文法可以通過消除左遞歸和提取左因子 （ 消除回溯 ） 變成 LL（ 1） 文法 119 167。 還可以證明 Ｇ是 LL（ 1） 的 ， 當(dāng)且僅當(dāng) Ｇ的任何兩個(gè)規(guī)則Ａ ∷ ＝ α ｜ β 滿足下面條件： 1) FIRST(α ) ∩ FIRST(β )＝ ?， 也就是 α 和 β 推導(dǎo)不出 以某個(gè)同一終結(jié)符 a為首的符號(hào)串 。 117 例如 ： 文法Ｇ ［ Ｓ ］ ： Ｓ ∷ ＝ iＣ tＳＳ ′ ｜ a Ｓ ′ ∷ ＝ eＳ｜ ε Ｃ ∷ ＝ b 它是 2型文法卻不是 LL（ 1） 文法 。 LL（ 1） 文法是 2型文法 ， 但并不是所有 2型文法都是 LL（ 1） 文法 。 109 2)構(gòu)造分析表 M過程 （ 以文法Ｇ ［ Ｅ ］ 為例 ） 下面列出文法Ｇ ［ Ｅ ］ 符號(hào)串頭終結(jié)符號(hào)集合和非終結(jié)符后繼終結(jié)符號(hào)集合 文法Ｇ ［ Ｅ ］ : ① Ｅ → ＴＥ ′ ② Ｅ ′ → ＋ＴＥ ′ ｜ ε ③ Ｔ → FT′ ④ Ｔ ′ →* ＦＴ ′ ｜ ε ⑤ Ｆ → （ Ｅ ） ｜ i 110 對(duì)下述文法Ｇ［Ｅ］求出符號(hào)串頭終結(jié)符號(hào)集合和非終結(jié)符后繼終結(jié)符號(hào)集合整理得： 文法Ｇ［Ｅ］ : ① Ｅ → ＴＥ ′ ② Ｅ ′ → ＋ＴＥ ′ ｜ ε ③ Ｔ → 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)文法所定義的語(yǔ)言 ,恰好是它分析表Ｍ所識(shí)別全部句子。 (因?yàn)? S ?* S 由 定義 ∈FOLLOW （ S）） ∷ ＝ α Ｂ β 的規(guī)則 ， 且 β ≠ ε ，則將 FIRST（ β ） 中一切非 ε 符號(hào)加進(jìn)ＦＯＬＬＯＷ （ Ｂ ） 中 。 100 考慮文法Ｇ ［ Ｅ ］ : Ｅ → ＴＥ ′ Ｅ ′ → ＋ＴＥ ′ ｜ ε Ｔ → FT′ Ｔ ′ →* ＦＴ ′ ｜ ε Ｆ → （ Ｅ ） ｜ i 由算法步驟 FIRST（ +） ={+} FIRST（ *） ={*} FIRST（（ ） ={（ } FIRST（ ）） ={） } FIRST（ i） ={i} 由算法步驟 FIRST（ E’） ={+， ε } FIRST（ T’） ={*， ε } FIRST（ F） ={（ ， i} 101 文法Ｇ ［ Ｅ ］ : Ｅ → ＴＥ ′ ,Ｅ ′ → ＋ＴＥ ′ ｜ ε ,Ｔ → FT′ Ｔ ′ →* ＦＴ ′ ｜ ε ,Ｆ → （ Ｅ ） ｜ i 對(duì)于算法步驟 d. 因?yàn)椋?→ FT′ 且 F不能推出 ? 所以 FIRST（ T） =FIRST（ F） ； 所以 FIRST（ T’） 不能被加入 FIRST（ T） 利用該算法還能方便地得到如下的符號(hào)串頭終結(jié)符號(hào)集： FIRST（ TE’） =FIRST（ T） =FIRST（ F） ={（ ， i} FIRST（ +TE’） =FIRST（ +） FIRST（ FT’） =FIRST（ F） ={（ ， i} FIRST（ *FT’） =FIRST（ *） ={*} FIRST（（ E）） =FIRST（（ ） ={（ } FIRST（ ε ） ={ε } 102 2)后繼終結(jié)符號(hào)集合 ① 定義 假定 S是文法 G的開始符號(hào)，對(duì)于 G的任何非終結(jié)符 A，我們定義 FOLLOW（ A） ={ a|S ?*… Aa… ,a ∈ Ｖ Ｔ } 特別是， 若 S ?*…A ，則規(guī)定 ∈ FOLLOW（ A） 即： FOLLOW（ A）是所有句型中出現(xiàn)在緊接 A之后的終結(jié)符或 103 ② 構(gòu)造后繼符號(hào)集合 FOLLOW的算法 對(duì)文法中每個(gè)非終結(jié)符Ａ ， 為了構(gòu)造ＦＯＬＬＯＷ （ Ａ ） ， 可反復(fù)應(yīng)用如下規(guī)則 ， 直到每個(gè)ＦＯＬＬＯＷ集不再擴(kuò)大為止 。 首先置 FIRST(α )=?,然后將 FIRST(X1)中一切非 ε 的符號(hào)加進(jìn) FIRST（ α ）中，若 ε ∈FIRST （Ｘ １ ），再將 FIRST（Ｘ ２ ）的一切非 ε 加進(jìn) FIRST（ α ）中，如此等等。 １ Ｙ ２ …Ｙ Ｋ 每個(gè)非終結(jié)符號(hào)都可能推導(dǎo)出空符號(hào)串 ， 即 Ｙ １ Ｙ ２ …Ｙ Ｋ ? *ε ， 則把 ε 也加進(jìn)ＦＩＲＳＴ （ Ｘ ） 中 。 ∈ Ｖ Ｎ ， 且有形如Ｘ ∷ ＝ aα 規(guī)則 （ a∈ Ｖ Ｔ ） ， 或Ｘ ∷ ＝ ε 的規(guī)則 ，把 a或 （ 和 ） ε 加入ＦＩＲＳＴ （ Ｘ ） 中 。 假定 α是文法 G的任一符號(hào)串 ，或者說 α∈ （ VTＵ VＮ ） * ， 我們定義 FIRST（ α ） ＝ ｛ a｜ α ?*a… ， a∈ Ｖ Ｔ ｝ 特別是 ， 若 α ?*ε ， 則規(guī)定 ε ∈ FIRST（ α ） 即 FIRST（ α ） 是 α 的所有可能推導(dǎo)的開頭終結(jié)符或可能的 ε 97 例如：設(shè)文法 G T ∷ ＝ AB A ∷ ＝ PQ|BC P ∷ ＝ pP|? Q ∷ ＝ qQ|? B ∷ ＝ bB|e C ∷ ＝ cC|f 求 FIRST（ PQ） 由定義有 PQ ?pPQ=p… PQ ? ? Q ? Q ? q Q ? q… PQ ? ? Q ? Q ? ? 所以 FIRST（ PQ） ={p,q, ?} 同理 FIRST（ BC) ={b,e} 對(duì)于一個(gè)簡(jiǎn)單的文法我們用手工可以求得其FIRST集 ， 對(duì)于復(fù)雜的文法我們通常使用下述算法求解 98 ② 構(gòu)造頭終結(jié)符號(hào)集合 FIRST的算法 對(duì)于文法中的每一個(gè)文法符Ｘ ∈ (Ｖ Ｎ ＵＶ Ｔ )， 構(gòu)造ＦＩＲＳＴ （ Ｘ ） 時(shí) ，