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