消除回溯的条件 。 由前面的讨论可知，要实现无回溯的↓分析，文法必须满足一 定的条件。为导出这些条件，我们定义候选式的终结首符集 FIRST(y)={a|Y→*aδ，a∈Vr,δeV*的并约定Y→*e 时，8∈FIRST(Y) 若对于A-产生式的每个候选式y(i=1,2,..,m)都推不出e,且 FIRST(y)互不相交，则当正扫描的当前输入符号为 aiEFIRST(M)时，唯一可用于推导的产生式只能是A→M. 例如，文法G1[S]:S→AAA→aAb|*,A-产生式有两个候选 式，且 FIRST(aAb)=fa) FIRST(*)=的，两集不 相交，设输入串为aa*bb*,其最左推导为S→AA(a)→aAbA (a)→aaAbbA(*)→aa*bbA()→aa*bb*(#) 注：上面第每步推导右侧括号内为当前扫描的输入符号，#为结 束符。 我们得到了一个无回溯的条件：FIRST(Yi)OFIRST(Y)=☑ 消除回溯的条件 • 由前面的讨论可知，要实现无回溯的分析,文法必须满足一 定的条件。为导出这些条件,我们定义候选式的终结首符集 FIRST()={a | * a, aVT,V*} 并约定 * 时,FIRST() • 若对于A-产生式的每个候选式i(i=1,2,…,m)都推不出 , 且 FIRST(i ) 互不相交,则当正扫描的当前输入符号为 aiFIRST(j)时,唯一可用于推导的产生式只能是A→j. • 例如,文法G1[S]: S→AA A→aAb | *, A-产生式有两个候选 式, 且 FIRST(aAb)={a} FIRST(*)={*},两集不 相交,设输入串为aa*bb*,其最左推导为 SAA (a) aAbA (a) aaAbbA (*) aa*bbA (*)aa*bb* (#) 注:上面第每步推导右侧括号内为当前扫描的输入符号,#为结 束符. • 我们得到了一个无回溯的条件: FIRST(i) FIRST(j)=