]>
Commit | Line | Data |
---|---|---|
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 |