解决减少/减少冲突

Question

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

Answer 1

可以通过更多的前瞻性来解决reduce/reduce冲突。也可以通过重构来解决这个问题。

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

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

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

这里，D的最后两个生成是明确的，但是当看到u时，不能做出关于将A缩减为B或C的决定。不过，多看一个符号就可以了，因为下一个符号的第二个决定了缩减。

重构解决方案：

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

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

Answer 2

通常，任何冲突都可以通过额外的前瞻性解决。在极端情况下，您需要读取到文件的末尾。转移/减少和减少/减少冲突之间没有显著差异。他们的决心有点相似。

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

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

如果你有问题，请告诉我。