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