The REGEXP_ENGINE signature

The REGEXP_ENGINE signature …​

Synopsis

signature REGEXP_ENGINE

structure BackTrackEngine : REGEXP_ENGINE
structure DfaEngine : REGEXP_ENGINE
structure ThompsonEngine : REGEXP_ENGINE

Interface

type regexp

type 'a match = {pos : 'a, len : int} MatchTree.match_tree

val compile : RegExpSyntax.syntax -> regexp

val find : regexp -> (char,'a) StringCvt.reader -> ('a match, 'a) StringCvt.reader

val prefix : regexp ->(char,'a) StringCvt.reader -> ('a match, 'a) StringCvt.reader

val match : (RegExpSyntax.syntax * ('a match -> 'b)) list
	      -> (char,'a) StringCvt.reader -> ('b, 'a) StringCvt.reader

Description

type regexp

something (* the type of a compiled regular expression *)

(* a match specifies the position (as a stream) and the length of the match *)
type 'a match = {pos : 'a, len : int} MatchTree.match_tree

something

val compile : RegExpSyntax.syntax -> regexp

something (* compile a regular expression from the abstract syntax *)

val find : regexp -> (char,'a) StringCvt.reader -> ('a match, 'a) StringCvt.reader

something (* scan the stream for the first occurence of the regular expression. The call *

  • find re getc strm *

  • returns NONE if the end of stream is reached without a match. Otherwise it

  • returns SOME(match, strm'), where match is the match-tree for the match and

  • strm' is the stream following the match. *)

val prefix : regexp ->(char,'a) StringCvt.reader -> ('a match, 'a) StringCvt.reader

something (* attempt to match the stream at the current position with the

  • regular expression *)

val match : (RegExpSyntax.syntax * ('a match -> 'b)) list -> (char,'a) StringCvt.reader -> ('b, 'a) StringCvt.reader

something (* attempt to the match the stream at the current position with one of

  • the abstract syntax representations of regular expressions and trigger

  • the corresponding action *)

Instances

structure BackTrackEngine

A backtracking interpreter for the regular-expression syntax. This implementation requires no extra compilation time, but backtracking can result in slow searches for some regular expressions.

structure DfaEngine

This implementation compiles the regular expression to a nondeterministic finite-state machine and then coverts that to a deterministic machine. The resulting machine is fast, but can be exponential in size for some regular expressions.

structure ThompsonEngine

An implementation of Ken Thompson’s famous Regular Expression Search Algorithm.