automata.c 8.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353
  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. #include <stdio.h>
  29. #include "pcctscfg.h"
  30. #include "dlg.h"
  31. #ifdef MEMCHK
  32. #include "trax.h"
  33. #else
  34. #ifdef __STDC__
  35. #include <stdlib.h>
  36. #else
  37. #include <malloc.h>
  38. #endif /* __STDC__ */
  39. #endif
  40. #define hash_list struct _hash_list_
  41. hash_list{
  42. hash_list *next; /* next thing in list */
  43. dfa_node *node;
  44. };
  45. int dfa_allocated = 0; /* keeps track of number of dfa nodes */
  46. dfa_node **dfa_array; /* root of binary tree that stores dfa array */
  47. dfa_node *dfa_model_node;
  48. hash_list *dfa_hash[HASH_SIZE]; /* used to quickly find */
  49. /* desired dfa node */
  50. void
  51. #ifdef __USE_PROTOS
  52. make_dfa_model_node(int width)
  53. #else
  54. make_dfa_model_node(width)
  55. int width;
  56. #endif
  57. {
  58. register int i;
  59. dfa_model_node = (dfa_node*) malloc(sizeof(dfa_node)
  60. + sizeof(int)*width);
  61. dfa_model_node->node_no = -1; /* impossible value for real dfa node */
  62. dfa_model_node->dfa_set = 0;
  63. dfa_model_node->alternatives = FALSE;
  64. dfa_model_node->done = FALSE;
  65. dfa_model_node->nfa_states = empty;
  66. for(i = 0; i<width; i++){
  67. dfa_model_node->trans[i] = NIL_INDEX;
  68. }
  69. }
  70. /* adds a new nfa to the binary tree and returns a pointer to it */
  71. dfa_node *
  72. #ifdef __USE_PROTOS
  73. new_dfa_node(set nfa_states)
  74. #else
  75. new_dfa_node(nfa_states)
  76. set nfa_states;
  77. #endif
  78. {
  79. register int j;
  80. register dfa_node *t;
  81. static int dfa_size=0; /* elements dfa_array[] can hold */
  82. ++dfa_allocated;
  83. if (dfa_size<=dfa_allocated){
  84. /* need to redo array */
  85. if (!dfa_array){
  86. /* need some to do initial allocation */
  87. dfa_size=dfa_allocated+DFA_MIN;
  88. dfa_array=(dfa_node **) malloc(sizeof(dfa_node*)*
  89. dfa_size);
  90. }else{
  91. /* need more space */
  92. dfa_size=2*(dfa_allocated+1);
  93. dfa_array=(dfa_node **) realloc(dfa_array,
  94. sizeof(dfa_node*)*dfa_size);
  95. }
  96. }
  97. /* fill out entry in array */
  98. t = (dfa_node*) malloc(sizeof(nfa_node)+sizeof(int)*class_no);
  99. *t = *dfa_model_node;
  100. for (j=0; j<class_no; ++j)
  101. t->trans[j] = NIL_INDEX;
  102. t->node_no = dfa_allocated;
  103. t->nfa_states = set_dup(nfa_states);
  104. dfa_array[dfa_allocated] = t;
  105. return t;
  106. }
  107. /* past a pointer to the start of the nfa graph
  108. * nfa_to_dfa convers this graph to dfa. The function returns
  109. * a pointer to the first dfa state.
  110. * NOTE: The function that prints out the table will have to figure out how
  111. * to find the other dfa states given the first dfa_state and the number of dfa
  112. * nodes allocated
  113. */
  114. dfa_node **
  115. #ifdef __USE_PROTOS
  116. nfa_to_dfa(nfa_node *start)
  117. #else
  118. nfa_to_dfa(start)
  119. nfa_node *start;
  120. #endif
  121. {
  122. register dfa_node *d_state, *trans_d_state;
  123. register int a;
  124. set t;
  125. int last_done;
  126. unsigned *nfa_list;
  127. unsigned *reach_list;
  128. reach_list = (unsigned *) malloc((2+nfa_allocated)*sizeof(unsigned));
  129. if (!start) return NULL;
  130. t = set_of(NFA_NO(start));
  131. _set_pdq(t,reach_list);
  132. closure(&t,reach_list);
  133. /* Make t a dfa state */
  134. d_state = dfastate(t);
  135. last_done = DFA_NO(d_state);
  136. do {
  137. /* Mark dfa state x as "done" */
  138. d_state->done = TRUE;
  139. nfa_list = set_pdq(d_state->nfa_states);
  140. for (a = 0; a<class_no; ++a) {
  141. /* Add NFA states reached by a from d_state */
  142. reach(nfa_list,a,reach_list);
  143. /* Were any states found? */
  144. if ((*reach_list)!=nil) {
  145. /* was t=empty; */
  146. set_free(t);
  147. /* yes, compute closure */
  148. closure(&t,reach_list);
  149. /* Make DFA state of it ... */
  150. trans_d_state = dfastate(t);
  151. /* And make transition x->t, labeled with a */
  152. d_state->trans[a] = DFA_NO(trans_d_state);
  153. d_state->alternatives = TRUE;
  154. }
  155. }
  156. free(nfa_list);
  157. ++last_done; /* move forward in queue */
  158. /* And so forth until nothing isn't done */
  159. d_state = DFA(last_done);
  160. } while (last_done<=dfa_allocated);
  161. free(reach_list);
  162. set_free(t);
  163. /* returns pointer to the array that holds the automaton */
  164. return dfa_array;
  165. }
  166. void
  167. #ifdef __USE_PROTOS
  168. clear_hash(void)
  169. #else
  170. clear_hash()
  171. #endif
  172. {
  173. register int i;
  174. for(i=0; i<HASH_SIZE; ++i)
  175. dfa_hash[i] = 0;
  176. }
  177. #if HASH_STAT
  178. void
  179. #ifdef __USE_PROTOS
  180. fprint_hash_stats(FILE *f)
  181. #else
  182. fprint_hash_stats(f)
  183. FILE *f;
  184. #endif
  185. {
  186. register hash_list *p;
  187. register int i,j;
  188. register total;
  189. total=0;
  190. for(i=0; i<HASH_SIZE; ++i){
  191. j=0;
  192. p = dfa_hash[i];
  193. while(p){
  194. ++j;
  195. p = p->next;
  196. }
  197. total+=j;
  198. fprintf(f,"bin[%d] has %d\n",i,j);
  199. }
  200. fprintf(f,"total = %d\n",total);
  201. }
  202. #endif
  203. /* Returns a pointer to a dfa node that has the same nfa nodes in it.
  204. * This may or may not be a newly created node.
  205. */
  206. dfa_node *
  207. #ifdef __USE_PROTOS
  208. dfastate(set nfa_states)
  209. #else
  210. dfastate(nfa_states)
  211. set nfa_states;
  212. #endif
  213. {
  214. register hash_list *p;
  215. int bin;
  216. /* hash using set and see if it exists */
  217. bin = set_hash(nfa_states,HASH_SIZE);
  218. p = dfa_hash[bin];
  219. while(p && !set_equ(nfa_states,(p->node)->nfa_states)){
  220. p = p->next;
  221. }
  222. if(!p){
  223. /* next state to add to hash table */
  224. p = (hash_list*)malloc(sizeof(hash_list));
  225. p->node = new_dfa_node(nfa_states);
  226. p->next = dfa_hash[bin];
  227. dfa_hash[bin] = p;
  228. }
  229. return (p->node);
  230. }
  231. /* this reach assumes the closure has been done already on set */
  232. int
  233. #ifdef __USE_PROTOS
  234. reach(unsigned *nfa_list, register int a, unsigned *reach_list)
  235. #else
  236. reach(nfa_list, a, reach_list)
  237. unsigned *nfa_list;
  238. register int a;
  239. unsigned *reach_list;
  240. #endif
  241. {
  242. register unsigned *e;
  243. register nfa_node *node;
  244. int t=0;
  245. e = nfa_list;
  246. if (e){
  247. while (*e != nil){
  248. node = NFA(*e);
  249. if (set_el(a,node->label)){
  250. t=1;
  251. *reach_list=NFA_NO(node->trans[0]);
  252. ++reach_list;
  253. }
  254. ++e;
  255. }
  256. }
  257. *reach_list=nil;
  258. return t;
  259. }
  260. /* finds all the nodes that can be reached by epsilon transitions
  261. from the set of a nodes and returns puts them back in set b */
  262. set
  263. #ifdef __USE_PROTOS
  264. closure(set *b, unsigned *reach_list)
  265. #else
  266. closure(b, reach_list)
  267. set *b;
  268. unsigned *reach_list;
  269. #endif
  270. {
  271. register nfa_node *node,*n; /* current node being examined */
  272. register unsigned *e;
  273. ++operation_no;
  274. #if 0
  275. t = e = set_pdq(*b);
  276. #else
  277. e=reach_list;
  278. #endif
  279. while (*e != nil){
  280. node = NFA(*e);
  281. set_orel(NFA_NO(node),b);
  282. /* mark it done */
  283. node->nfa_set = operation_no;
  284. if ((n=node->trans[0]) != NIL_INDEX && set_nil(node->label) &&
  285. (n->nfa_set != operation_no)){
  286. /* put in b */
  287. set_orel(NFA_NO(n),b);
  288. close1(n,operation_no,b);
  289. }
  290. if ((n=node->trans[1]) != NIL_INDEX &&
  291. (n->nfa_set != operation_no)){
  292. /* put in b */
  293. set_orel(NFA_NO(node->trans[1]),b);
  294. close1(n,operation_no,b);
  295. }
  296. ++e;
  297. }
  298. #if 0
  299. free(t);
  300. #endif
  301. return *b;
  302. }
  303. #ifdef __USE_PROTOS
  304. void close1(nfa_node *node, int o, set *b)
  305. #else
  306. void close1(node,o,b)
  307. nfa_node *node;
  308. int o; /* marker to avoid cycles */
  309. set *b;
  310. #endif
  311. {
  312. register nfa_node *n; /* current node being examined */
  313. /* mark it done */
  314. node->nfa_set = o;
  315. if ((n=node->trans[0]) != NIL_INDEX && set_nil(node->label) &&
  316. (n->nfa_set != o)){
  317. /* put in b */
  318. set_orel(NFA_NO(n),b);
  319. close1(n,o,b);
  320. }
  321. if ((n=node->trans[1]) != NIL_INDEX &&
  322. (n->nfa_set != o)){
  323. /* put in b */
  324. set_orel(NFA_NO(node->trans[1]),b);
  325. close1(n,o,b);
  326. }
  327. }