parsing - 在我的语法中解决左递归

Question

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

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

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

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

我的两个问题是：

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

Answer 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 现在必须解析为以非终结符开头的字符串。

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