parsing - 逐步消除这种间接左递归

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 中的 C -> Cd

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

呜呼！左递归自由语法！