是A拥有的所有规则.没有等于ε的αi,否则我们会有A→A规则和一个单元规则.也没有等于ε的βj,否则会有一个ε-规则.由A生成的句型只用*A→Aαk*规则,这些句型都有这样的形式:
并且当A→βi规则使用时,句型不再以A开头,对一些i,和一些k1...kj它有如下的形式:
这里j可能为0.同样的句型也可以用如下规则生成:
或者,不重新引入ε规则生成的话就是这样:
这里AheadAtail和Atails是新引入的非终结符.所有αi都不是ε类型,所以Atail不会推导出ε,所以Atails不是左递归.不过A可能仍然是左递归的,但不是直接左递归,因为没有βj是以A开始,然而它们却可能推导出以A开始的句型.
任何时刻句型的最左边都是非终结符,然后每次使用其中一个右侧替代.每一个非终结符都有一个标号,计作i1i2...im,于是在推导中我们得到了这么一串数:i1i2...imi1.现在,如果我们没有任何包含jα(j≤i)的规则Ai→A那这就是不存咋的,因为*i1<i2<...<im<i1*是不存在的.
现在就要消除这种形式的规则.我们从A1开始.对A1,要消除了只是直接递归的规则,我们已经看到了应该怎么做.接着轮到A2.每一个有着A2→A1α形式的产生式都要被替代成如下:
这不可能产生A2→A1γ形式的新规则,因为我们已经消除了A1的左递归规则,而且αi都不为ε.接着,我们来处理A2的直接左递归规则.这样对A2的工作就结束了.同样,我们对A3到An进行处理,按照总是先替代Ai→A1γ再Ai→A2δ等的顺序.我们必须按照这样的顺序,因为替换一个Ai→A2δ的规则可能会引入一个Ai→A3γ规则,而不是Ai→A1α规则.