这个解析器生成器说这个语法不是LR(1),但我有疑虑

Question

我用Java编写了一个解析器生成器,经过几次颠簸(例如早期版本并不特别喜欢左递归),我设法让它与一些简单的语法一起工作(所以我可以手工验证产品是否正确我试着给它一个更复杂的语法,输出结果是它不是一个LR(1)语法(源于解析后试图在解析表中的同一个单元格上写两次)

有问题的语法是

S-> aAb | SA
A-> aA | e | S.

我很确定这个语法是LR(1),无论如何,这是我程序的输出 http://pastebin.com/hJNC9uuN

任何建议都将是最宝贵的谢谢(如果有人有一个解析器生成器输出自动机和解析表,所以我可以面对它们更好)

Answer 1

这个语法不能是LR(1),因为它不明确.以下是两种派生字符串的方法ab:

S→aAb→ab

S→SA→aAbA→abA→ab

您的LR(1)集实际上包含转移/减少冲突.查看状态5,其中包括以下项目:

[A->S. { $a }]
[A->.aA { $a }]

这是一个转变/减少冲突:你转移a,还是减少a？因此,该工具在此输入上看起来正确:语法不是LR(1),并且它发现它不是LR(1).

希望这可以帮助!