[mirror_edk2.git] / Tools / CodeTools / Source / Pccts / dlg / automata.c

/* 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
Commit	Line	Data
878ddf1f	1	/* Automata conversion functions for DLG\r
	2	*\r
	3	* SOFTWARE RIGHTS\r
	4	*\r
	5	* We reserve no LEGAL rights to the Purdue Compiler Construction Tool\r
	6	* Set (PCCTS) -- PCCTS is in the public domain. An individual or\r
	7	* company may do whatever they wish with source code distributed with\r
	8	* PCCTS or the code generated by PCCTS, including the incorporation of\r
	9	* PCCTS, or its output, into commerical software.\r
	10	*\r
	11	* We encourage users to develop software with PCCTS. However, we do ask\r
	12	* that credit is given to us for developing PCCTS. By "credit",\r
	13	* we mean that if you incorporate our source code into one of your\r
	14	* programs (commercial product, research project, or otherwise) that you\r
	15	* acknowledge this fact somewhere in the documentation, research report,\r
	16	* etc... If you like PCCTS and have developed a nice tool with the\r
	17	* output, please mention that you developed it using PCCTS. In\r
	18	* addition, we ask that this header remain intact in our source code.\r
	19	* As long as these guidelines are kept, we expect to continue enhancing\r
	20	* this system and expect to make other tools available as they are\r
	21	* completed.\r
	22	*\r
	23	* DLG 1.33\r
	24	* Will Cohen\r
	25	* With mods by Terence Parr; AHPCRC, University of Minnesota\r
	26	* 1989-2001\r
	27	*/\r
	28	\r
	29	#include <stdio.h>\r
	30	#include "pcctscfg.h"\r
	31	#include "dlg.h"\r
	32	#ifdef MEMCHK\r
	33	#include "trax.h"\r
	34	#else\r
	35	#ifdef __STDC__\r
	36	#include <stdlib.h>\r
	37	#else\r
	38	#include <malloc.h>\r
	39	#endif /* __STDC__ */\r
	40	#endif\r
	41	\r
	42	#define hash_list struct _hash_list_\r
	43	hash_list{\r
	44	hash_list next; / next thing in list */\r
	45	dfa_node *node;\r
	46	};\r
	47	\r
	48	int dfa_allocated = 0; /* keeps track of number of dfa nodes */\r
	49	dfa_node *dfa_array; / root of binary tree that stores dfa array */\r
	50	dfa_node *dfa_model_node;\r
	51	hash_list dfa_hash[HASH_SIZE]; / used to quickly find */\r
	52	/* desired dfa node */\r
	53	\r
	54	void \r
	55	#ifdef __USE_PROTOS\r
	56	make_dfa_model_node(int width)\r
	57	#else\r
	58	make_dfa_model_node(width)\r
	59	int width;\r
	60	#endif\r
	61	{\r
	62	register int i;\r
	63	dfa_model_node = (dfa_node*) malloc(sizeof(dfa_node)\r
	64	+ sizeof(int)*width);\r
65	dfa_model_node->node_no = -1; /* impossible value for real dfa node */\r
66	dfa_model_node->dfa_set = 0;\r
67	dfa_model_node->alternatives = FALSE;\r
68	dfa_model_node->done = FALSE;\r
69	dfa_model_node->nfa_states = empty;\r
70	for(i = 0; i<width; i++){\r
71	dfa_model_node->trans[i] = NIL_INDEX;\r
72	}\r
73	}\r
74	\r
75	\r
76	/* adds a new nfa to the binary tree and returns a pointer to it */\r
77	dfa_node *\r
78	#ifdef __USE_PROTOS\r
79	new_dfa_node(set nfa_states)\r
80	#else\r
81	new_dfa_node(nfa_states)\r
82	set nfa_states;\r
83	#endif\r
84	{\r
85	register int j;\r
86	register dfa_node *t;\r
87	static int dfa_size=0; /* elements dfa_array[] can hold */\r
88	\r
89	++dfa_allocated;\r
90	if (dfa_size<=dfa_allocated){\r
91	/* need to redo array */\r
92	if (!dfa_array){\r
93	/* need some to do inital allocation */\r
94	dfa_size=dfa_allocated+DFA_MIN;\r
95	dfa_array=(dfa_node *) malloc(sizeof(dfa_node)*\r
96	dfa_size);\r
97	}else{\r
98	/* need more space */\r
99	dfa_size=2*(dfa_allocated+1);\r
100	dfa_array=(dfa_node **) realloc(dfa_array,\r
101	sizeof(dfa_node)dfa_size);\r
102	}\r
103	}\r
104	/* fill out entry in array */\r
105	t = (dfa_node) malloc(sizeof(nfa_node)+sizeof(int)class_no);\r
106	t = dfa_model_node;\r
107	for (j=0; j<class_no; ++j)\r
108	t->trans[j] = NIL_INDEX;\r
109	t->node_no = dfa_allocated;\r
110	t->nfa_states = set_dup(nfa_states);\r
111	dfa_array[dfa_allocated] = t;\r
112	return t;\r
113	}\r
114	\r
115	\r
116	/* past a pointer to the start start of the nfa graph\r
117	* nfa_to_dfa convers this graph to dfa. The function returns\r
118	* a pointer to the first dfa state.\r
119	* NOTE: The function that prints out the table will have to figure out how\r
120	* to find the other dfa states given the first dfa_state and the number of dfa\r
121	* nodes allocated\r
122	*/\r
123	dfa_node **\r
124	#ifdef __USE_PROTOS\r
125	nfa_to_dfa(nfa_node *start)\r
126	#else\r
127	nfa_to_dfa(start)\r
128	nfa_node *start;\r
129	#endif\r
130	{\r
131	register dfa_node d_state, trans_d_state;\r
132	register int a;\r
133	set t;\r
134	int last_done;\r
135	unsigned *nfa_list;\r
136	unsigned *reach_list;\r
137	\r
138	reach_list = (unsigned ) malloc((2+nfa_allocated)sizeof(unsigned));\r
139	if (!start) return NULL;\r
140	t = set_of(NFA_NO(start));\r
141	_set_pdq(t,reach_list);\r
142	closure(&t,reach_list);\r
143	/* Make t a dfa state */\r
144	d_state = dfastate(t);\r
145	last_done = DFA_NO(d_state);\r
146	\r
147	do {\r
148	/* Mark dfa state x as "done" */\r
149	d_state->done = TRUE;\r
150	nfa_list = set_pdq(d_state->nfa_states);\r
151	for (a = 0; a<class_no; ++a) {\r
152	/* Add NFA states reached by a from d_state */\r
153	reach(nfa_list,a,reach_list);\r
154	/* Were any states found? */\r
155	if ((*reach_list)!=nil) {\r
156	/* was t=empty; */\r
157	set_free(t);\r
158	/* yes, compute closure */\r
159	closure(&t,reach_list);\r
160	/* Make DFA state of it ... */\r
161	trans_d_state = dfastate(t);\r
162	/* And make transition x->t, labeled with a */\r
163	d_state->trans[a] = DFA_NO(trans_d_state);\r
164	d_state->alternatives = TRUE;\r
165	}\r
166	}\r
167	free(nfa_list);\r
168	++last_done; /* move forward in queue */\r
169	/* And so forth until nothing isn't done */\r
170	d_state = DFA(last_done);\r
171	} while (last_done<=dfa_allocated);\r
172	\r
173	free(reach_list);\r
174	set_free(t);\r
175	\r
176	/* returns pointer to the array that holds the automaton */\r
177	return dfa_array;\r
178	}\r
179	\r
180	void \r
181	#ifdef __USE_PROTOS\r
182	clear_hash(void)\r
183	#else\r
184	clear_hash()\r
185	#endif\r
186	{\r
187	register int i;\r
188	\r
189	for(i=0; i<HASH_SIZE; ++i)\r
190	dfa_hash[i] = 0;\r
191	}\r
192	\r
193	#if HASH_STAT\r
194	void\r
195	#ifdef __USE_PROTOS\r
196	fprint_hash_stats(FILE *f)\r
197	#else\r
198	fprint_hash_stats(f)\r
199	FILE *f;\r
200	#endif\r
201	{\r
202	register hash_list *p;\r
203	register int i,j;\r
204	register total;\r
205	\r
206	total=0;\r
207	for(i=0; i<HASH_SIZE; ++i){\r
208	j=0;\r
209	p = dfa_hash[i];\r
210	while(p){\r
211	++j;\r
212	p = p->next;\r
213	}\r
214	total+=j;\r
215	fprintf(f,"bin[%d] has %d\n",i,j);\r
216	}\r
217	fprintf(f,"total = %d\n",total);\r
218	}\r
219	#endif\r
220	\r
221	/* Returns a pointer to a dfa node that has the same nfa nodes in it.\r
222	* This may or maynot be a newly created node.\r
223	*/\r
224	dfa_node *\r
225	#ifdef __USE_PROTOS\r
226	dfastate(set nfa_states)\r
227	#else\r
228	dfastate(nfa_states)\r
229	set nfa_states;\r
230	#endif\r
231	{\r
232	register hash_list *p;\r
233	int bin;\r
234	\r
235	/* hash using set and see if it exists */\r
236	bin = set_hash(nfa_states,HASH_SIZE);\r
237	p = dfa_hash[bin];\r
238	while(p && !set_equ(nfa_states,(p->node)->nfa_states)){\r
239	p = p->next;\r
240	}\r
241	if(!p){\r
242	/* next state to add to hash table */\r
243	p = (hash_list*)malloc(sizeof(hash_list));\r
244	p->node = new_dfa_node(nfa_states);\r
245	p->next = dfa_hash[bin];\r
246	dfa_hash[bin] = p;\r
247	}\r
248	return (p->node);\r
249	}\r
250	\r
251	\r
252	/* this reach assumes the closure has been done already on set */\r
253	int \r
254	#ifdef __USE_PROTOS\r
255	reach(unsigned nfa_list, register int a, unsigned reach_list)\r
256	#else\r
257	reach(nfa_list, a, reach_list)\r
258	unsigned *nfa_list;\r
259	register int a;\r
260	unsigned *reach_list;\r
261	#endif\r
262	{\r
263	register unsigned *e;\r
264	register nfa_node *node;\r
265	int t=0;\r
266	\r
267	e = nfa_list;\r
268	if (e){\r
269	while (*e != nil){\r
270	node = NFA(*e);\r
271	if (set_el(a,node->label)){\r
272	t=1;\r
273	*reach_list=NFA_NO(node->trans[0]);\r
274	++reach_list;\r
275	}\r
276	++e;\r
277	}\r
278	}\r
279	*reach_list=nil;\r
280	return t;\r
281	}\r
282	\r
283	/* finds all the nodes that can be reached by epsilon transitions\r
284	from the set of a nodes and returns puts them back in set b */\r
285	set \r
286	#ifdef __USE_PROTOS\r
287	closure(set b, unsigned reach_list)\r
288	#else\r
289	closure(b, reach_list)\r
290	set *b;\r
291	unsigned *reach_list;\r
292	#endif\r
293	{\r
294	register nfa_node node,n; /* current node being examined */\r
295	register unsigned *e;\r
296	\r
297	++operation_no;\r
298	#if 0\r
299	t = e = set_pdq(*b);\r
300	#else\r
301	e=reach_list;\r
302	#endif\r
303	while (*e != nil){\r
304	node = NFA(*e);\r
305	set_orel(NFA_NO(node),b);\r
306	/* mark it done */\r
307	node->nfa_set = operation_no;\r
308	if ((n=node->trans[0]) != NIL_INDEX && set_nil(node->label) &&\r
309	(n->nfa_set != operation_no)){\r
310	/* put in b */\r
311	set_orel(NFA_NO(n),b);\r
312	close1(n,operation_no,b);\r
313	}\r
314	if ((n=node->trans[1]) != NIL_INDEX &&\r
315	(n->nfa_set != operation_no)){\r
316	/* put in b */\r
317	set_orel(NFA_NO(node->trans[1]),b);\r
318	close1(n,operation_no,b);\r
319	}\r
320	++e;\r
321	}\r
322	#if 0\r
323	free(t);\r
324	#endif\r
325	return *b;\r
326	}\r
327	\r
328	#ifdef __USE_PROTOS\r
329	void close1(nfa_node node, int o, set b)\r
330	#else\r
331	void close1(node,o,b)\r
332	nfa_node *node;\r
333	int o; /* marker to avoid cycles */\r
334	set *b;\r
335	#endif\r
336	{\r
337	register nfa_node n; / current node being examined */\r
338	\r
339	/* mark it done */\r
340	node->nfa_set = o;\r
341	if ((n=node->trans[0]) != NIL_INDEX && set_nil(node->label) &&\r
342	(n->nfa_set != o)){\r
343	/* put in b */\r
344	set_orel(NFA_NO(n),b);\r
345	close1(n,o,b);\r
346	}\r
347	if ((n=node->trans[1]) != NIL_INDEX &&\r
348	(n->nfa_set != o)){\r
349	/* put in b */\r
350	set_orel(NFA_NO(node->trans[1]),b);\r
351	close1(n,o,b);\r
352	}\r
353	}\r