parsingocamlml-yacc

Ocaml parser for applying a function


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?


Solution

  • 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)}
    ;