Opal is a minimum collection of useful parsers and combinators (~150 loc of OCaml) that makes writing parsers easier. It is designed to be small, self-contained, pure-functional, and only includes most essential parsers, so that one could include single file in the project or just embed it in other OCaml source code files.
I find myself writing lots of recursive-descent parsers from scratch in OCaml when I was solving Hackerrank FP challenges. That's why I wrote opal: to include it in the source code and build parsers on top of parser combinators easily.
Trivial arithmetic calculator:
open Opal
let parens = between (exactly '(') (exactly ')')
let integer = many1 digit => implode % int_of_string
let add = exactly '+' >> return ( + )
let sub = exactly '-' >> return ( - )
let mul = exactly '*' >> return ( * )
let div = exactly '/' >> return ( / )
let rec expr input = chainl1 term (add <|> sub) input
and term input = chainl1 factor (mul <|> div) input
and factor input = (parens expr <|> integer) input
let () =
let input = LazyStream.of_channel stdin in
match parse expr input with
| Some ans -> Printf.printf "%d\n" ans
| None -> print_endline "ERROR!"For non-trivial examples, see Hackerrank challenge solutions using opal in
examples/.
The expressiveness of parser combinators are attributed to higher-order
functions and the extensive use of currying. However, due to lack of do
syntax, the bind operation of monad would not be as succinct as that in Haskell.
A parser monad is either None (indicates failure), or Some pair of result
and unconsumed input, where the result is a user-defined value. The input is a
lazy stream of arbitrary token type. A parser is a function that accepts an
input and returns a parser monad. Although most parsers in opal is polymorphic
over token type and result type, some useful parsers only accepts char as
input token type.
Since combinators in opal are roughly based on Haskell's Parsec. The following documentation is somehow a rip-off of Parsec's doc.
type 'a LazyStream t
Polymorphic lazy stream type.
val LazyStream.of_stream : 'a Stream.t -> 'a LazyStream.t
Build a lazy stream from stream.
val LazyStream.of_function : (unit -> 'a) -> 'a LazyStream.t
Build a lazy stream from a function f. The elements in the stream is populated
by calling f ().
val LazyStream.of_string : string -> char LazyStream.t
Build a char lazy stream from string.
val LazyStream.of_channel : in_channel -> char LazyStream.t
Build a char lazy stream from a input channel.
val implode : char list -> bytes
Implode character list into a string. Useful when used with many.
val explode : bytes -> char list
Explode a string into a character list.
val ( % ) : ('a -> 'b) -> ('b -> 'c) -> 'a -> 'c
Infix operator for left-to-right function composition. (f % g % h) x is
equivalent to h (g (f x)).
val parse : ('token, 'result) parser -> 'token LazyStream -> 'result option
parse parser input parses input with parser, and returns Some result if
succeed, or None on failure.
type 'token input = 'token LazyStream.t
type ('token, 'result) monad = ('result * 'token input) option
type ('token, 'result) parser = 'token input -> ('token, 'result) monad
A parser is a function that accepts an input and returns either None on
failure, or Some (result, input'), where result is user-defined value and
input' is unconsumed input after parsing.
val return : 'result -> 'token input -> ('token, 'result) monad
Accepts a value and an input, and returns a monad.
val ( >>= ) : ('t, 'r) parser -> ('r -> ('t, 'r) monad) -> ('t, 'r) parser
x >>= f returns a new parser that if parser x succeeds, applies function f
on monad produced by x, and produces a new monad (a.k.a. bind).
val ( let* ) : ('t, 'r) parser -> ('r -> ('t, 'r) monad) -> ('t, 'r) parser
This operator is the same as >>= but using the let notation.
It is usefull to avoid ugly sequences of bindings. For exemple, p >>= fun x -> f x can
be rewritten let* x = p in f x. Combined with the return function, we can define complex parsers :
let tuple_parser =
let* x = digit in
let* _ = exactly ',' in
let* y = digit in
return (x, y)val ( <|> ) : ('t, 'r) parser -> ('t, 'r) parser -> ('t, 'r) parser
Choice combinator. The parser p <|> q first applies p. If it succeeds, the
value of p is returned. If p fails, parser q is tried.
val mzero : 'a -> ('t, 'r) monad
A parser that always fails.
val any : ('t, 'r) parser
The parser succeeds for any token in the input. Consumes a token and returns it.
val satisfy : ('t -> bool) -> ('t, 'r) parser
The parser satisfy test succeeds for any token for which the supplied function
test returns true. Returns the token that is actually parsed.
val eof : 'a -> ('t, 'a) parser
The parser eof x succeeds if the input is exhausted. Returns value x.
val ( => ) : ('t, 'r) parser -> ('r -> 'a) -> ('t, 'a) parser
Map combinator. x => f parses x. If it succeeds, returns the value of x
applied with f.
val ( >> ) : ('t, 'a) parser -> ('t, 'b) parser -> ('t, 'b) parser
Ignore-left combinator. x >> y parses x and then y. Returns the value
returned by y.
val ( << ) : ('t, 'a) parser -> ('t, 'b) parser -> ('t, 'a) parser
Ignore-right combinator. x >> y parses x and then y. Returns the value
returned by x.
val ( <~> ) : ('t, 'r) parser -> ('t, 'r list) parser -> 't input -> ('t, 'r list) monad
Cons combinator. x <~> y parses x and then y. Returns the value of x
prepended to the value of y (a list).
let ident = letter <~> many alpha_numval choice : ('t, 'r) parser list -> ('t, 'r) parser
choice ps tries to apply the parsers in the list ps in order, until one of
them succeeds. Returns the value of the succeeding parser.
val count : int -> ('t, 'r) parser -> 't input -> ('t, 'r list) monad
count n parses n occurrences of p. If n is smaller or equal to zero, the
parser equals to return []. Returns a list of n values returned by p.
between : ('t, 'a) parser -> ('t, 'b) parser -> ('t, 'r) parser -> ('t, 'r) parser
between open close p parses open, followed by p and close. Returns the
value returned by p.
let braces = between (exactly '{') (exactly '}')val option : 'r -> ('t, 'r) parser -> ('t, 'r) parser
option default p tries to apply parser p. If p fails, it returns the
value default, otherwise the value returned by p.
let priority = option 0 (digit => String.make 1 % int_of_string)val optional : 'r -> ('t, 'r) parser -> ('t, unit) parser
optional p tries to apply parser p. It will parse p or nothing. It only
fails if p fails. Discard the result of p.
val skip_many : ('t, 'r) parser -> ('t, unit) parser
skip_many p applies p zero or more times, skipping its result.
let spaces = skip_many spaceval skip_many1 : ('t, 'r) parser -> ('t, unit) parser
skip_many1 p applies p one or more times, skipping its result.
val many : ('t, 'r) parser -> 't input -> ('t, 'r list) monad
many p applies the parser p zero or more times. Returns a list of returned
values of p.
val many1 : ('t, 'r) parser -> 't input -> ('t, 'r list) monad
many1 p applies the parser p one or more times. Returns a list of returned
values of p.
val sep_by : ('t, 'r) parser -> ('t, 'a) parser -> 't input -> ('t, 'r list) monad
sep_by p sep parses zero or more occurrences of p, separated by sep.
Returns a list of values returned by p.
let comma_sep p = sep_by p (token ",")val sep_by1 : ('t, 'r) parser -> ('t, 'a) parser -> 't input -> ('t, 'r list) monad
sep_by1 p sep parses one or more occurrences of p, separated by sep.
Returns a list of values returned by p.
val end_by: ('t, 'r) parser -> ('t, 'a) parser -> ('t, 'r) parser
end_by p sep parses zero or more ocurrences of p, separated and ended by
sep. Returns a list of values returned by p.
let statements = end_by statement (token ";")val end_by1: ('t, 'r) parser -> ('t, 'a) parser -> ('t, 'r) parser
end_by1 p sep parses one or more ocurrences of p, separated and ended by
sep. Returns a list of values returned by p.
val chainl : ('t, 'r) parser -> ('t, 'r -> 'r -> 'r) parser -> 'r -> ('t, 'r) parser
chainl p op default parses zero or more occurrences of p, separated by
op. Returns a value obtained by a left associative application of all
functions by op to the values returned by p. If there are zero occurences
of p, the value default is returned.
val chainl1 : ('t, 'r) parser -> ('t, 'r -> 'r -> 'r) parser -> ('t, 'r) parser
chainl1 p op parses one or more occurrences of p, separate by op.
Returns a value obtained by a left associative application of all functions
returned by op to the values returned by p. This parser can be used to
eliminate left recursion which typically occurs in expression grammars. See
the arithmetic caculator example above.
val chainr : ('t, 'r) parser -> ('t, 'r -> 'r -> 'r) parser -> 'r -> ('t, 'r) parser
chainr p op default parses zero or more occurrences of p, separated by
op. Returns a value obtained by right associative application of all
functions returned by op to the values returned by p. If there are no
occurrences of p, the value x is returned.
val chainr1 : ('t, 'r) parser -> ('t, 'r -> 'r -> 'r) parser -> ('t, 'r) parser
chainr p op parses one or more occurrences of p, separated by op.
Returns a value obtained by right associative application of all functions
returned by op to the values returned by p.
val exactly : 'r -> ('t, 'r) parser
exactly x parses a single token x. Returns the parsed token (i.e. x).
let semi_colon = exactly ';'val one_of : 'r list -> ('t, 'r) parser
one_of xs succeeds if the current token is in the supplied list of tokens
xs. Returns the parsed token.
let vowel = one_of ['a'; 'e'; 'i'; 'o'; 'u']val none_of : 'r list -> ('t, 'r) parser
As the dual of one_of, none_of xs succeeds if the current token not in
the supplied list of tokens xs. Returns the parsed token.
let consonant = none_of ['a'; 'e'; 'i'; 'o'; 'u']val range : 'r -> 'r -> ('t, 'r) parser
range low high succeeds if the current token is in the range between low
and high (inclusive). Returns the parsed token.
val space = (char, char) parser
Parses a white space character ('\s\t\r\n'). Returns the parsed character.
val spaces = (char, unit) parser
Skip zero or more white spaces characters.
val newline = (char, char) parser
Parses a newline character ('\n'). Returns a newline character.
val tab = (char, char) parser
Parses a tab character ('\t'). Returns a tab character.
val upper = (char, char) parser
Parses an upper case letter (a character between 'A' and 'Z'). Returns the parsed character.
val lower = (char, char) parser
Parses a lower case letter (a character between 'a' and 'z'). Returns the parsed character.
val digit : (char, char) parser
Parses a digit. Returns the parsed character.
val letter = (char, char) parser
Parses a letter (an upper case or lower case letter). Returns the parsed character.
val alpha_num = (char, char) parser
Parses a letter or digit. Returns the parser character.
val hex_digit = (char, char) parser
Parses a hexadecimal digit (a digit or a letter between 'a' and 'f' or 'A' and 'F'). Returns the parsed character.
val oct_digit = (char, char) parser
Parses an octal digit (a character between '0' and '7'). Returns the parsed character.
val lexeme : (char, 'r) parser -> (char, 'r) parser
lexeme p first applies skip_many space and then parser p. Returns the
value returned by p.
val token : string -> char input -> (char, char list) monad
token s skips leading white spaces and parses a sequence of characters given
by string s. Returns the parsed character sequence as a list.
div_or_mod = token "div" <|> token "mod"