home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS 1992 September / Simtel20_Sept92.cdr / msdos / c / lex.arc / ECLOSU.C < prev    next >
Text File  |  1986-03-10  |  2KB  |  48 lines
  1. /*
  2.  * Copyright (c) 1978 Charles H. Forsyth
  3.  */
  4.  
  5. #include <stdio.h>
  6. #include "lexlex.h"
  7.  
  8. /*
  9.  * Construct the epsilon closure of a given set; this is the set of states
  10.  * that may be reached by some number of epsilon transitions from that state.
  11.  */
  12. struct set *
  13. eclosure(t)
  14. struct set *t;
  15. {
  16.         register struct nfa *np, *xp;
  17.         register int i;
  18.         struct nfa **sp, **tp, **ip, *stack[MAXNFA], *temp[MAXNFA];
  19.  
  20.         tp = temp;
  21.         for (sp = stack, i = 0; i < t->s_len; i++)
  22.                 if (sp <= stack+MAXNFA)
  23.                         *tp++ = *sp++ = t->s_els[i];
  24.                 else {
  25.                         error("Stack overflow in `eclosure'");
  26.                         exit(1);
  27.                 }
  28.         while (sp > stack) {
  29.                 np = *--sp;
  30.                 if (np->n_char==EPSILON)
  31.                 for (i = 0; i < 2; i++)
  32.                         if (xp = np->n_succ[i]) {
  33.                                 for (ip = temp; ip < tp;)
  34.                                         if (*ip++ == xp)
  35.                                                 goto cont;
  36.                                 if (tp >= temp+MAXNFA) {
  37.                                         error("eclosure: list overflow");
  38.                                         exit(1);
  39.                                 }
  40.                                 *sp++ = *tp++ = xp;
  41.                         cont:;
  42.                         }
  43.         }
  44.         t = newset(temp, tp-temp, 1);
  45.         return(t);
  46. }
  47.  
  48.