5.2 LL(1)文法的判别

LL(1)文法的判别,文法化简-不含有有害规则和多余规则消除左递归和提左公因子求出能的非终结符计算FIRST集计算FOLLOW集计算SELECT集,(3).求出能推出的非终结符,例G:EE+T|TTT*F|FF(E)|i,消除左递归:G:ETEE+TE|TFTT*FT|F(E)|i,解题过程见黑板!,算法描述,建立一个一维数组X，用以记录非终结符能否推出。将数组X中对应每一非终结符的标记置初值为“未定”。,扫描文法中的产生式。(a)若某一非终结符的某一产生式右部为,则将数组中对应该非终结符的标志置为“是”，并从文法中删除该非终结符的所有产生式。(b)若某一产生式右部含有终结符，则删除该产生式。(右部含有终结符，一定无法推出)若这使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应该非终结符的标记值改为否。,扫描产生式右部的每一符号。(此时产生式右部全部为非终结符)(a)若扫描到的非终结符在数组中对应的标志是是,则删去该非终结符，若这使产生式右部为空,则对产生式左部的非终结符在数组中对应的标志改“是”,并删除该非终结符为左部的所有产生式。(b)若扫描到的非终结符在数组中对应的标志是否,则删去该产生式，若这使产生式左部非终结符的有关产生式都被删去，则把在数组中该非终结符对应的标志改成“否”。,重复，直到扫描完一遍文法的产生式，数组中非终结符对应的特征再没有改变为止。,(4).计算FIRST集,对每一文法符号XV,计算FIRST(X)(a)若XVT，则FIRST(X)X(b)若XVN，且有产生式Xa,aVT,则aFIRST(X)即把a加入到FIRSR(X)中(c)若XVN，且有产生式X,则FIRST(X),(d)若XVN,且有产生式XY1Y2Yi-1YiYn,当Y1Y2Yi-1都能推出时，则FIRST(Y1)FIRST(Y2)FIRST(Yi-1)FIRST(Yi)都包含在FIRST(X)中,(e)当(d)中XY1Y2Yn所有Yj都可以推出,(j=1,2,n),则FIRST(Y1)FIRST(Y2)FIRST(Yn)都包含在FIRST(X)中反复使用上述(b)(e)步直到每个符号的FIRST集合不再增大为止。,求一个符号串的FIRST集合,若符号串V*，=X1X2Xi-1XiXn,若X1不能推导出,则FIRST()=FIRST(X1)若对任何j(1ji-1,2in)FIRST(Xj)若对任何j(1jn)FIRST(Xj),例:求FIRST集,G:ETEE+TE|TFTT*FT|F(E)|i,解题过程见黑板!,(5).计算FOLLOW集,(a)设S为文法中开始符号，把#加入FOLLOW(S)中(b)若AB是一个产生式，则把FIRST()加入FOLLOW(B)中(c)若AB是一个产生式,或AB是一个产生式,且可推出,即FIRST(),则把FOLLOW(A)也加入FOLLOW(B)中(d)反复使用(b)直到每个非终结符的FOLLOW集不再增大为止。,例:求FOLLOW集,G:ETEE+TE|TFTT*FT|F(E)|i,解题过程见黑板!,例:LL(1)文法判别,G:ETEE+TE|TFTT*FT|F(E)|i,FIRST(+TE)FIRST()=FIRST(E)FOLLOW(E)=FIRST(*FT)FIRST()=FIRST(T)FOLLOW(T)=FIRST(E)FIRST(i)=,该文法是LL(1)文法!,(6).计算SELECT集,给定上下文无关文法的产生式A,AVN,V*,若，SELECT(A)=FIRST()若，SELECT(A)=(FIRST()FOLLOW(A),G:ETEE+TE|TFTT*FT|F(E)|i,例:判断文法是否是LL1文法,G:SABSbCAbABBaDCbCADDaSDc,文法化简消除左递归和提左公因子求出能推出的非终结符计算FIRST集计算FOLLOW集计算SELECT集,求出能推出的非终结符,G:SABSbCAbABBaDCbCADDaSDc,计算FIRST集,G:SABSbCAbABBaDCbCADDaSDc,1)求每个非终结符的FIRST集,2)求每个产生式右部的FIRST集,FIRST(AB)=a,b,FIRST(bC)=b,FIRST(AB)FIRST(bC)=b,所以,该文法不是LL(1)文法!,计算FOLLOW集,G:SABSbCA