parsing - 解决减少/减少冲突

Question

我们有一个 CFG 语法，我们构造了 LR(1) Parsing Table。我们看到解析表上的一个单元格有一个减少 - 减少冲突。是否可以通过在每一步使用更多的前瞻输入符号来解决这个冲突？我问这个是因为我认为通过增加前瞻符号，我们可以（并不总是）只解决移位 - 减少冲突。我的意思是减少 - 减少冲突中的额外前瞻对我们没有帮助。我对吗 ？

Answer 1

有可能通过更多的前瞻来解决减少/减少冲突。也可以通过重构来解决。

这实际上取决于冲突的性质。没有一般程序。

一个减少/减少冲突的例子，可以通过额外的前瞻来解决：

A → something
B → A
C → A
D → B u v
D → C u w

在这里，最后两个产生的是明确的，但是当看到 时不能D做出关于减少A到B或到的决定。不过，再一个前瞻符号就可以了，因为第二个下一个符号决定了减少。Cu

重构解决方案：

Au → A u
Bu → Au
Cu → Au
D  → Bu v
D  → Cu w

通过将 B/C 选择推迟一个标记，我们成功地消除了 reduce/reduce 冲突。请注意，即使u不是单个令牌，此解决方案也将起作用；例如，它可以通过非终端。因此，此模型可能适用于仅增加前瞻不足的情况。

Answer 2

一般来说，任何冲突都可以通过额外的前瞻性来解决。在极端情况下，您需要阅读到文件末尾。shift/reduce 和 reduce/reduce 冲突之间没有显着差异。他们的分辨率有点相似。

我写了一篇关于解决冲突的文章。它提出了一种可以找出冲突原因的方法。在某些情况下，这有助于重构语法或定义解析策略。

请看一下：http ://cdsan.com/LinkPool/Data/2915/Conflicts-In-The-LR-Grammars.pdf

如果您有任何问题，请告诉我。