【文章內容簡介】 dure T’Begin If sym = ‘,’ Then begin Advance 。 S。 T’ Endsends。 （2）計算每個非終結符的FIRST集合和FOLLOW集合： FIRST（S）={a，∧，( } FIRST（T）={a，∧，( } FIRST（T’）={，ε} FOLLOW（S）={ )，’，’，} FOLLOW（T）={ ) } FOLLOW（T’）={ ) } 從而可見改造后的文法符合LL(1)文法的充分必要條件，所以是LL(1)的。 該文法的預測分析表a^(),SSaS^S(T)TTS T’TS T’TS T’T’T’ξT,S T’對下面的文法G： E→TE’ E’→+E∣ε T→FT’ T’→T∣ε F→PF’ F’→*F’∣ε P→(E)∣a∣b∣∧（1） 計算這個文法的每個非終結符的FIRST和FOLLOW。（2） 證明這個文法是LL(1)的。（3） 構造它的預測分析表。（4） 構造它的遞歸下降分析程序。分析：對于這類題目，我們首先應當檢查文法是否符合LL(1)文法的條件，根據(jù)需要，先通過消除左遞歸、提取右公因子的方法，把文法改造成符合LL(1)文法的條件，在此基礎上，我們才能構造出不帶回溯的遞歸下降識別程序。注意，本題在構造子程序時，對于每個產生式候選，在調用第一個非終結符對應的子程序之前，檢查了首符集。解：（1） 計算每個非終結符的FIRST集合和FOLLOW集合如下： FIRST（E）={(，a，b，∧} FIRST（E’）={+，ε} FIRST（T）={(，a，b，∧} FIRST（T’）={(，a，b，∧，ε} FIRST（F）={(，a，b，∧} FIRST（F’）={*，ε} FIRST（P）={(，a，b，∧} FOLLOW（E）={，)} FOLLOW（E’）={，)} FOLLOW（T）={+，)，} FOLLOW（T’）={+，)，} FOLLOW（F）={(，a，b，∧，+，)，} FOLLOW（F’）={(，a，b，∧，+，)，} FOLLOW（P）={*，(，a，b，∧，+，)，}（2） 本文法是LL ( 1 )文法。證明： 通過觀察可知文法中不含有左遞歸，滿足LL (1)文法定義的第一個條件?？紤]下列產生式： E’→+E∣ε T’→T∣ε F’→*F’∣ε P→(E)∣a∣b∣∧ 因為： FIRST（+E）∩FIRST（ε）={+}∩{ε}=216。 FIRST（E’）∩FOLLOW（E’）={+}∩{，)}= 216。 FIRST（T）∩FIRST（ε）={(，a，b，∧}∩{ε}=216。 FIRST（T’）∩FOLLOW（T’）={(，a，b，∧}∩{+，)，}=216。 FIRST（*F’）∩FIRST（ε）={*}∩{ε}=216。 FIRST（F’）∩FOLLOW（F’）={*}∩{(，a，b，∧，+，)，}= 216。 FIRST（（E））∩FIRST（a）∩FIRST（b）∩FIRST（∧）= 216。 所以該文法是LL(1)文法。（3） 構造其預測分析表： 預測分析表+ * ( ) a b ^ EE224。T E’E224。T E’E224。T E’E224。T E’E’E’224。+EE’ 224。ξE’ ξTT 224。FT’T’224。FT’T224。FT’T224。FT’T’T’224。ξT’ 224。 TT’224。ξT’224。TT’224。TT’ 224。TT’224。ξFF 224。PF’F224。PF’P224。PF’F224。PF’F’F’ 224。 ξF’ 224。*F’F’ 224。 ξF’224。ξF’224。ξF’224。ξF’224。ξF’224。ξPP 224。(E)P224。aP224。bP224。 ^（4） 構造其遞歸下降分析程序： Procedure E。 Begin T 。 E’ End 。Procedure E’ 。 Begin If sym = ‘ + ’Then begin Acvance 。 E End End 。Procedure T 。 Begin F 。 T’End 。Procedure T’ 。Begin If sym ∈first ( T ) Then T Else if sym = ‘*’ then errorEnd 。Procedure F 。Begin If sym ∈first ( P ) P。 F’。End 。 Procedure F’ Begin If sym = ‘ * ’ Then begin Advance 。 F’ End End。Procedure P Begin If sym = ‘ a ’ or sym = ‘ b ‘ or sym = ‘ ^Then acvance Else if sym = ‘ ( ‘ Then begin Advance 。 E 。 If sym = ‘ ) ‘ Then advance Else error End Else error End。 下面文法中，哪些是LL(1)的，說明理由。 （1）、 S→Abc A→a∣ε B→b∣ε （2）、 S→Ab A→a∣B∣ε B→b∣ε （3）、 S→ABBA A→a∣ε B→b∣ε （4）、 S→aSe∣B B→bBe∣C C→cCe∣d 分析：判斷文法是否是LL(1)的，要根據(jù)LL(1)文法的條件逐一檢查：首先要確定文法不含左遞歸；隨后計算文法的各非終結符（X）的首符集FIRST（X）和隨符集FOLLOW（X）。首先要理解這兩個集合的計算方法，特別要注意算法終止的條件：直到集合不再變化為止。也就是說，反復檢查每一個產生式，直到從頭到尾檢查了所有產生式，而FIRST集合和FOLLOW集合都沒有變化了，這時候計算才能結束。最后根據(jù)LL(1)文法的充分必要條件（即LL(1)文法定義）來判斷是否是LL(1)文法。 解：（1） 該文法不含左遞歸，計算每個非終結符的FIRST集合和FOLLOW集合如下： FIRST（S）={a，b，c} FIRST（A）={a，ε} FIRST（B）={b，ε} FOLLOW（S）={} FOLLOW（A）={b，c} FOLLOW（B）={c} 可見該文法滿足LL(1)文法的三個條件，是LL(1)文法。（2） 該文法不含左遞歸，計算每個非終結符的FIRST集合和FOLLOW集合如下： FIRST（S）={a，b} FIRST（A）={a，b，ε} FIRST（B）={b，ε} FOLLOW（S）={} FOLLOW（A）= FOLLOW（B）= 考慮A→a∣B∣ε，因為FIRST（B）∩FOLLOW（A）=≠216。，所以該文法不是LL(1)文法。（3） 該文法不含左遞歸，計算每個非終結符的FIRST集合和FOLLOW集合如下： FIRST（S）={a，b，ε} FIRST（A）={a，ε} FIRST（B）={b，ε} FOLLOW（S）={} FOLLOW（A）={a，b，} FOLLOW（B）={a，b，} 考慮A→a∣ε和B→b∣ε，因為 FIRST（a）∩FOLLOW（A）={a}≠216。 FIRST（b）∩FOLLOW（B）=≠216。 所以該文法不是LL(1)文法。（4） 該文法不含左遞歸，計算每個非終結符的FIRST集合和FOLLOW集合如下： FIRST（S）={a，b，c，d} FIRST（B）={b，c，d} FIRST（C）={c，d} FOLLOW（S）={e，} FOLLOW（B）={e，} FOLLOW（C）={e，} 可見該文法滿足LL(1)文法的三個條件，是LL(1)文法。 對下面文法： Expr→Expr Expr→(Expr)∣Var ExprTail→Expr∣ε Var→id VarTail VarTail→(Expr)∣ε （1）、構造LL(1)分析表。 （2）、給出對句子idid((id))的分析過程。 分析：構造文法的預測分析表，通常應當按下列順序進行：（1）、消除文法的左遞歸（包括所有直接左遞歸和間接左遞歸）；（2）、對消除左遞歸后的文法，提取左公因子；（3）、對經過上述改造后的文法，計算它的每個非終結符的FIRST集合和FOLLOW集合；（4）、根據(jù)FIRST集合和FOLLOW集合構造預測分析表。 第一步對文法G的每個產生式A→α執(zhí)行第一步和第三步；第二步對每個終結符a∈FIRST(α)，把A→α加至M[A，a]中；第三步若ε∈FIRST(α)，則對任何b∈FOLLOW(A)把A→α加至M[A，b]中；第四步把所有無定義的M[A，a]標上“出錯標志”。 解： （1）、計算每個非終結符的FIRST集合和FOLLOW集合如下： FIRST(Expr)={，(，id} FIRST(ExprTail)={，ε} FIRST(Var)={id} FIRST(VarTail)={(，ε} FOLLOW(Expr)={)，} FOLLOW(ExprTail)={)，} FOLLOW(Var)={，)，} FOLLOW(VarTail)={，∣，} 構造其預測分析表如下： id()ExprExpr→ ExprExpr ExprExpr→( Expr)ExprTailExprTail→ExprExprTail→εExprTail→εVarVar→id VarTailVarTailVarTail→εVarTail→(Expr)VarTail→εVarTail→ε （2）、句子idid((id))的分析過程如下： 步驟符號棧輸入串所用產生式0 Expridid((id)) 1 ExprTail Varidid((id)) Expr→Var ExprTail2 ExprTail VarTail ididid((id)) Var→id V