Why does this simple grammar have a shift / contraction conflict?

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

      

THIS WORKS:

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

      

PRESENT CHARACTERISTICS 2: SHIFT / REDUCE CONFLICTS:

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

      

Why?

+3


source to share


4 answers


This is because the second is actually ambiguous. So the first grammar, but you solved the ambiguity by adding %left

.

This one %left

does not work in the second grammar because associativity and precedence are not inherited from rule to rule. That is, binaryop

nonterminal does not inherit any such thing, even if it produces PLUS

and MINUS

. Associativity and precedence are localized in the rule and revolve around terminal symbols.

We can't do it %left binaryop

, but we can refactor the grammar a bit:



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

      

This has no conflicts because it is implicitly left-associative. That is, the production of a longer and longer expression can only happen on the left side binaryop

, since the right side is term

, which only produces INTs.

+3


source


You need to specify the priority for the rule exp binop exp

if you want the priority rules to resolve ambiguity:

exp : exp binaryop exp %prec PLUS;

      

With this change, all conflicts are resolved.

Edit

The comments seem to indicate some confusion as to what the precedence rules in yacc / bison do.



Precedence rules are a way to semi-automatically resolve shift / decrease conflicts in grammar. They are only semi-automatic in that you need to know what you are doing when you prioritize.

Basically, whenever there is a shift / decrease conflict between the token to be shifted and the rule to be reduced, yacc compares the priority of the token to be shifted and the rule to be reduced, and - as long as both have priorities - no matter which one is higher. If either the token or the rule has no priority, then the conflict is reported to the user.

%left

/ %right

/ %nonassoc

enter the image when the marker and rule have ONLY priority. In this case, %left

means abbreviation, %right

means shift, and %nonassoc

means that it is not, which leads to a syntax error at runtime if the parser works in this case.

Priority levels are assigned to tokens with %left

/ %right

/ %nonassoc

and rules with %prec

. The only oddity is that rules without %prec

and at least one terminal on the RHS take precedence over the last terminal on the RHS. This can sometimes lead to prioritizing rules that you really don't want to take precedence, which can sometimes lead to hiding conflicts due to mishandling them. You can avoid these problems by adding an extra layer of indirection in the rule in question - change the problem terminal to RHS to a new non-terminal that expands to that terminal.

+4


source


I guess this falls under what the Bison management calls " Mysterious Conflicts ." You can replicate this with:

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

      

which gives me four S / R conflicts.

0


source


The output file describing the conflicting grammar released by Bison (version 2.3) on Linux looks like this. The key information at the top is "State 7 has conflicts".

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  

      

And here is information about "State 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

      

The problem is described by markers .

in the lines marked with 1

. For some reason, it %left

doesn't act as you'd expect, so Bison identifies a conflict when it reads exp PLUS exp

and finds after it PLUS

or MINUS

. In such cases, Bison (and Yacc) perform a shift, not a reduction. In this context, it seems to me to be tantamount to rules taking precedence.

Changing %left

to %right

and excluding it does not change the result (in terms of conflict warnings). I also tried Yacc on Solaris and created essentially the same conflict.

So why does the first grammar work? Here's the output:

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)

      

The difference seems to be that in states 6 and 7, she is able to distinguish what to do based on the following.

One way to fix the problem:

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

%%

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

      

0


source







All Articles