逐步消除此间接左递归

Question

我已经看到这个算法应该可以用来删除所有左递归.然而,我遇到了这个特殊语法的问题:

A -> Cd
B -> Ce
C -> A | B | f

无论我尝试什么,我最终都在循环中或使用仍然间接留下递归的语法.

在这个语法上正确实现这个算法的步骤是什么？

Answer 1

规则是您首先为非终端建立某种顺序,然后找到间接递归发生的所有路径.

在这种情况下,顺序是A <B <C,并且非终端C的递归的可能路径将是

C=> A => Cd

和

C=> B => Ce

因此C的新规则将是

C=> Cd | Ce | f

现在你可以简单地删除直接左递归:

C=> fC'
C'=> dC' | eC' | eps

并且得到的非递归语法将是:

A => Cd
B => Ce
C => fC'
C' => dC' | eC' | eps

Answer 2

已经弄清楚了.

我的困惑在于,按照这个顺序,算法似乎什么都不做,所以我认为这一定是错的,并且在第一次迭代中开始替换A - > Cd(忽略j不能超越i)进入无限循环.

1)通过重新排序规则:

C -> A | B | f 
A -> Cd
B -> Ce

2)替换A - > Cd中的C.

C -> A | B | f 
A -> Ad | Bd | fd
B -> Ce

3)B还没有在j的范围内,所以留下它并替换A的直接左递归

C -> A | B | f 
A -> BdA' | fdA'
A'-> dA' | epsylon
B -> Ce

4)替换B中的C - > Ce

C -> A | B | f 
A -> BdA' | fdA'
A'-> dA' | epsylon
B -> Ae | Be | fe

5)还没完成!还需要更换新规则B - > Ae(A的生产范围为j)

C -> A | B | f 
A -> BdA' | fdA'
A'-> dA' | epsylon
B -> BdA'e | fdA'e | Be | fe

6)在B的产生中替换直接左递归

C -> A | B | f 
A -> BdA' | fdA'
A'-> dA' | epsylon
B -> fdA'eB' | feB'
B'-> dA'eB' | eB' | epsylon

哇噢!左递归免费语法!