compiler-construction - 左递归消除

Question

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

我将使用这个语法：

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

当i = 1和j = 1时，我们正在考虑将所有形式A -> A r的产生式替换为：

A -> δ ₁ γ | δ ₂ γ | .. | δ _k γ

因此，当我查看匹配的A -> 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 | 美国广播公司 | 卑诗省 | DD，但我应该使用 A _j -> BC | DD 如果是这样，那么我会得到：

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' | ε