Check In tool source code based on Build tool project revision r1655.

git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@8964 6f19259b-4bc3-4df7-8a09-765794883524

1 files changed, 353 insertions, 0 deletions

diff --git a/BaseTools/Source/C/VfrCompile/Pccts/dlg/automata.c b/BaseTools/Source/C/VfrCompile/Pccts/dlg/automata.c
new file mode 100644
index 0000000000..d6d5d7809d
--- /dev/null
+++ b/BaseTools/Source/C/VfrCompile/Pccts/dlg/automata.c
@@ -0,0 +1,353 @@
+/* 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);

+	}

+}