3

我写了以下野牛语法文件：

%left '+' '-'
%left '*' '/'

%token NUMBER

%%

expr
: NUMBER
| expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr
| expr     expr %prec '*' /* implicit multiplication */
;

现在bison报告关于expr : expr expr. 我已将问题提取到以下最小集合：

%left OP

%%

expr
: 'a'
| expr expr %prec OP
;

我不明白为什么bison仍然抱怨转移/减少冲突。我找到了一些旧邮件存档：Re: bison/yacc: shift/reduce conflict using %prec for composition，但我也不明白作者的解释。

有人可以澄清为什么这个语法是模棱两可的，以及如何解决冲突？

编辑：NUMBER NUMBER我的意思是NUMBER * NUMBER，即这两个数字的乘积。

4

2 回答 2

3

这里的问题是令牌NUMBER没有优先级。因此，当有一个状态可以改变NUMBER或减少规则时（无论该规则是否具有优先级），它无法决定该做什么。

现在，您可以通过添加优先级NUMBER（使其*与将在.NUMBERexpr: '(' expr ')''('

更大的问题是，如果您添加一元前缀运算符，例如expr: '-' expr. 在这种情况下，您不会遇到冲突，因为 '-' 已经具有优先级，但是输入 likeNUMBER - NUMBER将被解析为NUMBER ( - NUMBER )，这可能根本不是您想要的。没有用优先规则处理这个问题的好方法。

这种混淆的根本原因是野牛的优先规则不能通过比较两个规则来解决优先级，正如您基于使用“优先级”这个词可能天真地期望的那样。相反，它们通过将要减少的规则的“优先级”与要转移的令牌的“优先级”进行比较，并以此为基础决定转移或减少。在解析中发生这种情况的地方，第二条规则尚未被识别；相反，野牛只是根据令牌猜测它可能是什么。

于 2012-02-12T03:03:54.370 回答
2

部分答案是仔细查看bison -v. 对于您的第一个语法，我得到了以下摘录：

State 8 conflicts: 1 shift/reduce
State 9 conflicts: 1 shift/reduce
State 10 conflicts: 1 shift/reduce
State 11 conflicts: 1 shift/reduce
State 12 conflicts: 1 shift/reduce

Grammar

    0 $accept: expr $end

    1 expr: NUMBER
    2     | expr '+' expr
    3     | expr '-' expr
    4     | expr '*' expr
    5     | expr '/' expr
    6     | expr expr

所以语法中有5个移位/减少冲突。这些是不太严重的冲突类型；%expect 5如果您确信语法所做的事情是正确的，您可以在语法中声明您期望它们。

state 0

    0 $accept: . expr $end

    NUMBER  shift, and go to state 1

    expr  go to state 2

state 1

    1 expr: NUMBER .

    $default  reduce using rule 1 (expr)

state 2

    0 $accept: expr . $end
    2 expr: expr . '+' expr
    3     | expr . '-' expr
    4     | expr . '*' expr
    5     | expr . '/' expr
    6     | expr . expr

    $end    shift, and go to state 3
    '+'     shift, and go to state 4
    '-'     shift, and go to state 5
    '*'     shift, and go to state 6
    '/'     shift, and go to state 7
    NUMBER  shift, and go to state 1

    expr  go to state 8

state 3

    0 $accept: expr $end .

    $default  accept

state 4

    2 expr: expr '+' . expr

    NUMBER  shift, and go to state 1

    expr  go to state 9

状态 5、6、7 模拟状态 4，但适用于其他运营商。状态 8 是第一个发生转移/减少冲突的状态。请记住，.规则中的（点）表示解析器到达此状态时的位置。

state 8

    2 expr: expr . '+' expr
    3     | expr . '-' expr
    4     | expr . '*' expr
    5     | expr . '/' expr
    6     | expr . expr
    6     | expr expr .

    NUMBER  shift, and go to state 1

    NUMBER    [reduce using rule 6 (expr)]
    $default  reduce using rule 6 (expr)

    expr  go to state 8

state 9

    2 expr: expr . '+' expr
    2     | expr '+' expr .
    3     | expr . '-' expr
    4     | expr . '*' expr
    5     | expr . '/' expr
    6     | expr . expr

    '*'     shift, and go to state 6
    '/'     shift, and go to state 7
    NUMBER  shift, and go to state 1

    NUMBER    [reduce using rule 2 (expr)]
    $default  reduce using rule 2 (expr)

    expr  go to state 8

这两个状态之间存在差异和相似之处，但状态 10、11、12 与状态 9 匹配，只是歧义点不同。

麻烦的是，当语法看到：

NUMBER OP NUMBER NUMBER

它无法判断是否将其解析为：

( NUMBER OP NUMBER ) NUMBER expr expr

或作为：

NUMBER OP ( NUMBER NUMBER )
 expr  OP       expr

鉴于在每种情况下都是移位/减少冲突，它选择移位。如果那是您想要的，那么添加%expect 5并继续生活。如果那不是你想要的，那么你需要重新考虑你的语法。一对相邻的数字表示什么，您确定不需要一些操作符（可能是逗号或冒号）来分隔它们吗？

我尝试使用以下方法提高缺失运算符的优先级：

%left MISSING

在其他优先声明之后，然后使用：

expr expr %prec MISSING

这并没有改变什么。通过将 MISSING 列在其他运算符之前也不会使 MISSING 的优先级非常低。

如果您考虑应该如何解析这样的表达式，您就会对问题有所了解：

NUMBER OP NUMBER NUMBER NUMBER OP NUMBER NUMBER OP NUMBER

每次出现的OP都相同。我的脑袋好痛！的也bison一样！

于 2012-02-11T20:05:18.580 回答