relabel.c 5.8 KB

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