java - 这个解析器生成器说这个语法不是 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)。

希望这可以帮助！