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