title: Ocaml: build list for Ast type in recursive function
body: <p>I have a handwritten LL1 parser. My AST is not as simplified as it could be. The portion for statements looks like this:</p>
  
  <pre><code>type stmt_opt = StmtExpression of assignment | OptNil
  [@@deriving show]
  (*stmt_list -&gt; stmt stmt_list | ε *)
  type stmtlist =
      | StmtList of stmt * stmtlist
      | StmtlistNil 
  [@@deriving show]
  
  and stmt = 
  | Assignment of assignment
  | Return of stmt_opt 
  | Parentheses of stmtlist
  | If of assignment * stmt
  | For of assignment * assignment * assignment * stmt
  | While of assignment * stmt
  (*“lparen” formals_opt “rparen” “LBRACE” vdecl_list stmt_list “RBRACE”*)
  [@@deriving show]
  </code></pre>
  
  <p>As you can see, I'm still holding onto a lot of unnecessary information. I'd like to build my statement ast like this:</p>
  
  <pre><code>type stmt =
      Block of stmt list
    | Expr of expr
    | Return of expr
    | If of expr * stmt * stmt
    | For of expr * expr * expr * stmt
    | While of expr * stmt
  </code></pre>
  
  <p>I'm a little lost as to do this because I really built my LL1 parser by the books (which I believe don't anticipate very long grammars): every nonterminal has a parse method and every parse method returns a tokenlist and an ast.</p>
  
  <p>I think, in order to build a Block type like in my goal statement AST, I need to build a list of statements inside my recursive parseStmt method. I have reduced my parser code to only the parser methods that call parseStmtList and the specific instances where they call parseStmtList</p>
  
  <pre><code>(*stmt_list = stmt stmt_list | epsilon*)
  let rec parseStmtList tokenlist lst = 
      match tokenlist.head with 
      | Lexer.RightBrace -&gt; (tokenlist, Ast.StmtlistNil )
      | _ -&gt; let (tokenlist_stmt, stmt) = parseStmt tokenlist in 
            let new_lst = lst::stmt in
            let (tokenlist_stmt_list, stmt_list) = tokenlist_stmt new_lst |&gt; parseStmtList in
            (tokenlist_stmt_list, Ast.Block(stmt_lst))
  
  (*stmt -&gt; assignment SEMI 
  |  RETURN stmt_opt SEMI
  |  LBRACE stmt_list RBRACE 
  |  IF LPAREN assignment RPAREN stmt 
  |  FOR LPAREN assignment SEMI assignment SEMI assignment RPAREN stmt  
  |  WHILE LPAREN assignment RPAREN stmt
  *)
  
  and parseStmt tokenlist = 
     begin
     match tokenlist.head with 
     | Lexer.ID identifier -&gt; let (tokenlist_assignment, assignment) = parseAssignment tokenlist in
                  begin
                  match tokenlist_assignment.head with
                  | Lexer.Semicolon -&gt; (next tokenlist_assignment, Ast.Assignment(assignment))
                  | _-&gt; let err_msg = __LOC__ ^ "Syntax Error semicolon expected but received" ^ show_token_list tokenlist in
                       raise (Syntax_error err_msg) 
                  end
           | Lexer.LeftBrace -&gt; let tokenlist_leftbrace = next tokenlist in 
                          let (tokenlist_expr, expr) = parseStmtList tokenlist_leftbrace [] in
                          begin
                          match tokenlist_expr.head with
                          | Lexer.RightBrace -&gt; (next tokenlist_expr, Ast.Parentheses(expr))
                          | _-&gt; let err_msg = __LOC__ ^ "Syntax Error right brace expected but received" ^ show_token_list tokenlist in
                                raise (Syntax_error err_msg)
                          end
     | _-&gt; let err_msg = __LOC__ ^ "Syntax Error left brace expected but received" ^ show_token_list tokenlist in
                      raise (Syntax_error err_msg)
      end
  </code></pre>
  
  <p>However, I'm getting the error:</p>
  
  <pre><code>Error: This expression has type 'a -&gt; token_list * Ast.stmtlist
         but an expression was expected of type 'b * 'c
  </code></pre>
  
  <p>for the line <code>let (tokenlist_stmt_list, stmt_list) = tokenlist_stmt new_lst |&gt; parseStmtList in</code> in <code>parseStmtList</code></p>