Reparse

Reparse is a monadic, recursive descent based, comprehensive, parser construction library for ocaml.

Modules

Reparse.Parser

Why Use Reparse?

• Develop parsers in ocaml, i.e. one doesn't have to learn yet another parser generator specific DSL and its idiosyncrasies.
• Easily create and re-use third-pary developed reparse parsers. Reparse parsers can be easily composed with other third-pary reparse parsers.
• Interactively develop parsers using tools you may already be familiar, such as utop, ocaml toplevel.
• Test your parsers using ocaml test libraries and tools such as alcotest, ounit2 and the like.

In summary, Reparse allows you to leverage your existing ocaml knowledge and skillset to develop parsers.

Getting Started

opam install reparse

add reparse to dune,

(executable # or library
  (name hello_world)
  (public_name hello_world)
  (libraries reparse))

Hello World Calculator?

A calculator is the hello world of parsers. Here is an implementation in Reparse which supports +,-,* and / operations.

The expression grammar is defined by the following BNF grammar:

<expr>   ::= <term>   "+" <expr> 
           | <term>
<term>   ::= <factor> "*" <term> 
           | <factor>
<factor> ::= "(" <expr> ")" 
           | integer

module P = Reparse.Parser
open P.Infix

type expr =
  | Int  of int
  | Add  of expr * expr
  | Sub  of expr * expr
  | Mult of expr * expr
  | Div  of expr * expr

let skip_spaces = P.skip P.space

let binop : 'a P.t -> char -> 'b P.t -> ('a -> 'b -> 'c) -> 'c P.t =
 fun exp1 op exp2 f ->
  P.map3
    (fun e1 _ e2 -> f e1 e2)
    exp1
    (skip_spaces *> P.char op <* skip_spaces)
    exp2

let integer : expr P.t =
  let+ d = P.digits in
  Int (int_of_string d)

let factor : expr P.t -> expr P.t =
 fun expr ->
  P.any
    [ P.char '(' *> skip_spaces *> expr <* skip_spaces <* P.char ')'
    ; skip_spaces *> integer <* skip_spaces ]

let term : expr P.t -> expr P.t =
 fun factor ->
  P.recur (fun term ->
      let mult = binop factor '*' term (fun e1 e2 -> Mult (e1, e2)) in
      let div = binop factor '/' term (fun e1 e2 -> Div (e1, e2)) in
      mult <|> div <|> factor )

let expr : expr P.t =
  P.recur (fun expr ->
      let factor = factor expr in
      let term = term factor in
      let add = binop term '+' expr (fun e1 e2 -> Add (e1, e2)) in
      let sub = binop term '-' expr (fun e1 e2 -> Sub (e1, e2)) in
      P.any [add; sub; term] )

let rec eval : expr -> int = function
  | Int i         -> i
  | Add (e1, e2)  -> eval e1 + eval e2
  | Sub (e1, e2)  -> eval e1 - eval e2
  | Mult (e1, e2) -> eval e1 * eval e2
  | Div (e1, e2)  -> eval e1 / eval e2

(* Test AST *)
let r =
  let actual = P.parse_string expr "1*2-4+3" in
  let expected = Sub (Mult (Int 1, Int 2), Add (Int 4, Int 3)) in
  Bool.equal (expected = actual) true

(* Run and test the evaluator. *)
let exp_result =
  let v = eval (P.parse_string expr "12+1*10") in
  Int.equal 22 v

More Examples?

• RFC 8259 compliant JSON parser
• HTTP Multipart parser