wrong expression type on ocamlyacc

Question

As part of a school project I have to recognize a .dot file and produce the corresponding parse tree. To accomplish this, I have to use ocamllex and ocamlyacc which whom I've difficulties...

This is my ocaml .mli types file :

type id = string 
and node = id
and attr = id * id
and attr_list = attr list list
and attr_stmt =
    Graphs of (attr_list)
    | Nodes of (attr_list)
    | Edge of (attr_list)
and node_stmt = node * attr_list
and node_subgraph = 
    Node of (node)
    | Subgraphs of (graph)  
and edge_stmt = node_subgraph * (node_subgraph list) * attr_list
and stmt = 
    Node_stmt of (node_stmt)
    | Edge_stmt of (edge_stmt)
    | Attr_stmt of (attr_stmt)
    | Attr of (attr)
    | Subgraph of  graph
and graph = 
    Graph_node of (node * stmt list)
    | Graph of (stmt list);;

this is my lexer file :

{
    open Parser
}
rule token = parse 
    (* Espacements *)
    | [ ' ' '\t' '\n']+  {token lexbuf}
    (* *)
    | "graph" {GRAPH}
    | "subgraph" {SUBGRAPH}
    | "--" {EDGE}
    (* Délimiteurs *)
    | "{" {LEFT_ACC}
    | "}" {RIGHT_ACC}
    | "(" {LEFT_PAR}
    | ")" {RIGHT_PAR}
    | "[" {LEFT_BRA}
    | "]" {RIGHT_BRA} 
    | "," {COMMA}
    | ";" {SEMICOLON}
    | "=" {EQUAL}
    | ":" {TWOPOINT}
    | ['a'-'z''A'-'Z''0'-'9']*  as id {ID (id)} 
    | eof { raise End_of_file }

and this is my not finished yacc file :

%{
    open Types
%}

%token <string> ID 
%token <string> STR
%token GRAPH SUBGRAPH EDGE
%token LEFT_ACC RIGHT_ACC LEFT_PAR RIGHT_PAR LEFT_BRA RIGHT_BRA
%token COMME SEMICOLON EQUAL TWOPOINT EOF 

%start main
%type <graph> main 

%%

main:
 graph EOF { $1 }


graph:
    GRAPH ID LEFT_ACC content RIGHT_ACC {$4}
    | GRAPH LEFT_ACC content RIGHT_ACC {$3}

subgraph:
    SUBGRAPH ID LEFT_ACC content RIGHT_ACC {$4}
    | SUBGRAPH LEFT_ACC content RIGHT_ACC {$3}

content:
    | ID EDGE ID SEMICOLON {[($1,$3)]}

It seems enough for recognizing a simple dot file like

graph D {
    A -- B ;
}

But when I try to compile my parser interface I get this error : This expression has type 'a list but an expression was expected of type Types.graph (refers to ID EDGE ID SEMICOLON {[$1,$3)]} line )

I don't understand because {[$1,$3]} has a (string * string) list type. And if we are looking to types.mli that can be a graph.

Otherwise, have I correctly understand the running of ocamllex and ocamlyacc ?

Answer 1

A value of type graph has to start with either Graph or Graph_node. This is not at all the same as (string * string) list.