The ppMatcher functor


signature PPMATCHER
functor ppMatcher (LABEL) : PPMATCHER

This functor creates from an alphabet a structure containing functions to create, display and use a pattern matcher, allowing search for occurrences of patterns from a regular set of pattern sequences over the alphabet.

Functor result interface

eqtype t
  = DummyPat of t
datatype re = datatype
structure M : PPCFM
val matcher : t re -> s M.machine
val display : t re -> OS.Process.status
val find : t re -> t list -> int list


eqtype t
the type of symbols in patterns.

  = DummyPat of t
the type of symbols in patterns, extended by a dummy symbol.

datatype re = datatype

matcher r
returns a minimal deterministic finite automaton with counter, accepting sequences which end in a pattern sequence of the regular set defined by r.

display r
displays the pattern matcher, i.e. the finite automaton used to search for patterns of the pattern set defined by r. Writes files and

find r l
returns the list of end positions of all occurrences of patterns from the set of pattern sequences defined by r in the input sequence s.

See Also

LABEL, RegExp, ppCFm


We need the extension by a dummy symbol since otherwise the automaton created from the regular expression would have exactly the symbols in the regular expressions as alphabet. Symbols in an input sequence that do not occur in the regular expression are treated as the dummy symbol by the automaton.

structure Match = ppMatcher(StringLabels) ;
open Match;

val patM = (Times [Atom "a",Star(Atom "a")]);
display patM;

find patM ["a","b","a","a","cd","a"]
- datatype alphabet = a | b;
  structure alphabetLabels =
    struct type label = alphabet
           fun toString a = "a" | toString b = "b"
  structure Match = ppMatcher(alphabetLabels); open Match;

- val pat = Plus[Times [Star(Atom a),Atom b],Times[Atom a,Atom a]];
  display pat;

- find pat [a,b,a,a,b,a];
val it = [2,4,5] : int list