# 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

[ Top | Parent | Contents | Index | Root ]

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