Ocaml parser for applying a function

Question

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?

octachron · Accepted Answer · 2025-03-26 23:19:17Z

1

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

edited Mar 26 at 23:19

answered Mar 26 at 9:49

octachron

19.1k2 gold badges19 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Addem Mar 26 at 17:18

When I try this, it says that the precedence is never used, and there are still states with shift/reduce conflicts. I've been trying to think about how I could maybe create a new "production rule" (I don't know if that's what they're called here, but I think that's what they'd be in a BNF grammar). But every example of how to enforce left-associativity in a BNF that I see, exploits the existence of a symbol for the operation.

octachron Mar 26 at 18:35

See the edit, which gives a minimal example of grammar with no conflicts left.

Chris Mar 26 at 19:55

I think you may have mistyped your explanation, which seems to suggest your example does have conflicts.

Collectives™ on Stack Overflow

Ocaml parser for applying a function

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related