Menhir conflict for Julia grammar

Learning
1

Hello,
I’ve been trying to create parser for a subset of Julia, but I have an odd conflict that I can’t seem to resolve.
The minimal grammar I use is :

expr := CST x
| SUB expr
| expr SUB expr
| WHILE expr bloc END

bloc := List of expr? separated by ;

Unary minus has higher precedence than binary.
Here is a short code providing a conflict :

    %{
  open Ast
  open Lexing
%}

%token WHILE END
%token <int> CST
%token SUB 
%token SEMICOLON 

%left SUB
%nonassoc unary_minus

%start expr

%type <Ast.expr> expr

%%

expr:
  e = exprDesc
    { { desc = e; loc = $startpos, $endpos} : expr}
;

exprDesc:
  | x = CST 
    { Econst (Cint x) }
  | SUB e = expr %prec unary_minus
    { Eunop (Uneg, e) }
  | e1 = expr SUB e2 = expr
    { Ebinop (e1, Bsub, e2) }
  | WHILE e = expr b = bloc END
    { Ewhile (e, b) }
;

bloc:
  l = separated_nonempty_list(SEMICOLON, ioption(expr))
  { 
    List.fold_right (fun x cur ->
                      match x with | None -> cur | Some v -> v :: cur
                    ) l []
  }
;

And here is the conflict as described by menhir -v :

** Conflict (shift/reduce/reduce) in state 8.
** Tokens involved: SUB SEMICOLON END
** The following explanations concentrate on token SUB.
** This state is reached from expr after reading:

WHILE expr SUB expr 

** The derivations that appear below have the following common factor:
** (The question mark symbol (?) represents the spot where the derivations begin to differ.)

expr 
exprDesc 
(?)

** In state 8, looking ahead at SUB, reducing production
** exprDesc -> SUB expr 
** is permitted because of the following sub-derivation:

WHILE expr bloc END 
           separated_nonempty_list(SEMICOLON,ioption(expr)) 
           expr 
           exprDesc 
           expr SUB expr // lookahead token appears
           exprDesc // lookahead token is inherited
           SUB expr . 

** In state 8, looking ahead at SUB, shifting is permitted
** because of the following sub-derivation:

WHILE expr bloc END 
      exprDesc 
      expr SUB expr 
               exprDesc 
               expr . SUB expr 

** In state 8, looking ahead at SUB, reducing production
** exprDesc -> expr SUB expr 
** is permitted because of the following sub-derivation:

WHILE expr bloc END // lookahead token appears because bloc can begin with SUB
      exprDesc // lookahead token is inherited
      expr SUB expr .

It seems like the precedence between unary_minus and SUB is not used. How can I fix that ?
Thank you for reading

2

That is not how I interpret the error message. As far as I can tell, Menhir rightly complains that it cannot distinguish

while a - b
  -c
end

from

while a
  -b - c
end

Where does the condition of the loop stop and where does the body of the loop start?

3

[This isn’t a helpful comment, but] I was surprised to find no extant Julia grammar written in Yacc/Bison. There seems to be some “tree-sitter” grammar ,but I can’t quite figure out what it means, never having used tree-sitter. And the official parser is in LISP (which I guess I could dig thru and figure out, but feh, not gonna do that just for curiosity’s sake).

Maybe it might be useful to approach the Julia developers and ask if they have a more (ahem) neutral description of the language syntax?

4

The problem was indeed not one related to priority, it just has to do with how Julia decides when the while block starts : It takes the longest expression possible for the condition. To do that, I split expressions in 2 :those that can start with an expression and those that don’t.

5

tree-sitter is a GLR (generalized LR) parser using a javascript EDSL to specify the grammar. It’s not that bad. BTW @mjambon wrote a binding for OCaml here: