（3）构造预测分析表。 ）构造预测分析表。 a b （ E E’ T T’ F F’ P FT’ T PF’ ε (E) FT’ T PF’ ε a FT’ T PF’ ε b TE’ TE’ TE’
^ TE’
) ε
+
*
# ε ε
+E ε ε *F’
FT’ T PF’ ε ^ ε ε ε
（4）构造递归下降分析程序。 ）构造递归下降分析程序。 （1）设置过程advance为读下一个单词送全程变量 （2）设置过程error为错误处理程序 1. 主程序 Begin advance; E; End 2. E过程 过程 Procedure E Begin T; E’; end
E TE‘ E’ ＋E｜ε ｜ T FT‘ T’ T｜ε ｜ F PF‘ F’ *F‘｜ε ｜ P (E)｜a｜b｜＾ ｜ ｜ ｜＾
3. E’过程 过程 Procedure E’ Begin if sym=‘+’ then begin advance; E; end else if sym in [#,)] return else error
E TE‘ E’ ＋E｜ε ｜ T FT‘ T’ T｜ε ｜ F PF‘ F’ *F‘｜ε ｜ P (E)｜a｜b｜＾ ｜ ｜ ｜＾
4. T过程 过程 Procedure T Begin F; T’; End 5. T’过程 过程 Procedure T’ Begin if sym in [ ),+,# ] return else T end
（2）证明这个文法是 （1）的。 ）证明这个文法是LL（ ） i. 对产生式 对产生式P (E)｜a｜b｜^ ，有 ｜ ｜ ｜ FIRST((E))∩FISRT(a) ∩FIRST(b) ∩FIRST(^)=φ ∩ φ ii. 对产生式 对产生式E’ ＋E｜ε ｜ E TE‘ FIRST(+E) ∩FOLLOW(E’)= E’ ＋E｜ε ｜ {+} ∩ { ) , # }= φ T FT‘ 对产生式T’ T｜ε 对产生式 ｜ FIRST(T) ∩FOLLOW(T’)= T’ T｜ε ｜ { ( , a , b , ^ } ∩ {+, ) , # } = φ F PF‘ 对产生式F‘ *F’｜ε 对产生式 ｜ ｜ FIRST（*F’) ∩FOLLOW(F’)= F’ *F‘｜ε （ ｜ ｜ ｜＾ {*} ∩ {(, a , b , ^ , +, ) , # }= φ P (E)｜a｜b｜＾ iii. 文法不含左递归。 文法不含左递归。 可知，文法G是 （ ） 综上 i,ii,iii 可知，文法 是LL（1）的。
P91 习题 习题2 2、对下面的文法 ： 、对下面的文法G： E TE‘ E’ ＋E｜ε ｜ T FT‘ T’ T｜ε ｜ F PF‘ F’ *F‘｜ε ｜ P (E)｜a｜b｜＾ ｜ ｜ ｜＾ （1）计算这个文法的每个非终结符的 ）计算这个文法的每个非终结符的FIRST集和 集和 FOLLOW集。 集 （2）证明这个文法是 （1）的。 ）证明这个文法是LL（ ） （3）构造它的预测分析表。 ）构造它的预测分析表。 （4）构造它的递归下降分析程序。 ）构造它的递归下降分析程序。
E TE‘ E’ ＋E｜ε ｜ T FT‘ T’ T｜ε ｜ F PF‘ F’ *F‘｜ε ｜ P (E)｜a｜b｜＾ ｜ ｜ ｜＾
8. P过程 过程 Procedure P Begin if sym in [ a, b, ^] then advance else if sym =‘ ( ‘ then begin advance; E if sym=‘)’ then advance; else error; end else error; end
7. F’过程 过程 Procedure F Begin if sym=‘*’ then begin advance; F’ end else if sym in [ a, b, (, ), ^, +, # ] then return else error; end
E TE‘ E’ ＋E｜ε ｜ T FT‘ T’ T｜ε ｜ F PF‘ F’ *F‘｜ε ｜ P (E)｜a｜b｜＾ ｜ ｜ ｜＾
解：（1）计算 ）计算FIRST与FOLLOW集 与 集 FIRST(P)={ ( , a , b , ^ } FIRST(F’)={ * , ε} FIRST(F)=FIRST(P) ={ ( , a , b , ^ } FIRST(T’)=FIRST(T)∪{ε}={ ( , a , b , ^ , ε} ∪ε FIRST(T)=FIRST(F) ={ ( , a , b , ^ } FIRST(E’)={ + , ε } FIRST(E)=FIRST(T)={ ( , a , b , ^ }
FIRST E E’ T T’ F F’ P
(,a,b,^ +,ε (,a,b,^ (,a,b,^,ε (,a,b,^ *,ε
FOLLOW
),# ), +, ) , # +, ) , # (, a , b , ^ , +, ) , # (, a , b , ^ , +, ) , #
) , a , b , ^ *,(, a , b , ^ , +, ) , #
E TE‘ E’ ＋E｜ε ｜ T FT‘ T’ T｜ε ｜ F PF‘ F’ *F‘｜ε ｜
P (E)｜a｜b｜＾ ｜ ｜ ｜＾ FOLLOW(E)={ ) , # } FOLLOW(E’)=FOLLOW(E)={ ) , # } FOLLOW(T)=FIRST(E’)\ ε ∪FOLLOW(E)={+, ) , # } FOLLOW(T’)=FOLLOW(T)=={+, ) , # } FOLLOW(F)=FIRST(T’)\ ε ∪FOLLOW(T)={ (,a,b,^ , +, ) , # } FOLLOW(F’)=FOLLOW(F)={(, a , b , ^ , +, ) , # } FOLLOW(P)=FIRST(F’)\ ε ∪FOLLOW(F)={*,( ,a, b ,^,+ , ) ,# }
E TE‘ E’ ＋E｜ε ｜ T FT‘ T’ T｜ε ｜ F PF‘ F’ *F‘｜ε ｜ P (E)｜a｜b｜＾ ｜ ｜ ｜＾
6. F过程 过程 Procedure F Begin P; F’ end
E TE‘ E’ ＋E｜ε ｜ T FT‘ T’ T｜ε ｜ F PF‘ F’ *F‘｜ε ｜ P (E)｜a｜b｜＾ ｜ ｜ ｜＾