快乐:减少/减少冲突

Question

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

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

set1 : 'A'          
     | 'B'             

set2 : 'B'          
     | 'C'  

但接下来还可以吗？

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

Answer 1

不同之处在于,在第一种情况下,解析器必须先选择减少量,然后再查看是否'X'会有一个或两个减少.

在第二种情况下,解析器可以使用相同的状态,让我们调用它BX,当它看到a B和X-both移位时 - 然后根据下一个令牌,可以移位(如果是X),然后减少'B' 'X' 'X'规则,或以其他方式减少'B' 'X'立即.

请注意,如果他们没有相同的令牌后立即 -eg你有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

假设我们得到了'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)

请注意,我们可以进行两种可能的缩减:to set1或者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

假设我们得到了'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在任何其他情况下减少到-or,减少到set1.

它被set1选为"默认"减少这一事实可能会对错误处理产生影响.

关于GLR的附录

默认情况下,Happy(和bison或yacc)生成LALR(1)解析器,但您可以使用--glr(或%glr-parser在bison声明文件中)生成GLR解析器.这可以通过同时尝试两种"可能性"来解决歧义; 在任何一种情况下,解析器都会分叉并查看它到底有多远.

这可能是不明智的,除非你真的需要它,知道你需要它,并且知道如果出现问题会发生什么.我不确定如果两个叉子成功终止会发生什么; 在我的非科学测试中,似乎总是选择更长的解析.

Lexer黑客攻击

如果您不想使用GLR,但又不想显着重构解析器,则可以考虑使用词法分析器来克服此问题.

现在,你有这个:

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

您可以为单个'X'字符发出令牌,为两个令牌发送不同的令牌:

root : set1 ONE_X
     | set2 TWO_XS

这解决了单个令牌中的歧义,并且因此是明确的LALR(1)语法.