compiler-construction - 左递归消除

Question

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

我将使用这个语法:

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 | ABC | BC | D D，但是我应该使用 A_j -> B C | 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' | ε