1

我的语法在第六个生产规则中有左递归的情况。

左递归

我通过像这样替换规则 6 和 7 解决了这个问题:

解决左递归

我在这个语法中找不到任何间接的左递归。

唯一困扰我的是最终的生产规则,它有一个终端被两个非终端包围。

我的两个问题是:

  • 我解决的左递归是否正确?
  • 最终的生产规则是左递归吗?我不确定如何处理这种特殊情况。
4

1 回答 1

1

是的,您的分辨率是正确的。您可能希望删除 epsilon 规则以方便使用,但接受的字符串是正确的。

X -> -
X -> -Z
Z -> +
Z -> +Z
Z -> X + Y
... and Y is of the form 0* 1 (no syntax collisions)

作为检查,请注意您现在可以用两条新规则替换这条最终规则,一条用于 X 的每个扩展:

Z -> -  + Y
Z -> -Z + Y

这会将 X 完全从 Z 规则中删除,然后每个 Z 规则将以终端开始。

不,您的最终生产规则不再是左递归的。X 现在必须解析为以非终结符开头的字符串。

不过,我不得不承认,我很好奇这种语言的用途。:-)

于 2016-04-18T16:05:59.427 回答