home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 11 Util / 11-Util.zip / OS2_LEX.ZIP / ECLOSU.C < prev    next >
C/C++ Source or Header  |  1989-10-07  |  2KB  |  48 lines
  1. /*
  2.  * Copyright (c) 1978 Charles H. Forsyth
  3.  */
  4.  
  5. #include <stdlib.h>
  6. #include <stdio.h>
  7. #include "lexlex.h"
  8. #include "lextern.h"
  9.  
  10. /*
  11.  * Construct the epsilon closure of a given set; this is the set of states
  12.  * that may be reached by some number of epsilon transitions from that state.
  13.  */
  14. struct set *eclosure(struct set *t)
  15. {
  16.         register struct nfa *np, *xp;
  17.         register 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.