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
relabel(nfa_node * start,int level)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
partition(nfa_node * start,int level)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
intersect_nfa_labels(nfa_node * start,set * maximal_class)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
r_intersect(nfa_node * start,set * maximal_class)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
label_with_classes(nfa_node * start)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
label_node(nfa_node * start)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