![[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.6 ! millert 1: /* $OpenBSD: ecs.c,v 1.5 2001/11/19 19:02:14 mpech 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: *
1.4 deraadt 16: * Redistribution and use in source and binary forms, with or without
1.6 ! millert 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.
1.1 deraadt 34: */
35:
1.6 ! millert 36: /* $Header: /cvs/src/usr.bin/lex/ecs.c,v 1.5 2001/11/19 19:02:14 mpech Exp $ */
1.1 deraadt 37:
38: #include "flexdef.h"
39:
40: /* ccl2ecl - convert character classes to set of equivalence classes */
41:
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:
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:
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: {
1.5 mpech 152: int ccl_char;
1.1 deraadt 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:
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: }