从CFG中删除左递归

Question

以下语法留下了递归：

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

您如何去除左递归。我阅读了Wikipedia的解释，但是我对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'