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