逐步消除这种间接左递归

Question

我见过this algorithm应该可以使用它来删除所有左递归。 然而，我正在与这个特定的语法问题：

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

无论我尝试我在循环或语法仍然是间接的左递归的结束。

在此语法上正确实施this algorithm的步骤是什么？

Answer 1

规则是你首先为非终端建立某种顺序，然后找到所有发生间接递归的路径。对于非终端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）中所述的替换C - >镉

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

3）乙尚未在j的范围内，所以留给和替换直接的

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

4左递归）在乙替换C - >铈

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

5）尚未完成！还需要更换新的规则B - > AE（制造用的是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 

生产代替直接左递归！左递归自由语法！