1 /* $NetBSD: ecs.c,v 1.1.1.1 2009/10/26 00:24:20 christos Exp $ */ 2 3 /* ecs - equivalence class routines */ 4 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. */ 35 36 37 #include "flexdef.h" 38 39 /* ccl2ecl - convert character classes to set of equivalence classes */ 40 41 void ccl2ecl () 42 { 43 int i, ich, newlen, cclp, ccls, cclmec; 44 45 for (i = 1; i <= lastccl; ++i) { 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 56 for (ccls = 0; ccls < ccllen[i]; ++ccls) { 57 ich = ccltbl[cclp + ccls]; 58 cclmec = ecgroup[ich]; 59 60 if (cclmec > 0) { 61 ccltbl[cclp + newlen] = cclmec; 62 ++newlen; 63 } 64 } 65 66 ccllen[i] = newlen; 67 } 68 } 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 79 int cre8ecs (fwd, bck, num) 80 int fwd[], bck[], num; 81 { 82 int i, j, numcl; 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 */ 91 for (i = 1; i <= num; ++i) 92 if (bck[i] == NIL) { 93 bck[i] = ++numcl; 94 for (j = fwd[i]; j != NIL; j = fwd[j]) 95 bck[j] = -numcl; 96 } 97 98 return numcl; 99 } 100 101 102 /* mkeccl - update equivalence classes based on character class xtions 103 * 104 * synopsis 105 * Char ccls[]; 106 * int lenccl, fwd[llsiz], bck[llsiz], llsiz, NUL_mapping; 107 * void mkeccl( Char ccls[], int lenccl, int fwd[llsiz], int bck[llsiz], 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 117 void mkeccl (ccls, lenccl, fwd, bck, llsiz, NUL_mapping) 118 Char ccls[]; 119 int lenccl, fwd[], bck[], llsiz, NUL_mapping; 120 { 121 int cclp, oldec, newec; 122 int cclm, i, j; 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 131 while (cclp < lenccl) { 132 cclm = ccls[cclp]; 133 134 if (NUL_mapping && cclm == 0) 135 cclm = NUL_mapping; 136 137 oldec = bck[cclm]; 138 newec = cclm; 139 140 j = cclp + 1; 141 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) { 144 register int ccl_char; 145 146 if (NUL_mapping && ccls[j] == 0) 147 ccl_char = NUL_mapping; 148 else 149 ccl_char = ccls[j]; 150 151 if (ccl_char > i) 152 break; 153 154 if (ccl_char == i && !cclflags[j]) { 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 } 171 } 172 173 /* Symbol isn't in character class. Put it in the old 174 * equivalence class. 175 */ 176 177 bck[i] = oldec; 178 179 if (oldec != NIL) 180 fwd[oldec] = i; 181 182 oldec = i; 183 184 next_pt:; 185 } 186 187 if (bck[cclm] != NIL || oldec != bck[cclm]) { 188 bck[cclm] = NIL; 189 fwd[oldec] = NIL; 190 } 191 192 fwd[newec] = NIL; 193 194 /* Find next ccl member to process. */ 195 196 for (++cclp; cclflags[cclp] && cclp < lenccl; ++cclp) { 197 /* Reset "doesn't need processing" flag. */ 198 cclflags[cclp] = 0; 199 } 200 } 201 } 202 203 204 /* mkechar - create equivalence class for single character */ 205 206 void mkechar (tch, fwd, bck) 207 int tch, fwd[], bck[]; 208 { 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 213 if (fwd[tch] != NIL) 214 bck[fwd[tch]] = bck[tch]; 215 216 if (bck[tch] != NIL) 217 fwd[bck[tch]] = fwd[tch]; 218 219 fwd[tch] = NIL; 220 bck[tch] = NIL; 221 } 222