package containers

  1. Overview
  2. Docs
package containers
Legend:
Library
Module
Module type
Parameter
Class
Class type

Very Simple Parser Combinators

status still a bit unstable, the type 'at might still change.

Examples:

parse recursive structures
open Containers_string.Parse;;

type tree = L of int | N of tree * tree;;

let mk_leaf x = L x
let mk_node x y = N(x,y)

let ptree = fix @@ fun self ->
  skip_space *>
  ( (char '(' *> (pure mk_node <*> self <*> self) <* char ')')
    <|>
    (U.int >|= mk_leaf) )
;;

parse_string_exn "(1 (2 3))" ptree;;
parse_string_exn "((1 2) (3 (4 5)))" ptree;;
Parse a list of words
open Containers_string.Parse;;
let p = U.list ~sep:"," U.word;;
parse_string_exn "[abc , de, hello ,world  ]" p;;
Stress Test

This makes a list of 100_000 integers, prints it and parses it back.

let p = CCParse.(U.list ~sep:"," U.int);;

let l = CCList.(1 -- 100_000);;
let l_printed =
  CCFormat.to_string (CCList.print ~sep:"," ~start:"[" ~stop:"]" CCInt.print) l;;

let l' = CCParse.parse_string_exn ~p l_printed;;

assert (l=l');;
  • since 0.11
type 'a or_error = [
  1. | `Ok of 'a
  2. | `Error of string
]
type line_num = int
  • since 0.13
type col_num = int
  • since 0.13
  • since 0.13
exception ParseError of line_num * col_num * unit -> string

position * message

This type changed at 0.13

Input

module MemoTbl : sig ... end
type input = {
  1. is_done : unit -> bool;
    (*

    End of input?

    *)
  2. cur : unit -> char;
    (*

    Current char

    *)
  3. next : unit -> char;
    (*

    Returns current char; if not is_done, move to next char, otherwise throw ParseError

    *)
  4. pos : unit -> int;
    (*

    Current pos

    *)
  5. lnum : unit -> line_num;
    (*

    Line number

    • since 0.13
    *)
  6. cnum : unit -> col_num;
    (*

    Column number

    • since 0.13
    *)
  7. memo : MemoTbl.t;
    (*

    Memoization table, if any

    *)
  8. backtrack : int -> unit;
    (*

    Restore to previous pos

    *)
  9. sub : int -> int -> string;
    (*

    sub pos len extracts slice from pos with len

    *)
}

The type of input, which must allow for backtracking somehow. This type is unstable and its details might change.

val input_of_string : string -> input

Parse the string

val input_of_chan : ?size:int -> in_channel -> input

input_of_chan ic reads lazily the content of ic as parsing goes. All content that is read is saved to an internal buffer for backtracking.

  • parameter size

    number of bytes read at once from ic

  • since 0.13

Combinators

type 'a t = input -> ok:('a -> unit) -> err:(exn -> unit) -> unit

Takes the input and two continuations:

  • ok to call with the result when it's done
  • err to call when the parser met an error

The type definition changed since 0.14 to avoid stack overflows

val return : 'a -> 'a t

Always succeeds, without consuming its input

val pure : 'a -> 'a t

Synonym to return

val (>|=) : 'a t -> ('a -> 'b) -> 'b t

Map

val (>>=) : 'a t -> ('a -> 'b t) -> 'b t

Monadic bind

val (<*>) : ('a -> 'b) t -> 'a t -> 'b t

Applicative

val (<*) : 'a t -> _ t -> 'a t

a <* b parses a into x, parses b and ignores its result, and returns x

val (*>) : _ t -> 'a t -> 'a t

a *> b parses a, then parses b into x, and returns x. The results of a is ignored.

val fail : string -> 'a t

fail msg fails with the given message. It can trigger a backtrack

val eoi : unit t

Expect the end of input, fails otherwise

val nop : unit t

Succeed with ()

val char : char -> char t

char c parses the char c and nothing else

val char_if : (char -> bool) -> char t

char_if f parses a character c if f c = true

val chars_if : (char -> bool) -> string t

chars_if f parses a string of chars that satisfy f

val chars1_if : (char -> bool) -> string t

Same as chars_if, but only non-empty strings

val endline : char t

Parses '\n'

val space : char t

Tab or space

val white : char t

Tab or space or newline

val skip_chars : (char -> bool) -> unit t

Skip 0 or more chars satisfying the predicate

val skip_space : unit t

Skip ' ' and '\t'

val skip_white : unit t

Skip ' ' and '\t' and '\n'

val is_alpha : char -> bool

Is the char a letter?

val is_num : char -> bool

Is the char a digit?

val is_alpha_num : char -> bool
val is_space : char -> bool

True on ' ' and '\t'

val is_white : char -> bool

True on ' ' and '\t' and '\n'

  • since 0.13
val (~~~) : (char -> bool) -> char -> bool

Negation on predicates

val (|||) : (char -> bool) -> (char -> bool) -> char -> bool

Disjunction on predicates

val (&&&) : (char -> bool) -> (char -> bool) -> char -> bool

Conjunction on predicates

val (<|>) : 'a t -> 'a t -> 'a t

a <|> b tries to parse a, and if a fails, backtracks and tries to parse b. Therefore, it succeeds if either succeeds

val string : string -> string t

string s parses exactly the string s, and nothing else

val many : 'a t -> 'a list t

many p parses a list of p, eagerly (as long as possible)

val many1 : 'a t -> 'a list t

parses a non empty list

val skip : _ t -> unit t

skip p parses p and ignores its result

val sep : by:_ t -> 'a t -> 'a list t

sep ~by p parses a list of p separated by by

val sep1 : by:_ t -> 'a t -> 'a list t

sep1 ~by p parses a non empty list of p, separated by by

val fix : ('a t -> 'a t) -> 'a t

Fixpoint combinator

val memo : 'a t -> 'a t

Memoize the parser. memo p will behave like p, but when called in a state (read: position in input) it has already processed, memo p returns a result directly. The implementation uses an underlying hashtable. This can be costly in memory, but improve the run time a lot if there is a lot of backtracking involving p.

This function is not thread-safe.

  • since 0.13
val fix_memo : ('a t -> 'a t) -> 'a t

Same as fix, but the fixpoint is memoized.

  • since 0.13

Parse

Those functions have a label ~p on the parser, since 0.14.

val parse : input:input -> p:'a t -> 'a or_error

parse ~input p applies p on the input, and returns `Ok x if p succeeds with x, or `Error s otherwise

val parse_exn : input:input -> p:'a t -> 'a
val parse_string : string -> p:'a t -> 'a or_error

Specialization of parse for string inputs

val parse_string_exn : string -> p:'a t -> 'a
val parse_file : ?size:int -> file:string -> p:'a t -> 'a or_error

parse_file ~file p parses file with p by opening the file and using input_of_chan.

  • parameter size

    size of chunks read from file

  • since 0.13
val parse_file_exn : ?size:int -> file:string -> p:'a t -> 'a

Unsafe version of parse_file

  • since 0.13

Utils

module U : sig ... end
OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct