如何消除具有 epsilon 产生式的左递归？

Question

我看过这个link。但是我有点困惑如何在这里消除∈产生式。

我有以下语法

 S-->Sz|Sxw|xw|yw|∈

我可以看到删除 epsilon 产生式后语法变成了

 S-->Sz|Sxw|xw|yw|z

现在，如果我解决了这个问题，我会得到如下结果

  S-->xwS`|zS`|ywS`
  S`-->zS`|xwS`|∈

现在我可以看到 S-->xwS`|zS` 和 S`-->zS` |xwS`。这变成了 same.Is 是对的还是我做错了什么？？

Answer 1

重复规则没有错。

在尝试理解语法时，我经常发现有用的一种方法是将其转换为正则表达式

 S := (xw + yw + z)(z + xw)*

因为它让我很好地了解了整个语法并有助于发现错误。所以如果我把它分成这样：

 S  := (xw + yw + z)S'
 S' := (z + xw)*

它让我更容易看到我是否犯了任何错误。