可有人告诉我如何消除使用规则这个文法左递归？

Question

我试图从语法删除左recusion，我能做到这一点SOMETIEMES。我显然不知道这些规则，因为我只知道如何通过试错来做到这一点。我看到的规则是这样的：The rules that I found on Wikipedia

S --> SX | SSb | XS | a
X --> Xb | Sa | b

所以，我知道在这个特殊的例子，我可以首先从S规则中删除立即左递归，然后之后，我得到这样的：

S --> XSS' | aS'
S' --> XS' | SbS' | epsilon
X --> Xb | Sa | b 

然后，从这里我可以合并的生产进入X生产得到：

 X --> Xb | XSS' | aS'a | b

然后我可以从那里取出立即左递归让我最后的答案。但是有人可以解释的规则我，因为我没有按照他们在我最后得出答案。我有种很幸运。我需要知道如何从任何给定的语法删除左递归。任何帮助将不胜感激。谢谢。

Answer 1

1. 找到所有非终端的制造与左递归的尸体并将其删除。
2. 将它们添加到一个新的非终端A”
3. 对于每一个非末端A”产物： 删除第一个递归调用一个 在最后添加一个”呼叫
4. 您小量生产添加到非终端A”
5. 用于所有剩余的非末端生产A，添加A”到端

例如：A - > AB | BB |一种

1. A - >了Bb |至
2. A“ - >抗体
3. A ' - >'
4. A ' - > BA' | Ë
5. A - >好消息| AA'

结果：A - > BBA“| AA 'A' - > BA“| Ë