消除左递归（似乎无法理解）

Question

我有以下语法：

S --> SaA
S --> bB
A --> aB
A --> c
B --> Bb
B --> d

现在，看看解决左递归的一般规则，我可以说：

B --> dB'
B' --> e | bB'

但这就是我所能得到的。我尝试扩展 S:

S --> SaA | bB
S --> SaaB | Sac | bB

但我无法以正确的算法形式得到它。

我错过了什么？

Answer 1

我想知道你为什么要 "expand" S。它已经存在的形式，

S  -> SaA | bB

非常适合应用与 B 相同的转换。它会变成

S  -> bBS'
S' -> ε | aA

现在，您可以根据需要扩展 BS'。