[mirror_edk2.git] / Tools / CodeTools / TianoTools / Pccts / dlg / relabel.c

/* This group of functions does the character class compression.\r
   It goes over the dfa and relabels the arcs with the partitions\r
   of characters in the NFA.  The partitions are stored in the\r
   array class.\r
\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 "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
int	class_no = CHAR_RANGE;	/* number of classes for labels */\r
int	first_el[CHAR_RANGE];	/* first element in each class partition */\r
set	class_sets[CHAR_RANGE];	/* array holds partitions from class */\r
				/* compression */\r
\r
/* goes through labels on NFA graph and partitions the characters into\r
 * character classes.  This reduces the amount of space required for each\r
 * dfa node, since only one arc is required each class instead of one arc\r
 * for each character\r
 * level:\r
 * 0 no compression done\r
 * 1 remove unused characters from classes\r
 * 2 compress equivalent characters into same class\r
 *\r
 * returns the number of character classes required\r
 */\r
#ifdef __USE_PROTOS\r
int relabel(nfa_node* start,int level)\r
#else\r
int relabel(start,level)\r
int level;\r
nfa_node *start;\r
#endif\r
{\r
	if (level){\r
		set_free(used_classes);	\r
		partition(start,level);\r
		label_with_classes(start);\r
	}else{\r
		/* classes equivalent to all characters in alphabet */\r
		class_no = CHAR_RANGE;\r
	}\r
	return class_no;\r
}\r
\r
/* makes character class sets for new labels */\r
#ifdef __USE_PROTOS\r
void partition(nfa_node* start,int level)\r
#else\r
void partition(start,level)\r
nfa_node	*start;	/* beginning of nfa graph */\r
int		level;	/* compression level to uses */\r
#endif\r
{\r
	set current_class;\r
	set unpart_chars;\r
	set temp;\r
\r
	unpart_chars = set_dup(used_chars);\r
#if 0\r
	/* EOF (-1+1) alway in class 0 */\r
	class_sets[0] = set_of(0);\r
	first_el[0] = 0;\r
	used_classes = set_of(0);\r
	temp = set_dif(unpart_chars, class_sets[0]);\r
	set_free(unpart_chars);\r
	unpart_chars = temp;\r
	class_no = 1;\r
#else\r
	class_no = 0;\r
#endif\r
	while (!set_nil(unpart_chars)){\r
		/* don't look for equivalent labels if c <= 1 */\r
		if (level <= 1){\r
			current_class = set_of(set_int(unpart_chars));\r
		}else{\r
			current_class = set_dup(unpart_chars);\r
			intersect_nfa_labels(start,&current_class);\r
		}\r
		set_orel(class_no,&used_classes);\r
		first_el[class_no] = set_int(current_class);\r
		class_sets[class_no] = current_class;\r
		temp = set_dif(unpart_chars,current_class);\r
		set_free(unpart_chars);\r
		unpart_chars = temp;\r
		++class_no;\r
	}\r
\r
	/* free unpart_chars -ATG 5/6/95 */\r
	set_free(unpart_chars);\r
\r
#if 0\r
	/* group all the other unused characters into a class */\r
	set_orel(class_no,&used_classes);\r
	first_el[class_no] = set_int(current_class);\r
	class_sets[class_no] = set_dif(normal_chars,used_chars);\r
	++class_no;\r
#endif\r
}\r
\r
\r
/* given pointer to beginning of graph and recursively walks it trying\r
 * to find a maximal partition.  This partion in returned in maximal_class\r
 */\r
