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