grammar - 为什么这个简单的语法会有移位/减少冲突？

Question

%token <token> PLUS MINUS INT
%left PLUS MINUS

这有效：

exp : exp PLUS exp;
exp : exp MINUS exp;
exp : INT;

这有 2 个转变/减少冲突：

exp : exp binaryop exp;
exp : INT;
binaryop: PLUS | MINUS ;

为什么？

Answer 1

这是因为第二个实际上是模棱两可的。第一个语法也是如此，但是您通过添加来解决歧义%left。

这%left在第二种语法中不起作用，因为关联性和优先级不会从规则继承到规则。即binaryop非终结符不会继承任何这样的东西，即使它产生PLUSand MINUS。关联性和优先级被本地化为一个规则，并围绕终端符号。

我们不能这样做%left binaryop，但我们可以稍微重构一下语法：

exp : exp binaryop term
exp : term;
term : INT;
binaryop: PLUS | MINUS ;

这现在没有冲突，因为它是隐式左关联的。即一个越来越长的表达式的产生只能发生在左边binaryop，因为右边是term只产生一个INT的a。

Answer 2

exp binop exp如果您希望优先级规则解决歧义，则需要为规则指定优先级：

exp : exp binaryop exp %prec PLUS;

有了这个改变，所有的冲突都解决了。

编辑

这些评论似乎表明对 yacc/bison 中的优先规则的作用有些混淆。

优先规则是一种半自动解决语法中移位/减少冲突的方法。它们只是半自动的，因为您在指定优先级时必须知道自己在做什么。

Bascially, whenever there is a shift/reduce conflict between a token to be shifted and a rule to be reduced, yacc compares the precedence of the token to be shifted and the rule to be reduced, and -- as long as both have assigned precedences -- does whichever is higher precedence. If either the token or the rule has no precedence assigned, then the conflict is reported to the user.

%left/%right/%nonassoc come into the picture when the token and rule have the SAME precedence. In that case %left means do the reduce, %right means do the shift, and %nonassoc means do neither, causing a syntax error at runtime if the parser runs into this case.

The precedence levels themselves are assigned to tokens with%left/%right/%nonassoc and to rules with %prec. The only oddness is that rules with no %prec and at least one terminal on the RHS get the precedence of the last terminal on the RHS. This can sometimes end up assigning precedences to rules that you really don't want to have precedence, which can sometimes result in hiding conflicts due to resolving them incorrectly. You can avoid these problems by adding an extra level of indirection in the rule in question -- change the problematic terminal on the RHS to to a new non-terminal that expands to just that terminal.

Answer 3

我认为这属于 Bison 手册所称的“神秘冲突”。您可以使用以下方法复制它：

exp:   exp plus exp;
exp:   exp minus exp;
exp:   INT;
plus:  PLUS;
minus: MINUS;

这给了我四个 S/R 冲突。

Answer 4

Bison（2.3版）在Linux上产生的描述冲突语法的输出文件如下。顶部的关键信息是“状态 7 有冲突”。

State 7 conflicts: 2 shift/reduce

Grammar

    0 $accept: exp $end

    1 exp: exp binaryop exp
    2    | INT

    3 binaryop: PLUS
    4         | MINUS

Terminals, with rules where they appear

$end (0) 0
error (256)
PLUS (258) 3
MINUS (259) 4
INT (260) 2

Nonterminals, with rules where they appear

$accept (6)
    on left: 0
exp (7)
    on left: 1 2, on right: 0 1
binaryop (8)
    on left: 3 4, on right: 1

state 0

    0 $accept: . exp $end

    INT  shift, and go to state 1

    exp  go to state 2

state 1

    2 exp: INT .

    $default  reduce using rule 2 (exp)

state 2

    0 $accept: exp . $end
    1 exp: exp . binaryop exp

    $end   shift, and go to state 3
    PLUS   shift, and go to state 4
    MINUS  shift, and go to state 5

    binaryop  go to state 6

state 3

    0 $accept: exp $end .

    $default  accept

state 4

    3 binaryop: PLUS .

    $default  reduce using rule 3 (binaryop)

state 5

    4 binaryop: MINUS .

    $default  reduce using rule 4 (binaryop)

state 6

    1 exp: exp binaryop . exp

    INT  shift, and go to state 1

    exp  go to state 7  

以下是有关“状态 7”的信息：

state 7

    1 exp: exp . binaryop exp
    1    | exp binaryop exp .

    PLUS   shift, and go to state 4
    MINUS  shift, and go to state 5

    PLUS      [reduce using rule 1 (exp)]
    MINUS     [reduce using rule 1 (exp)]
    $default  reduce using rule 1 (exp)

    binaryop  go to state 6

故障由.标记行中的标记描述1。出于某种原因，%left并没有像您期望的那样“生效”，因此 Bison 在读取exp PLUS exp并找到 aPLUS或MINUS之后会识别冲突。在这种情况下，Bison（和 Yacc）会执行 shift 而不是 reduce。在这种情况下，在我看来，这无异于给予规则正确的优先权。

更改%leftto%right并省略它不会改变结果（就冲突警告而言）。我还在 Solaris 上尝试了 Yacc，它产生了基本相同的冲突。

那么，为什么第一个语法有效？这是输出：

Grammar

    0 $accept: exp $end

    1 exp: exp PLUS exp
    2    | exp MINUS exp
    3    | INT

Terminals, with rules where they appear

$end (0) 0
error (256)
PLUS (258) 1
MINUS (259) 2
INT (260) 3

Nonterminals, with rules where they appear

$accept (6)
    on left: 0
exp (7)
    on left: 1 2 3, on right: 0 1 2

state 0

    0 $accept: . exp $end

    INT  shift, and go to state 1

    exp  go to state 2

state 1

    3 exp: INT .

    $default  reduce using rule 3 (exp)

state 2

    0 $accept: exp . $end
    1 exp: exp . PLUS exp
    2    | exp . MINUS exp

    $end   shift, and go to state 3
    PLUS   shift, and go to state 4
    MINUS  shift, and go to state 5

state 3

    0 $accept: exp $end .

    $default  accept

state 4

    1 exp: exp PLUS . exp

    INT  shift, and go to state 1

    exp  go to state 6

state 5

    2 exp: exp MINUS . exp

    INT  shift, and go to state 1

    exp  go to state 7

state 6

    1 exp: exp . PLUS exp
    1    | exp PLUS exp .
    2    | exp . MINUS exp

    $default  reduce using rule 1 (exp)

state 7

    1 exp: exp . PLUS exp
    2    | exp . MINUS exp
    2    | exp MINUS exp .

    $default  reduce using rule 2 (exp)

区别似乎在于，在状态 6 和 7 中，它能够根据接下来发生的事情来区分要做什么。

解决问题的一种方法是：

%token <token> PLUS MINUS INT
%left PLUS MINUS

%%

exp  : exp binaryop term;
exp  : term;
term : INT;
binaryop: PLUS | MINUS;