#ifdef __USE_PROTOS\r
void intersect_nfa_labels(nfa_node* start,set* maximal_class)\r
#else\r
void intersect_nfa_labels(start,maximal_class)\r
nfa_node *start;\r
set *maximal_class;\r
#endif\r
{\r
	/* pick a new operation number */\r
	++operation_no;\r
	r_intersect(start,maximal_class);	\r
}\r
\r
#ifdef __USE_PROTOS\r
void r_intersect(nfa_node* start,set* maximal_class)\r
#else\r
void r_intersect(start,maximal_class)\r
nfa_node *start;\r
set * maximal_class;\r
#endif\r
{\r
	set temp;\r
\r
	if(start && start->nfa_set != operation_no)\r
	{\r
		start->nfa_set = operation_no;\r
		temp = set_and(*maximal_class,start->label);\r
		if (!set_nil(temp))\r
		{\r
			set_free(*maximal_class);\r
			*maximal_class = temp;\r
		}else{\r
			set_free(temp);\r
		}\r
		r_intersect(start->trans[0],maximal_class);\r
		r_intersect(start->trans[1],maximal_class);\r
	}\r
}\r
\r
\r
/* puts class labels in place of old character labels */\r
#ifdef __USE_PROTOS\r
void label_with_classes(nfa_node* start)\r
#else\r
void label_with_classes(start)\r
nfa_node *start;\r
#endif\r
{\r
	++operation_no;\r
	label_node(start);\r
}\r
\r
#ifdef __USE_PROTOS\r
void label_node(nfa_node *start)\r
#else\r
void label_node(start)\r
nfa_node *start;\r
#endif\r
{\r
	set new_label;\r
	register int i;\r
\r
	/* only do node if it hasn't been done before */\r
	if (start && start->nfa_set != operation_no){\r
		start->nfa_set = operation_no;\r
		new_label = empty;\r
		for (i = 0; i<class_no; ++i){\r
			/* if one element of class in old_label,\r
			   all elements are. */\r
			if (set_el(first_el[i],start->label))\r
				set_orel(i,&new_label);\r
		}\r
		set_free(start->label);\r
		start->label = new_label;\r
		/* do any nodes that can be reached from this one */\r
		label_node(start->trans[0]);\r
		label_node(start->trans[1]);\r
	}\r
}\r
Commit	Line	Data
878ddf1f	1	/* This group of functions does the character class compression.\r
	2	It goes over the dfa and relabels the arcs with the partitions\r
	3	of characters in the NFA. The partitions are stored in the\r
	4	array class.\r
	5	\r
	6	*\r
	7	* SOFTWARE RIGHTS\r
	8	*\r
	9	* We reserve no LEGAL rights to the Purdue Compiler Construction Tool\r
	10	* Set (PCCTS) -- PCCTS is in the public domain. An individual or\r
	11	* company may do whatever they wish with source code distributed with\r
	12	* PCCTS or the code generated by PCCTS, including the incorporation of\r
	13	* PCCTS, or its output, into commerical software.\r
	14	*\r
	15	* We encourage users to develop software with PCCTS. However, we do ask\r
	16	* that credit is given to us for developing PCCTS. By "credit",\r
	17	* we mean that if you incorporate our source code into one of your\r
	18	* programs (commercial product, research project, or otherwise) that you\r
	19	* acknowledge this fact somewhere in the documentation, research report,\r
	20	* etc... If you like PCCTS and have developed a nice tool with the\r
	21	* output, please mention that you developed it using PCCTS. In\r
	22	* addition, we ask that this header remain intact in our source code.\r
	23	* As long as these guidelines are kept, we expect to continue enhancing\r
	24	* this system and expect to make other tools available as they are\r
	25	* completed.\r
	26	*\r
	27	* DLG 1.33\r
	28	* Will Cohen\r
	29	* With mods by Terence Parr; AHPCRC, University of Minnesota\r
	30	* 1989-2001\r
	31	*/\r
	32	\r
	33	#include <stdio.h>\r
	34	#include "dlg.h"\r
	35	#ifdef MEMCHK\r
	36	#include "trax.h"\r
	37	#else\r
	38	#ifdef __STDC__\r
	39	#include <stdlib.h>\r
	40	#else\r
	41	#include <malloc.h>\r
	42	#endif /* __STDC__ */\r
	43	#endif\r
	44	\r
	45	int class_no = CHAR_RANGE; /* number of classes for labels */\r
	46	int first_el[CHAR_RANGE]; /* first element in each class partition */\r
	47	set class_sets[CHAR_RANGE]; /* array holds partitions from class */\r
	48	/* compression */\r
	49	\r
	50	/* goes through labels on NFA graph and partitions the characters into\r
	51	* character classes. This reduces the amount of space required for each\r
	52	* dfa node, since only one arc is required each class instead of one arc\r
	53	* for each character\r
	54	* level:\r
	55	* 0 no compression done\r
	56	* 1 remove unused characters from classes\r
	57	* 2 compress equivalent characters into same class\r
	58	*\r
	59	* returns the number of character classes required\r
	60	*/\r
	61	#ifdef __USE_PROTOS\r
	62	int relabel(nfa_node* start,int level)\r
	63	#else\r
	64	int relabel(start,level)\r
65	int level;\r
66	nfa_node *start;\r
67	#endif\r
68	{\r
69	if (level){\r
70	set_free(used_classes); \r
71	partition(start,level);\r
72	label_with_classes(start);\r
73	}else{\r
74	/* classes equivalent to all characters in alphabet */\r
75	class_no = CHAR_RANGE;\r
76	}\r
77	return class_no;\r
78	}\r
79	\r
80	/* makes character class sets for new labels */\r
81	#ifdef __USE_PROTOS\r
82	void partition(nfa_node* start,int level)\r
83	#else\r
84	void partition(start,level)\r
85	nfa_node start; / beginning of nfa graph */\r
86	int level; /* compression level to uses */\r
87	#endif\r
88	{\r
89	set current_class;\r
90	set unpart_chars;\r
91	set temp;\r
92	\r
93	unpart_chars = set_dup(used_chars);\r
94	#if 0\r
95	/* EOF (-1+1) alway in class 0 */\r
96	class_sets[0] = set_of(0);\r
97	first_el[0] = 0;\r
98	used_classes = set_of(0);\r
99	temp = set_dif(unpart_chars, class_sets[0]);\r
100	set_free(unpart_chars);\r
101	unpart_chars = temp;\r
102	class_no = 1;\r
103	#else\r
104	class_no = 0;\r
105	#endif\r
106	while (!set_nil(unpart_chars)){\r
107	/* don't look for equivalent labels if c <= 1 */\r
108	if (level <= 1){\r
109	current_class = set_of(set_int(unpart_chars));\r
110	}else{\r
111	current_class = set_dup(unpart_chars);\r
112	intersect_nfa_labels(start,&current_class);\r
113	}\r
114	set_orel(class_no,&used_classes);\r
115	first_el[class_no] = set_int(current_class);\r
116	class_sets[class_no] = current_class;\r
117	temp = set_dif(unpart_chars,current_class);\r
118	set_free(unpart_chars);\r
119	unpart_chars = temp;\r
120	++class_no;\r
121	}\r
122	\r
123	/* free unpart_chars -ATG 5/6/95 */\r
124	set_free(unpart_chars);\r
125	\r
126	#if 0\r
127	/* group all the other unused characters into a class */\r
128	set_orel(class_no,&used_classes);\r
129	first_el[class_no] = set_int(current_class);\r
130	class_sets[class_no] = set_dif(normal_chars,used_chars);\r
131	++class_no;\r
132	#endif\r
133	}\r
134	\r
135	\r
136	/* given pointer to beginning of graph and recursively walks it trying\r
137	* to find a maximal partition. This partion in returned in maximal_class\r
138	*/\r
139	#ifdef __USE_PROTOS\r
140	void intersect_nfa_labels(nfa_node* start,set* maximal_class)\r
141	#else\r
142	void intersect_nfa_labels(start,maximal_class)\r
143	nfa_node *start;\r
144	set *maximal_class;\r
145	#endif\r
146	{\r
147	/* pick a new operation number */\r
148	++operation_no;\r
149	r_intersect(start,maximal_class); \r
150	}\r
151	\r
152	#ifdef __USE_PROTOS\r
153	void r_intersect(nfa_node* start,set* maximal_class)\r
154	#else\r
155	void r_intersect(start,maximal_class)\r
156	nfa_node *start;\r
157	set * maximal_class;\r
158	#endif\r
159	{\r
160	set temp;\r
161	\r
162	if(start && start->nfa_set != operation_no)\r
163	{\r
164	start->nfa_set = operation_no;\r
165	temp = set_and(*maximal_class,start->label);\r
166	if (!set_nil(temp))\r
167	{\r
168	set_free(*maximal_class);\r
169	*maximal_class = temp;\r
170	}else{\r
171	set_free(temp);\r
172	}\r
173	r_intersect(start->trans[0],maximal_class);\r
174	r_intersect(start->trans[1],maximal_class);\r
175	}\r
176	}\r
177	\r
178	\r
179	/* puts class labels in place of old character labels */\r
180	#ifdef __USE_PROTOS\r
181	void label_with_classes(nfa_node* start)\r
182	#else\r
183	void label_with_classes(start)\r
184	nfa_node *start;\r
185	#endif\r
186	{\r
187	++operation_no;\r
188	label_node(start);\r
189	}\r
190	\r
191	#ifdef __USE_PROTOS\r
192	void label_node(nfa_node *start)\r
193	#else\r
194	void label_node(start)\r
195	nfa_node *start;\r
196	#endif\r
197	{\r
198	set new_label;\r
199	register int i;\r
200	\r
201	/* only do node if it hasn't been done before */\r
202	if (start && start->nfa_set != operation_no){\r
203	start->nfa_set = operation_no;\r
204	new_label = empty;\r
205	for (i = 0; i<class_no; ++i){\r
206	/* if one element of class in old_label,\r
207	all elements are. */\r
208	if (set_el(first_el[i],start->label))\r
209	set_orel(i,&new_label);\r
210	}\r
211	set_free(start->label);\r
212	start->label = new_label;\r
213	/* do any nodes that can be reached from this one */\r
214	label_node(start->trans[0]);\r
215	label_node(start->trans[1]);\r
216	}\r
217	}\r