helm/DEVEL/pxp/pxp/pxp_dfa.mli

   1 (* $Id$
   2  * ----------------------------------------------------------------------
   3  *
   4  *)
   5
   6 module Graph : sig
   7   type graph
   8   type vertex
   9
  10   (* A directed graph whose edges are marked with strings (= element types)
  11    * and with the constraint that for a given vertex and a given element
  12    * type the edge must be unique.
  13    *)
  14
  15   exception Edge_not_unique
  16
  17   val create : unit -> graph
  18       (* Creates an empty graph *)
  19
  20   val new_vertex : graph -> vertex
  21       (* Adds a new vertex to the graph, and returns the vertex *)
  22
  23   val new_edge : vertex -> string -> vertex -> unit
  24       (* new_edge v_from etype v_to:
  25        * Adds a new edge from vertex v_from to vertex v_to, marked with
  26        * etype.
  27        * Raises Edge_not_unique if there is already an edge etype starting
  28        * at v_from to a different vertex than v_to.
  29        *)
  30
  31   val graph_of_vertex : vertex -> graph
  32       (* Returns the graph the passed vertex is contained in. *)
  33
  34   val union : graph -> graph -> unit
  35       (* union g1 g2:
  36        * Moves the vertexes and edged found in g2 to g1.
  37        * After that, g2 is empty again.
  38        *)
  39
  40   val outgoing_edges : vertex -> (string * vertex) list
  41       (* Returns the list of outgoing edges starting in the passed vertex *)
  42
  43   val follow_edge : vertex -> string -> vertex
  44       (* Follows the edge starting in the passed vertex which is marked
  45        * with the passed element type.
  46        * Raises Not_found if there is no such edge.
  47        *)
  48
  49   val ingoing_edges : vertex -> (vertex * string) list
  50       (* Returns the list of ingoing edges ending in the passed vertex *)
  51 end
  52
  53 module VertexSet : Set.S with type elt = Graph.vertex
  54
  55
  56 type dfa_definition =
  57     { dfa_graph : Graph.graph;
  58       dfa_start : Graph.vertex;   (* Where the automaton starts *)
  59       dfa_stops : VertexSet.t;    (* Where the automaton may stop *)
  60       dfa_null  : bool;           (* Whether dfa_start member of dfa_stops *)
  61     }
  62
  63 val dfa_of_regexp_content_model : Pxp_types.regexp_spec -> dfa_definition
  64   (* Computes the DFA or raises Not_found if it does not exist *)
  65
  66 (* ======================================================================
  67  * History:
  68  *
  69  * $Log$
  70  * Revision 1.1  2000/11/17 09:57:29  lpadovan
  71  * Initial revision
  72  *
  73  * Revision 1.1  2000/07/23 02:16:08  gerd
  74  *      Initial revision.
  75  *
  76  *
  77  *)