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

Question

我见过this algorithm人们应该能够使用它来删除所有左递归。然而我遇到了这个特定语法的问题:

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

无论我尝试什么，我都会陷入循环或语法仍然是间接左递归。

正确实现this algorithm的步骤是什么？关于这个语法？

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