diff options
Diffstat (limited to 'BaseTools/Source/C/VfrCompile/Pccts/dlg/automata.c')
| -rw-r--r-- | BaseTools/Source/C/VfrCompile/Pccts/dlg/automata.c | 353 |
1 files changed, 0 insertions, 353 deletions
diff --git a/BaseTools/Source/C/VfrCompile/Pccts/dlg/automata.c b/BaseTools/Source/C/VfrCompile/Pccts/dlg/automata.c deleted file mode 100644 index d6d5d7809d..0000000000 --- a/BaseTools/Source/C/VfrCompile/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 <stdio.h>
-#include "pcctscfg.h"
-#include "dlg.h"
-#ifdef MEMCHK
-#include "trax.h"
-#else
-#ifdef __STDC__
-#include <stdlib.h>
-#else
-#include <malloc.h>
-#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; i<width; i++){
- dfa_model_node->trans[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; j<class_no; ++j)
- t->trans[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; a<class_no; ++a) {
- /* Add NFA states reached by a from d_state */
- reach(nfa_list,a,reach_list);
- /* Were any states found? */
- if ((*reach_list)!=nil) {
- /* was t=empty; */
- set_free(t);
- /* yes, compute closure */
- closure(&t,reach_list);
- /* Make DFA state of it ... */
- trans_d_state = dfastate(t);
- /* And make transition x->t, 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; i<HASH_SIZE; ++i)
- dfa_hash[i] = 0;
-}
-
-#if HASH_STAT
-void
-#ifdef __USE_PROTOS
-fprint_hash_stats(FILE *f)
-#else
-fprint_hash_stats(f)
-FILE *f;
-#endif
-{
- register hash_list *p;
- register int i,j;
- register total;
-
- total=0;
- for(i=0; i<HASH_SIZE; ++i){
- j=0;
- p = dfa_hash[i];
- while(p){
- ++j;
- p = p->next;
- }
- 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);
- }
-}
|