]>
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 |