util/flex/ecs.c

   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 are permitted provided
  15  * that: (1) source distributions retain this entire copyright notice and
  16  * comment, and (2) distributions including binaries display the following
  17  * acknowledgement:  ``This product includes software developed by the
  18  * University of California, Berkeley and its contributors'' in the
  19  * documentation or other materials provided with the distribution and in
  20  * all advertising materials mentioning features or use of this software.
  21  * Neither the name of the University nor the names of its contributors may
  22  * be used to endorse or promote products derived from this software without
  23  * 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 #ifndef lint
  30 static char rcsid[] =
  31     "@(#) $Id: ecs.c,v 1.2 1994/06/24 10:56:45 ceriel Exp $ (LBL)";
  32 #endif
  33
  34 #include "flexdef.h"
  35
  36 /* ccl2ecl - convert character classes to set of equivalence classes
  37  *
  38  * synopsis
  39  *    ccl2ecl();
  40  */
  41
  42 void ccl2ecl()
  43
  44     {
  45     int i, ich, newlen, cclp, ccls, cclmec;
  46
  47     for ( i = 1; i <= lastccl; ++i )
  48         {
  49         /* we loop through each character class, and for each character
  50          * in the class, add the character's equivalence class to the
  51          * new "character" class we are creating.  Thus when we are all
  52          * done, character classes will really consist of collections
  53          * of equivalence classes
  54          */
  55
  56         newlen = 0;
  57         cclp = cclmap[i];
  58
  59         for ( ccls = 0; ccls < ccllen[i]; ++ccls )
  60             {
  61             ich = ccltbl[cclp + ccls];
  62             cclmec = ecgroup[ich];
  63
  64             if ( xlation && cclmec < 0 )
  65                 {
  66                 /* special hack--if we're doing %t tables then it's
  67                  * possible that no representative of this character's
  68                  * equivalence class is in the ccl.  So waiting till
  69                  * we see the representative would be disastrous.  Instead,
  70                  * we add this character's equivalence class anyway, if it's
  71                  * not already present.
  72                  */
  73                 int j;
  74
  75                 /* this loop makes this whole process n^2; but we don't
  76                  * really care about %t performance anyway
  77                  */
  78                 for ( j = 0; j < newlen; ++j )
  79                     if ( ccltbl[cclp + j] == -cclmec )
  80                         break;
  81
  82                 if ( j >= newlen )
  83                     { /* no representative yet, add this one in */
  84                     ccltbl[cclp + newlen] = -cclmec;
  85                     ++newlen;
  86                     }
  87                 }
  88
  89             else if ( cclmec > 0 )
  90                 {
  91                 ccltbl[cclp + newlen] = cclmec;
  92                 ++newlen;
  93                 }
  94             }
  95
  96         ccllen[i] = newlen;
  97         }
  98     }
  99
 100
 101 /* cre8ecs - associate equivalence class numbers with class members
 102  *
 103  * synopsis
 104  *    int cre8ecs();
 105  *    number of classes = cre8ecs( fwd, bck, num );
 106  *
 107  *  fwd is the forward linked-list of equivalence class members.  bck
 108  *  is the backward linked-list, and num is the number of class members.
 109  *
 110  *  Returned is the number of classes.
 111  */
 112
 113 int cre8ecs( fwd, bck, num )
 114 int fwd[], bck[], num;
 115
 116     {
 117     int i, j, numcl;
 118
 119     numcl = 0;
 120
 121     /* create equivalence class numbers.  From now on, abs( bck(x) )
 122      * is the equivalence class number for object x.  If bck(x)
 123      * is positive, then x is the representative of its equivalence
 124      * class.
 125      */
 126     for ( i = 1; i <= num; ++i )
 127         if ( bck[i] == NIL )
 128             {
 129             bck[i] = ++numcl;
 130             for ( j = fwd[i]; j != NIL; j = fwd[j] )
 131                 bck[j] = -numcl;
 132             }
 133
 134     return ( numcl );
 135     }
 136
 137
 138 /* ecs_from_xlation - associate equivalence class numbers using %t table
 139  *
 140  * synopsis
 141  *    numecs = ecs_from_xlation( ecmap );
 142  *
 143  *  Upon return, ecmap will map each character code to its equivalence
 144  *  class.  The mapping will be positive if the character is the representative
 145  *  of its class, negative otherwise.
 146  *
 147  *  Returns the number of equivalence classes used.
 148  */
 149
 150 int ecs_from_xlation( ecmap )
 151 int ecmap[];
 152
 153     {
 154     int i;
 155     int nul_is_alone = false;
 156     int did_default_xlation_class = false;
 157
 158     if ( xlation[0] != 0 )
 159         {
 160         /* if NUL shares its translation with other characters, choose one
 161          * of the other characters as the representative for the equivalence
 162          * class.  This allows a cheap test later to see whether we can
 163          * do away with NUL's equivalence class.
 164          */
 165         for ( i = 1; i < csize; ++i )
 166             if ( xlation[i] == -xlation[0] )
 167                 {
 168                 xlation[i] = xlation[0];
 169                 ecmap[0] = -xlation[0];
 170                 break;
 171                 }
 172
 173         if ( i >= csize )
 174             /* didn't find a companion character--remember this fact */
 175             nul_is_alone = true;
 176         }
 177
 178     for ( i = 1; i < csize; ++i )
 179         if ( xlation[i] == 0 )
 180             {
 181             if ( did_default_xlation_class )
 182                 ecmap[i] = -num_xlations;
 183
 184             else
 185                 {
 186                 /* make an equivalence class for those characters not
 187                  * specified in the %t table
 188                  */
 189                 ++num_xlations;
 190                 ecmap[i] = num_xlations;
 191                 did_default_xlation_class = true;
 192                 }
 193             }
 194
 195         else
 196             ecmap[i] = xlation[i];
 197
 198     if ( nul_is_alone )
 199         /* force NUL's equivalence class to be the last one */
 200         {
 201         ++num_xlations;
 202         ecmap[0] = num_xlations;
 203
 204         /* there's actually a bug here: if someone is fanatic enough to
 205          * put every character in its own translation class, then right
 206          * now we just promoted NUL's equivalence class to be csize + 1;
 207          * we can handle NUL's class number being == csize (by instead
 208          * putting it in its own table), but we can't handle some *other*
 209          * character having to be put in its own table, too.  So in
 210          * this case we bail out.
 211          */
 212         if ( num_xlations > csize )
 213             flexfatal( "too many %t classes!" );
 214         }
 215
 216     return num_xlations;
 217     }
 218
 219
 220 /* mkeccl - update equivalence classes based on character class xtions
 221  *
 222  * synopsis
 223  *    Char ccls[];
 224  *    int lenccl, fwd[llsiz], bck[llsiz], llsiz, NUL_mapping;
 225  *    mkeccl( ccls, lenccl, fwd, bck, llsiz, NUL_mapping );
 226  *
 227  * where ccls contains the elements of the character class, lenccl is the
 228  * number of elements in the ccl, fwd is the forward link-list of equivalent
 229  * characters, bck is the backward link-list, and llsiz size of the link-list
 230  *
 231  * NUL_mapping is the value which NUL (0) should be mapped to.
 232  */
 233
 234 void mkeccl( ccls, lenccl, fwd, bck, llsiz, NUL_mapping )
 235 Char ccls[];
 236 int lenccl, fwd[], bck[], llsiz, NUL_mapping;
 237
 238     {
 239     int cclp, oldec, newec;
 240     int cclm, i, j;
 241     static unsigned char cclflags[CSIZE];       /* initialized to all '\0' */
 242
 243     /* note that it doesn't matter whether or not the character class is
 244      * negated.  The same results will be obtained in either case.
 245      */
 246
 247     cclp = 0;
 248
 249     while ( cclp < lenccl )
 250         {
 251         cclm = ccls[cclp];
 252
 253         if ( NUL_mapping && cclm == 0 )
 254             cclm = NUL_mapping;
 255
 256         oldec = bck[cclm];
 257         newec = cclm;
 258
 259         j = cclp + 1;
 260
 261         for ( i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i] )
 262             { /* look for the symbol in the character class */
 263             for ( ; j < lenccl; ++j )
 264                 {
 265                 register int ccl_char;
 266
 267                 if ( NUL_mapping && ccls[j] == 0 )
 268                     ccl_char = NUL_mapping;
 269                 else
 270                     ccl_char = ccls[j];
 271
 272                 if ( ccl_char > i )
 273                     break;
 274
 275                 if ( ccl_char == i && ! cclflags[j] )
 276                     {
 277                     /* we found an old companion of cclm in the ccl.
 278                      * link it into the new equivalence class and flag it as
 279                      * having been processed
 280                      */
 281
 282                     bck[i] = newec;
 283                     fwd[newec] = i;
 284                     newec = i;
 285                     cclflags[j] = 1;    /* set flag so we don't reprocess */
 286
 287                     /* get next equivalence class member */
 288                     /* continue 2 */
 289                     goto next_pt;
 290                     }
 291                 }
 292
 293             /* symbol isn't in character class.  Put it in the old equivalence
 294              * class
 295              */
 296
 297             bck[i] = oldec;
 298
 299             if ( oldec != NIL )
 300                 fwd[oldec] = i;
 301
 302             oldec = i;
 303 next_pt:
 304             ;
 305             }
 306
 307         if ( bck[cclm] != NIL || oldec != bck[cclm] )
 308             {
 309             bck[cclm] = NIL;
 310             fwd[oldec] = NIL;
 311             }
 312
 313         fwd[newec] = NIL;
 314
 315         /* find next ccl member to process */
 316
 317         for ( ++cclp; cclflags[cclp] && cclp < lenccl; ++cclp )
 318             {
 319             /* reset "doesn't need processing" flag */
 320             cclflags[cclp] = 0;
 321             }
 322         }
 323     }
 324
 325
 326 /* mkechar - create equivalence class for single character
 327  *
 328  * synopsis
 329  *    int tch, fwd[], bck[];
 330  *    mkechar( tch, fwd, bck );
 331  */
 332
 333 void mkechar( tch, fwd, bck )
 334 int tch, fwd[], bck[];
 335
 336     {
 337     /* if until now the character has been a proper subset of
 338      * an equivalence class, break it away to create a new ec
 339      */
 340
 341     if ( fwd[tch] != NIL )
 342         bck[fwd[tch]] = bck[tch];
 343
 344     if ( bck[tch] != NIL )
 345         fwd[bck[tch]] = fwd[tch];
 346
 347     fwd[tch] = NIL;
 348     bck[tch] = NIL;
 349     }