这个语法如何摆脱左关联递归中的无限递归？

Question

“假设我们有这样的语法，其中 alpha 可以是任意终结符和非终结符序列：

A -> A 阿尔法 | B

我们可以将这个语法重写为：

A -> B A'

A' -> 阿尔法 A' | ε”

我很困惑为什么需要 epsilon（如果它只是一个空字符串/标记）以及该语法如何使用左递归在自上而下的解析器中删除无限递归。

我尝试在网上查找一些示例，但找不到任何示例。我还查看了关于左递归的维基，它确实解释了它，但我只是不明白解释。

Answer 1

A

（无限）上的左递归被替换为

A'

上的右递归。

但是，为了解析鞋底

B

，以下

A'

必须解析为

epsilon

（空）。

A'

的递归不是无限的，因为总是必须在递归步骤中解析

alpha

。