package reparse

  1. Overview
  2. Docs

Reparse

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

Modules

Reparse

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
open Reparse

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

let skip_spaces = skip (ignore_m space)

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

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

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

let term : expr t -> expr t =
 fun factor ->
  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 t =
  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
      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 = 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 (parse_string expr "12+1*10") in
  Int.equal 22 v
;;

More Examples?