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 } 354
