如何从缺少beta的语法中删除左递归?

Question

问题来了:

→A*B | A+CDE | Aab

所有的作品都以a开头，我想这符合规则了吧?正如你所看到的，它缺少beta。如何对它执行左递归?左递归可以在上面执行吗?

到目前为止，我所学到的是，如果是这样:A ->A*B | A+CDE | Aab | B

那么我就把b看作是，解为:

→bA '

"→*BA' | +CDEA' | abA' |御柱

没有beta，我很困惑。我认为是什么?

Answer 1

我认为首先需要在A产品中添加新的规则来停止递归。比如b在您的示例中

A -> A*B | A+CDE | Aab | b

如果这是不可能的，我想生产将是这样的:

A -> A*B | A+CDE | Aab | e

那么，第一步将是左分解:

A -> AT | e
T -> *B | +CDE | ab

然后删除左递归:

A -> A'
A' -> TA' | e
T -> *B | +CDE | ab

Answer 2

在尝试删除右递归之前，您需要通过删除所有无用和非生产性的非终结符来减少语法。由于A是非生产性的(它没有非递归生产)，它将与使用它的任何生产一起被消除。这当然消除了左递归:-)。