如何消除左递归

首先，什么叫做左递归呢？ 一个左递归的语法通常有这样的形式 : A->Aa .而自顶向下的语法分析是无法处理左递归语法的。为什么呢？无论是递归分析还是预测分析或者是LL文法分析，在碰到左递归这种语法时都会陷入死循环当中。如果我们用递归分析，那么在分析A这个非终结符号的时候就会调用functionA，functionA将A分解成A，a，然后在我们再次碰到A的时候又会调用functionA，这样便形成了无限递归。如果我们用非递归的LL文法分析，那么在我们将把A->Aa无限次地压入到栈中，即每次d出A都会压入Aa。所以我们必须采取手段消除左递归，下面给出标准方法。

其中β1…βn 不是从A开始

其实原理在于通过转换将A的语法不从非终结符号（A本身）开始，而是从终结符号β1…βn 开始。虽然A的原语法是从A本身开始的，但是第一个符号一锋裤定是β1…βn中的一个，而不可能是任何一个α。所以我们通过一个中间变量A’来表示剩下的α，然而不要忘记由于A’ ->αA’ 这条规则，A’ ->ε 必须也存在于语法规则中，否则末尾将无法匹配完成。

但是，上述方法只适用于立即左递归，还有一种更隐蔽的非立即左递归，如 S ->Aa | b , A ->Sc | d ,我们如果用自顶向下的分析方法会陷入 S ->Aa ->Sca 这样的死循环中。当然，也有相应的解决办法。

将所有非终端符号以某个固定的顺序A_1, \ldots A_n排列

从 i = 1 到 n {

从 j = 1 到 i – 1 {

设A_j的生成规则为

A_j \rightarrow \delta_1 | \ldots | \delta_k

将所有掘袜规则 A_i \rightarrow A_j \gamma换成

A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma

移除A_i规则中的直接左递归

}

}

也许看上面的规则过于抽象，我们用S ->Aa | b , A ->Sc | d 来实践一下上述的方法。我们以S，A的顺序排列。则只需执行一次主程序体，且Ai 为A，Aj为S。则：

A ->Aac | bc | d, 然后再运用前面的规则消除直接左递归可得：A ->bcA’ | dA’ , A’ ->acA’ | ε

请注意，以上的解决方案是基银散简于右递归的文法，并不是完全适用于所有的情况。我们得到的文法可能含有 ε表达式，并且可能会改变语法的结合律。解决方案就是保留左递归的语法，不用自顶向下的方式分析。

为了消除那些经多步推导陆激袜所出现的左递归性，可首先查出那些具有左递归性的非终结符号，然后对以这些非终结符号为左部的产生式，通过逐步代入有关产生式的方式将它们化为直接左递归的产生式，最后再消除其中的全部直接左递归即可。显然，这是一个十分繁琐的过程。下面，我们再介绍一种一次消去文法的一切左递归性的方法，为此，先引入文法的一种矩阵表示。

设G是一前后文无关文法，它的VN中含有n个非终结符号：X1,X2,…,Xn，对于G的每一产生式

Xi→γ1|γ2|…|γm，

我们可将它的各候选式γ1,γ2,…,γm分为两类： 把以非终结符号打头的γi归为一类；而将以终结符号打头的归为另一类。例如，若某个γk以Xj打头，就把γk写成Xjαji (αji∈V+)。此时，若将元语言符号→及|形式地用“=”及“+”表示，即可将此产生式写成

Xi=X1α1i+X2α2i+…+Xnαni+β i

其中，β i是那些以终结符号打头的诸候选式之“和”。此外，若此产生式不含以某一非终结符号Xj打头的候选式，则相应的αji为。这样，我们就可将G的诸产生式写成如下的矩阵方程

(X1 X2 … Xn)=(X1 X2 … Xn)·α11[]α12[]…[]α1n

α21[]α22[]…[]α2n

…[]…[]…[]…

αn1[]αn2[]…[]αnn+(β1 β2 … βn)(411)

或

X=XA+B(412)

式(411)或式(412)即为文法G的一种矩阵表示。不过，需要注意的是，对上面各式中所出现的运算符应作如下的理解： 乘法运算表示字符串的连接，加法运算表示选择。仿342中的讨论可知，矩阵方程(412)有形如

X=BA*(413)

的解。显然，要计算矩阵A的闭包A*一般是很困难的，但可设法予以回避。事实上，由于

A*=I+A+A2+…=I+AA*

其中

I=ε[][][]…[]

[]ε[][]…[]

…[]…[]…[]…[]…

[][][]…[]ε

若设

A*=Z=z11[]z12[]…[]z1n

z21[]z22[]…[]z2n

…[]…[]…[]…

zn1[]zn2[]…[]znn

则可得如下两个矩阵式早激

X=BZ(414)

Z=I+AZ(415)

由于列矩阵B的各元素的每一项均以终结符号开始，故矩阵式(414)相应的诸产生式的右部符号串也以终结符号开始，也就是说它们都不是左递归的。至于由式(415)新引入的产生式，由于它们的左部为zij，显然也不会有任何的左递归性。此外，从式(412)推演到式(414)和式(415)的过程中，实际上只进行了一些等价铅辩的代换演算，故由式(414)和式(415)所表示的文法将与原文法G等价。但若新文法中含有无用的产生式 (它们可能由式(415)引入)，则应予以剔除。

例41考虑文法

S→Sa|Ab|a(416)

A→Sc

显然，其中S，A都是左递归的非终结符号。首先写出此文法的矩阵表示

(S A)=(S A)a[]c

b[]+(a )

令

a[]c

b[]*=Z=z11[]z12

z21[]z22

则有

(S A)=(a ) z11[]z12

z21[]z22

z11[]z12

z21[]z22=ε[]

[]ε+a[]c

b[]z11[]z12

z21[]z22

于是，我们就得到了与文法(416)等价的文法

S→az11A→az12

z11→az11|cz21|ε

z12→az12|cz22

z21→bz11z22→bz12|ε

删除其中的无用产生式，我们有

S→az11

z11→az11|cz21|ε

z21→bz11

---