home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / pccts.zip / pccts / dlg / automata.c next >
C/C++ Source or Header  |  1994-03-31  |  7KB  |  306 lines
  1. /* Automata conversion functions for DLG
  2.  *
  3.  * SOFTWARE RIGHTS
  4.  *
  5.  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
  6.  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
  7.  * company may do whatever they wish with source code distributed with
  8.  * PCCTS or the code generated by PCCTS, including the incorporation of
  9.  * PCCTS, or its output, into commerical software.
  10.  * 
  11.  * We encourage users to develop software with PCCTS.  However, we do ask
  12.  * that credit is given to us for developing PCCTS.  By "credit",
  13.  * we mean that if you incorporate our source code into one of your
  14.  * programs (commercial product, research project, or otherwise) that you
  15.  * acknowledge this fact somewhere in the documentation, research report,
  16.  * etc...  If you like PCCTS and have developed a nice tool with the
  17.  * output, please mention that you developed it using PCCTS.  In
  18.  * addition, we ask that this header remain intact in our source code.
  19.  * As long as these guidelines are kept, we expect to continue enhancing
  20.  * this system and expect to make other tools available as they are
  21.  * completed.
  22.  *
  23.  * DLG 1.20
  24.  * Will Cohen
  25.  * With mods by Terence Parr; AHPCRC, University of Minnesota
  26.  * 1989-1994
  27.  */
  28.  
  29. #include <stdio.h>
  30. #include "dlg.h"
  31. #ifdef MEMCHK
  32. #include "trax.h"
  33. #else
  34. #ifdef __STDC__
  35. #include <stdlib.h>
  36. #else
  37. #include <malloc.h>
  38. #endif /* __STDC__ */
  39. #endif
  40.  
  41. #define hash_list struct _hash_list_
  42. hash_list{
  43.     hash_list *next;    /* next thing in list */
  44.     dfa_node *node;
  45. };
  46.  
  47. int    dfa_allocated = 0;    /* keeps track of number of dfa nodes */
  48. dfa_node    **dfa_array;    /* root of binary tree that stores dfa array */
  49. dfa_node    *dfa_model_node;
  50. hash_list     *dfa_hash[HASH_SIZE];    /* used to quickly find */
  51.                     /* desired dfa node */
  52.  
  53. void
  54. make_dfa_model_node(width)
  55. int width;
  56. {
  57.     register int i;
  58.     dfa_model_node = (dfa_node*) malloc(sizeof(dfa_node)
  59.              + sizeof(int)*width);
  60.     dfa_model_node->node_no = -1; /* impossible value for real dfa node */
  61.     dfa_model_node->dfa_set = 0;
  62.     dfa_model_node->alternatives = FALSE;
  63.     dfa_model_node->done = FALSE;
  64.     dfa_model_node->nfa_states = empty;
  65.     for(i = 0; i<width; i++){
  66.         dfa_model_node->trans[i] = NIL_INDEX;
  67.     }
  68. }
  69.  
  70.  
  71. /* adds a new nfa to the binary tree and returns a pointer to it */
  72. dfa_node *new_dfa_node(nfa_states)
  73. set nfa_states;
  74. {
  75.     register int j;
  76.     register dfa_node *t;
  77.     static int dfa_size=0;    /* elements dfa_array[] can hold */
  78.  
  79.     ++dfa_allocated;
  80.     if (dfa_size<=dfa_allocated){
  81.         /* need to redo array */
  82.         if (!dfa_array){
  83.             /* need some to do inital allocation */
  84.             dfa_size=dfa_allocated+DFA_MIN;
  85.             dfa_array=(dfa_node **) malloc(sizeof(dfa_node*)*
  86.                 dfa_size);
  87.         }else{
  88.             /* need more space */
  89.             dfa_size=2*(dfa_allocated+1);
  90.             dfa_array=(dfa_node **) realloc(dfa_array, 
  91.                 sizeof(dfa_node*)*dfa_size);
  92.         }
  93.     }
  94.     /* fill out entry in array */
  95.     t = (dfa_node*) malloc(sizeof(nfa_node)+sizeof(int)*class_no);
  96.     *t = *dfa_model_node;
  97.     for (j=0; j<class_no; ++j)
  98.         t->trans[j] = NIL_INDEX;
  99.     t->node_no = dfa_allocated;
  100.     t->nfa_states = set_dup(nfa_states);
  101.     dfa_array[dfa_allocated] = t;
  102.     return t;
  103. }
  104.  
  105.  
  106. /* past a pointer to the start start of the nfa graph
  107.  * nfa_to_dfa convers this graph to dfa.  The function returns
  108.  * a pointer to the first dfa state.
  109.  * NOTE:  The function that prints out the table will have to figure out how
  110.  * to find the other dfa states given the first dfa_state and the number of dfa
  111.  * nodes allocated
  112.  */
  113. dfa_node **nfa_to_dfa(start)
  114. nfa_node *start;
  115. {
  116.     register dfa_node *d_state, *trans_d_state;
  117.     register int a;
  118.     set t;
  119.     int last_done;
  120.     unsigned *nfa_list;
  121.     unsigned *reach_list;
  122.  
  123.     reach_list = (unsigned *) malloc((2+nfa_allocated)*sizeof(unsigned));
  124.     if (!start) return NULL;
  125.     t = set_of(NFA_NO(start));
  126.     _set_pdq(t,reach_list);
  127.     closure(&t,reach_list);
  128.     /* Make t a dfa state */
  129.     d_state = dfastate(t);
  130.     last_done = DFA_NO(d_state);
  131.     
  132.     do {
  133.         /* Mark dfa state x as "done" */
  134.         d_state->done = TRUE;
  135.         nfa_list = set_pdq(d_state->nfa_states);
  136.         for (a = 0; a<class_no; ++a) {
  137.             /* Add NFA states reached by a from d_state */
  138.             reach(nfa_list,a,reach_list);
  139.             /* Were any states found? */
  140.             if ((*reach_list)!=nil) {
  141.                 t=empty;
  142.                 /* yes, compute closure */
  143.                 closure(&t,reach_list);
  144.                 /* Make DFA state of it ... */
  145.                 trans_d_state = dfastate(t);
  146.                 /* And make transition x->t, labeled with a */
  147.                 d_state->trans[a] = DFA_NO(trans_d_state);
  148.                 d_state->alternatives = TRUE;
  149.             }
  150.         }
  151.         free(nfa_list);
  152.         ++last_done; /* move forward in queue */
  153.         /* And so forth until nothing isn't done */
  154.         d_state = DFA(last_done);
  155.     } while (last_done<=dfa_allocated);
  156.     free(reach_list);
  157.     /* returns pointer to the array that holds the automaton */
  158.     return dfa_array;
  159. }
  160.  
  161. clear_hash()
  162. {
  163.     register int i;
  164.  
  165.     for(i=0; i<HASH_SIZE; ++i)
  166.         dfa_hash[i] = 0;
  167. }
  168.  
  169. #if HASH_STAT
  170. fprint_hash_stats(f)
  171. FILE *f;
  172. {
  173.     register hash_list *p;
  174.     register int i,j;
  175.     register total;
  176.  
  177.     total=0;
  178.     for(i=0; i<HASH_SIZE; ++i){
  179.         j=0;
  180.         p = dfa_hash[i];
  181.         while(p){
  182.             ++j;
  183.             p = p->next;
  184.         }
  185.         total+=j;
  186.         fprintf(f,"bin[%d] has %d\n",i,j);
  187.     }
  188.     fprintf(f,"total = %d\n",total);
  189. }
  190. #endif
  191.  
  192. /* Returns a pointer to a dfa node that has the same nfa nodes in it.
  193.  * This may or maynot be a newly created node.
  194.  */
  195. dfa_node *dfastate(nfa_states)
  196. set nfa_states;        /* list of nfa states it could be */
  197. {
  198.     register hash_list *p;
  199.     int bin;
  200.  
  201.     /* hash using set and see if it exists */
  202.     bin = set_hash(nfa_states,HASH_SIZE);
  203.     p = dfa_hash[bin];
  204.     while(p && !set_equ(nfa_states,(p->node)->nfa_states)){
  205.         p = p->next;
  206.     }
  207.     if(!p){
  208.         /* next state to add to hash table */
  209.         p = (hash_list*)malloc(sizeof(hash_list));
  210.         p->node = new_dfa_node(nfa_states);
  211.         p->next = dfa_hash[bin];
  212.         dfa_hash[bin] = p;
  213.     }
  214.     return (p->node);
  215. }
  216.  
  217.  
  218. /* this reach assumes the closure has been done already on set */
  219. int reach(nfa_list,a,reach_list)
  220. unsigned *nfa_list;
  221. register int a;
  222. unsigned *reach_list;
  223. {
  224.     register unsigned *e;
  225.     register nfa_node *node;
  226.     int t=0;
  227.  
  228.     e = nfa_list;
  229.     if (e){
  230.         while (*e != nil){
  231.             node = NFA(*e);
  232.             if (set_el(a,node->label)){
  233.                 t=1;
  234.                 *reach_list=NFA_NO(node->trans[0]);
  235.                 ++reach_list;
  236.             }
  237.             ++e;
  238.         }
  239.     }
  240.     *reach_list=nil;
  241.     return t;
  242. }
  243.  
  244. /* finds all the nodes that can be reached by epsilon transitions
  245.    from the set of a nodes and returns puts them back in set b */
  246. set closure(b,reach_list)
  247. set *b;
  248. unsigned *reach_list;
  249. {
  250.     register nfa_node *node,*n;    /* current node being examined */
  251.     register unsigned *t,*e;
  252.  
  253.     ++operation_no;
  254. #if 0
  255.     t = e = set_pdq(*b);
  256. #else
  257.     e=reach_list;
  258. #endif
  259.     while (*e != nil){
  260.         node = NFA(*e);
  261.         set_orel(NFA_NO(node),b);
  262.         /* mark it done */
  263.         node->nfa_set = operation_no;
  264.         if ((n=node->trans[0]) != NIL_INDEX && set_nil(node->label) &&
  265.           (n->nfa_set != operation_no)){
  266.             /* put in b */
  267.             set_orel(NFA_NO(n),b);
  268.             close1(n,operation_no,b);
  269.         }
  270.         if ((n=node->trans[1]) != NIL_INDEX &&
  271.           (n->nfa_set != operation_no)){
  272.             /* put in b */
  273.             set_orel(NFA_NO(node->trans[1]),b);
  274.             close1(n,operation_no,b);
  275.         }
  276.         ++e;
  277.     }
  278. #if 0
  279.     free(t);
  280. #endif
  281.     return *b;
  282. }
  283.  
  284. close1(node,o,b)
  285. nfa_node *node;
  286. int o;    /* marker to avoid cycles */
  287. set *b;
  288. {
  289.     register nfa_node *n;    /* current node being examined */
  290.  
  291.     /* mark it done */
  292.     node->nfa_set = o;
  293.     if ((n=node->trans[0]) != NIL_INDEX && set_nil(node->label) &&
  294.       (n->nfa_set != o)){
  295.         /* put in b */
  296.         set_orel(NFA_NO(n),b);
  297.         close1(n,o,b);
  298.     }
  299.     if ((n=node->trans[1]) != NIL_INDEX &&
  300.       (n->nfa_set != o)){
  301.         /* put in b */
  302.         set_orel(NFA_NO(node->trans[1]),b);
  303.         close1(n,o,b);
  304.     }
  305. }
  306.