Type error when equipping Menhir with an abstract syntax tree

Question

EDIT:

My below question still stands but I appreciate that it's hard to answer without sifting through a pile of code. Therefore, to ask a somewhat similar question, does anyone have any examples of Menhir being used to implement an AST? Preferably not "toy" projects like a calculator but I would appreciate any help I could get.

Original Question:

I'm trying to implement an abstract syntax tree using Menhir and there's an issue I can't seem to solve. My set up is as follows:

• The AST's specification is generated using atdgen. This is basically a file with all of my grammar rules translated to to the ATD format. This allows me to serialize some JSON which is what I use to print out the AST.
• In my parser.mly file I have a long list of production. As I'm using Menhir I can link these productions up to AST node creation, i.e. each production from the parser corresponds with an instruction to record a value in the AST.

The second point is where I'm really struggling to make progress. I have a huge grammar (the ast.atd file is ~600 lines long and the parser.mly file is ~1000 files long) so it's hard to pin down where I'm going wrong. I suspect I have a type error somewhere along the way.

Snippets of Code

Here's what my ast.atd file looks like:

    ...
type star = [ Star ]

type equal = [ Equal ]

type augassign = [
  | Plusequal
  | Minequal
  | Starequal
  | Slashequal
  | Percentequal
  | Amperequal
  | Vbarequal
  | Circumflexequal
  | Leftshiftequal
  | Rightshiftequal
  | Doublestarequal
  | Doubleslashequal
]
    ...

Here's what my parser.mly file looks like:

    ...
and_expr // Used in: xor_expr, and_expr
    : shift_expr
        { $1 }
    | and_expr AMPERSAND shift_expr
        { `And_shift ($1, `Ampersand, $3) } ;

shift_expr // Used in: and_expr, shift_expr
    : arith_expr
        { $1 }
    | shift_expr pick_LEFTSHIFT_RIGHTSHIFT arith_expr
        { `Shift_pick_arith ($1, $2, $3) } ;

pick_LEFTSHIFT_RIGHTSHIFT // Used in: shift_expr
    : LEFTSHIFT
        { `Leftshift }
    | RIGHTSHIFT
        { `Rightshift } ;
    ...

The error I get when I try to compile the files with

ocamlbuild -use-menhir -tag thread -use-ocamlfind -quiet -pkgs
    'core,yojson,atdgen' main.native

is a type error, i.e.

This expression has type [GIANT TYPE CONSTRUCTION] but an expression
    was expected of type [DIFFERENT GIANT TYPE CONSTRUCTION]

I realise that this question is somewhat difficult to answer in the abstract like this, and I'm happy to provide a link to the dropbox of my code, but I'd really appreciate if anyone could point me in the right direction.

Possibly of interest: I have some productions in parser.mly that were initially "empty" which I dealt with by using the ocaml option type (Some and None). Perhaps I could be having issues here?

Answer 1

About examples of code using menhir, you can have a look at the list on the right on the OPAM menhir page - all those depend on menhir.