The ppMatcher functor

Synopsis

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
datatype
  s
  = Dummy| Pat of t
datatype re = datatype RegExp.re
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


Description

eqtype t


the type of symbols in patterns.

datatype
  s
  = Dummy| Pat of t


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

datatype re = datatype RegExp.re


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 matcher.tmp.dot and matcher.tmp.ps.

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

Discussion

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.

Example:

structure Match = ppMatcher(StringLabels) ;
open Match;

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

find patM ["a","b","a","a","cd","a"]

Example:

- datatype alphabet = a | b;
  structure alphabetLabels =
    struct type label = alphabet
           fun toString a = "a" | toString b = "b"
    end;
  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