消除回溯的条件 例S-→aA|bA-→cAS 8 FIRST(cAS)={c}FOLLOW(A) FIRST(S)#={a,b,粉两个集合不相交，故可进行无回溯的 ↓分析.设输入串w=aca#,其推导过程如下： S#台aA# 当前输入符a属于FIRST(aA),用S→aA推导 =→acAS# 当前输入符c属于FIRST(cAS),用A→cAS推导 →acS# 当前输入符a属于FOLLOW(A),用A→推导 →acaA# 当前输入符a属于FIRST(aA),用SaA推导 →aca# 当前输入符#属于FOLLOW(A),用A-→推导，成功. 最后，我们将消除回溯的条件归纳为，对G中每个A∈V,A-产生 式中任何两个候选式Y,Y5,均满足： (1)FIRST(yi)OFIRST(Yi)= (ij1≤i,j≤m) (2)Y,Y中，至多有一个能推导出； (3)若y→*ε，则FIRST(ym⌒FOLLOW(A)=☑(i=1,2,.,mij) 。 注：条件(2)可省略.即(1)→(2) 我们把满足上述条件的文法称为LL(1)文法 消除回溯的条件 • 例 S→aA | b A→cAS |  FIRST(cAS)={c} FOLLOW(A) =FIRST(S){#}={a,b,#} 两个集合不相交, 故可进行无回溯的 分析.设输入串w=aca#,其推导过程如下: S#aA# 当前输入符a属于FIRST(aA),用S→aA推导 acAS# 当前输入符c属于FIRST(cAS),用A→cAS推导 acS# 当前输入符a属于FOLLOW(A),用A→推导. acaA# 当前输入符a属于FIRST(aA),用S→aA推导 aca# 当前输入符#属于FOLLOW(A),用A→推导,成功。 • 最后,我们将消除回溯的条件归纳为,对G中每个AVT,A-产生 式中任何两个候选式i,j,均满足: (1)FIRST(i) FIRST(j)=  (ij 1i,jm) (2) i,j中,至多有一个能推导出; (3)若j*,则FIRST(i)FOLLOW(A)= (i=1,2,…,m ij) • 注: 条件(2)可省略. 即(1) (2) • 我们把满足上述条件的文法称为LL(1)文法