menhir - associativity rules for reducing sequences of expressions

Question

writing a parser for lambda expressions,

data expr = Symbol of string | Lambda of string * expr | App of expr * expr

When writing the .mly file how can I express the idea that a sequence of expressions

e1 e2 e3 e4 

should be parsed as

App ((App (App e1 e2) e3) e4)

Using the rules:

%public expr_expr:
    | ID        { Symbol ($1) }
    | NUMBER    { Symbol ($1) }
    | LPAREN expr_expr RPAREN { ($2) }
    | LAMBDA ID ARROW expr_expr { Lambda ($2, $4) }
    | expr_expr expr_expr { Apply ($1, $2) }

gives the structure (e1 , (e2 , (e3 , e4))) as opposed to (((e1, e2), e3), e4). Is there a way of controlling the associativity of a rule as opposed to a token?

Answer 1

Disclaimer: I use ocamlyacc, not menhir, so I base my answer on the former. AFAIUI, the latter is backward compatible to it, so I assume that my answer might be useful anyway.

Citing the documentation http://caml.inria.fr/pub/docs/manual-ocaml/lexyacc.html:

Rules can also contain the %prec symbol directive in the right-hand side part, to override the default precedence and associativity of the rule with the precedence and associativity of the given symbol.

So I would try with

%left Application

to make your rule left associative (at the place where you define precedences; you will need to define at least the relative precedence of application and lambda abstraction) and then change your rule to

| expr_expr expr_expr { Apply ($1, $2) } %prec Application

This makes Application a dummy symbol, used only for the sake of assigning associativity and precedence.

Note 1: The above is partly guesswork on my part. Apparently I never (successfully) tried it myself that way. When I once wrote a lambda grammar, I enforced associativity by modifying the grammar.

Note 2: If it does not work as above, you may take a peek at the OCaml source code. The OCaml language has the same syntax for application.