README.md

6.4 消除左递归

我们先讨论消除直接左递归的方法。假定ε-规则和单元规则（unit rule）已经被消除了（见4.2.3.1和4.2.3.2）。现在，令A是一个左递归的非终结符（原文为rule），并且

是A的所有规则。没有等于ε的α_i，否则我们会有A→A，一个单元规则。也没有等于ε的β_j，否则会有一个ε-规则。A只用A→Aα_k规则生成的句型有这样的形式：

并且当A→β_i规则使用时，句型不再以A开头，对一些i，和一些k₁,...,k_j,它有如下的形式：

这里j可能为0.同样的句型可以被如下规则生成：

或者，使得没有新的ε规则重新生成的话：

这里A_head,A_tail和A_tails是新引入的非终结符。没有α_i是ε，所以A_tail不会推导出ε，所以A_tails不是左递归。A可能仍然是左递归的，但不是直接左递归，因为没有β_j以A开始。然而，它们可能推导出以A开始的句型。 一般的，消除间接左递归要更复杂。思路就是先将非终结符标号，标为A₁,A₂,...,A_n.现在，对一个左递归非终结符A，有一个推导

，每时每刻句型的最左边都是非终结符，然后再三地用它的一个右侧替代。每一个非终结符都有一个标号，写作i₁,i₂,...,i_m,于是在推导中我们得到了这么一串数：i₁,i₂,...,i_m,i₁.现在，如果我们没有任何A_i→A_jα(j≤i),这就是不可能的，因为i₁<i₂<...<i_m<i₁是不可能的。 现在就要消除这样的规则。我们从A₁开始。对A₁，要消除了只是直接递归的规则，我们已经看到了应该怎么做。接着轮到A₂。每一个有着A₂→A₁α形式的产生式都要被替代成

这里A₁的规则为

这不可能产生A₂→A₁γ形式的新规则，因为我们已经消除了A₁的左递归规则，而且α_i都不为ε。接着，我们消除A₂的直接递归规则。这样对A₂的工作就结束了。类似的，我们对A₃到A_n进行处理，按照总是先替代A_i→A₁γ,再A_i→A₂δ等等的顺序。我们必须按照这样的顺序，因为，替换一个A_i→A₂δ的规则可能会引入A_i→A₃γ这样的规则，而不会是A_i→A₁α