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