Resolving reduce/reduce conflict in yacc/ocamlyacc

Question

I'm trying to parse a grammar in ocamlyacc (pretty much the same as regular yacc) which supports function application with no operators (like in Ocaml or Haskell), and the normal assortment of binary and unary operators. I'm getting a reduce/reduce conflict with the '-' operator, which can be used both for subtraction and negation. Here is a sample of the grammar I'm using:

%token <int> INT
%token <string> ID
%token MINUS

%start expr
%type <expr> expr

%nonassoc INT ID
%left MINUS
%left APPLY

%%

expr: INT
    { ExprInt $1 }
| ID
    { ExprId $1 }
| expr MINUS expr
    { ExprSub($1, $3) }
| MINUS expr
    { ExprNeg $2 }
| expr expr %prec APPLY
    { ExprApply($1, $2) };

The problem is that when you get an expression like "a - b" the parser doesn't know whether this should be reduced as "a (-b)" (negation of b, followed by application) or "a - b" (subtraction). The subtraction reduction is correct. How do I resolve the conflict in favor of that rule?

Answer 1

Unfortunately, the only answer I can come up with means increasing the complexity of the grammar.

1. split expr into simple_expr and expr_with_prefix
2. allow only simple_expr or (expr_with_prefix) in an APPLY

The first step turns your reduce/reduce conflict into a shift/reduce conflict, but the parentheses resolve that.

You're going to have the same problem with 'a b c': is it a(b(c)) or (a(b))(c)? You'll need to also break off applied_expression and required (applied_expression) in the grammar.

I think this will do it, but I'm not sure:

expr := INT
      | parenthesized_expr
      | expr MINUS expr

parenthesized_expr := ( expr )
                    | ( applied_expr )
                    | ( expr_with_prefix )

applied_expr := expr expr

expr_with_prefix := MINUS expr

Answer 2

Well, this simplest answer is to just ignore it and let the default reduce/reduce resolution handle it -- reduce the rule that appears first in the grammar. In this case, that means reducing expr MINUS expr in preference to MINUS expr, which is exactly what you want. After seeing a-b, you want to parse it as a binary minus, rather than a unary minus and then an apply.