recursion - 从 CFG 中删除左递归

Question

以下文法有左递归：

T -> Tx | TYx | YX | x
X -> xx
Y -> Yy | Yx | y

你如何去删除左递归。我阅读了维基百科的解释，但我对 CFG 相当陌生，所以它没有多大意义。任何帮助表示赞赏？一个简单的英文解释将更加感激。

Answer 1

在此示例中，您可以按照 Robert C. Moore 的通用算法将左递归规则转换为右递归规则：

A -> A a1 | A a2 | ... | b1 | b2 | ...
# converts to
A  -> b1 A' | b2 A' | ...
A' -> e | a1 A' | a2 A' | ...                 # where e = epsilon

在我们的第一种情况下： A=T, a1=x, a2=Yx, b1=y, b2=x ...（类似的Y）

T  -> YXT' | xT'
T' -> e | xT' | YxT'
X  -> xx
Y  -> yY'
Y' -> e | yY' | xY'