1 /* $OpenBSD: ecs.c,v 1.6 2003/06/04 17:34:44 millert Exp $ */
2
3 /* ecs - equivalence class routines */
4
5 /*-
6 * Copyright (c) 1990 The Regents of the University of California.
7 * All rights reserved.
8 *
9 * This code is derived from software contributed to Berkeley by
10 * Vern Paxson.
11 *
12 * The United States Government has rights in this work pursuant
13 * to contract no. DE-AC03-76SF00098 between the United States
14 * Department of Energy and the University of California.
15 *
16 * Redistribution and use in source and binary forms, with or without
17 * modification, are permitted provided that the following conditions
18 * are met:
19 *
20 * 1. Redistributions of source code must retain the above copyright
21 * notice, this list of conditions and the following disclaimer.
22 * 2. Redistributions in binary form must reproduce the above copyright
23 * notice, this list of conditions and the following disclaimer in the
24 * documentation and/or other materials provided with the distribution.
25 *
26 * Neither the name of the University nor the names of its contributors
27 * may be used to endorse or promote products derived from this software
28 * without specific prior written permission.
29 *
30 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
31 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
32 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
33 * PURPOSE.
34 */
35
36 /* $Header: /cvs/src/usr.bin/lex/ecs.c,v 1.6 2003/06/04 17:34:44 millert Exp $ */
37
38 #include "flexdef.h"
39
40 /* ccl2ecl - convert character classes to set of equivalence classes */
41
ccl2ecl()42 void ccl2ecl()
43 {
44 int i, ich, newlen, cclp, ccls, cclmec;
45
46 for ( i = 1; i <= lastccl; ++i )
47 {
48 /* We loop through each character class, and for each character
49 * in the class, add the character's equivalence class to the
50 * new "character" class we are creating. Thus when we are all
51 * done, character classes will really consist of collections
52 * of equivalence classes
53 */
54
55 newlen = 0;
56 cclp = cclmap[i];
57
58 for ( ccls = 0; ccls < ccllen[i]; ++ccls )
59 {
60 ich = ccltbl[cclp + ccls];
61 cclmec = ecgroup[ich];
62
63 if ( cclmec > 0 )
64 {
65 ccltbl[cclp + newlen] = cclmec;
66 ++newlen;
67 }
68 }
69
70 ccllen[i] = newlen;
71 }
72 }
73
74
75 /* cre8ecs - associate equivalence class numbers with class members
76 *
77 * fwd is the forward linked-list of equivalence class members. bck
78 * is the backward linked-list, and num is the number of class members.
79 *
80 * Returned is the number of classes.
81 */
82
cre8ecs(fwd,bck,num)83 int cre8ecs( fwd, bck, num )
84 int fwd[], bck[], num;
85 {
86 int i, j, numcl;
87
88 numcl = 0;
89
90 /* Create equivalence class numbers. From now on, ABS( bck(x) )
91 * is the equivalence class number for object x. If bck(x)
92 * is positive, then x is the representative of its equivalence
93 * class.
94 */
95 for ( i = 1; i <= num; ++i )
96 if ( bck[i] == NIL )
97 {
98 bck[i] = ++numcl;
99 for ( j = fwd[i]; j != NIL; j = fwd[j] )
100 bck[j] = -numcl;
101 }
102
103 return numcl;
104 }
105
106
107 /* mkeccl - update equivalence classes based on character class xtions
108 *
109 * synopsis
110 * Char ccls[];
111 * int lenccl, fwd[llsiz], bck[llsiz], llsiz, NUL_mapping;
112 * void mkeccl( Char ccls[], int lenccl, int fwd[llsiz], int bck[llsiz],
113 * int llsiz, int NUL_mapping );
114 *
115 * ccls contains the elements of the character class, lenccl is the
116 * number of elements in the ccl, fwd is the forward link-list of equivalent
117 * characters, bck is the backward link-list, and llsiz size of the link-list.
118 *
119 * NUL_mapping is the value which NUL (0) should be mapped to.
120 */
121
mkeccl(ccls,lenccl,fwd,bck,llsiz,NUL_mapping)122 void mkeccl( ccls, lenccl, fwd, bck, llsiz, NUL_mapping )
123 Char ccls[];
124 int lenccl, fwd[], bck[], llsiz, NUL_mapping;
125 {
126 int cclp, oldec, newec;
127 int cclm, i, j;
128 static unsigned char cclflags[CSIZE]; /* initialized to all '\0' */
129
130 /* Note that it doesn't matter whether or not the character class is
131 * negated. The same results will be obtained in either case.
132 */
133
134 cclp = 0;
135
136 while ( cclp < lenccl )
137 {
138 cclm = ccls[cclp];
139
140 if ( NUL_mapping && cclm == 0 )
141 cclm = NUL_mapping;
142
143 oldec = bck[cclm];
144 newec = cclm;
145
146 j = cclp + 1;
147
148 for ( i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i] )
149 { /* look for the symbol in the character class */
150 for ( ; j < lenccl; ++j )
151 {
152 int ccl_char;
153
154 if ( NUL_mapping && ccls[j] == 0 )
155 ccl_char = NUL_mapping;
156 else
157 ccl_char = ccls[j];
158
159 if ( ccl_char > i )
160 break;
161
162 if ( ccl_char == i && ! cclflags[j] )
163 {
164 /* We found an old companion of cclm
165 * in the ccl. Link it into the new
166 * equivalence class and flag it as
167 * having been processed.
168 */
169
170 bck[i] = newec;
171 fwd[newec] = i;
172 newec = i;
173 /* Set flag so we don't reprocess. */
174 cclflags[j] = 1;
175
176 /* Get next equivalence class member. */
177 /* continue 2 */
178 goto next_pt;
179 }
180 }
181
182 /* Symbol isn't in character class. Put it in the old
183 * equivalence class.
184 */
185
186 bck[i] = oldec;
187
188 if ( oldec != NIL )
189 fwd[oldec] = i;
190
191 oldec = i;
192
193 next_pt: ;
194 }
195
196 if ( bck[cclm] != NIL || oldec != bck[cclm] )
197 {
198 bck[cclm] = NIL;
199 fwd[oldec] = NIL;
200 }
201
202 fwd[newec] = NIL;
203
204 /* Find next ccl member to process. */
205
206 for ( ++cclp; cclflags[cclp] && cclp < lenccl; ++cclp )
207 {
208 /* Reset "doesn't need processing" flag. */
209 cclflags[cclp] = 0;
210 }
211 }
212 }
213
214
215 /* mkechar - create equivalence class for single character */
216
mkechar(tch,fwd,bck)217 void mkechar( tch, fwd, bck )
218 int tch, fwd[], bck[];
219 {
220 /* If until now the character has been a proper subset of
221 * an equivalence class, break it away to create a new ec
222 */
223
224 if ( fwd[tch] != NIL )
225 bck[fwd[tch]] = bck[tch];
226
227 if ( bck[tch] != NIL )
228 fwd[bck[tch]] = fwd[tch];
229
230 fwd[tch] = NIL;
231 bck[tch] = NIL;
232 }
233