1 /* ecs - equivalence class routines */
4 * Copyright (c) 1990 The Regents of the University of California.
7 * This code is derived from software contributed to Berkeley by
10 * The United States Government has rights in this work pursuant
11 * to contract no. DE-AC03-76SF00098 between the United States
12 * Department of Energy and the University of California.
14 * Redistribution and use in source and binary forms are permitted provided
15 * that: (1) source distributions retain this entire copyright notice and
16 * comment, and (2) distributions including binaries display the following
17 * acknowledgement: ``This product includes software developed by the
18 * University of California, Berkeley and its contributors'' in the
19 * documentation or other materials provided with the distribution and in
20 * all advertising materials mentioning features or use of this software.
21 * Neither the name of the University nor the names of its contributors may
22 * be used to endorse or promote products derived from this software without
23 * specific prior written permission.
24 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
25 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
26 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
29 /* $Header: /home/daffy/u0/vern/flex/RCS/ecs.c,v 2.9 93/12/07 10:18:20 vern Exp $ */
30 /* $FreeBSD: src/usr.bin/lex/ecs.c,v 1.5 1999/10/27 07:56:43 obrien Exp $ */
31 /* $DragonFly: src/usr.bin/lex/ecs.c,v 1.4 2005/08/04 17:31:22 drhodus Exp $ */
35 /* ccl2ecl - convert character classes to set of equivalence classes */
39 int i, ich, newlen, cclp, ccls, cclmec;
41 for ( i = 1; i <= lastccl; ++i )
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
53 for ( ccls = 0; ccls < ccllen[i]; ++ccls )
55 ich = ccltbl[cclp + ccls];
56 cclmec = ecgroup[ich];
60 ccltbl[cclp + newlen] = cclmec;
70 /* cre8ecs - associate equivalence class numbers with class members
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.
75 * Returned is the number of classes.
78 int cre8ecs(int *fwd, int *bck, int num)
84 /* Create equivalence class numbers. From now on, ABS( bck(x) )
85 * is the equivalence class number for object x. If bck(x)
86 * is positive, then x is the representative of its equivalence
89 for ( i = 1; i <= num; ++i )
93 for ( j = fwd[i]; j != NIL; j = fwd[j] )
101 /* mkeccl - update equivalence classes based on character class xtions
105 * int lenccl, fwd[llsiz], bck[llsiz], llsiz, NUL_mapping;
106 * void mkeccl( Char ccls[], int lenccl, int fwd[llsiz], int bck[llsiz],
107 * int llsiz, int NUL_mapping );
109 * ccls contains the elements of the character class, lenccl is the
110 * number of elements in the ccl, fwd is the forward link-list of equivalent
111 * characters, bck is the backward link-list, and llsiz size of the link-list.
113 * NUL_mapping is the value which NUL (0) should be mapped to.
116 void mkeccl(Char *ccls, int lenccl, int *fwd, int *bck, int llsiz,
119 int cclp, oldec, newec;
121 static unsigned char cclflags[CSIZE]; /* initialized to all '\0' */
123 /* Note that it doesn't matter whether or not the character class is
124 * negated. The same results will be obtained in either case.
129 while ( cclp < lenccl )
133 if ( NUL_mapping && cclm == 0 )
141 for ( i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i] )
142 { /* look for the symbol in the character class */
143 for ( ; j < lenccl; ++j )
147 if ( NUL_mapping && ccls[j] == 0 )
148 ccl_char = NUL_mapping;
155 if ( ccl_char == i && ! cclflags[j] )
157 /* We found an old companion of cclm
158 * in the ccl. Link it into the new
159 * equivalence class and flag it as
160 * having been processed.
166 /* Set flag so we don't reprocess. */
169 /* Get next equivalence class member. */
175 /* Symbol isn't in character class. Put it in the old
189 if ( bck[cclm] != NIL || oldec != bck[cclm] )
197 /* Find next ccl member to process. */
199 for ( ++cclp; cclflags[cclp] && cclp < lenccl; ++cclp )
201 /* Reset "doesn't need processing" flag. */
208 /* mkechar - create equivalence class for single character */
210 void mkechar(int tch, int *fwd, int *bck)
212 /* If until now the character has been a proper subset of
213 * an equivalence class, break it away to create a new ec
216 if ( fwd[tch] != NIL )
217 bck[fwd[tch]] = bck[tch];
219 if ( bck[tch] != NIL )
220 fwd[bck[tch]] = fwd[tch];