對下面的文法G

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

TFT‘T’T｜

FPF‘F’*F‘｜

P(E)｜a｜b｜＾（1）計(jì)算這個文法的每個非終結(jié)符的FIRST集和FOLLOW集。（2）證明這個文法是LL（1）的。（3）構(gòu)造它的預(yù)測分析表。（4）構(gòu)造它的遞歸下降分析程序。解：（1）計(jì)算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）的。對產(chǎn)生式P(E)｜a｜b｜^，有FIRST((E))FISRT(a)FIRST(b)FIRST(^)=對產(chǎn)生式E’＋E｜

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

對產(chǎn)生式T’T｜

FIRST(T)FOLLOW(T’)=

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

對產(chǎn)生式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）構(gòu)造預(yù)測分析表。（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）設(shè)置過程advance為讀下一個單詞送全程變量（2）設(shè)置過程error為錯誤處理程序1.主程序Beginadvance;E;End2.E過程ProcedureEBeginT;E’;end（4）構(gòu)造遞歸下降分析程序。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;