views:

44

answers:

1

I'm writing a parser in C with bison, and while it appears to work correctly in all circumstances I've tried so far, I get a bunch of shift/reduce warnings on my binary operators (and one on my unary NOT operator as well).

binary_op :
      PLUS { }
      | MINUS { }
      | TIMES { }
      | SLASH { }
      | POWER { }
      | AND { }
      | OR { }
      | LE { }
      | LT { }
      | GE { }
      | GT { }
      | EQ { }
      | NE { }
      | MOD { }
    ;

unary_op :
    NOT { }
    ;

expr :
    ...
    | unary_op expr { }
    | expr binary_op expr { }

When I run my .y file through bison --verbose, I see:

state 51
   11 set_existence: expr . IN set
   12              | expr . NOT IN set
   34 expr: expr . binary_op expr
   34     | expr binary_op expr .

   ...
   NOT    shift, and go to state 26
   AND    shift, and go to state 27
   OR     shift, and go to state 28
   ....
   NOT     [reduce using rule 34 (expr)]
   AND     [reduce using rule 34 (expr)]
   OR      [reduce using rule 34 (expr)]

I don't see any issues actually parsing binary operators, but it seems I should probably resolve the shift/reduce issues anyway. I can't figure out where the conflict is -- the set_existence productions seem completely unrelated. My best guess (a shot in the dark) is that it could have something to do with the fact that EQ is used as a binary operator (equality comparison) as well as assignment (eg, "foo = bar = baz;" would set foo to true/false based on whether bar and baz are equal). If I change my equality comparison to be == ("foo = bar==baz;"), my parser acts as expected but still has the same shift/reduce conflicts.

EDIT: I do have associativity specified:

%left OR
%left AND
%left NOT
%left LT LE GT GE NE EQ
%left PLUS MINUS
%left TIMES MOD SLASH
%left POWER
+2  A: 

There are a couple of ways to avoid this. The first is to use the %left, %right and %nonassoc commands to specify the precedence level (see the manual).

The other option, which I personally prefer, is to encode the precedence directly into the grammar. For example, here is a BNF for simple arithmetic expressions:

expr ::= term | expr + term
term ::= factor | term * factor
factor ::= number | ( expr )

This eliminates the ambiguous parse at the grammar level.

Jack Kelly
+1 Beat me to it.
eldarerathis
Sorry, I should have specified that I do have precedence, though I can't say for sure whether this is incomplete
mynameisash
In that case, post more of your rules for `expr`. Nothing in that snipped you've posted should be shift-reduce-conflicting.
Jack Kelly