haskell - 快乐:减少/减少冲突

为什么这会引发关于减少/减少冲突的警告

root : set1 'X'
     | set2 'X' 'X'

set1 : 'A'
     | 'B'

set2 : 'B'
     | 'C'

但是接下来可以吗？

root : 'A' 'X'
     | 'B' 'X'
     | 'B' 'X' 'X'
     | 'C' 'X' 'X'

最佳答案

不同之处在于，在第一种情况下，解析器必须在查看是否会跟随一个 'X' 或两个 BX 之前就减少做出选择。

在第二种情况下，解析器可以使用相同的状态，我们称之为 B ，当它看到一个 X 和一个 X - 两者都移位 - 然后根据下一个标记，可以移位(如果是 'B' 'X' 'X' )，然后减少 'B' 'X'规则，或以其他方式立即减少 set1 'X'。

请注意，如果它们没有紧随其后的相同标记 - 例如你有 set2 'Y' 但 bison -v ——那么就没有问题了，因为前瞻将能够开始并选择要采取的减少。

以下是 'B' 输出中用于暴露此问题的相关部分:

案例一

state 0

$accept: . root $end

'A'  shift, and go to state 1
'B'  shift, and go to state 2
'C'  shift, and go to state 3

root  go to state 4
set1  go to state 5
set2  go to state 6

假设我们得到一个 set1 ，我们进入状态 2:

state 2

set1: 'B' .
set2: 'B' .

'X'       reduce using rule 4 (set1)
'X'       [reduce using rule 5 (set2)]
$default  reduce using rule 4 (set1)

请注意，我们可以进行两种可能的缩减:到 set2 或 'X' ，两者都具有相同的输入标记。因此减少/减少;我们只有一个前瞻标记，并且使用这种语法，唯一的标记可能是 'B'——在任何一种情况下!

案例二

state 0

$accept: . root $end

'A'  shift, and go to state 1
'B'  shift, and go to state 2
'C'  shift, and go to state 3

root  go to state 4

假设我们得到一个 'B' 'X' ，我们进入状态 2:

state 2

root: 'B' . 'X'
    | 'B' . 'X' 'X'

'X'  shift, and go to state 6

虽然我们只有一个前瞻标记，但解析器生成器可以产生一种状态，由于输入的适应结构，它可以看到 'X'。因此，我们在任何情况下都会进入状态 6(否则会出错；-)):

状态 6

root: 'B' 'X' .
    | 'B' 'X' . 'X'

'X'  shift, and go to state 9

$default  reduce using rule 2 (root)

这就是魔法发生的地方:如果我们看到 'B' 'X' ，我们转移并进入状态 9(在那里我们减少)，否则我们立即减少 'B' 。

为了完整起见，这里是状态 9:

state 9

root: 'B' 'X' 'X' .

$default  reduce using rule 3 (root)

如果我们有一个前瞻标记来消除歧义

使用此示例语法:

root: set1 'X'
    | set2 'Y'

set1: 'A'
    | 'B'

set2: 'B'
    | 'C'

然后，我们开始:

state 0

$accept: . root $end

'A'  shift, and go to state 1
'B'  shift, and go to state 2
'C'  shift, and go to state 3

root  go to state 4
set1  go to state 5
set2  go to state 6

我们移动 set1 并转到状态 2:

state 2

set1: 'B' .
set2: 'B' .

'Y'       reduce using rule 5 (set2)
$default  reduce using rule 4 (set1)

因此，在 set2 和 'B' 的两个规则中都达到了这种状态，其中堆栈上只有一个 'Y' 标记。在这种情况下，如果我们接下来看到 set2 ，我们将减少到 set1 ——或者在任何其他情况下，减少到 set1 。

它选择 bison 作为“默认”减少的事实可能会对错误处理产生影响。

GLR 附录

Happy(和 yacc 或 --glr )默认生成 LALR(1) 解析器，但您可以使用 %glr-parser (或 bison 声明文件中的 'X' )生成 GLR 解析器。这可以通过同时尝试两种“可能性”来解决歧义；解析器将 fork 并查看在任何一种情况下它的进展情况。

这可能是不明智的，除非你真的需要它，知道你需要它，并且知道如果出现问题会发生什么。我不确定如果两个 fork 都成功终止会发生什么；通过我的非科学测试，它似乎总是最终选择更长的解析。

词法分析器黑客

如果您不想使用 GLR，但又不想显着地重构解析器，则可以考虑使用词法分析器 hack 来解决此问题。

现在，你有这个:

root : set1 'X'
     | set2 'X' 'X'

您可以为单个 ojit_code 字符发出一个 token ，为两个字符发出不同的 token :

root : set1 ONE_X
     | set2 TWO_XS

这解决了单个标记内的歧义，因此是一个明确的 LALR(1) 语法。

关于haskell - 快乐:减少/减少冲突，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10765307/