将模糊CFG转换为无歧义CFG。

Question

我有语法：

S -> aSb | bSa | SS | epsilon

我想要生成一个明确的版本。

我尝试了分层，但只做到了这一点，这并不是明确的，我不相信，因为规则A -> aC和A -> AA都可以用于一些输入：

S -> A | epsilon

A -> aC | bD | AA

C -> Cb | b

D -> Da | a

Answer 1

S  -> aSb | bSa | SS | ϵ

如果我在这里没有完全错，这里唯一的问题是S的左递归，所以如果删除它，您应该很好：

S  -> S' S'
S' -> aSb | bSa | ϵ

这也应消除歧义。

另一种解决办法可以是：

S  -> aSbS | bSaS | ϵ