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