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