编译原理(四) 提取左因子法消除回溯

## 概念简述 回溯：分析工作部分地或全部地退回到之前的一个阶段，在当前阶段采取与之前不同的决策重新推进工作 FIRST(α)：令Ｇ是一个不含左递归的文法，对G的所有非终结符的每个候选α定义它的终结首符集FIRST(α)为： - FIRST(α)={a | α=>*a…, a∈VT} - 若α=>*ε，则规定ε∈FIRST(α) - FIRST(α)是α的所有可能推导的开头终结符或可能的ε ## 消除回溯 - 回溯的问题 回溯带来的问题就是低效率 - 回溯的条件 文法中，对于某个非终结符的规则其右部有多个选择，并根据所面临的输入字符不能准确的判断所要的选择，那么就需要搜索，就会导致回溯。 - 避免回溯的要求 FIRST(αi)∩FIRST(αj)=ϕ 令Ｇ是一个***不含左递归***的文法，对G的所有非终结符的每个候选α定义它的终结首符集FIRST(α)为： - FIRST(α)={a | α=>*a…, a∈VT} 若α=>*ε，则规定ε∈FIRST(α) FIRST(α)是α的所有可能推导的开头终结符或可能的ε - 如果非终结符Ａ的所有候选首符集两两不相交，即Ａ的任何两个不同候选αi和αｊ FIRST(αi) ∩FIRST(αj)=Φ - 那么当要求Ａ匹配输入串时，Ａ就能根据它所面临的第一个输入符号ａ，准确的指派某一个候选前去执行任务。这个候选就是那个终结首符集含ａ的α。 - 提取左因子法消除回溯 - 假定Ａ的规则是： Ａ→δβ1 |δβ2 | … |δβn |γ1 |γ2 | … |γm（其中，每个γ不以δ开头） 那么这些规则可以改写为： A→δA’ |γ1 |γ2 | … |γm A’→β1 |β2 | … |βn - 经过反复提取左因子，就能够把每个非终结符（包括新引进者）的所有候选首符集便成为两两不相交。我们为此要***付出的代价是大量引进新的非终结符和ε产生式***。 - 实现过于简单，故不再实现代码