3

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

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

set1 : 'A'          
     | 'B'             

set2 : 'B'          
     | 'C'

但接下来可以吗？

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

1 回答 1

9

不同之处在于，在第一种情况下，解析器必须先对归约做出选择，然后才能查看是否'X'会遵循一个或两个。

在第二种情况下，解析器可以使用相同的状态，我们称它为BX，当它看到 aB和 an时X——都移位了——然后根据下一个标记，可以移位（如果是X），然后减少'B' 'X' 'X'规则，或者减少'B' 'X'立即地。

请注意，如果它们没有紧随其后的相同标记——例如你有set1 'X'但是set2 'Y'——那么就不会有问题，因为前瞻将能够启动并选择要采取的减少。

bison -v以下是暴露此问题的输出中的相关部分：

案例一

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

假设我们得到 a 'B'，我们进入状态 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)

请注意，我们可以进行两种可能的归约：toset1或set2，两者都具有相同的输入标记。因此减少/减少；我们只有一个前瞻标记，并且使用这种语法，唯一的标记可能是'X'- 在任何一种情况下！

案例二

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

假设我们得到 a 'B'，我们进入状态 2：

state 2

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

'X'  shift, and go to state 6

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

状态 6

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

'X'  shift, and go to state 9

$default  reduce using rule 2 (root)

这就是魔法发生的地方：如果我们看到一个'X'，我们转移并进入状态 9（我们减少），否则我们'B' 'X'立即减少。

为了完整起见，这里是状态 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

我们转移'B'并进入状态 2：

state 2

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

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

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

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

GLR 附录

Happy（and bisonor yacc）默认生成 LALR(1) 解析器，尽管您可以使用--glr（或%glr-parser在您的bison声明文件中）生成 GLR 解析器。这可以通过同时尝试两种“可能性”来解决歧义；解析器将分叉并查看在任何一种情况下它会走多远。

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

词法分析器

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

现在，你有这个：

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

您可以改为为单个'X'字符发出标记，为两个字符发出不同的标记：

root : set1 ONE_X
     | set2 TWO_XS

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

于 2012-05-26T10:53:16.430 回答