对下面的文法G

对下面的文法GP912、对下面的文法G：ETE‘E’＋E｜

TFT‘T’T｜

FPF‘F’*F‘｜

P(E)｜a｜b｜＾（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‘E’＋E｜

TFT‘T’T｜

FPF‘F’*F‘｜

P(E)｜a｜b｜＾FIRSTFOLLOWE(,a,b,^),#E’+,),#T(,a,b,^+,),#T’(,a,b,^,

+,),#F(,a,b,^(,a,b,^,+,),#F’*,

(,a,b,^,+,),#P),a,b,^*,(,a,b,^,+,),#（2）证明这个文法是LL（1）的。对产生式P(E)｜a｜b｜^，有FIRST((E))FISRT(a)FIRST(b)FIRST(^)=对产生式E’＋E｜

FIRST(+E)FOLLOW(E’)={+}{),#}=

对产生式T’T｜

FIRST(T)FOLLOW(T’)=

{(,a,b,^}{+,),#}=

对产生式F‘*F’｜

FIRST（*F’)FOLLOW(F’)={*}{(,a,b,^,+,),#}=

文法不含左递归。综上i,ii,iii可知，文法G是LL（1）的。ETE‘E’＋E｜

TFT‘T’T｜

FPF‘F’*F‘｜

P(E)｜a｜b｜＾（3）构造预测分析表。（ab^)+*#E

TE’

TE’

TE’

TE’E’

+E

T

FT’

FT’

FT’

FT’T’

T

T

T

T

F

PF’

PF’

PF’

PF’F’

*F’

P(E)

a

b^（1）设置过程advance为读下一个单词送全程变量（2）设置过程error为错误处理程序1.主程序Beginadvance;E;End2.E过程ProcedureEBeginT;E’;end（4）构造递归下降分析程序。ETE‘E’＋E｜

TFT‘T’T｜

FPF‘F’*F‘｜

P

(E)｜a｜b｜＾3.E’过程ProcedureE’Beginifsym=‘+’thenbeginadvance;E;endelseifsymin[#,)]returnelseerrorETE‘E’＋E｜

TFT‘T’T｜

FPF‘F’*F‘｜

P

(E)｜a｜b｜＾4.T过程ProcedureTBeginF;T’;End5.T’过程ProcedureT’Beginifsymin[),+,#]returnelseTendETE‘E’＋E｜

TFT‘T’T｜

FPF‘F’*F‘｜

P

(E)｜a｜b｜＾6.F过程ProcedureFBeginP;F’endETE‘E’＋E｜

TFT‘T’T｜

FPF‘F’*F‘｜

P

(E)｜a｜b｜＾7.F’过程ProcedureFBeginifsym=‘*’thenbeginadvance;F’endelseifsymin[a,b,(,),^,+,#]thenreturnelseerror;endETE‘E’＋E｜

TFT‘T’T｜

FPF‘F’*F‘｜

P

(E)｜a｜b｜＾8.P过程ProcedurePBeginifsymin[a,b,^]thenadvanceelseifsym=‘(‘thenbeginadvance;Eifsym=‘)’thenadvance;