為了消除那些經多步推導所出現的左遞迴性，可首先查出那些具有左遞迴性的非終結符號，然後對以這些非終結符號為左部的產生式，透過逐步代入有關產生式的方式將它們化為直接左遞迴的產生式，最後再消除其中的全部直接左遞迴即可。顯然，這是一個十分繁瑣的過程。下面，我們再介紹一種一次消去文法的一切左遞迴性的方法，為此，先引入文法的一種矩陣表示。

設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)(411)

或

X=XA+B(412)

X=BA*(413)

的解。顯然，要計算矩陣A的閉包A*一般是很困難的，但可設法予以迴避。事實上，由於

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

其中

I=ε[]~[]~[]…[]~

~[]ε[]~[]…[]~

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

~[]~[]~[]…[]ε

若設

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

z21[]z22[]…[]z2n

…[]…[]…[]…

zn1[]zn2[]…[]znn

則可得如下兩個矩陣式

X=BZ(414)

Z=I+AZ(415)

由於列矩陣B的各元素的每一項均以終結符號開始，故矩陣式(414)相應的諸產生式的右部符號串也以終結符號開始，也就是說它們都不是左遞迴的。至於由式(415)新引入的產生式，由於它們的左部為zij，顯然也不會有任何的左遞迴性。此外，從式(412)推演到式(414)和式(415)的過程中，實際上只進行了一些等價的代換演算，故由式(414)和式(415)所表示的文法將與原文法G等價。但若新文法中含有無用的產生式 (它們可能由式(415)引入)，則應予以剔除。

例41考慮文法

S→Sa|Ab|a(416)

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

於是，我們就得到了與文法(416)等價的文法

S→az11A→az12

z11→az11|cz21|ε

z12→az12|cz22

z21→bz11z22→bz12|ε

S→az11

z11→az11|cz21|ε

z21→bz11