home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / gnurx.zip / rx / rxnfa.c < prev    next >
C/C++ Source or Header  |  1995-12-31  |  18KB  |  814 lines
  1. /***********************************************************
  2.  
  3. Copyright 1995 by Tom Lord
  4.  
  5.                         All Rights Reserved
  6.  
  7. Permission to use, copy, modify, and distribute this software and its 
  8. documentation for any purpose and without fee is hereby granted, 
  9. provided that the above copyright notice appear in all copies and that
  10. both that copyright notice and this permission notice appear in 
  11. supporting documentation, and that the name of the copyright holder not be
  12. used in advertising or publicity pertaining to distribution of the
  13. software without specific, written prior permission.  
  14.  
  15. Tom Lord DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  16. INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  17. EVENT SHALL TOM LORD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  18. CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
  19. USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
  20. OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  21. PERFORMANCE OF THIS SOFTWARE.
  22.  
  23. ******************************************************************/
  24.  
  25.  
  26. /*
  27.  * Tom Lord (lord@cygnus.com, lord@gnu.ai.mit.edu)
  28.  */
  29.  
  30.  
  31. #include "rxall.h"
  32. #include "rxnfa.h"
  33.  
  34.  
  35. #ifndef realloc
  36. extern char * realloc ();
  37. #endif
  38.  
  39. #ifndef malloc
  40. extern char * malloc ();
  41. #endif
  42.  
  43. #define remalloc(M, S) (M ? realloc (M, S) : malloc (S))
  44.  
  45.  
  46.  
  47. /* {Low Level Data Structure Code}
  48.  */
  49.  
  50. /* Constructs a new nfa node. */
  51. #ifdef __STDC__
  52. struct rx_nfa_state *
  53. rx_nfa_state (struct rx *rx)
  54. #else
  55. struct rx_nfa_state *
  56. rx_nfa_state (rx)
  57.      struct rx *rx;
  58. #endif
  59. {
  60.   struct rx_nfa_state * n = (struct rx_nfa_state *)malloc (sizeof (*n));
  61.   if (!n)
  62.     return 0;
  63.   bzero (n, sizeof (*n));
  64.   n->next = rx->nfa_states;
  65.   rx->nfa_states = n;
  66.   return n;
  67. }
  68.  
  69.  
  70. #ifdef __STDC__
  71. static void
  72. rx_free_nfa_state (struct rx_nfa_state * n)
  73. #else
  74. static void
  75. rx_free_nfa_state (n)
  76.   struct rx_nfa_state * n;
  77. #endif
  78. {
  79.   free ((char *)n);
  80. }
  81.  
  82.  
  83. /* This adds an edge between two nodes, but doesn't initialize the 
  84.  * edge label.
  85.  */
  86.  
  87. #ifdef __STDC__
  88. struct rx_nfa_edge * 
  89. rx_nfa_edge (struct rx *rx,
  90.          enum rx_nfa_etype type,
  91.          struct rx_nfa_state *start,
  92.          struct rx_nfa_state *dest)
  93. #else
  94. struct rx_nfa_edge * 
  95. rx_nfa_edge (rx, type, start, dest)
  96.      struct rx *rx;
  97.      enum rx_nfa_etype type;
  98.      struct rx_nfa_state *start;
  99.      struct rx_nfa_state *dest;
  100. #endif
  101. {
  102.   struct rx_nfa_edge *e;
  103.   e = (struct rx_nfa_edge *)malloc (sizeof (*e));
  104.   if (!e)
  105.     return 0;
  106.   e->next = start->edges;
  107.   start->edges = e;
  108.   e->type = type;
  109.   e->dest = dest;
  110.   return e;
  111. }
  112.  
  113.  
  114. #ifdef __STDC__
  115. static void
  116. rx_free_nfa_edge (struct rx_nfa_edge * e)
  117. #else
  118. static void
  119. rx_free_nfa_edge (e)
  120.      struct rx_nfa_edge * e;
  121. #endif
  122. {
  123.   free ((char *)e);
  124. }
  125.  
  126.  
  127. /* This constructs a POSSIBLE_FUTURE, which is a kind epsilon-closure
  128.  * of an NFA.  These are added to an nfa automaticly by eclose_nfa.
  129.  */  
  130.  
  131. #ifdef __STDC__
  132. static struct rx_possible_future * 
  133. rx_possible_future (struct rx * rx,
  134.          struct rx_se_list * effects)
  135. #else
  136. static struct rx_possible_future * 
  137. rx_possible_future (rx, effects)
  138.      struct rx * rx;
  139.      struct rx_se_list * effects;
  140. #endif
  141. {
  142.   struct rx_possible_future *ec;
  143.   ec = (struct rx_possible_future *) malloc (sizeof (*ec));
  144.   if (!ec)
  145.     return 0;
  146.   ec->destset = 0;
  147.   ec->next = 0;
  148.   ec->effects = effects;
  149.   return ec;
  150. }
  151.  
  152.  
  153. #ifdef __STDC__
  154. static void
  155. rx_free_possible_future (struct rx_possible_future * pf)
  156. #else
  157. static void
  158. rx_free_possible_future (pf)
  159.      struct rx_possible_future * pf;
  160. #endif
  161. {
  162.   free ((char *)pf);
  163. }
  164.  
  165.  
  166. #ifdef __STDC__
  167. static void
  168. rx_free_nfa_graph (struct rx *rx)
  169. #else
  170. static void
  171. rx_free_nfa_graph (rx)
  172.      struct rx *rx;
  173. #endif
  174. {
  175.   while (rx->nfa_states)
  176.     {
  177.       while (rx->nfa_states->edges)
  178.     {
  179.       switch (rx->nfa_states->edges->type)
  180.         {
  181.         case ne_cset:
  182.           rx_free_cset (rx->nfa_states->edges->params.cset);
  183.           break;
  184.         default:
  185.           break;
  186.         }
  187.       {
  188.         struct rx_nfa_edge * e;
  189.         e = rx->nfa_states->edges;
  190.         rx->nfa_states->edges = rx->nfa_states->edges->next;
  191.         rx_free_nfa_edge (e);
  192.       }
  193.     } /* while (rx->nfa_states->edges) */
  194.       {
  195.     /* Iterate over the partial epsilon closures of rx->nfa_states */
  196.     struct rx_possible_future * pf = rx->nfa_states->futures;
  197.     while (pf)
  198.       {
  199.         struct rx_possible_future * pft = pf;
  200.         pf = pf->next;
  201.         rx_free_possible_future (pft);
  202.       }
  203.       }
  204.       {
  205.     struct rx_nfa_state *n;
  206.     n = rx->nfa_states;
  207.     rx->nfa_states = rx->nfa_states->next;
  208.     rx_free_nfa_state (n);
  209.       }
  210.     }
  211. }
  212.  
  213.  
  214.  
  215. /* {Translating a Syntax Tree into an NFA}
  216.  *
  217.  */
  218.  
  219.  
  220. /* This is the Thompson regexp->nfa algorithm. 
  221.  * It is modified to allow for `side-effect epsilons.'  Those are
  222.  * edges that are taken whenever a similarly placed epsilon edge 
  223.  * would be, but which also imply that some side effect occurs 
  224.  * when the edge is taken.
  225.  *
  226.  * Side effects are used to model parts of the pattern langauge 
  227.  * that are not regular.
  228.  */
  229.  
  230. #ifdef __STDC__
  231. int
  232. rx_build_nfa (struct rx *rx,
  233.           struct rexp_node *rexp,
  234.           struct rx_nfa_state **start,
  235.           struct rx_nfa_state **end)
  236. #else
  237. int
  238. rx_build_nfa (rx, rexp, start, end)
  239.      struct rx *rx;
  240.      struct rexp_node *rexp;
  241.      struct rx_nfa_state **start;
  242.      struct rx_nfa_state **end;
  243. #endif
  244. {
  245.   struct rx_nfa_edge *edge;
  246.  
  247.   /* Start & end nodes may have been allocated by the caller. */
  248.   *start = *start ? *start : rx_nfa_state (rx);
  249.  
  250.   if (!*start)
  251.     return 0;
  252.  
  253.   if (!rexp)
  254.     {
  255.       *end = *start;
  256.       return 1;
  257.     }
  258.  
  259.   *end = *end ? *end : rx_nfa_state (rx);
  260.  
  261.   if (!*end)
  262.     {
  263.       rx_free_nfa_state (*start);
  264.       return 0;
  265.     }
  266.  
  267.   switch (rexp->type)
  268.     {
  269.     case r_cset:
  270.       edge = rx_nfa_edge (rx, ne_cset, *start, *end);
  271.       if (!edge)
  272.     return 0;
  273.       edge->params.cset = rx_copy_cset (rx->local_cset_size,
  274.                     rexp->params.cset);
  275.       if (!edge->params.cset)
  276.     {
  277.       rx_free_nfa_edge (edge);
  278.       return 0;
  279.     }
  280.       return 1;
  281.  
  282.     case r_opt:
  283.       return (rx_build_nfa (rx, rexp->params.pair.left, start, end)
  284.           && rx_nfa_edge (rx, ne_epsilon, *start, *end));
  285.  
  286.     case r_plus:
  287.       {
  288.     struct rx_nfa_state * star_start = 0;
  289.     struct rx_nfa_state * star_end = 0;
  290.     struct rx_nfa_state * shared;
  291.  
  292.     shared = 0;
  293.     if (!rx_build_nfa (rx, rexp->params.pair.left, start, &shared))
  294.       return 0;
  295.     return (rx_build_nfa (rx, rexp->params.pair.left,
  296.                   &star_start, &star_end)
  297.         && star_start
  298.         && star_end
  299.         && rx_nfa_edge (rx, ne_epsilon, star_start, star_end)
  300.         && rx_nfa_edge (rx, ne_epsilon, shared, star_start)
  301.         && rx_nfa_edge (rx, ne_epsilon, star_end, *end)
  302.         && rx_nfa_edge (rx, ne_epsilon, star_end, star_start));
  303.       }
  304.     case r_interval:
  305.     case r_star:
  306.       {
  307.     struct rx_nfa_state * star_start = 0;
  308.     struct rx_nfa_state * star_end = 0;
  309.     return (rx_build_nfa (rx, rexp->params.pair.left,
  310.                   &star_start, &star_end)
  311.         && star_start
  312.         && star_end
  313.         && rx_nfa_edge (rx, ne_epsilon, star_start, star_end)
  314.         && rx_nfa_edge (rx, ne_epsilon, *start, star_start)
  315.         && rx_nfa_edge (rx, ne_epsilon, star_end, *end)
  316.  
  317.         && rx_nfa_edge (rx, ne_epsilon, star_end, star_start));
  318.       }
  319.     case r_parens:
  320.       return rx_build_nfa (rx, rexp->params.pair.left, start, end);
  321.  
  322.     case r_concat:
  323.       {
  324.     struct rx_nfa_state *shared = 0;
  325.     return
  326.       (rx_build_nfa (rx, rexp->params.pair.left, start, &shared)
  327.        && rx_build_nfa (rx, rexp->params.pair.right, &shared, end));
  328.       }
  329.  
  330.     case r_alternate:
  331.       {
  332.     struct rx_nfa_state *ls = 0;
  333.     struct rx_nfa_state *le = 0;
  334.     struct rx_nfa_state *rs = 0;
  335.     struct rx_nfa_state *re = 0;
  336.     return (rx_build_nfa (rx, rexp->params.pair.left, &ls, &le)
  337.         && rx_build_nfa (rx, rexp->params.pair.right, &rs, &re)
  338.         && rx_nfa_edge (rx, ne_epsilon, *start, ls)
  339.         && rx_nfa_edge (rx, ne_epsilon, *start, rs)
  340.         && rx_nfa_edge (rx, ne_epsilon, le, *end)
  341.         && rx_nfa_edge (rx, ne_epsilon, re, *end));
  342.       }
  343.  
  344.     case r_context:
  345.       edge = rx_nfa_edge (rx, ne_side_effect, *start, *end);
  346.       if (!edge)
  347.     return 0;
  348.       edge->params.side_effect = (void *)rexp->params.intval;
  349.       return 1;
  350.     }
  351.  
  352.   /* this should never happen */
  353.   return 0;
  354. }
  355.  
  356.  
  357. /* {Low Level Data Structures for the Static NFA->SuperNFA Analysis}
  358.  *
  359.  * There are side effect lists -- lists of side effects occuring
  360.  * along an uninterrupted, acyclic path of side-effect epsilon edges.
  361.  * Such paths are collapsed to single edges in the course of computing
  362.  * epsilon closures.  The resulting single edges are labled with a list 
  363.  * of all the side effects from the original multi-edge path.  Equivalent
  364.  * lists of side effects are made == by the constructors below.
  365.  *
  366.  * There are also nfa state sets.  These are used to hold a list of all
  367.  * states reachable from a starting state for a given type of transition
  368.  * and side effect list.   These are also hash-consed.
  369.  */
  370.  
  371.  
  372.  
  373. /* The next several functions compare, construct, etc. lists of side
  374.  * effects.  See ECLOSE_NFA (below) for details.
  375.  */
  376.  
  377. /* Ordering of rx_se_list
  378.  * (-1, 0, 1 return value convention).
  379.  */
  380.  
  381. #ifdef __STDC__
  382. static int 
  383. se_list_cmp (void * va, void * vb)
  384. #else
  385. static int 
  386. se_list_cmp (va, vb)
  387.      void * va;
  388.      void * vb;
  389. #endif
  390. {
  391.   struct rx_se_list * a = (struct rx_se_list *)va;
  392.   struct rx_se_list * b = (struct rx_se_list *)vb;
  393.  
  394.   return ((va == vb)
  395.       ? 0
  396.       : (!va
  397.          ? -1
  398.          : (!vb
  399.         ? 1
  400.         : ((long)a->car < (long)b->car
  401.            ? 1
  402.            : ((long)a->car > (long)b->car
  403.               ? -1
  404.               : se_list_cmp ((void *)a->cdr, (void *)b->cdr))))));
  405. }
  406.  
  407.  
  408. #ifdef __STDC__
  409. static int 
  410. se_list_equal (void * va, void * vb)
  411. #else
  412. static int 
  413. se_list_equal (va, vb)
  414.      void * va;
  415.      void * vb;
  416. #endif
  417. {
  418.   return !(se_list_cmp (va, vb));
  419. }
  420.  
  421. static struct rx_hash_rules se_list_hash_rules = { se_list_equal, 0, 0, 0, 0 };
  422.  
  423.  
  424. #ifdef __STDC__
  425. static struct rx_se_list * 
  426. side_effect_cons (struct rx * rx,
  427.           void * se, struct rx_se_list * list)
  428. #else
  429. static struct rx_se_list * 
  430. side_effect_cons (rx, se, list)
  431.      struct rx * rx;
  432.      void * se;
  433.      struct rx_se_list * list;
  434. #endif
  435. {
  436.   struct rx_se_list * l;
  437.   l = ((struct rx_se_list *) malloc (sizeof (*l)));
  438.   if (!l)
  439.     return 0;
  440.   l->car = se;
  441.   l->cdr = list;
  442.   return l;
  443. }
  444.  
  445.  
  446. #ifdef __STDC__
  447. static struct rx_se_list *
  448. hash_cons_se_prog (struct rx * rx,
  449.            struct rx_hash * memo,
  450.            void * car, struct rx_se_list * cdr)
  451. #else
  452. static struct rx_se_list *
  453. hash_cons_se_prog (rx, memo, car, cdr)
  454.      struct rx * rx;
  455.      struct rx_hash * memo;
  456.      void * car;
  457.      struct rx_se_list * cdr;
  458. #endif
  459. {
  460.   long hash = (long)car ^ (long)cdr;
  461.   struct rx_se_list template;
  462.  
  463.   template.car = car;
  464.   template.cdr = cdr;
  465.   {
  466.     struct rx_hash_item * it = rx_hash_store (memo, hash,
  467.                           (void *)&template,
  468.                           &se_list_hash_rules);
  469.     if (!it)
  470.       return 0;
  471.     if (it->data == (void *)&template)
  472.       {
  473.     struct rx_se_list * consed;
  474.     consed = (struct rx_se_list *) malloc (sizeof (*consed));
  475.     *consed = template;
  476.     it->data = (void *)consed;
  477.       }
  478.     return (struct rx_se_list *)it->data;
  479.   }
  480. }
  481.      
  482.  
  483. #ifdef __STDC__
  484. static struct rx_se_list *
  485. hash_se_prog (struct rx * rx, struct rx_hash * memo, struct rx_se_list * prog)
  486. #else
  487. static struct rx_se_list *
  488. hash_se_prog (rx, memo, prog)
  489.      struct rx * rx;
  490.      struct rx_hash * memo;
  491.      struct rx_se_list * prog;
  492. #endif
  493. {
  494.   struct rx_se_list * answer = 0;
  495.   while (prog)
  496.     {
  497.       answer = hash_cons_se_prog (rx, memo, prog->car, answer);
  498.       if (!answer)
  499.     return 0;
  500.       prog = prog->cdr;
  501.     }
  502.   return answer;
  503. }
  504.  
  505.  
  506.  
  507. /* {Constructors, etc. for NFA State Sets}
  508.  */
  509.  
  510. #ifdef __STDC__
  511. static int 
  512. nfa_set_cmp (void * va, void * vb)
  513. #else
  514. static int 
  515. nfa_set_cmp (va, vb)
  516.      void * va;
  517.      void * vb;
  518. #endif
  519. {
  520.   struct rx_nfa_state_set * a = (struct rx_nfa_state_set *)va;
  521.   struct rx_nfa_state_set * b = (struct rx_nfa_state_set *)vb;
  522.  
  523.   return ((va == vb)
  524.       ? 0
  525.       : (!va
  526.          ? -1
  527.          : (!vb
  528.         ? 1
  529.         : (a->car->id < b->car->id
  530.            ? 1
  531.            : (a->car->id > b->car->id
  532.               ? -1
  533.               : nfa_set_cmp ((void *)a->cdr, (void *)b->cdr))))));
  534. }
  535.  
  536. #ifdef __STDC__
  537. static int 
  538. nfa_set_equal (void * va, void * vb)
  539. #else
  540. static int 
  541. nfa_set_equal (va, vb)
  542.      void * va;
  543.      void * vb;
  544. #endif
  545. {
  546.   return !nfa_set_cmp (va, vb);
  547. }
  548.  
  549. static struct rx_hash_rules nfa_set_hash_rules = { nfa_set_equal, 0, 0, 0, 0 };
  550.  
  551.  
  552. #ifdef __STDC__
  553. static struct rx_nfa_state_set * 
  554. nfa_set_cons (struct rx * rx,
  555.           struct rx_hash * memo, struct rx_nfa_state * state,
  556.           struct rx_nfa_state_set * set)
  557. #else
  558. static struct rx_nfa_state_set * 
  559. nfa_set_cons (rx, memo, state, set)
  560.      struct rx * rx;
  561.      struct rx_hash * memo;
  562.      struct rx_nfa_state * state;
  563.      struct rx_nfa_state_set * set;
  564. #endif
  565. {
  566.   struct rx_nfa_state_set template;
  567.   struct rx_hash_item * node;
  568.   template.car = state;
  569.   template.cdr = set;
  570.   node = rx_hash_store (memo,
  571.             (((long)state) >> 8) ^ (long)set,
  572.             &template, &nfa_set_hash_rules);
  573.   if (!node)
  574.     return 0;
  575.   if (node->data == &template)
  576.     {
  577.       struct rx_nfa_state_set * l;
  578.       l = (struct rx_nfa_state_set *) malloc (sizeof (*l));
  579.       node->data = (void *) l;
  580.       if (!l)
  581.     return 0;
  582.       *l = template;
  583.     }
  584.   return (struct rx_nfa_state_set *)node->data;
  585. }
  586.  
  587.  
  588. #ifdef __STDC__
  589. static struct rx_nfa_state_set * 
  590. nfa_set_enjoin (struct rx * rx,
  591.         struct rx_hash * memo, struct rx_nfa_state * state,
  592.         struct rx_nfa_state_set * set)
  593. #else
  594. static struct rx_nfa_state_set * 
  595. nfa_set_enjoin (rx, memo, state, set)
  596.      struct rx * rx;
  597.      struct rx_hash * memo;
  598.      struct rx_nfa_state * state;
  599.      struct rx_nfa_state_set * set;
  600. #endif
  601. {
  602.   if (!set || state->id < set->car->id)
  603.     return nfa_set_cons (rx, memo, state, set);
  604.   if (state->id == set->car->id)
  605.     return set;
  606.   else
  607.     {
  608.       struct rx_nfa_state_set * newcdr
  609.     = nfa_set_enjoin (rx, memo, state, set->cdr);
  610.       if (newcdr != set->cdr)
  611.     set = nfa_set_cons (rx, memo, set->car, newcdr);
  612.       return set;
  613.     }
  614. }
  615.  
  616.  
  617. /* {Computing Epsilon/Side-effect Closures.}
  618.  */
  619.  
  620. struct eclose_frame
  621. {
  622.   struct rx_se_list *prog_backwards;
  623. };
  624.  
  625.  
  626. /* This is called while computing closures for "outnode".
  627.  * The current node in the traversal is "node".
  628.  * "frame" contains a list of a all side effects between 
  629.  * "outnode" and "node" from most to least recent.
  630.  *
  631.  * Explores forward from "node", adding new possible
  632.  * futures to outnode.
  633.  *
  634.  * Returns 0 on allocation failure.
  635.  */
  636.  
  637. #ifdef __STDC__
  638. static int 
  639. eclose_node (struct rx *rx, struct rx_nfa_state *outnode,
  640.          struct rx_nfa_state *node, struct eclose_frame *frame)
  641. #else
  642. static int 
  643. eclose_node (rx, outnode, node, frame)
  644.      struct rx *rx;
  645.      struct rx_nfa_state *outnode;
  646.      struct rx_nfa_state *node;
  647.      struct eclose_frame *frame;
  648. #endif
  649. {
  650.   struct rx_nfa_edge *e = node->edges;
  651.  
  652.   /* For each node, we follow all epsilon paths to build the closure.
  653.    * The closure omits nodes that have only epsilon edges.
  654.    * The closure is split into partial closures -- all the states in
  655.    * a partial closure are reached by crossing the same list of
  656.    * of side effects (though not necessarily the same path).
  657.    */
  658.   if (node->mark)
  659.     return 1;
  660.   node->mark = 1;
  661.  
  662.   /* If "node" has more than just epsilon and 
  663.    * and side-effect transitions (id >= 0), or is final,
  664.    * then it has to be added to the possible futures
  665.    * of "outnode".
  666.    */
  667.   if (node->id >= 0 || node->is_final)
  668.     {
  669.       struct rx_possible_future **ec;
  670.       struct rx_se_list * prog_in_order;
  671.       int cmp;
  672.  
  673.       prog_in_order = ((struct rx_se_list *)hash_se_prog (rx,
  674.                               &rx->se_list_memo,
  675.                               frame->prog_backwards));
  676.  
  677.       ec = &outnode->futures;
  678.  
  679.       while (*ec)
  680.     {
  681.       cmp = se_list_cmp ((void *)(*ec)->effects, (void *)prog_in_order);
  682.       if (cmp <= 0)
  683.         break;
  684.       ec = &(*ec)->next;
  685.     }
  686.  
  687.       if (!*ec || (cmp < 0))
  688.     {
  689.       struct rx_possible_future * pf;
  690.       pf = rx_possible_future (rx, prog_in_order);
  691.       if (!pf)
  692.         return 0;
  693.       pf->next = *ec;
  694.       *ec = pf;
  695.     }
  696.       if (node->id >= 0)
  697.     {
  698.       (*ec)->destset = nfa_set_enjoin (rx, &rx->set_list_memo,
  699.                        node, (*ec)->destset);
  700.       if (!(*ec)->destset)
  701.         return 0;
  702.     }
  703.     }
  704.  
  705.   /* Recurse on outgoing epsilon and side effect nodes.
  706.    */
  707.   while (e)
  708.     {
  709.       switch (e->type)
  710.     {
  711.     case ne_epsilon:
  712.       if (!eclose_node (rx, outnode, e->dest, frame))
  713.         return 0;
  714.       break;
  715.     case ne_side_effect:
  716.       {
  717.         frame->prog_backwards = side_effect_cons (rx, 
  718.                               e->params.side_effect,
  719.                               frame->prog_backwards);
  720.         if (!frame->prog_backwards)
  721.           return 0;
  722.         if (!eclose_node (rx, outnode, e->dest, frame))
  723.           return 0;
  724.         {
  725.           struct rx_se_list * dying = frame->prog_backwards;
  726.           frame->prog_backwards = frame->prog_backwards->cdr;
  727.           free ((char *)dying);
  728.         }
  729.         break;
  730.       }
  731.     default:
  732.       break;
  733.     }
  734.       e = e->next;
  735.     }
  736.   node->mark = 0;
  737.   return 1;
  738. }
  739.  
  740.  
  741. #ifdef __STDC__
  742. struct rx_possible_future *
  743. rx_state_possible_futures (struct rx * rx, struct rx_nfa_state * n)
  744. #else
  745. struct rx_possible_future *
  746. rx_state_possible_futures (rx, n)
  747.      struct rx * rx;
  748.      struct rx_nfa_state * n;
  749. #endif
  750. {
  751.   if (n->futures_computed)
  752.     return n->futures;
  753.   else
  754.     {
  755.       struct eclose_frame frame;
  756.       frame.prog_backwards = 0;
  757.       if (!eclose_node (rx, n, n, &frame))
  758.     return 0;
  759.       else
  760.     {
  761.       n->futures_computed = 1;
  762.       return n->futures;
  763.     }
  764.     }
  765. }
  766.  
  767.  
  768.  
  769. /* {Storing the NFA in a Contiguous Region of Memory}
  770.  */
  771.  
  772.  
  773.  
  774. #ifdef __STDC__
  775. static void 
  776. se_memo_freer (struct rx_hash_item * node)
  777. #else
  778. static void 
  779. se_memo_freer (node)
  780.      struct rx_hash_item * node;
  781. #endif
  782. {
  783.   free ((char *)node->data);
  784. }
  785.  
  786.  
  787. #ifdef __STDC__
  788. static void 
  789. nfa_set_freer (struct rx_hash_item * node)
  790. #else
  791. static void 
  792. nfa_set_freer (node)
  793.      struct rx_hash_item * node;
  794. #endif
  795. {
  796.   free ((char *)node->data);
  797. }
  798.  
  799. #ifdef __STDC__
  800. void
  801. rx_free_nfa (struct rx *rx)
  802. #else
  803. void
  804. rx_free_nfa (rx)
  805.      struct rx *rx;
  806. #endif
  807. {
  808.   rx_free_hash_table (&rx->se_list_memo, se_memo_freer, &se_list_hash_rules);
  809.   bzero (&rx->se_list_memo, sizeof (rx->se_list_memo));
  810.   rx_free_hash_table (&rx->set_list_memo, nfa_set_freer, &nfa_set_hash_rules);
  811.   bzero (&rx->set_list_memo, sizeof (rx->set_list_memo));
  812.   rx_free_nfa_graph (rx);
  813. }
  814.