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