Eliminating shift/reduce errors for binary ops

Question

fsyacc is emitting shift/reduce errors for all binary ops.

I have this recursive production:

scalar_expr:
    | scalar_expr binary_op scalar_expr { Binary($2, $1, $3) }

Changing it to

scalar_expr:
    | constant binary_op constant { Binary($2, Constant($1), Constant($3)) }

eliminates the errors (but isn't what I want). Precedence and associativity are defined as follows:

%left BITAND BITOR BITXOR
%left ADD SUB
%left MUL DIV MOD

Here's an excerpt from the listing file showing the state that produces the errors (one other state has the same errors).

state 42:
  items:
    scalar_expr -> scalar_expr . binary_op scalar_expr
    scalar_expr -> scalar_expr binary_op scalar_expr . 

  actions:
    action 'EOF' (noprec):   reduce scalar_expr --> scalar_expr binary_op scalar_expr
    action 'MUL' (explicit left 9999):   shift 8
    action 'DIV' (explicit left 9999):   shift 9
    action 'MOD' (explicit left 9999):   shift 10
    action 'ADD' (explicit left 9998):   shift 6
    action 'SUB' (explicit left 9998):   shift 7
    action 'BITAND' (explicit left 9997):   shift 11
    action 'BITOR' (explicit left 9997):   shift 12
    action 'BITXOR' (explicit left 9997):   shift 13

You can see the parser shifts in all cases, which is correct, I think. I haven't found a case where the behavior is incorrect, at least.

How can I restate the grammar to eliminate these errors?

Answer 1

Is binary_op actually a production, i.e. you have something like:

binary_op:
   | ADD { OpDU.Add }
   | SUB { OpDU.Sub }
   ...

If so I think that is the problem, since I assume the precedence rules you defined wouldn't be honored in constant binary_op constant. You need to enumerate each scalar_expr pattern explicitly, e.g.

scalar_expr:
    | scalar_expr ADD scalar_expr { Binary(OpDU.Add, $1, $3) }
    | scalar_expr SUB scalar_expr { Binary(OpDU.Sub, $1, $3) }
    ...

(I don't think there is any way to abstract away this repetitiveness with FsYacc)

Answer 2

As Stephen pointed out in his answer, the precedence rules for your operators won't apply if you move them to a separate production. This is strange, since the state you posted seems to honor them correctly.

However, you should be able to declare and apply explicit precedence rules, e.g. you could define them as:

%left ADD_SUB_OP
%left MUL_DIV_OP

and apply them like this:

scalar_expr:
    | scalar_expr add_sub_ops scalar_expr %prec ADD_SUB_OP { Binary($2, $1, $3) }
    | scalar_expr mul_div_ops scalar_expr %prec MUL_DIV_OP { Binary($2, $1, $3) }

This way you still have to define multiple rules, but you can group all operators with the same precedence in a group (Note that the names I chose are a poor example; you may want to use names that reflect the precedence or describe the operators within so it's clear what they indicate).

Whether or not this solution is worth it depends on the number of operators per group I suppose.