左递归消除

Question

我试图通过消除间接递归然后直接递归来消除CFG的左递归，如algorithm所示。

我将使用这个语法：

A = A a | A B C | B C | D D 

当I = 1和J = 1我们正在寻找替代形式A的所有作品 - > A R与：

A→δ γ | δ γ | .. | δ _ķ γ

所以，当我看着A - >一个一个相匹配，我应该

A -> A a a | A B C a a | B C a | D D a 

更换其即时通讯肯定是不对的

任何人都可以点我当你用生产本身来取代产品时，如何取代产品的正确方向？

注：另外，我只是停留在第一个规则，以便省略了他人的简单

任何帮助，将不胜感激

[更新]发现接近原来的希腊符号我可以。另外，我是否可能在错误的方向上接近这一点。当i = 1和j = 1，A _j→A a | A B C | B C | D D，但我应该使用A _j - > B C | d d 如果是这样的话，我会得到：

A -> B C A | B C B C | D D A | D D B C | B C | D D 

至于那些然后消除在生产递归。这是一个更好的方向？

Answer 1

这是配方：

A → Aα1 | ... | Aαm | β1 | ... | βn 

应转化为：

A → β1 A' | ... | βn A' 
A' → α1 A' | ... | αm A' | ε 

即：

1. 新的作品中，递归是在更换递归作品对。为此使用新的非终端符号。
2. 将一个空白右侧的产品添加到新的非终端。
3. 在非递归作品的右侧附加新的非终端符号。

对于你的语法：

A = A a | A B C | B C | D D 

你将获得：

A = B C A' | D D A' 
A' = a A' | B C A' | ε