+++ /dev/null
-/* Automata conversion functions for DLG\r
- *\r
- * SOFTWARE RIGHTS\r
- *\r
- * We reserve no LEGAL rights to the Purdue Compiler Construction Tool\r
- * Set (PCCTS) -- PCCTS is in the public domain. An individual or\r
- * company may do whatever they wish with source code distributed with\r
- * PCCTS or the code generated by PCCTS, including the incorporation of\r
- * PCCTS, or its output, into commerical software.\r
- *\r
- * We encourage users to develop software with PCCTS. However, we do ask\r
- * that credit is given to us for developing PCCTS. By "credit",\r
- * we mean that if you incorporate our source code into one of your\r
- * programs (commercial product, research project, or otherwise) that you\r
- * acknowledge this fact somewhere in the documentation, research report,\r
- * etc... If you like PCCTS and have developed a nice tool with the\r
- * output, please mention that you developed it using PCCTS. In\r
- * addition, we ask that this header remain intact in our source code.\r
- * As long as these guidelines are kept, we expect to continue enhancing\r
- * this system and expect to make other tools available as they are\r
- * completed.\r
- *\r
- * DLG 1.33\r
- * Will Cohen\r
- * With mods by Terence Parr; AHPCRC, University of Minnesota\r
- * 1989-2001\r
- */\r
-\r
-#include <stdio.h>\r
-#include "pcctscfg.h"\r
-#include "dlg.h"\r
-#ifdef MEMCHK\r
-#include "trax.h"\r
-#else\r
-#ifdef __STDC__\r
-#include <stdlib.h>\r
-#else\r
-#include <malloc.h>\r
-#endif /* __STDC__ */\r
-#endif\r
-\r
-#define hash_list struct _hash_list_\r
-hash_list{\r
- hash_list *next; /* next thing in list */\r
- dfa_node *node;\r
- };\r
-\r
-int dfa_allocated = 0; /* keeps track of number of dfa nodes */\r
-dfa_node **dfa_array; /* root of binary tree that stores dfa array */\r
-dfa_node *dfa_model_node;\r
-hash_list *dfa_hash[HASH_SIZE]; /* used to quickly find */\r
- /* desired dfa node */\r
-\r
-void \r
-#ifdef __USE_PROTOS\r
-make_dfa_model_node(int width)\r
-#else\r
-make_dfa_model_node(width)\r
-int width;\r
-#endif\r
-{\r
- register int i;\r
- dfa_model_node = (dfa_node*) malloc(sizeof(dfa_node)\r
- + sizeof(int)*width);\r
- dfa_model_node->node_no = -1; /* impossible value for real dfa node */\r
- dfa_model_node->dfa_set = 0;\r
- dfa_model_node->alternatives = FALSE;\r
- dfa_model_node->done = FALSE;\r
- dfa_model_node->nfa_states = empty;\r
- for(i = 0; i<width; i++){\r
- dfa_model_node->trans[i] = NIL_INDEX;\r
- }\r
-}\r
-\r
-\r
-/* adds a new nfa to the binary tree and returns a pointer to it */\r
-dfa_node *\r
-#ifdef __USE_PROTOS\r
-new_dfa_node(set nfa_states)\r
-#else\r
-new_dfa_node(nfa_states)\r
-set nfa_states;\r
-#endif\r
-{\r
- register int j;\r
- register dfa_node *t;\r
- static int dfa_size=0; /* elements dfa_array[] can hold */\r
-\r
- ++dfa_allocated;\r
- if (dfa_size<=dfa_allocated){\r
- /* need to redo array */\r
- if (!dfa_array){\r
- /* need some to do inital allocation */\r
- dfa_size=dfa_allocated+DFA_MIN;\r
- dfa_array=(dfa_node **) malloc(sizeof(dfa_node*)*\r
- dfa_size);\r
- }else{\r
- /* need more space */\r
- dfa_size=2*(dfa_allocated+1);\r
- dfa_array=(dfa_node **) realloc(dfa_array,\r
- sizeof(dfa_node*)*dfa_size);\r
- }\r
- }\r
- /* fill out entry in array */\r
- t = (dfa_node*) malloc(sizeof(nfa_node)+sizeof(int)*class_no);\r
- *t = *dfa_model_node;\r
- for (j=0; j<class_no; ++j)\r
- t->trans[j] = NIL_INDEX;\r
- t->node_no = dfa_allocated;\r
- t->nfa_states = set_dup(nfa_states);\r
- dfa_array[dfa_allocated] = t;\r
- return t;\r
-}\r
-\r
-\r
-/* past a pointer to the start start of the nfa graph\r
- * nfa_to_dfa convers this graph to dfa. The function returns\r
- * a pointer to the first dfa state.\r
- * NOTE: The function that prints out the table will have to figure out how\r
- * to find the other dfa states given the first dfa_state and the number of dfa\r
- * nodes allocated\r
- */\r
-dfa_node **\r
-#ifdef __USE_PROTOS\r
-nfa_to_dfa(nfa_node *start)\r
-#else\r
-nfa_to_dfa(start)\r
-nfa_node *start;\r
-#endif\r
-{\r
- register dfa_node *d_state, *trans_d_state;\r
- register int a;\r
- set t;\r
- int last_done;\r
- unsigned *nfa_list;\r
- unsigned *reach_list;\r
-\r
- reach_list = (unsigned *) malloc((2+nfa_allocated)*sizeof(unsigned));\r
- if (!start) return NULL;\r
- t = set_of(NFA_NO(start));\r
- _set_pdq(t,reach_list);\r
- closure(&t,reach_list);\r
- /* Make t a dfa state */\r
- d_state = dfastate(t);\r
- last_done = DFA_NO(d_state);\r
- \r
- do {\r
- /* Mark dfa state x as "done" */\r
- d_state->done = TRUE;\r
- nfa_list = set_pdq(d_state->nfa_states);\r
- for (a = 0; a<class_no; ++a) {\r
- /* Add NFA states reached by a from d_state */\r
- reach(nfa_list,a,reach_list);\r
- /* Were any states found? */\r
- if ((*reach_list)!=nil) {\r
- /* was t=empty; */\r
- set_free(t);\r
- /* yes, compute closure */\r
- closure(&t,reach_list);\r
- /* Make DFA state of it ... */\r
- trans_d_state = dfastate(t);\r
- /* And make transition x->t, labeled with a */\r
- d_state->trans[a] = DFA_NO(trans_d_state);\r
- d_state->alternatives = TRUE;\r
- }\r
- }\r
- free(nfa_list);\r
- ++last_done; /* move forward in queue */\r
- /* And so forth until nothing isn't done */\r
- d_state = DFA(last_done);\r
- } while (last_done<=dfa_allocated);\r
-\r
- free(reach_list);\r
- set_free(t);\r
-\r
- /* returns pointer to the array that holds the automaton */\r
- return dfa_array;\r
-}\r
-\r
-void \r
-#ifdef __USE_PROTOS\r
-clear_hash(void)\r
-#else\r
-clear_hash()\r
-#endif\r
-{\r
- register int i;\r
-\r
- for(i=0; i<HASH_SIZE; ++i)\r
- dfa_hash[i] = 0;\r
-}\r
-\r
-#if HASH_STAT\r
-void\r
-#ifdef __USE_PROTOS\r
-fprint_hash_stats(FILE *f)\r
-#else\r
-fprint_hash_stats(f)\r
-FILE *f;\r
-#endif\r
-{\r
- register hash_list *p;\r
- register int i,j;\r
- register total;\r
-\r
- total=0;\r
- for(i=0; i<HASH_SIZE; ++i){\r
- j=0;\r
- p = dfa_hash[i];\r
- while(p){\r
- ++j;\r
- p = p->next;\r
- }\r
- total+=j;\r
- fprintf(f,"bin[%d] has %d\n",i,j);\r
- }\r
- fprintf(f,"total = %d\n",total);\r
-}\r
-#endif\r
-\r
-/* Returns a pointer to a dfa node that has the same nfa nodes in it.\r
- * This may or maynot be a newly created node.\r
- */\r
-dfa_node *\r
-#ifdef __USE_PROTOS\r
-dfastate(set nfa_states)\r
-#else\r
-dfastate(nfa_states)\r
-set nfa_states;\r
-#endif\r
-{\r
- register hash_list *p;\r
- int bin;\r
-\r
- /* hash using set and see if it exists */\r
- bin = set_hash(nfa_states,HASH_SIZE);\r
- p = dfa_hash[bin];\r
- while(p && !set_equ(nfa_states,(p->node)->nfa_states)){\r
- p = p->next;\r
- }\r
- if(!p){\r
- /* next state to add to hash table */\r
- p = (hash_list*)malloc(sizeof(hash_list));\r
- p->node = new_dfa_node(nfa_states);\r
- p->next = dfa_hash[bin];\r
- dfa_hash[bin] = p;\r
- }\r
- return (p->node);\r
-}\r
-\r
-\r
-/* this reach assumes the closure has been done already on set */\r
-int \r
-#ifdef __USE_PROTOS\r
-reach(unsigned *nfa_list, register int a, unsigned *reach_list)\r
-#else\r
-reach(nfa_list, a, reach_list)\r
-unsigned *nfa_list;\r
-register int a;\r
-unsigned *reach_list;\r
-#endif\r
-{\r
- register unsigned *e;\r
- register nfa_node *node;\r
- int t=0;\r
-\r
- e = nfa_list;\r
- if (e){\r
- while (*e != nil){\r
- node = NFA(*e);\r
- if (set_el(a,node->label)){\r
- t=1;\r
- *reach_list=NFA_NO(node->trans[0]);\r
- ++reach_list;\r
- }\r
- ++e;\r
- }\r
- }\r
- *reach_list=nil;\r
- return t;\r
-}\r
-\r
-/* finds all the nodes that can be reached by epsilon transitions\r
- from the set of a nodes and returns puts them back in set b */\r
-set \r
-#ifdef __USE_PROTOS\r
-closure(set *b, unsigned *reach_list)\r
-#else\r
-closure(b, reach_list)\r
-set *b;\r
-unsigned *reach_list;\r
-#endif\r
-{\r
- register nfa_node *node,*n; /* current node being examined */\r
- register unsigned *e;\r
-\r
- ++operation_no;\r
-#if 0\r
- t = e = set_pdq(*b);\r
-#else\r
- e=reach_list;\r
-#endif\r
- while (*e != nil){\r
- node = NFA(*e);\r
- set_orel(NFA_NO(node),b);\r
- /* mark it done */\r
- node->nfa_set = operation_no;\r
- if ((n=node->trans[0]) != NIL_INDEX && set_nil(node->label) &&\r
- (n->nfa_set != operation_no)){\r
- /* put in b */\r
- set_orel(NFA_NO(n),b);\r
- close1(n,operation_no,b);\r
- }\r
- if ((n=node->trans[1]) != NIL_INDEX &&\r
- (n->nfa_set != operation_no)){\r
- /* put in b */\r
- set_orel(NFA_NO(node->trans[1]),b);\r
- close1(n,operation_no,b);\r
- }\r
- ++e;\r
- }\r
-#if 0\r
- free(t);\r
-#endif\r
- return *b;\r
-}\r
-\r
-#ifdef __USE_PROTOS\r
-void close1(nfa_node *node, int o, set *b)\r
-#else\r
-void close1(node,o,b)\r
-nfa_node *node;\r
-int o; /* marker to avoid cycles */\r
-set *b;\r
-#endif\r
-{\r
- register nfa_node *n; /* current node being examined */\r
-\r
- /* mark it done */\r
- node->nfa_set = o;\r
- if ((n=node->trans[0]) != NIL_INDEX && set_nil(node->label) &&\r
- (n->nfa_set != o)){\r
- /* put in b */\r
- set_orel(NFA_NO(n),b);\r
- close1(n,o,b);\r
- }\r
- if ((n=node->trans[1]) != NIL_INDEX &&\r
- (n->nfa_set != o)){\r
- /* put in b */\r
- set_orel(NFA_NO(node->trans[1]),b);\r
- close1(n,o,b);\r
- }\r
-}\r
projects / mirror_edk2.git / blobdiff