Juxtaposition in Menhir

Community
1

I would like to use “simple” precedence rules to write a parser in Menhir for a grammar where juxtaposition is right-associative function application (like OCaml syntax, so e.g. f g x should be parsed Apply (Apply (Var "f", Var "g"), Var "x")). One might naïvely expect the following to work:

%token <string> VAR
%token EOF

%right APP

%start <Ast.t> main
%%

main : e = expr EOF { e }

expr:
  | e1=expr e2=expr %prec APP
    { Ast.Apply (e1,e2) }
  | x=VAR
    { Ast.Var x }

but alas

$ menhir lib/parser.mly 
File "lib/parser.mly", line 4, characters 0-6:
Warning: the precedence level assigned to APP is never useful.
File "lib/parser.mly", line 12, characters 26-29:
Warning: this %prec declaration is never useful.
Warning: one state has shift/reduce conflicts.
Warning: one shift/reduce conflict was arbitrarily resolved.

I know how to get this to work the hard way, using explicit “levels” of expressions, like this:

%token <string> VAR
%token LPAREN RPAREN
%token EOF

%start <Ast.t> main
%%

main : e = expr EOF { e }

expr:
  | e1=expr e2=expr1
    { Ast.Apply (e1,e2) }
  | e=expr1
    { e }

expr1:
  | x=VAR
    { Ast.Var x }
  | LPAREN e=expr RPAREN
    { e }

So, is there a way to get the same result but using precedence annotations?

Thanks!

2

This is left-associative. It would be right-asociative if the output was Apply (Var "f", Apply (Var "g", Var "x")).

Sure.

Shift/reduce conflicts occur when encountering a token. In your case, the parser stack already contains two expressions and the next token is VAR, so the parser has to take a decision. Does it ignore the token and reduce the stack using expr expr -> expr? Or does it shift the token (and later reduce it using VAR -> expr)? To decide how to solve this conflict, Menhir compares the precedence of VAR with the precedence of the rule expr expr -> expr.

If you only use %prec APP, then you are not telling Menhir anything, because APP and VAR have uncomparable precedences. If you change %right APP into

%nonassoc VAR
%right APP

then APP gets a higher precedence than VAR, which makes your grammar left-associative. In other words, whether you write %left or %right or %nonassoc here is actually meaningless. The grammar will always be left-associative. And conversely, if you swap the two lines, the grammar will always be right-associative, irrespective of the associativity you specify.

So, if you want the associativity to be taken into account, you need the precedence of the rule expr expr -> expr to be exactly the same as VAR:

%right VAR (* or %left VAR, depending on what you want *)
...
expr:
  | e1=expr e2=expr %prec VAR
  | x=VAR
5 Likes
3

This is left-associative.

Yes, sorry. Left associativity was my intention here. I have trouble with chirality in the real world too.

To decide how to solve this conflict, Menhir compares the precedence of VAR with the precedence of the rule expr expr -> expr .

This is a helpful and lucid explanation. Thank you very much!