SML/NJ Library Manual

The REGEXP_ENGINE signature

Synopsis

signature REGEXP_ENGINE
structure BackTrackEngine : REGEXP_ENGINE
structure DfaEngine : REGEXP_ENGINE


This is the signature of a concrete matching engine. It defines an abstract type regexp into which regular expressions are compiled, as well as functions to match the compiled regular expression with various semantics.

Two engines are provided. The structure BackTrackEngine is a backtracking engine that is slow, but requires little memory, incurs low startup overhead and reports full matching information (matching information for all subexpressions of the regular expression). The structure DfaEngine is a finite-automaton implementation, and thus provides fast matching, but is memory-itensive, has a startup overhead (the creation of the automaton), and only reports the root match.

Interface

type regexp
val compile : RegExpSyntax.syntax -> regexp
val find : regexp -> (char,'a) StringCvt.reader -> ({pos : 'a, len : int} option MatchTree.match_tree,'a) StringCvt.reader
val prefix : regexp -> (char,'a) StringCvt.reader -> ({pos : 'a, len : int} option MatchTree.match_tree,'a) StringCvt.reader
val match : (RegExpSyntax.syntax * ({pos : 'a, len : int} option MatchTree.match_tree -> 'b)) list -> (char,'a) StringCvt.reader -> ('b,'a) StringCvt.reader


Description

type regexp

the type of a compiled regular expression.

compile s

compiles a regular expression from the abstract syntax.

find r getc

Given a compiled regular expression r and a character reader getc, this function returns a reader that scans the stream for the first match of the regular expression. The reader returns NONE if no match is found.

prefix r getc

Given a compiled regular expression r and a character reader getc, this functions returns a reader that attempts to match the stream at its current position with the regular expression. The reader returns NONE if there is not match at the current position of the stream.

match l getc

Given a list l of tuples made up of a regular expression (in abstract syntax) and a function from matching tree to values of type 'b, and given a character reader getc, this function returns a reader that attempts to match one of the given regular expressions at the current position of the stream. If a match is found, the corresponding function is applied to the match tree and the result is returned. The reader returns NONE if no match is found.

See Also

MatchTree, RegExpSyntax

Last Modified June 3, 1998
Comments to John Reppy
Copyright © 1998 Bell Labs, Lucent Technologies