home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / gnurx.zip / rx / rxnfa.h < prev    next >
C/C++ Source or Header  |  1995-12-31  |  7KB  |  232 lines
  1. /* classes: h_files */
  2.  
  3. #ifndef RXNFAH
  4. #define RXNFAH
  5. /***********************************************************
  6.  
  7. Copyright 1995 by Tom Lord
  8.  
  9.                         All Rights Reserved
  10.  
  11. Permission to use, copy, modify, and distribute this software and its 
  12. documentation for any purpose and without fee is hereby granted, 
  13. provided that the above copyright notice appear in all copies and that
  14. both that copyright notice and this permission notice appear in 
  15. supporting documentation, and that the name of the copyright holder not be
  16. used in advertising or publicity pertaining to distribution of the
  17. software without specific, written prior permission.  
  18.  
  19. Tom Lord DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  20. INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  21. EVENT SHALL TOM LORD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  22. CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
  23. USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
  24. OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  25. PERFORMANCE OF THIS SOFTWARE.
  26.  
  27. ******************************************************************/
  28.  
  29.  
  30.  
  31. /*
  32.  * Tom Lord (lord@cygnus.com, lord@gnu.ai.mit.edu)
  33.  */
  34.  
  35. #include "_rx.h"
  36. #include "rxnode.h"
  37.  
  38.  
  39. /* NFA
  40.  *
  41.  * A syntax tree is compiled into an NFA.  This page defines the structure
  42.  * of that NFA.
  43.  */
  44.  
  45. struct rx_nfa_state
  46. {
  47.   /* These are kept in a list as the NFA is being built. 
  48.    * Here is the link.
  49.    */
  50.   struct rx_nfa_state *next;
  51.  
  52.   /* After the NFA is built, states are given integer id's.
  53.    * States whose outgoing transitions are all either epsilon or 
  54.    * side effect edges are given ids less than 0.  Other states
  55.    * are given successive non-negative ids starting from 0.
  56.    *
  57.    * Here is the id for this state:
  58.    */
  59.   int id;
  60.  
  61.   /* The list of NFA edges that go from this state to some other. */
  62.   struct rx_nfa_edge *edges;
  63.  
  64.   /* If you land in this state, then you implicitly land
  65.    * in all other states reachable by only epsilon translations.
  66.    * Call the set of maximal loop-less paths to such states the 
  67.    * epsilon closure of this state.
  68.    *
  69.    * There may be other states that are reachable by a mixture of
  70.    * epsilon and side effect edges.  Consider the set of maximal loop-less
  71.    * paths of that sort from this state.  Call it the epsilon-side-effect
  72.    * closure of the state.
  73.    * 
  74.    * The epsilon closure of the state is a subset of the epsilon-side-
  75.    * effect closure.  It consists of all the paths that contain 
  76.    * no side effects -- only epsilon edges.
  77.    * 
  78.    * The paths in the epsilon-side-effect closure  can be partitioned
  79.    * into equivalance sets. Two paths are equivalant if they have the
  80.    * same set of side effects, in the same order.  The epsilon-closure
  81.    * is one of these equivalance sets.  Let's call these equivalance
  82.    * sets: observably equivalant path sets.  That name is chosen
  83.    * because equivalance of two paths means they cause the same side
  84.    * effects -- so they lead to the same subsequent observations other
  85.    * than that they may wind up in different target states.
  86.    *
  87.    * The superstate nfa, which is derived from this nfa, is based on
  88.    * the observation that all of the paths in an observably equivalant
  89.    * path set can be explored at the same time, provided that the
  90.    * matcher keeps track not of a single nfa state, but of a set of
  91.    * states.   In particular, after following all the paths in an
  92.    * observably equivalant set, you wind up at a set of target states.
  93.    * That set of target states corresponds to one state in the
  94.    * superstate NFA.
  95.    *
  96.    * Staticly, before matching begins, it is convenient to analyze the
  97.    * nfa.  Each state is labeled with a list of the observably
  98.    * equivalant path sets who's union covers all the
  99.    * epsilon-side-effect paths beginning in this state.  This list is
  100.    * called the possible futures of the state.
  101.    *
  102.    * A trivial example is this NFA:
  103.    *             s1
  104.    *         A  --->  B
  105.    *
  106.    *             s2  
  107.    *            --->  C
  108.    *
  109.    *             epsilon           s1
  110.    *            --------->  D   ------> E
  111.    * 
  112.    * 
  113.    * In this example, A has two possible futures.
  114.    * One invokes the side effect `s1' and contains two paths,
  115.    * one ending in state B, the other in state E.
  116.    * The other invokes the side effect `s2' and contains only
  117.    * one path, landing in state C.
  118.    *
  119.    * Here is a list of the possible futures of this state:
  120.    */
  121.   struct rx_possible_future *futures;
  122.   int futures_computed:1;
  123.  
  124.  
  125.   /* There are exactly two distinguished states in every NFA: */
  126.   unsigned int is_final:1;
  127.   unsigned int is_start:1;
  128.  
  129.   /* These are used internally during NFA construction... */
  130.   unsigned int eclosure_needed:1;
  131.   unsigned int mark:1;
  132. };
  133.  
  134.  
  135. /* An edge in an NFA is typed: 
  136.  */
  137. enum rx_nfa_etype
  138. {
  139.   /* A cset edge is labled with a set of characters one of which
  140.    * must be matched for the edge to be taken.
  141.    */
  142.   ne_cset,
  143.  
  144.   /* An epsilon edge is taken whenever its starting state is
  145.    * reached. 
  146.    */
  147.   ne_epsilon,
  148.  
  149.   /* A side effect edge is taken whenever its starting state is
  150.    * reached.  Side effects may cause the match to fail or the
  151.    * position of the matcher to advance.
  152.    */
  153.   ne_side_effect
  154. };
  155.  
  156. struct rx_nfa_edge
  157. {
  158.   struct rx_nfa_edge *next;
  159.   enum rx_nfa_etype type;
  160.   struct rx_nfa_state *dest;
  161.   union
  162.   {
  163.     rx_Bitset cset;
  164.     void * side_effect;
  165.   } params;
  166. };
  167.  
  168.  
  169.  
  170. /* A possible future consists of a list of side effects
  171.  * and a set of destination states.  Below are their
  172.  * representations.  These structures are hash-consed so
  173.  * that lists with the same elements share a representation
  174.  * (their addresses are ==).
  175.  */
  176.  
  177. struct rx_nfa_state_set
  178. {
  179.   struct rx_nfa_state * car;
  180.   struct rx_nfa_state_set * cdr;
  181. };
  182.  
  183. struct rx_se_list
  184. {
  185.   void * car;
  186.   struct rx_se_list * cdr;
  187. };
  188.  
  189. struct rx_possible_future
  190. {
  191.   struct rx_possible_future *next;
  192.   struct rx_se_list * effects;
  193.   struct rx_nfa_state_set * destset;
  194. };
  195.  
  196.  
  197.  
  198.  
  199. #ifdef __STDC__
  200. extern struct rx_nfa_state * rx_nfa_state (struct rx *rx);
  201. extern struct rx_nfa_edge * rx_nfa_edge (struct rx *rx,
  202.                      enum rx_nfa_etype type,
  203.                      struct rx_nfa_state *start,
  204.                      struct rx_nfa_state *dest);
  205. extern int rx_build_nfa (struct rx *rx,
  206.              struct rexp_node *rexp,
  207.              struct rx_nfa_state **start,
  208.              struct rx_nfa_state **end);
  209. extern struct rx_possible_future * rx_state_possible_futures (struct rx * rx, struct rx_nfa_state * n);
  210. extern void rx_free_nfa (struct rx *rx);
  211.  
  212. #else /* STDC */
  213. extern struct rx_nfa_state * rx_nfa_state ();
  214. extern struct rx_nfa_edge * rx_nfa_edge ();
  215. extern int rx_build_nfa ();
  216. extern struct rx_possible_future * rx_state_possible_futures ();
  217. extern void rx_free_nfa ();
  218.  
  219. #endif /* STDC */
  220.  
  221.  
  222.  
  223.  
  224.  
  225.  
  226.  
  227.  
  228.  
  229.  
  230.  
  231. #endif  /* RXNFAH */
  232.