【正文】 a1 a2 … ai … an 輸入串 總控程序 分析表 m X . . . 分析棧 167。 自頂向下語法分析 三、 LL(1)分析法 （ 2） LL（ 1） 方法分析過程 考慮文法Ｇ ［ Ｅ ］ : Ｅ → ＴＥ ′ Ｅ ′→ ＋ＴＥ ′｜ ε Ｔ → FT′ Ｔ ′→* ＦＴ ′｜ ε Ｆ → （ Ｅ ） ｜ i 1） 建立文法 LL（ 1） 的分析表 相應(yīng)的分析表如 下表 所示 （ 其構(gòu)造方法 ， 在后面敘述 )。 97 167。 自頂向下語法分析 三、 LL(1)分析法 98 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) 167。 自頂向下語法分析 三、 LL(1)分析法 99 由上述分析過程可以看出 ， 在分析的每一時刻 ， 當(dāng)前已讀過的符號與棧中的符號一起總是構(gòu)成了當(dāng)前的左句型 ， ＬＬ （ １ ） 分析器確實構(gòu)造了輸入串的一個最左推導(dǎo) 。 2） 分析過程 現(xiàn)在以輸入符號串 i＋ i*i為例 ， 列出利用上述算法對此符號串的分析過程如下 : 步驟 分析棧 余留輸入串 所用產(chǎn)生式 (1) E i+i*i E→TE’ (2) E’T i+i*i T→FT’ (3) E’T’F i+i*i F→i (4) E’T’i i+i*i (5) E’T’ +i*i T’→ε (6) E’ +i*i E→+TE’ (7) E’T+ +i*i (8) E’ T i*i T→FT’ (9) E’T’F i*i F→i (10) E’T’i i*i (11) E’T’ *i T’→*FT’ (12) E’T’F* *i (13) E’T’F i F→ i (14) E’T’i i (15) E’T’ T’→ ε (16) E’ E’→ ε (17) 成功 （ 3） 一般分析步驟 其中 “ 輸入 ” 就是待分析的符號串 ， 它以右界符 作為結(jié)尾 。 分析表Ｍ可 用一個矩陣 （ 或二維數(shù)組 ） 來表示 。 它概括了相應(yīng)文法的全部信息 。 分析表的每一行與文法的一個非終結(jié)符Ａ相關(guān)聯(lián) ， 而每一列則與文法的 一個終結(jié)符號或 相關(guān)聯(lián) 。 分析表元素Ｍ ［ Ａ ， a］ （ a∈ Ｖ Ｔ U｛ ｝） 或者指示了當(dāng)前推導(dǎo)所應(yīng)使用的產(chǎn)生式 ， 或者指出了輸入串中含有語法 錯誤 。 分析器對每個輸入串的分析在總控程序控制下進(jìn)行 。 100 167。 自頂向下語法分析 三、 LL(1)分析法 其步驟如下： 1） 分析開始時 ， 首先將符號 及文法的開始符號Ｓ依次置于分析棧的 底部 ， 并把各指示器調(diào)整至起始位置 ,即分別指向分析棧的棧頂元素和輸入串的首字符 。 然后反復(fù)執(zhí)行第 （ 2） 步 2） 設(shè)在分析的某一步 ， 分析棧及余留的輸入符號串處于如下格局 X1X2… Xm1Xm aiai+1… 其中 ， Ｘ １ ， Ｘ ２ ， … ， Ｘ m為分析過程中所得的文法符號 ， 此時 ， 可 視棧頂符號Ｘ m的不同情況 ， 分別做如下的動作 : 101 167。 自頂向下語法分析 三、 LL(1)分析法 ① 若Ｘ m∈ Ｖ Ｎ ， 則以Ｘ m及 ai組成符號對 （ Ｘ m， ai） 查分析表Ｍ ， 設(shè) Ｍ ［ Ｘ m,ai］ 為一產(chǎn)生式 ， 譬如說 Xm→ ＵＶＷ ， 此時將Ｘ m從分析棧中 退出 ， 并將ＵＶＷ按反序推入棧中 （ 即用該產(chǎn)生式推導(dǎo)一步 ） ， 從而得 到新的格局 : X1X2… Xm1WVU aiai+1… 但若Ｍ ［ Ｘ m， ai］ ＝ “ ＥＲＲＯＲ ” ， 則調(diào)用出錯處理程序進(jìn)行處理 。 ② 若Ｘ m＝ ai≠， 則表明棧頂符號已與當(dāng)前正掃視的輸入符號得到匹配 ， 此時應(yīng)將Ｘ m（ 即 ai） 從棧中退出 ， 并將輸入符號指示器向前推進(jìn)一個 ③ 若Ｘ m＝ ai＝ ， 則表明輸入串已完全得到匹配 ， 此時即可宣告分析 成功而結(jié)束分析工作 。 102 167。 自頂向下語法分析 三、 LL(1)分析法 (4)幾點說明 1) 分析表 M根據(jù)具體文法構(gòu)造，文法不同 M就不同 2) LL（ 1）分析法的總控程序?qū)τ诓煌姆偸且粯拥摹? 3) 分析表 M[A， a]或指出應(yīng)選規(guī)則或指出錯誤（空白時） 4) LL（ 1）語法分析程序的機(jī)器模型是一個下推自動機(jī) 103 構(gòu)造一個 LL（ 1） 分析器問題 ， 主要歸結(jié)為構(gòu)造 LL（ 1） 分析表的問題 。 167。 自頂向下語法分析 三、 LL(1)分析法 一、自頂向下分析方法的問題及其解決辦法 二、遞歸子程序分析法（遞歸下降分析法） 三、 LL（ 1）分析法 （ 1）分析方法 （ 1）文法 104 167。 自頂向下語法分析 三、 LL(1)分析法 105 3. 構(gòu)造分析表 （ 1） 頭終結(jié)符號集合和后繼終結(jié)符號集合 1） 頭終結(jié)符號集合 ① 定義 為了構(gòu)造分析表 ， 我們引進(jìn)與文法有關(guān)的集合 FIRST集和 FOLLOW集 。 假定 α是文法 G的任一符號串 ， 或者說 α∈ (VTＵ VＮ )* ， 我們定義 FIRST（ α） ＝ ｛ b｜ α?*b… ， b∈ Ｖ Ｔ ｝ 特別是 ， 若 α?*ε， 則規(guī)定 ε∈ FIRST（ α） 即 FIRST（ α） 是 α的所有可能推導(dǎo)的開頭終結(jié)符或可能的 ε 167。 自頂向下語法分析 三、 LL(1)分析法 106 例如：設(shè)文法 G T ∷ ＝ AB A ∷ ＝ PQ|BC P ∷ ＝ pP|? Q ∷ ＝ qQ|? B ∷ ＝ bB|e C ∷ ＝ cC|f 求 FIRST（ PQ） 由定義有 PQ ?pPqQ=p… PQ ? ? Q ? Q ? q Q ? q… PQ ? ? Q ? Q ? ? 所以 FIRST（ PQ） ={p,q, ?} 同理 FIRST（ BC) ={b,e} 對于一個簡單的文法我們用手工可以求得其 FISRT集 ， 對于復(fù)雜的文法我們通常使用下述算法求解 167。 自頂向下語法分析 三、 LL(1)分析法 ② 構(gòu)造頭終結(jié)符號集合 FIRST的算法 對于文法中的每一個文法符Ｘ ∈ (Ｖ Ｎ ＵＶ Ｔ )， 構(gòu)造ＦＩＲＳＴ （ Ｘ ） 時 ， 只要連續(xù)使用下列規(guī)則 ， 直至每個ＦＩＲＳＴ集不再擴(kuò)大為止 。 X∈ Ｖ Ｔ ， 則ＦＩＲＳＴ （ Ｘ ） ＝ ｛ Ｘ ｝ 。 ∈ Ｖ Ｎ ， 且有形如Ｘ ∷ ＝ bα規(guī)則 （ b∈ Ｖ Ｔ ） ， 或Ｘ ∷ ＝ ε的規(guī)則 ， 把 b或 （ 和 ） ε加入ＦＩＲＳＴ （ Ｘ ） 中 。 ∷ ＝Ｙ １ Ｙ ２ … YＫ 的規(guī)則 ， 若Ｙ １ ∈ Ｖ Ｎ ， 則將 FIRST（ Ｙ １ ） 中一切非 ε符號加進(jìn)ＦＩＲＳＴ （ Ｘ ） 中 ， 對于一切 2≤i≤k， 若Ｙ １ ?*ε， 則把Ｙ 2中首符號集 （ 除 ε外 ） 也加進(jìn) FIRST（ Ｘ ） 中 ，如此繼續(xù)下去 ， 直到Ｙ k1 ? *ε， 則把 YK中首符號集 (除 ε外 )也入FIRST(X)中 。 １ Ｙ ２ … Ｙ Ｋ 每個非終結(jié)符號都可能推導(dǎo)出空符號串 ， 即 Ｙ １ Ｙ ２ … Ｙ Ｋ ? *ε， 則把 ε也加進(jìn)ＦＩＲＳＴ （ Ｘ ） 中 。 107 167。 自頂向下語法分析 三、 LL(1)分析法 現(xiàn)在，可以對文法 G的任何符號串 α＝Ｘ １ Ｘ ２ … Ｘ n， 可按如下步驟構(gòu)造 FIRST（ α）。 首先置 FIRST(α)=?,然后將 FIRST(X1)中一切非 ε的符號加進(jìn) FIRST（ α） 若 ε∈ FIRST（Ｘ １ ），再將 FIRST（Ｘ ２ ）的一切非 ε加進(jìn) FIRST（ α） 中，如此等等。最后，若對于１ ≤i≤n， ε∈ ＦＩＲＳＴ（Ｘ i），則再將 ε加進(jìn)ＦＩＲＳＴ（ α）中。 108 考慮文法Ｇ ［ Ｅ ］ : Ｅ → ＴＥ ′ Ｅ ′→ ＋ＴＥ ′｜ ε Ｔ → FT′ Ｔ ′→* ＦＴ ′｜ ε Ｆ → （ Ｅ ） ｜ i 由算法步驟 FIRST（ +） ={+} FIRST（ *） ={*} FIRST（（ ） ={（ } FIRST（ ）） ={） } FIRST（ i） ={i} 由算法步驟 FIRST（ E’） ={+， ε} FIRST（ T’） ={*， ε} FIRST（ F） ={（ ， i} 167。 自頂向下語法分析 三、 LL(1)分析法 109 文法Ｇ ［ Ｅ ］ : Ｅ → ＴＥ ′, Ｅ ′→ ＋ＴＥ ′｜ ε, Ｔ → FT′ Ｔ ′→* ＦＴ ′｜ ε , Ｆ → （ Ｅ ） ｜ i 對于算法步驟 d. 因為Ｔ → FT′ 所以 將 FIRST（ F） 中非 ? 的所有符號加入 FIRST（ T） 中 ， 又因為 F不能推出 ?， 所以 FIRST（ T’） 不能被加入 FIRST（ T） 167。 自頂向下語法分析 三、 LL(1)分析法 110 利用該算法還能方便地得到如下的符號串頭終結(jié)符號集： FIRST（ TE’） =FIRST（ T） =FIRST（ F） ={（ ， i} FIRST（ +TE’） =FIRST（ +） FIRST（ FT’） =FIRST（ F） ={（ ， i} FIRST（ *FT’） =FIRST（ *） ={*} FIRST（（ E）） =FIRST（（ ） ={（ } FIRST（ ε） ={ε} 167。 自頂向下語法分析 三、 LL(1)分析法 2)后繼終結(jié)符號集合 ① 定義 假定 S是文法 G的開始符號，對于 G的任何非終結(jié)符 A，我們定義 FOLLOW（ A） ={ c | S ?*…Ac…, c ∈ Ｖ Ｔ } 特別是，若 S ?*…A ，則規(guī)定 ∈ FOLLOW（ A） 即： FOLL