I have a file, parser.mly
, which has the following
%{
open Ast
%}
(* Ast holds the abstract syntax tree type definitions. *)
%token EOF
%token OR
%left OR
%start <Ast.prog> prog
%%
prog:
| e = expr; EOF {e}
;
expr:
| e1 = expr; OR; e2 = expr { Binop(Or, e1, e2) }
;
I'm trying to add a definition for function application.
However, function application doesn't have its own token. It's just an expression followed by another expression.
When I try to code this with something like
| e1 = expr; e2 = expr { App(e1, e2) }
very understandably, the compiler gives the error message that 2 states have shift/reduce conflicts, because this kind of rule introduces ambiguity.
Now I can eliminate the ambiguity that comes with OR
tokens by declaring them left-associative. But how do I do it in this case, where no token can be declared to be left-associative?
Using menhir, you can add a precedence declaration to the rule itself:
| e1 = expr; e2 = expr %prec APP { App(e1, e2) }
For instance, there are no conflict left with
%token EOF
%token UNIT
%token OR
%nonassoc UNIT
%left OR
%left APP
%start <e> prog
%%
prog:
| e = expr; EOF {e}
;
expr:
| UNIT { Unit }
| e1 = expr; OR; e2 = expr { Binop(Or, e1, e2) }
| e1=expr e2=expr %prec APP { App(e1,e2)}
;