【正文】 8）現(xiàn)在第５個輸入字符是‘ a?，于是讀入下一個字符，它又是‘ a? 主返 TOP→ SCIN ch=?e?? 1 2 READ P(B) ch=?a?? ERROR READ P(A) ERROR SCOUT = ≠ = ≠ 3 4 5 6 7 8 子程序 P(E) 72 ch e a d e a a （ 19） P(E)子程序調用子程序 P(A)， P(A)調用遞歸入口子程序 SCIN，將 P(A)在 P(E)中的返回地址送入返回棧中 主返 P(E):8 TOP→ SCIN ch=?e?? 1 2 READ P(B) ch=?a?? ERROR READ P(A) ERROR SCOUT = ≠ = ≠ 3 4 5 6 7 8 子程序 P(E) 73 ch e a d e a a （ 19） P(E)子程序調用子程序 P(A)， P(A)調用遞歸入口子程序 SCIN，將 P(A)在 P(E)中的返回地址送入返回棧中 主返 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 74 ch e a d e a a （ 20）子程序 P(A)判斷 ch?＝’ a?。 主返 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)調用遞歸出口子程序 SCOUT，將返回棧中 P(A)在 P(E)中的返回地址 P(E):8取出。 主返 TOP→ SCIN ch=?e?? 1 2 READ P(B) ch=?a?? ERROR READ P(A) ERROR SCOUT = ≠ = ≠ 3 4 5 6 7 8 子程序 P(E) 79 ch e a d e a a （ 21） P(E)調用遞歸出口子程序 SCOUT，將返回棧中 P(E)在主程序中的返回地址取出，即返回主程序，結束。 也就是說 ， 字符串 eadeaa被語法分析程序 所接受 ， 這表明字符串 ‘ eadeaa’是文法Ｇ （ Ｅ ）的句子 。 BEGIN IF ch=’+’ THEN BEGIN getch(ch)。 E’ END END 規(guī)則 E::=TE’ PROCEDURE E。 E’ END 83 規(guī)則 T::=FT’ PROCEDURE T。 T’ END 規(guī)則 T’::=*FT’|ε PROCEDURE T’。 F。 BEGIN IF CH=‘(‘ THEN BEGIN getch(ch)。 IF ch=‘)’ THEN getch(ch) ELSE error END ELSE IF CH=’i‘ THEN getch(ch) ELSE error END 規(guī)則 F::=(E)|i 85 4. 遞歸子程序法特點 ? 優(yōu)點 （ 1）程序結構和層次清晰，易于手工實現(xiàn) 。 （ 3）可以加入語義加工子程序 ? 缺點 （ 1）編寫程序和調試工作量大 （ 2）對上下文無關文法需要改寫 86 四、 LL（ 1）分析法 （ 1）分析方法 （ 1）文法 87 1. 定義 LL（ 1） 分析方法也是一種自頂向下不帶回溯的分析方法， LL的意思是：從左（ Left）到右掃描輸入符號串并建立它的最左推導（ Left most derivations）。如果向前查看 K個符號（ K1）才能確定應選規(guī)則時，這種語法分析方法就稱 LL（ K） 分析法。 我們通常把按 LL（ 1） 方法執(zhí)行語法分析任務的程序稱為 LL（ 1） 分析程序或 LL（ 1） 分析器 ， 它由一個總控程序 、 一張分析表和一個分析棧組成 ， 如下 圖 所示 。 90 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) 91 由上述分析過程可以看出 ， 在分析的每一時刻 ， 當前已讀過的符號與棧中的符號一起總是構成了當前的左句型 ， ＬＬ （ １ ） 分析器確實構造了輸入串的一個最左推導 。 然后反復執(zhí)行第 （ 2） 步 2） 設在分析的某一步 ， 分析棧及余留的輸入符號串處于如下格局 X1X2… Xm1Xm aiai+1… 其中 ， Ｘ １ ， Ｘ ２ ， …， Ｘ m為分析過程中所得的文法符號 ， 此時 ， 可視棧頂符號Ｘ m的不同情況 ，分別做如下的動作 : 93 ① 若Ｘ m∈ Ｖ Ｎ ， 則以Ｘ m及 ai組成符號對 （ Ｘ m， ai）查分析表Ｍ ， 設Ｍ ［ Ｘ m,ai］ 為一產生式 ， 譬如說Xm→ ＵＶＷ ， 此時將Ｘ m從分析棧中退出 ， 并將ＵＶＷ按反序推入棧中 （ 即用該產生式推導一步 ） ，從而得到新的格局 : X1X2… Xm1WVU aiai+1… 但若Ｍ ［ Ｘ m， ai］ ＝ “ ＥＲＲＯＲ ” ， 則調用出錯處理程序進行處理 。 95 (4)幾點說明 ? 分析表 M根據(jù)具體文法構造，文法不同 M就不同 ? LL（ 1）分析法的總控程序對于不同文法總是一樣的。 96 3. 構造分析表 （ 1） 頭終結符號集合和后繼終結符號集合 1） 頭終結符號集合 ① 定義 為了構造分析表 ， 我們引進與文法有關的集合FIRST集和 FOLLOW集 。 X∈ Ｖ Ｔ ， 則ＦＩＲＳＴ （ Ｘ ） ＝ ｛ Ｘ ｝ 。 ∷ ＝Ｙ １ Ｙ ２ …YＫ 的規(guī)則 ， 若Ｙ １ ∈ Ｖ Ｎ ， 則將 FIRST（ Ｙ １ ） 中一切非 ε 符號加進ＦＩＲＳＴ （ Ｘ ） 中 ， 對于一切 2≤i≤k ， 若Ｙ １ ?*ε ， 則把Ｙ 2中首符號集 （ 除 ε 外 ） 也加進 FIRST（ Ｘ ）中 ， 如此繼續(xù)下去 ， 直到Ｙ k1 ? *ε ， 則把 YK中首符號集 (除 ε 外 )也入FIRST(X)中 。 99 現(xiàn)在，可以對文法 G的任何符號串 α ＝Ｘ１Ｘ２ …Ｘ n， 可按如下步驟構造 FIRST（ α ）。最后，若對于１ ≤ i≤n ， ε ∈ ＦＩＲＳＴ（Ｘ i），則再將 ε 加進ＦＩＲＳＴ（ α ）中。 ， 令 ∈ ＦＯＬＬＯＷ（ Ｓ ） 。 ∷ ＝ α B或Ａ ∷ ＝ α Bβ 的規(guī)則 ，且 β ?*ε ， 則ＦＯＬＬＯＷ （ Ａ ） 中全部終結符均屬于ＦＯＬＬＯＷ （ Ｂ ） 104 考慮文法Ｇ ［ Ｅ ］ : ① Ｅ → ＴＥ ′ ② Ｅ ′ → ＋ＴＥ ′ ｜ ε ③ Ｔ → FT′ ④ Ｔ ′ →* ＦＴ ′ ｜ ε ⑤ Ｆ → （ Ｅ ） ｜ i FOLLOW（ E） ＝ { ＃ ,） } 由算法步驟 ： ∈ FOLLOW（ E） (E是文法開始符號 ） 由算法步驟 ⑤ 得： ） ∈ FOLLOW（ E） 所以 FOLLOW（ E） ＝ { ＃ ,） } FOLLOW（ E’） ＝ { ＃ ,） } 由算法步驟 ① 得： FOLLOW(E)? FOLLOW(E’) 所以 FOLLOW（ E’） ＝ { ＃ ,） } 105 考慮文法Ｇ ［ Ｅ ］ : ① Ｅ → ＴＥ ′ ② Ｅ ′ → ＋ＴＥ ′ ｜ ε ③ Ｔ → FT′ ④ Ｔ ′ →* ＦＴ ′ ｜ ε ⑤ Ｆ → （ Ｅ ） ｜ i FOLLOW（ T） ＝ { +,＃ ,） } 1)由算法步驟 ① 、 ② 得： +∈ FOLLOW（ T） (因為 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） (因為 FIRST(T’) {ε }={*}) 2)由算法步驟 ③ 得： FOLLOW（ T） ?FOLLOW（ F） 即 {+,） ， } ?FOLLOW(F)} (由規(guī)則 ④ 得：Ｔ ′ ?*ε ,所以由算法 ③ 得： FOLLOW（ T’） ?FOLLOW（ F） 即 {+,） ， } ?FOLLOW(F)} 所以 FOLLOW（ T） ＝ { +,*,＃ ,） } 108 (2)構造分析表 M 1)構造分析表 M算法 求出ＦＩＲＳＴ集和ＦＯＬＬＯＷ集后 ， 就可以構造文法Ｇ的ＬＬ （ １ ） 分析表 ， 對于Ｇ中每一個規(guī)則Ａ ∷ ＝α ， 可按如下算法確定表中各元素 ① 對ＦＩＲＳＴ （ α ） 中每一終結符 a， 置Ｍ ［ A,a］ ＝“ Ａ → α ” ② 若 ε ∈ ＦＩＲＳＴ （ α ） ， 則對屬于ＦＯＬＬＯＷ（ Ａ ） 中的每一符號 b(b為終結符或＃ )， 置Ｍ ［ Ａ ， b］＝ “ Ａ → α ”； ③ 把Ｍ中所有不能按規(guī)則 ① 、 ② 定義的元素均置為出錯 。 所謂 多重定義入口 是指分析表中某 M[A， a]有兩個或兩個以上產生式。 對 LL（ 1） 文法進行 LL（ 1）分析才是有意義的 。 我們可以按照上述方法構造它的分析表 ,從該表可以看出 ,元素 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)文法性質 LL（ 1） 文法有一些明顯的性質 ， 它 不是二義的 ， 也 不含左遞歸 。 2) α 和 β 中最多只有一個可能推出空串 。 自底向上語法分析 120 例 設有文法 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是否為此文法的句子。對符號串 abbcde分析過程如下所示