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: /home/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 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 { 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 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