Lightweight Regular Expressions

From: Christian Lindig (lindig@is.gaertner.de)
Date: Sun Sep 19 1999 - 22:03:40 MET DST


Date: Sun, 19 Sep 1999 22:03:40 +0200
From: Christian Lindig <lindig@is.gaertner.de>
To: Caml Mailing List <caml-list@inria.fr>
Subject: Lightweight Regular Expressions

OCamls regular expression module Str is expressive and fast but
requires custom linking. An algorithm by Mark Hopkins (once posted to
comp.compilers) permits to implement regular expression matching in
about 100 lines of code; the OCaml module is appended below in the
hope that is useful. Someone mentioned this algorithm in
comp.text.xml for checking XML DTDs and provided a Haskell source.
The module below is mostly a port to OCaml.

    + no precompiling of regexp's - they are interpreted directly
    + small OCaml module, no custom linking, no C runtime
    + can match any sequence of symbols, not just characters
    
    - only regexp matching, no subexpression matching, no substitution
    - not as efficient as an automaton based approach

-- Christian

-- 
 Christian Lindig       Gaertner Datensysteme GbR, Braunschweig,  Germany 
                        http://www.gaertner.de/~lindig lindig@gaertner.de

(* $Id: rx.ml,v 1.1 1999/08/29 09:03:01 lindig Exp $

This module provides regular expression matching. Regular expressions don't need to be compiled before they can be matched against some input. Instead the automaton is build while the input is consumed. The drawback of this method is that no subexpression matching is possible to extract matching substrings.

This algorithm used here is by Mark Hopkins who posted it once to comp.compiles. Search the comp.compilers archive for a detailed article and an implementation in C. 1999 Christian Lindig <lindig@gaertner.de> *)

type 'a rx = | RXzero (* {} *) | RXunit (* "" *) | RXsym of 'a (* 'x' *) | RXmany of ('a rx) (* e* *) | RXsome of ('a rx) (* e+ *) | RXopt of ('a rx) (* e? *) | RXseq of ('a rx) * ('a rx) (* e1 e2 *) | RXalt of ('a rx) * ('a rx) (* e1 | e2 *)

let zero = RXzero let unit = RXunit let sym x = RXsym x let many = function | RXunit -> RXunit | RXzero -> RXunit | x -> RXmany x let some = function | RXunit -> RXunit | RXzero -> RXzero | x -> RXsome x let opt = function | RXunit -> RXunit | RXzero -> RXunit | x -> RXopt x let seq x y = match (x,y) with | RXzero, x -> RXzero | RXunit, x -> x | x , RXzero-> RXzero | x , RXunit-> x | x , y -> RXseq(x,y) let alt x y = match (x,y) with | RXzero, x -> x | x , RXzero-> x | x , y -> RXalt(x,y)

(* two convenience infix operators *)

let ( ||| ) = alt let ( *** ) = seq

(* [nullable e] is true, iff the empty sequence (RXzero) is recognized by [e]. *)

let rec nullable = function | RXzero -> false | RXunit -> true | RXsym x -> false | RXmany e -> true | RXsome e -> nullable e | RXopt e -> true | RXseq(e1,e2) -> nullable e1 && nullable e2 | RXalt(e1,e2) -> nullable e1 || nullable e2

(* [residual e x] returns a regular expression e' that recognizes the language L(e') = { w | xw \in L(e)}. *)

let rec residual e' x = match e' with | RXzero -> RXzero | RXunit -> RXzero | RXsym x' -> if x' = x then RXunit else RXzero | RXmany e -> seq (residual e x) (many e) | RXsome e -> seq (residual e x) (many e) | RXopt e -> residual e x | RXseq(e1,e2) -> if nullable e1 then alt (seq (residual e1 x) e2) (residual e2 x) else seq (residual e1 x) e2 | RXalt(e1,e2) -> alt (residual e1 x) (residual e2 x) (* [matches e syms] is true, iff the word [syms] is an element of L(e), i.e. [e] matches the symbols [syms]. *)

let matches e syms = nullable (List.fold_left residual e syms)

(* [matchstr e str] is true, iff string [str] is matched by regular expression [e] *) let matchstr e str = let len = String.length str in let rec loop e i = if i = len then nullable e else loop (residual e (String.get str i)) (i+1) in loop e 0

(* examples *)

let e1 = many (sym 'a') *** some (sym 'b') let e2 = sym 'a' *** opt (sym 'b') *** some (sym 'a')



This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:25 MET