如何判断一个文法是LL(1)文法.ppt

LL的含义自左向右扫描分析输入符号串从识别符号开始生成句子的最左推导LL(1):向前看一个输入符号，便能唯一确定当前应选择的规则LL(k):向前看k个输入符号，才能唯一确定当前应选择的规则,4.2.3LL(1)文法的判别,要构造确定的自顶向下分析程序要求描述文法必须是LL(1)文法,同一非终结符有多个候选式时,引起回溯的原因,【例4.1】=acbGS:SaAbAcd|c,（1）候选式的终结首符号相同,（2）候选式的终结首符号相同,【例4.8】SAaAa|,1.FIRST集,FIRST()：从可能推导出的所有开头终结符号或,对于文法G的所有非终结符的每个候选式，其终结首符号集称为FIRST集，定义如下：,【例】SaAbAcd|c,【例】SAaAa|,（1）若=a，且aVT，则aFIRST()；例：FIRST(i)=iFIRST(+TE)=+,ETEE+TE|TFTT*FT|F(E)|i,构造FIRST集的算法,（2）若=X，XVN，且有产生式Xb，则把b加入到FIRST()中；例：FIRST(FT)=(,i?,将FIRST(X1)中的一切非的终结符加进FIRST()；若FIRST(X1),则将FIRST(X2)中的一切非的终结符加进FIRST()；若FIRST(X1)且FIRST(X2),则将FIRST(X3)中的一切非的终结符加进FIRST()；依此类推，若对于一切1in,FIRST(Xi)，则将加进FIRST()。,（3）若=X1X2Xn，其中XiVN,1in；,ETEE+TE|TFTT*FT|F(E)|i,例：FIRST(FT)=,FIRST(F)-=(,i,FIRST(F)=(,iFIRST(T)=*,FIRST(T)=FIRST(F)-=(,iFIRST(E)=+,FIRST(E)=FIRST(T)-=(,iFIRST(TE)=FIRST(T)-=(,iFIRST(+TE)=+FIRST()=FIRST(FT)=FIRST(F)-=(,iFIRST(*FT)=*FIRST(（E）)=(FIRST(i)=i,【例4.9】GEETEE+TE|TFTT*FT|F(E)|i,2.FOLLOW集,FOLLOW(A)：是所有句型中紧接A之后的终结符号或#,对于文法G的非终结符的后继符号集称为FOLLOW集，定义如下：,构造集合FOLLOW的算法,（1）若为开始符号，则把“#”加入FOLLOW(A)中；,（2）若BA()，则把FIRST()-加入FOLLOW(A)中；,注：FOLLOW集合中不能有,ETEE+TE|TFTT*FT|F(E)|i,#FOLLOW(E),由F(E)可知，)FOLLOW(E),由ETE，应把FOLLOW(E)加入FOLLOW(E)由E+TE且E，应把FOLLOW(E)加入FOLLOW(T),【例4.10】GEETEE+TE|TFTT*FT|F(E)|i,求FOLLOWFOLLOW(E)=#,)E是开始符号#FOLLOW(E)又F(E)FOLLOW(E)FOLLOW(E)=#,)ETEFOLLOW(E)加入FOLLOW(E)FOLLOW(T)=+,),#E+TEFIRST(E)-加入FOLLOW(T)又E，FOLLOW(E)加入FOLLOW(T)FOLLOW(T)=FOLLOW(T)=+,),#TFTFOLLOW(T)加入FOLLOW(T)FOLLOW(F)=*,+,),#TFTFOLLOW(F)=FIRST（T）-又TFOLLOW(T)加入FOLLOW(F),FIRST(F)=(,iFIRST(T)=*,FIRST(T)=(,iFIRST(E)=+,FIRST(E)=(,i,若一个文法满足以下条件，则称该文法G为LL(1)文法：,（1）文法不含左递归；,（2）对于每个非终结符A的各个候选式的终结首符号集两两不相交。即，如果A1|2|n，则FIRST(i)FIRST(j)=，其中1i，jn，且ij。,（3）对于文法中每个非终结符A，若它某个候选式的终结首符号集包含，则FIRST(A)FOLLOW(A),3LL(1)文法的判别条件,【例4.11】GE：ETEE+TE|