pd.if.org Git - pccts/blob - dlg/automata.c

   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.33
  24  * Will Cohen
  25  * With mods by Terence Parr; AHPCRC, University of Minnesota
  26  * 1989-1995
  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                                 /* was t=empty; */
 142                                 set_free(t);
 143                                 /* yes, compute closure */
 144                                 closure(&t,reach_list);
 145                                 /* Make DFA state of it ... */
 146                                 trans_d_state = dfastate(t);
 147                                 /* And make transition x->t, labeled with a */
 148                                 d_state->trans[a] = DFA_NO(trans_d_state);
 149                                 d_state->alternatives = TRUE;
 150                         }
 151                 }
 152                 free(nfa_list);
 153                 ++last_done; /* move forward in queue */
 154                 /* And so forth until nothing isn't done */
 155                 d_state = DFA(last_done);
 156         } while (last_done<=dfa_allocated);
 157
 158         free(reach_list);
 159         set_free(t);
 160
 161         /* returns pointer to the array that holds the automaton */
 162         return dfa_array;
 163 }
 164
 165 clear_hash()
 166 {
 167         register int i;
 168
 169         for(i=0; i<HASH_SIZE; ++i)
 170                 dfa_hash[i] = 0;
 171 }
 172
 173 #if HASH_STAT
 174 fprint_hash_stats(f)
 175 FILE *f;
 176 {
 177         register hash_list *p;
 178         register int i,j;
 179         register total;
 180
 181         total=0;
 182         for(i=0; i<HASH_SIZE; ++i){
 183                 j=0;
 184                 p = dfa_hash[i];
 185                 while(p){
 186                         ++j;
 187                         p = p->next;
 188                 }
 189                 total+=j;
 190                 fprintf(f,"bin[%d] has %d\n",i,j);
 191         }
 192         fprintf(f,"total = %d\n",total);
 193 }
 194 #endif
 195
 196 /* Returns a pointer to a dfa node that has the same nfa nodes in it.
 197  * This may or maynot be a newly created node.
 198  */
 199 dfa_node *dfastate(nfa_states)
 200 set nfa_states;         /* list of nfa states it could be */
 201 {
 202         register hash_list *p;
 203         int bin;
 204
 205         /* hash using set and see if it exists */
 206         bin = set_hash(nfa_states,HASH_SIZE);
 207         p = dfa_hash[bin];
 208         while(p && !set_equ(nfa_states,(p->node)->nfa_states)){
 209                 p = p->next;
 210         }
 211         if(!p){
 212                 /* next state to add to hash table */
 213                 p = (hash_list*)malloc(sizeof(hash_list));
 214                 p->node = new_dfa_node(nfa_states);
 215                 p->next = dfa_hash[bin];
 216                 dfa_hash[bin] = p;
 217         }
 218         return (p->node);
 219 }
 220
 221
 222 /* this reach assumes the closure has been done already on set */
 223 int reach(nfa_list,a,reach_list)
 224 unsigned *nfa_list;
 225 register int a;
 226 unsigned *reach_list;
 227 {
 228         register unsigned *e;
 229         register nfa_node *node;
 230         int t=0;
 231
 232         e = nfa_list;
 233         if (e){
 234                 while (*e != nil){
 235                         node = NFA(*e);
 236                         if (set_el(a,node->label)){
 237                                 t=1;
 238                                 *reach_list=NFA_NO(node->trans[0]);
 239                                 ++reach_list;
 240                         }
 241                         ++e;
 242                 }
 243         }
 244         *reach_list=nil;
 245         return t;
 246 }
 247
 248 /* finds all the nodes that can be reached by epsilon transitions
 249    from the set of a nodes and returns puts them back in set b */
 250 set closure(b,reach_list)
 251 set *b;
 252 unsigned *reach_list;
 253 {
 254         register nfa_node *node,*n;     /* current node being examined */
 255         register unsigned *t,*e;
 256
 257         ++operation_no;
 258 #if 0
 259         t = e = set_pdq(*b);
 260 #else
 261         e=reach_list;
 262 #endif
 263         while (*e != nil){
 264                 node = NFA(*e);
 265                 set_orel(NFA_NO(node),b);
 266                 /* mark it done */
 267                 node->nfa_set = operation_no;
 268                 if ((n=node->trans[0]) != NIL_INDEX && set_nil(node->label) &&
 269                   (n->nfa_set != operation_no)){
 270                         /* put in b */
 271                         set_orel(NFA_NO(n),b);
 272                         close1(n,operation_no,b);
 273                 }
 274                 if ((n=node->trans[1]) != NIL_INDEX &&
 275                   (n->nfa_set != operation_no)){
 276                         /* put in b */
 277                         set_orel(NFA_NO(node->trans[1]),b);
 278                         close1(n,operation_no,b);
 279                 }
 280                 ++e;
 281         }
 282 #if 0
 283         free(t);
 284 #endif
 285         return *b;
 286 }
 287
 288 close1(node,o,b)
 289 nfa_node *node;
 290 int o;  /* marker to avoid cycles */
 291 set *b;
 292 {
 293         register nfa_node *n;   /* current node being examined */
 294
 295         /* mark it done */
 296         node->nfa_set = o;
 297         if ((n=node->trans[0]) != NIL_INDEX && set_nil(node->label) &&
 298           (n->nfa_set != o)){
 299                 /* put in b */
 300                 set_orel(NFA_NO(n),b);
 301                 close1(n,o,b);
 302         }
 303         if ((n=node->trans[1]) != NIL_INDEX &&
 304           (n->nfa_set != o)){
 305                 /* put in b */
 306                 set_orel(NFA_NO(node->trans[1]),b);
 307                 close1(n,o,b);
 308         }
 309 }