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

11编译原理2020年3月28日LL的含义－自左向右扫描分析输入符号串－从识别符号开始生成句子的最左推导LL(1):向前看一个输入符号，便能唯一确定当前应选择的规则LL(k):向前看k个输入符号，才能唯一确定当前应选择的规则4.2.3LL(1)文法的判别要构造确定的自顶向下分析程序要求描述文法必须是LL(1)文法22编译原理2020年3月28日同一非终结符有多个候选式时引起回溯的原因【例4.1】α=acbG[S]:S→aAbA→cd|c（1）候选式的终结首符号相同（2）候选式的终结首符号相同【例4.8】S→AaA→a|33编译原理2020年3月28日1.FIRST集FIRST(α)：从α可能推导出的所有开头终结符号或ε对于文法G的所有非终结符的每个候选式，其终结首符号集称为FIRST集，定义如下：，则规定∈FIRST()若【例】S→aAbA→cd|ca…，a∈VTFIRST()={a|FIRST(aAb)={a}FIRST(cd)={c}FIRST(c)={c}【例】S→AaA→a|FIRST(a)={a}FIRST()={}FIRST(Aa)={a}FIRST(S)={a}FIRST(A)={c}FIRST(S)={a}FIRST(A)={a,}44编译原理2020年3月28日（1）若α=aα′，且a∈VT，则a∈FIRST(α)；例：FIRST(i)={i}FIRST(+TE')={+}E→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|i构造FIRST集的算法（2）若α=Xα′，X∈VN，且有产生式X→b…，则把b加入到FIRST(α)中；例：FIRST(FT')={(,i}??55编译原理2020年3月28日①将FIRST(X1)中的一切非ε的终结符加进FIRST(α)；②若ε∈FIRST(X1),则将FIRST(X2)中的一切非ε的终结符加进FIRST(α)；③若ε∈FIRST(X1)且ε∈FIRST(X2),则将FIRST(X3)中的一切非ε的终结符加进FIRST(α)；④依此类推，若对于一切1≤i≤n,ε∈FIRST(Xi)，则将ε加进FIRST(α)。（3）若α=X1X2…Xnα′，其中Xi∈VN,1≤i≤n；E→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|i例：FIRST(FT')=注意：要顺序往下做，一旦不满足条件，过程就要中断进行FIRST(F)-{ε}={(,i}66编译原理2020年3月28日FIRST(F)={(,i}FIRST(T’)={*,ε}FIRST(T)=FIRST(F)-{ε}={(,i}FIRST(E’)={+,ε}FIRST(E)=FIRST(T)-{ε}={(,i}FIRST(TE’)=FIRST(T)-{ε}={(,i}FIRST(+TE’)={+}FIRST(ε)={ε}FIRST(FT’)=FIRST(F)-{ε}={(,i}FIRST(*FT’)={*}FIRST(（E）)={(}FIRST(i)={i}【例4.9】G[E]E→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|i77编译原理2020年3月28日2.FOLLOW集FOLLOW(A)：是所有句型中紧接A之后的终结符号或#对于文法G的非终结符的后继符号集称为FOLLOW集，定义如下：…A，则规定#∈FOLLOW(A)若S…Aa…，a∈VT}FOLLOW(A)={a|SE→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|iT+TE'，则+∈FOLLOW(T)E88编译原理2020年3月28日构造集合FOLLOW的算法（1）若为开始符号，则把“#”加入FOLLOW(A)中；（2）若B→A(≠)，则把FIRST()-{}加入FOLLOW(A)中；注：FOLLOW集合中不能有ε（3）若B→A或B→A，且则把FOLLOW(B)加入FOLLOW(A)中。，E→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|i#∈FOLLOW(E)由F→(E)可知，)∈FOLLOW(E)由E→TE'，应把FOLLOW(E)加入∈FOLLOW(E')由E'→+TE'且E'ε，应把FOLLOW(E')加入FOLLOW(T)99编译原理2020年3月28日【例4.10】G[E]E→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|i求FOLLOWFOLLOW(E)={#,)}∵E是开始符号∴#∈FOLLOW(E)又F→(E)∴)∈FOLLOW(E)FOLLOW(E’)={#,)}∵E→TE’∴FOLLOW(E)加入FOLLOW(E’)FOLLOW(T)={+,),#}∵E’→+TE’∴FIRST(E’)-{ε}加入FOLLOW(T)又E’ε，∴FOLLOW(E’)加入FOLLOW(T)FOLLOW(T’)=FOLLOW(T)={+,),#}∵T→FT’∴FOLLOW(T)加入FOLLOW(T’)FOLLOW(F)={*,+,),#}∵T→FT’∴FOLLOW(F)=FIRST（T’）-{ε}又T’ε∴FOLLOW(T)加入FOLLOW(F)FIRST(F)={(,i}FIRST(T’)={*,ε}FIRST(T)={(,i}FIRST(E’)={+,ε}FIRST(E)={(,i}1010编译原理2020年3月28日若一个文法满足以下条件，则称该文法G为LL(1)文法：（1）文法不含左递归；（2）对于每个非终结符A的各个候选式的终结首符号集两两不相交。即，如果A→α1|α2|…|αn，则FIRST(αi)∩FIRST(αj)=Φ，其中1≤i，j≤n，且i≠j。（3）对于文法中每个非终结符A，若它某个候选式的终结首符号集包含ε，则FIRST(A)∩FOLLOW(A)＝Φ3．LL(1)文法的判别条件1111编译原理2020年3月28日【例4.11】G[E]：E→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|i判别该文法是否为LL(1)文法。FIRST(F)={(,i}FIRST(T’)={*,ε}FIRST(T)={(,i}FIRST(E’)={+,ε}FIRST(E)={(,i}