Tools/Source/TianoTools/Pccts/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-2001
  27  */
  28
  29 #include <stdio.h>
  30 #include "pcctscfg.h"
  31 #include "dlg.h"
  32 #ifdef MEMCHK
  33 #include "trax.h"
  34 #else
  35 #ifdef __STDC__
  36 #include <stdlib.h>
  37 #else
  38 #include <malloc.h>
  39 #endif /* __STDC__ */
  40 #endif
  41
  42 #define hash_list struct _hash_list_
  43 hash_list{
  44         hash_list *next;        /* next thing in list */
  45         dfa_node *node;
  46  };
  47
  48 int     dfa_allocated = 0;      /* keeps track of number of dfa nodes */
  49 dfa_node        **dfa_array;    /* root of binary tree that stores dfa array */
  50 dfa_node        *dfa_model_node;
  51 hash_list       *dfa_hash[HASH_SIZE];   /* used to quickly find */
  52                                         /* desired dfa node */
  53
  54 void
  55 #ifdef __USE_PROTOS
  56 make_dfa_model_node(int width)
  57 #else
  58 make_dfa_model_node(width)
  59 int width;
  60 #endif
  61 {
  62         register int i;
  63         dfa_model_node = (dfa_node*) malloc(sizeof(dfa_node)
  64                          + sizeof(int)*width);
  65         dfa_model_node->node_no = -1; /* impossible value for real dfa node */
  66         dfa_model_node->dfa_set = 0;
  67         dfa_model_node->alternatives = FALSE;
  68         dfa_model_node->done = FALSE;
  69         dfa_model_node->nfa_states = empty;
  70         for(i = 0; i<width; i++){
  71                 dfa_model_node->trans[i] = NIL_INDEX;
  72         }
  73 }
  74
  75
  76 /* adds a new nfa to the binary tree and returns a pointer to it */
  77 dfa_node *
  78 #ifdef __USE_PROTOS
  79 new_dfa_node(set nfa_states)
  80 #else
  81 new_dfa_node(nfa_states)
  82 set nfa_states;
  83 #endif
  84 {
  85         register int j;
  86         register dfa_node *t;
  87         static int dfa_size=0;  /* elements dfa_array[] can hold */
  88
  89         ++dfa_allocated;
  90         if (dfa_size<=dfa_allocated){
  91                 /* need to redo array */
  92                 if (!dfa_array){
  93                         /* need some to do inital allocation */
  94                         dfa_size=dfa_allocated+DFA_MIN;
  95                         dfa_array=(dfa_node **) malloc(sizeof(dfa_node*)*
  96                                 dfa_size);
  97                 }else{
  98                         /* need more space */
  99                         dfa_size=2*(dfa_allocated+1);
 100                         dfa_array=(dfa_node **) realloc(dfa_array,
 101                                 sizeof(dfa_node*)*dfa_size);
 102                 }
 103         }
 104         /* fill out entry in array */
 105         t = (dfa_node*) malloc(sizeof(nfa_node)+sizeof(int)*class_no);
 106         *t = *dfa_model_node;
 107         for (j=0; j<class_no; ++j)
 108                 t->trans[j] = NIL_INDEX;
 109         t->node_no = dfa_allocated;
 110         t->nfa_states = set_dup(nfa_states);
 111         dfa_array[dfa_allocated] = t;
 112         return t;
 113 }
 114
 115
 116 /* past a pointer to the start start of the nfa graph
 117  * nfa_to_dfa convers this graph to dfa.  The function returns
 118  * a pointer to the first dfa state.
 119  * NOTE:  The function that prints out the table will have to figure out how
 120  * to find the other dfa states given the first dfa_state and the number of dfa
 121  * nodes allocated
 122  */
 123 dfa_node **
 124 #ifdef __USE_PROTOS
 125 nfa_to_dfa(nfa_node *start)
 126 #else
 127 nfa_to_dfa(start)
 128 nfa_node *start;
 129 #endif
 130 {
 131         register dfa_node *d_state, *trans_d_state;
 132         register int a;
 133         set t;
 134         int last_done;
 135         unsigned *nfa_list;
 136         unsigned *reach_list;
 137
 138         reach_list = (unsigned *) malloc((2+nfa_allocated)*sizeof(unsigned));
 139         if (!start) return NULL;
 140         t = set_of(NFA_NO(start));
 141         _set_pdq(t,reach_list);
 142         closure(&t,reach_list);
 143         /* Make t a dfa state */
 144         d_state = dfastate(t);
 145         last_done = DFA_NO(d_state);
 146
 147         do {
 148                 /* Mark dfa state x as "done" */
 149                 d_state->done = TRUE;
 150                 nfa_list = set_pdq(d_state->nfa_states);
 151                 for (a = 0; a<class_no; ++a) {
 152                         /* Add NFA states reached by a from d_state */
 153                         reach(nfa_list,a,reach_list);
 154                         /* Were any states found? */
 155                         if ((*reach_list)!=nil) {
 156                                 /* was t=empty; */
 157                                 set_free(t);
 158                                 /* yes, compute closure */
 159                                 closure(&t,reach_list);
 160                                 /* Make DFA state of it ... */
 161                                 trans_d_state = dfastate(t);
 162                                 /* And make transition x->t, labeled with a */
 163                                 d_state->trans[a] = DFA_NO(trans_d_state);
 164                                 d_state->alternatives = TRUE;
 165                         }
 166                 }
 167                 free(nfa_list);
 168                 ++last_done; /* move forward in queue */
 169                 /* And so forth until nothing isn't done */
 170                 d_state = DFA(last_done);
 171         } while (last_done<=dfa_allocated);
 172
 173         free(reach_list);
 174         set_free(t);
 175
 176         /* returns pointer to the array that holds the automaton */
 177         return dfa_array;
 178 }
 179
 180 void
 181 #ifdef __USE_PROTOS
 182 clear_hash(void)
 183 #else
 184 clear_hash()
 185 #endif
 186 {
 187         register int i;
 188
 189         for(i=0; i<HASH_SIZE; ++i)
 190                 dfa_hash[i] = 0;
 191 }
 192
 193 #if HASH_STAT
 194 void
 195 #ifdef __USE_PROTOS
 196 fprint_hash_stats(FILE *f)
 197 #else
 198 fprint_hash_stats(f)
 199 FILE *f;
 200 #endif
 201 {
 202         register hash_list *p;
 203         register int i,j;
 204         register total;
 205
 206         total=0;
 207         for(i=0; i<HASH_SIZE; ++i){
 208                 j=0;
 209                 p = dfa_hash[i];
 210                 while(p){
 211                         ++j;
 212                         p = p->next;
 213                 }
 214                 total+=j;
 215                 fprintf(f,"bin[%d] has %d\n",i,j);
 216         }
 217         fprintf(f,"total = %d\n",total);
 218 }
 219 #endif
 220
 221 /* Returns a pointer to a dfa node that has the same nfa nodes in it.
 222  * This may or maynot be a newly created node.
 223  */
 224 dfa_node *
 225 #ifdef __USE_PROTOS
 226 dfastate(set nfa_states)
 227 #else
 228 dfastate(nfa_states)
 229 set nfa_states;
 230 #endif
 231 {
 232         register hash_list *p;
 233         int bin;
 234
 235         /* hash using set and see if it exists */
 236         bin = set_hash(nfa_states,HASH_SIZE);
 237         p = dfa_hash[bin];
 238         while(p && !set_equ(nfa_states,(p->node)->nfa_states)){
 239                 p = p->next;
 240         }
 241         if(!p){
 242                 /* next state to add to hash table */
 243                 p = (hash_list*)malloc(sizeof(hash_list));
 244                 p->node = new_dfa_node(nfa_states);
 245                 p->next = dfa_hash[bin];
 246                 dfa_hash[bin] = p;
 247         }
 248         return (p->node);
 249 }
 250
 251
 252 /* this reach assumes the closure has been done already on set */
 253 int
 254 #ifdef __USE_PROTOS
 255 reach(unsigned *nfa_list, register int a, unsigned *reach_list)
 256 #else
 257 reach(nfa_list, a, reach_list)
 258 unsigned *nfa_list;
 259 register int a;
 260 unsigned *reach_list;
 261 #endif
 262 {
 263         register unsigned *e;
 264         register nfa_node *node;
 265         int t=0;
 266
 267         e = nfa_list;
 268         if (e){
 269                 while (*e != nil){
 270                         node = NFA(*e);
 271                         if (set_el(a,node->label)){
 272                                 t=1;
 273                                 *reach_list=NFA_NO(node->trans[0]);
 274                                 ++reach_list;
 275                         }
 276                         ++e;
 277                 }
 278         }
 279         *reach_list=nil;
 280         return t;
 281 }
 282
 283 /* finds all the nodes that can be reached by epsilon transitions
 284    from the set of a nodes and returns puts them back in set b */
 285 set
 286 #ifdef __USE_PROTOS
 287 closure(set *b, unsigned *reach_list)
 288 #else
 289 closure(b, reach_list)
 290 set *b;
 291 unsigned *reach_list;
 292 #endif
 293 {
 294         register nfa_node *node,*n;     /* current node being examined */
 295         register unsigned *e;
 296
 297         ++operation_no;
 298 #if 0
 299         t = e = set_pdq(*b);
 300 #else
 301         e=reach_list;
 302 #endif
 303         while (*e != nil){
 304                 node = NFA(*e);
 305                 set_orel(NFA_NO(node),b);
 306                 /* mark it done */
 307                 node->nfa_set = operation_no;
 308                 if ((n=node->trans[0]) != NIL_INDEX && set_nil(node->label) &&
 309                   (n->nfa_set != operation_no)){
 310                         /* put in b */
 311                         set_orel(NFA_NO(n),b);
 312                         close1(n,operation_no,b);
 313                 }
 314                 if ((n=node->trans[1]) != NIL_INDEX &&
 315                   (n->nfa_set != operation_no)){
 316                         /* put in b */
 317                         set_orel(NFA_NO(node->trans[1]),b);
 318                         close1(n,operation_no,b);
 319                 }
 320                 ++e;
 321         }
 322 #if 0
 323         free(t);
 324 #endif
 325         return *b;
 326 }
 327
 328 #ifdef __USE_PROTOS
 329 void close1(nfa_node *node, int o, set *b)
 330 #else
 331 void close1(node,o,b)
 332 nfa_node *node;
 333 int o;  /* marker to avoid cycles */
 334 set *b;
 335 #endif
 336 {
 337         register nfa_node *n;   /* current node being examined */
 338
 339         /* mark it done */
 340         node->nfa_set = o;
 341         if ((n=node->trans[0]) != NIL_INDEX && set_nil(node->label) &&
 342           (n->nfa_set != o)){
 343                 /* put in b */
 344                 set_orel(NFA_NO(n),b);
 345                 close1(n,o,b);
 346         }
 347         if ((n=node->trans[1]) != NIL_INDEX &&
 348           (n->nfa_set != o)){
 349                 /* put in b */
 350                 set_orel(NFA_NO(node->trans[1]),b);
 351                 close1(n,o,b);
 352         }
 353 }