conflicts: 2 shift/reduce

Question

I'm trying to write a little interpreter with GNU bison. I wanted to ask if anyone could explain the difference between the directive% right and% left and where my mistake is in the code below.

%token <flo> FLO
%token <name> NAME
%right '='
%left '+' '-'
%left '*' '/' '%'
%left '&' '|' 'x'
%left NEG NOT LOGIC_NOT
%left '^'
%left ARG

%type <flo> exp

%%

language:     /* nothing */
            | language statment

statment:     '\n'
            | exp
            | error                     { yyerrok; }
;

exp:      FLO                           { $$ = $1; }
        | NAME '(' ')'                  { $$ = ycall($1); }
        | NAME '(' exp ')'              { $$ = ycall($1, $3); }
        | NAME '(' exp ',' exp ')'      { $$ = ycall($1, $3, $5); }
        | NAME '=' exp                  { $$ = 1; ysetvar($1, $3); }
        | NAME %prec VAR                { $$ = ygetvar($1); }
        | '_' exp %prec ARG             { $$ = ygetarg($2, args); }
        | '(' exp ')'                   { $$ = $2; }
        /* 1 Operand */
        | '-' exp %prec NEG             { $$ = - $2; }
        | '~' exp %prec NOT             { $$ = ~ static_cast<int>($2); }
        | '!' exp %prec LOGIC_NOT       { $$ = ! static_cast<int>($2); }
        /* 2 Operands */
        | exp '+' exp                   { $$ = $1 + $3; }
        | exp '-' exp                   { $$ = $1 - $3; }
        | exp '*' exp                   { $$ = $1 * $3; }
        | exp '/' exp                   { $$ = $1 / $3; }
        | exp '%' exp                   { $$ = static_cast<int>($1) % static_cast<int>($3); }
        | exp '^' exp                   { $$ = pow($1, $3); }
        | exp '&' exp                   { $$ = static_cast<int>($1) & static_cast<int>($3); }
        | exp '|' exp                   { $$ = static_cast<int>($1) | static_cast<int>($3); }
        | exp 'x' exp                   { $$ = static_cast<int>($1) ^ static_cast<int>($3); }
;

Answer 1

Look at the y.output file produced by yacc or bison with the -v argument. The first conflict is in state 5:

State 5

    7 exp: NAME . '(' ')'
    8    | NAME . '(' exp ')'
    9    | NAME . '(' exp ',' exp ')'
   10    | NAME . '=' exp
   11    | NAME .

    '='  shift, and go to state 14
    '('  shift, and go to state 15

    '('       [reduce using rule 11 (exp)]
    $default  reduce using rule 11 (exp)

In this case the conflcit is when there's a '(' after a NAME -- this is an ambiguity in your grammar in which it might be a call expression, or it might be a simple NAME expression followed by a parenthesized expression, due to the fact that you have no separator between statements in your language.

The second conflict is:

State 13

    4 statment: exp .
   17 exp: exp . '+' exp
   18    | exp . '-' exp
   19    | exp . '*' exp
   20    | exp . '/' exp
   21    | exp . '%' exp
   22    | exp . '^' exp
   23    | exp . '&' exp
   24    | exp . '|' exp
   25    | exp . 'x' exp

    '+'  shift, and go to state 21
    '-'  shift, and go to state 22
    '*'  shift, and go to state 23
    '/'  shift, and go to state 24
    '%'  shift, and go to state 25
    '&'  shift, and go to state 26
    '|'  shift, and go to state 27
    'x'  shift, and go to state 28
    '^'  shift, and go to state 29

    '-'       [reduce using rule 4 (statment)]
    $default  reduce using rule 4 (statment)

which is essentially the same problem, this time with a '-' -- the input NAME - NAME might be a single binary subtract statements, or it might be two statements -- a NAME followed by a unary negate.

If you add a separator between statements (such as ;), both of these conflicts would go away.