left-recursion - 消除特定语法的左递归

Question

我已经浏览了一百万个示例/教程，但我仍然无法消除此语法的左递归：

S --> C
C --> Dc|c
D --> Cd|d

有任何想法吗？

Answer 1

首先通过消除 D 间接递归到立即数。你只有两个非终结符，所以可以这样做。

S --> C
C --> Cdc|dc|c

然后你可以让它尾递归：

S --> C
C --> dcC'|cC'
C'--> dcC'

第二部分的技巧是从 C 派生的所有终端（这里是 dc 和 c）中取出所有终端并给它们一个尾巴（C --> dcC'|cC'）。此 dc 和 c 与第一个规则集中 Cdc 之后出现的终端集相同。然后为新的非终结符（尾部）创建一个规则，并将其放在第一个规则的终结符之后（即，这个 dc 来自 Cdc）。

为了更清楚：

S --> C
C --> Db|f
D --> Ca|c

-->

S --> C
C --> Cab|cb|f

-->

S --> C
C --> cbC'|fC'
C'--> abC'