【正文】 產生式不匹配 end if。 exit when x=。 id num + * / mod ( ) 。L E。L ε E TE39。 TE39。 +TE39。 ε ε T FT39。 FT39。 ε ε *FT39。 mod FT39。 27 4 用預測分析器分析句子（續(xù)） 棧 當前剩余輸入 動作 L id+id*id。L) (L→E。E id+id*id。) (E→TE39。E39。 pop(T), push(FT39。) L。T39。 pop(F), push(id) (F→id) L。T39。 pop(id), next(ip) id L。T39。 pop(T39。→ε) L。 +id*id。), push(+TE39。→+TE39。E39。 pop(+), next(ip) + L。T id*id。) (T→FT39。E39。F id*id。E39。id id*id。E39。 *id。), push(*FT39。→*FT39。E39。F* *id。E39。F id。E39。id id。E39。 。) (T39。E39。 pop(E39?！? L。 pop(。 L pop(L) (L→ε) 正確結束 28 構造預測分析表 1. 首先構造 FIRST集合與 FOLLOW集合； 2. 然后根據(jù)兩個集合構造預測分析表。 ■ 通俗地講， α 的 FIRST集合就是從 α 開始可以導出的文法符號序列中的開頭終結符。 例如： FIRST(E)={ (， id, num } FOLLOW(E)={ )， 。L|ε E →TE39?！?TE39。|ε T →FT39?！?FT39。|mod FT39。 ■ 29 構造預測分析表（續(xù) 1） 算法 計算 X的 FIRST集合 輸入 文法符號 X 輸出 X的 FIRST集合 方法 應用下述規(guī)則： 1. 若 X∈T ， 則 FIRST(X)={X}； 2. 若 X是非終結符且有 X→ε ， 則加入 ε 到 FIRST(X)； 3. 若 X 是非終結符且有 X→Y 1Y2...Yk， 并設 Y0=ε ，Yk+1=ε 。 ■ ? 對任意文法符號序列 X1X2...Xn， FIRST(X1X2...Xn)的計算方法與算法 步驟 3類似 ? 即： FIRST(X1X2...Xn)是所有 FIRST(Xi)(i=1,2,..,k)的并集 ? 其中 k為第一個具有性質 ε 不屬于 FIRST(Yj)或 kn的文法符號 ? 若 kn，則 ε∈FIRST(X1X2...Xn ） 再考慮： FIRST(E)=FIRST(TE39。E39。L|ε E →TE39。→+TE39。|ε T →FT39?！?FT39。|mod FT39。 3. 若有產生式 A→αB 或 A→αBβ 而 ε∈FIRST(β) ， 則FOLLOW(A)的全體加入到 FOLLOW(B)。 提示： 自下而上計算 FIRST 自上而下計算 FOLLOW(為什么 ?) L →E 。 E39。| TE39。 T39。|/FT39。|ε F →(E)|id|num FIRST(F) = {( id num} FIRST(T39。) = {+ ε} FIRST(E) = FIRST(T) = FIRST(F) = {( id num} FIRST(L) = {ε}∪FIRST(E) = {ε ( id num} FOLLOW(L) = {} FOLL0W(E) = {) 。) = {) 。 )} FOLLOW(T39。 )} FOLLOW(F) = {+ * / mod ) 。 ■ M[A， a]如何指導下一步動作： 1. 若當前棧頂為 A， 當前輸入為 a， 則 規(guī)則 2表示下一步動作是展開 A→α ， 因為 a∈FIRST(α) ， 所以展開后下一次正好匹配 a。 33 構造預測分析表（續(xù) 5） FIRST(F/T/E)= {( id num} FIRST(T39。) = {+ ε} FIRST(L) = {ε ( id num} FOLLOW(L) = {} FOLL0W(E/E39。} FOLLOW(T/T39。 )} FOLLOW(F) = {+ * / mod ) 。 L E E39。 F E。L E。 TE39。 +TE39。 FT39。 FT39。 /FT39。 id num (E) ε ε ε ε ε ε ε 34 LL(1)文法 M[A,a]的作用： 指導產生式產生句子（指導推導） 問題： 是否為任意文法構造的分析表 M[A,a]中都最多有一個條目？ 例 二義文法文法的預測分析表： 文法： S→iCtSS39?！鷈S|ε C→b a b e i t S S39。) = {ε, e} FIRST(S) = {i, a} FOLLOW(S) = {, e} FOLLOW(S39。 b eS ε ε 35 LL(1)文法（續(xù) 1） 定義 文法 G被稱為是 LL(1)文法 ， 當且僅當為它構造的預測分析表中不含多重定義的條目。第一個 L代表從左到右掃描輸入序列，第二個 L表示產生最左推導， 1表示在確定分析器的每一步動作時向前看一個終結符。 推論 G是 LL(1)的 ， 當且僅當 G的任何兩個產生式 A→α|β滿足 : 1. 對任何終結符 a， α 和 β 不能同時推導出以 a開始的串 ； 2. α 和 β 最多有一個可以推導出 ε ； 3. 若 β= *ε, 則 α 不能導出以 FOLLOW(A)中終結符開始的任何串。 ■ 37 LL(1)文法（續(xù) 3） 推論 G是 LL(1)的 ， 當且僅當 G的任何兩個產生式 A→α|β 滿足 : 1. 對任何終結符 a， α 和 β 不能同時推導出以 a開始的串 ； 2. α 和 β 最多有一個可以推導出 ε ； 3. 若 β= *ε, 則 α 不能導出以 FOLLOW(A)中終結符開始的任何串。 (1) E39。|ε (2) (39。 (3) T39。|ε (4) F →(E) | F|id (5)..(7) E→E+T|T T→T*F|F () F→(E)| F|id 文法 ()不是 LL(1)的，因為不滿足條件 1。（為什么？） 文法 (39。 具體判斷請同學們自己做。為什么？（考慮算術表達式文法）， 二義文法呢？ 38 LL(1)文法（續(xù) 4） LL(1)文法的弱點： 1. 文法難寫 、 難懂； 2. 適應范圍有限 ， 往往寫不出有些語言的 LL(1)文法 。 結束（ 2022年 4月 5日） 下周二交語法分析前 4次課作業(yè)