OCaml template for menhir/ocamllex/dune indentation-aware parser

dune

(menhir
  (modules parser))
  
(ocamllex lexer)

(executable
  (name ex))

ex.ml

let rec eval = function
  | Exp.Int n -> n
  | Exp.Add ns -> List.map eval ns |> List.fold_left (+) 0

let _ =
  Lexing.from_channel stdin
  |> Parser.f Indenter.f
  |> eval
  |> string_of_int
  |> print_endline

exp.ml

type t = Int of int
       | Add of t * t

indenter.ml

module P = Parser

let convert_space_to_indent width f =
  let indent = ref 0 in
  let make_indent _ = [P.BR; P.INDENT] in
  let make_dedent _ = [P.BR; P.DEDENT] in
  let g h a b = List.init (a - b) h |> List.concat in
  fun lexbuf -> match f lexbuf with
    | P.SPACE n ->
        let m = n / width in
        let k = !indent in
        if m > k then (indent := m; g make_indent m k)
        else if m < k then (indent := m; g make_dedent k m)
        else [P.BR]
    | P.EOF ->
        let k = !indent in
        (indent := 0; g make_dedent k 0 @ [P.EOF])
    | e -> [e]

let flatten f =
  let xs = ref [] in
  fun lexbuf -> match !xs with
    | x::xs' -> xs := xs'; x
    | [] -> (match f lexbuf with
      | x::xs' -> xs := xs'; x
      | [] -> failwith "Lexer did nto return EOF token")

let f = Lexer.f |> convert_space_to_indent 2 |> flatten

lexer.mll

{
open Parser
}

let digit = ['0'-'9']
let num = (digit | ['1'-'9'] digit*)
let indent = '\n' ' '*
let whitespace = [' ' '\t']

rule f = parse
  | indent as s { SPACE (String.length s - 1) }
  | whitespace+ { f lexbuf }
  | num as n { INT (int_of_string n) }
  | "+" { ADD }
  | eof { EOF }

parser.mly

%token <int> INT
%token ADD
%token EOF
%token <int> SPACE
%token INDENT
%token DEDENT
%token BR

%start f <Exp.t>

%%

f : e = expr; EOF { e }

expr :
  | n = INT; BR { Exp.Int n }
  | ADD; BR; INDENT; es = list(expr); DEDENT { Exp.Add es }

sample.add

+
  1
  2
  +
    3
    4
  5

This currently fails to build for me. Adding my notes here in case it helps someone in the future:

1. It has required a dune-project file that includes a stanza like (using menhir 2.1).

2. Second, the parser.mly file fails with:

   File "parser.mly", line 9, characters 9-16:
   Error: syntax error after 'f' and before '<Exp.t>'.
   Ill-formed '%start' declaration.
   A start symbol must begin with a lowercase letter.
   Examples of well-formed declarations:
     %start program
     %start expression phrase
     %start <int> date time
   

   This can be fixed by replacing the start line in the .mly file with: %start <Exp.t> f

3. Value constructor Exp.Add is incompatible by with its use in the .mly file:

   x  dune build
   File "parser.mly", line 17, characters 45-59:
   Error: The constructor Exp.Add expects 2 argument(s),
          but is applied here to 1 argument(s)
   

   This can be fixed by defining the type in exp.ml as:

   type t = Int of int
          | Add of t list
   

There are a number of helpful examples from the menhir project, showing how to use dune. Here's a simple one: https://gitlab.inria.fr/fpottier/menhir/-/tree/master/demos/calc-ast