《对下面的文法G》PPT课件.ppt

P91 习题2 2、对下面的文法G： ETE EE TFT TT FPF F*F P(E)ab （1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。 （2）证明这个文法是LL（1）的。 （3）构造它的预测分析表。 （4）构造它的递归下降分析程序。,解：（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 , 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 ,+ , ) ,# ,ETE EE TFT TT FPF F*F P(E)ab,（2）证明这个文法是LL（1）的。 对产生式P(E)ab ，有 FIRST(E)FISRT(a) FIRST(b) FIRST()= 对产生式EE FIRST(+E) FOLLOW(E)= + ) , # = 对产生式TT FIRST(T) FOLLOW(T)= ( , a , b , +, ) , # = 对产生式F*F FIRST（*F) FOLLOW(F)= * (, a , b , , +, ) , # = 文法不含左递归。 综上 i,ii,iii 可知，文法G是LL（1）的。,ETE EE TFT TT FPF F*F P(E)ab,（3）构造预测分析表。,（1）设置过程advance为读下一个单词送全程变量 （2）设置过程error为错误处理程序,1. 主程序 Begin advance; E; End 2. E过程 Procedure E Begin T; E; end,（4）构造递归下降分析程序。,ETE EE TFT TT FPF F*F P(E)ab,3. E过程 Procedure E Begin if sym=+ then begin advance; E; end else if sym in #,) return else error,ETE EE TFT TT FPF F*F P(E)ab,4. T过程 Procedure T Begin F; T; End 5. T过程 Procedure T Begin if sym in ),+,# return else T end,ETE EE TFT TT FPF F*F P(E)ab,6. F过程 Procedure F Begin P; F end,ETE EE TFT TT FPF F*F P(E)ab,7. F过程 Procedure F Begin if sym=* then begin advance; F end else if sym in a, b, (, ), , +, # then return else error; end,ETE EE TFT TT FPF F*F P(E)ab,8. P过程 Procedure P Begin if sym in a, b, then advance else if sym = ( then begin advance; E