X-Git-Url: https://pd.if.org/git/?p=pccts;a=blobdiff_plain;f=dlg%2Fautomata.c;fp=dlg%2Fautomata.c;h=b912613a8db5fa666d9dfc7c917ae0183166c64b;hp=0000000000000000000000000000000000000000;hb=dbdf5b07e8658f27641734bd3fad465de01650e5;hpb=a5858ad3d85781b0412eac53847e35a1bf24e70d

diff --git a/dlg/automata.c b/dlg/automata.c
new file mode 100755
index 0000000..b912613
--- /dev/null
+++ b/dlg/automata.c
@@ -0,0 +1,309 @@
+/* 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-1995
+ */
+
+#include <stdio.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
+make_dfa_model_node(width)
+int width;
+{
+	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 *new_dfa_node(nfa_states)
+set nfa_states;
+{
+	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 **nfa_to_dfa(start)
+nfa_node *start;
+{
+	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;
+}
+
+clear_hash()
+{
+	register int i;
+
+	for(i=0; i<HASH_SIZE; ++i)
+		dfa_hash[i] = 0;
+}
+
+#if HASH_STAT
+fprint_hash_stats(f)
+FILE *f;
+{
+	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 *dfastate(nfa_states)
+set nfa_states;		/* list of nfa states it could be */
+{
+	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 reach(nfa_list,a,reach_list)
+unsigned *nfa_list;
+register int a;
+unsigned *reach_list;
+{
+	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 closure(b,reach_list)
+set *b;
+unsigned *reach_list;
+{
+	register nfa_node *node,*n;	/* current node being examined */
+	register unsigned *t,*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;
+}
+
+close1(node,o,b)
+nfa_node *node;
+int o;	/* marker to avoid cycles */
+set *b;
+{
+	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);
+	}
+}