On ocamlyacc, function application grammar and precedence

Question

I'm OCaml newbie and I'm trying to write a simple OCaml-like grammar, and I can't figure this out. My grammar allows something like this:

let sub = fun x -> fun y -> x - y;;

However, if I want to use the function so defined, I can write: (sub 7) 3 but I can't write sub 7 3, which really bugs me. For some reason, it gets interpreted as if I wrote sub (7 3) (which would treat 7 as a function with argument 3). The relevant sections are:

/* other operators, then at the very end: */
%left APPLY

/* ... */

expr:
    /* ... */
    | expr expr %prec APPLY      { Apply($1, $2) }

Thanks!

Answer 1

In case you came to this question and thought you had finally reached that moment when you find exactly what you're looking for, then were disappointed, here is a more explicit answer:

You cannot use %prec for the reason Thelema mentioned. So you must define associativity in establishing a recursive set of rules.

Here's a simplified parser.mly

    %token <int> Num
    %token <string> Id
    %token TRUE FALSE
    %token LET REC EQ IN FUN ARROW IF THEN ELSE
    %token PLUS MINUS MUL DIV LT LE NE AND OR
    %token EOF          

    %start exp
    %type <Simple.expr> exp

    %%

/* Associativity increases from exp to exp8
 * Each precedence level trickles down to higher level expressions if the pattern is not matched 
 */

/* Parses the LET, LET REC, FUN, and IF expressions */
exp:
      LET Id EQ exp IN exp      { Let($2,$4,$6) }
    | LET REC Id EQ exp IN exp  { Letrec($3,$5,$7) }
    | FUN Id ARROW exp          { Fun($2,$4) }
    | IF exp THEN exp ELSE exp  { If($2,$4,$6) }
    | exp2                      { $1 }

/* Parses OR expressions */
exp2:
      exp2 OR exp3              { Bin($1,Or,$3) }
    | exp3                      { $1 }

/* Parses AND expressions */
exp3:
      exp3 AND exp4             { Bin($1,And,$3) }
    | exp4                      { $1 }

/* Parses EQ, NE, LT, and LE expressions */
exp4:
      exp4 EQ exp5              { Bin($1,Eq,$3) }
    | exp4 NE exp5              { Bin($1,Ne,$3) }
    | exp4 LT exp5              { Bin($1,Lt,$3) }
    | exp4 LE exp5              { Bin($1,Le,$3) }
    | exp5                      { $1 }

/* Parses PLUS and MINUS expressions */
exp5:
      exp5 PLUS exp6            { Bin($1,Plus,$3) }
    | exp5 MINUS exp6           { Bin($1,Minus,$3) }
    | exp6                      { $1 }

/* Parses MUL and DIV expressions */
exp6:
      exp6 MUL exp7             { Bin($1,Mul,$3)}
    | exp6 DIV exp7             { Bin($1,Div,$3)}
    | exp7                      { $1 }

/* Parses Function Application expressions */
exp7:
      exp7 exp8                 { Apply($1,$2) }
    | exp8                      { $1 }

/* Parses numbers (Num), strings (Id), booleans (True | False), and expressions in parentheses */
exp8:
      Num                       { Const($1) }
    | Id                        { Var($1) }
    | TRUE                      { True }
    | FALSE                     { False }
    | LPAREN exp RPAREN         { $2 }

The recursive work-around is really for catching the case that we're concerned with regarding this question, however it's easy to see how it can be applied to defining associativity for the rest of the expressions as well.

The gist of this approach is to attempt to match the pattern in question against the patterns defined in the start case (exp), and you leave a call to the immediately succeeding case (exp2) as a catch-all pattern if your pattern does not match any before it; continuing with this approach until the pattern finally matches. This implies that the highest priority pattern exists in the furthest down case - in this example, exp8.

In this example, the case for Apply (Function Application) is in exp7. This is because Apply is defined to have the highest associativity of any pattern in this example. The reason it does not have priority over the cases in exp8 is due to Apply evaluating to further calls to expression cases, not value calls. If exp8 didn't exist, we'd have an infinite look on our hands.

In the hypothetical simple.ml, Function Application is defined as an expression of the following property: Apply of expr * expr. And since Apply is left-recursive, we are evaluating the right expression (exp8) and recursing on the left (exp7).

Answer 2

The ocaml compiler does function application as follows: (from ocaml/parsing/parser.mly)

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

where simple_expr is a subset of the possible expr values that can evaluate to a function without needing parentheses. This excludes all the non-self-bracketed constructs from being used inline with a function call. It also clarifies the associativity of the subexpressions, as the second subexpression is explicitly a list.

As to why your attempt to use %left APPLY to get the correct associativity doesn't work, from the comments in ocaml's parser.mly:

We will only use associativities with operators of the kind  x * x -> x
for example, in the rules of the form    expr: expr BINOP expr
in all other cases, we define two precedences if needed to resolve
conflicts.

I'd say this means that you can't use %prec for associativity without an operator. Try creating the associativity you want through defining more rules, and see where that leads.