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?

James A. Rosen James A. Rosen · Accepted Answer · 2008-08-23T20:49:00

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

split expr into simple_expr and expr_with_prefix
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

Resolving reduce/reduce conflict in yacc/ocamlyacc

2 Answers