OCaml function application precedence and associativity

Question

I need to give high precedence and left associativity to function application in my OCaml parser. I have a bunch of different tokens it matches for such as

%token LET REC EQ IN FUN ARROW 
%token IF THEN ELSE
%token PLUS MINUS MUL DIV LT LE NE AND OR
%token LPAREN RPAREN

and I gave all of these precedence and associativity using %left,right... However, since exp that I'm using to match with isn't a token I was wondering how I would do that in this case:

exp:
| exp exp                    { App($1,$2)}

I have all my matches for exp, didnt make a bunch of different exp1 exp2s and so on and want to know if its possible to give exp exp the highest precedence and left assoc it.

I posted this on another forum for my class and got:

You can associate a dummy token with the function application rules as follows:

rule:   ....   %precc DUMMY_FUN_APP

And then specify associativity using %left and the dummy token.

But im not really sure what this means so if someone could elaborate on this or give me another solution that would be great.

Answer 1

You don't say what parser generator you're using. If you're using ocamlyacc, you might look at the actual grammar of OCaml for ideas. You can find the grammar here: https://github.com/ocaml/ocaml/blob/trunk/parsing/parser.mly

In parser.mly, tokens are listed in precedence order from low to high. Some of the tokens are dummy tokens that are listed only to establish a precedence. These tokens are then referenced from within the syntax rules using %prec token_name.

Here are the last few lines of the token list:

%nonassoc below_SHARP
%nonassoc SHARP          /* simple_expr/toplevel_directive */
%nonassoc below_DOT
%nonassoc DOT
/* Finally, the first tokens of simple_expr are above everything else. */
%nonassoc BACKQUOTE BANG BEGIN CHAR FALSE FLOAT INT INT32 INT64
          LBRACE LBRACELESS LBRACKET LBRACKETBAR LIDENT LPAREN
          NEW NATIVEINT PREFIXOP STRING TRUE UIDENT

Note that the dummy token below_SHARP has very high precedence.

Here are the relevant rules for function application:

expr:
  | simple_expr simple_labeled_expr_list
      { mkexp(Pexp_apply($1, List.rev $2)) }

simple_labeled_expr_list:
    labeled_simple_expr
      { [$1] }
  | simple_labeled_expr_list labeled_simple_expr
      { $2 :: $1 }

labeled_simple_expr:
    simple_expr %prec below_SHARP
      { ("", $1) }

For what it's worth, I've always found yacc associativity and precedence delcarations to be extremely tricky to understand except in simple cases.