usr.bin/lex/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 /* $Header: /home/daffy/u0/vern/flex/RCS/ecs.c,v 2.9 93/12/07 10:18:20 vern Exp $ */
  30 /* $FreeBSD: src/usr.bin/lex/ecs.c,v 1.5 1999/10/27 07:56:43 obrien Exp $ */
  31 /* $DragonFly: src/usr.bin/lex/ecs.c,v 1.4 2005/08/04 17:31:22 drhodus Exp $ */
  32
  33 #include "flexdef.h"
  34
  35 /* ccl2ecl - convert character classes to set of equivalence classes */
  36
  37 void ccl2ecl(void)
  38         {
  39         int i, ich, newlen, cclp, ccls, cclmec;
  40
  41         for ( i = 1; i <= lastccl; ++i )
  42                 {
  43                 /* We loop through each character class, and for each character
  44                  * in the class, add the character's equivalence class to the
  45                  * new "character" class we are creating.  Thus when we are all
  46                  * done, character classes will really consist of collections
  47                  * of equivalence classes
  48                  */
  49
  50                 newlen = 0;
  51                 cclp = cclmap[i];
  52
  53                 for ( ccls = 0; ccls < ccllen[i]; ++ccls )
  54                         {
  55                         ich = ccltbl[cclp + ccls];
  56                         cclmec = ecgroup[ich];
  57
  58                         if ( cclmec > 0 )
  59                                 {
  60                                 ccltbl[cclp + newlen] = cclmec;
  61                                 ++newlen;
  62                                 }
  63                         }
  64
  65                 ccllen[i] = newlen;
  66                 }
  67         }
  68
  69
  70 /* cre8ecs - associate equivalence class numbers with class members
  71  *
  72  * fwd is the forward linked-list of equivalence class members.  bck
  73  * is the backward linked-list, and num is the number of class members.
  74  *
  75  * Returned is the number of classes.
  76  */
  77
  78 int cre8ecs(int *fwd, int *bck, int 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                         {
  92                         bck[i] = ++numcl;
  93                         for ( j = fwd[i]; j != NIL; j = fwd[j] )
  94                                 bck[j] = -numcl;
  95                         }
  96
  97         return numcl;
  98         }
  99
 100
 101 /* mkeccl - update equivalence classes based on character class xtions
 102  *
 103  * synopsis
 104  *    Char ccls[];
 105  *    int lenccl, fwd[llsiz], bck[llsiz], llsiz, NUL_mapping;
 106  *    void mkeccl( Char ccls[], int lenccl, int fwd[llsiz], int bck[llsiz],
 107  *                      int llsiz, int NUL_mapping );
 108  *
 109  * ccls contains the elements of the character class, lenccl is the
 110  * number of elements in the ccl, fwd is the forward link-list of equivalent
 111  * characters, bck is the backward link-list, and llsiz size of the link-list.
 112  *
 113  * NUL_mapping is the value which NUL (0) should be mapped to.
 114  */
 115
 116 void mkeccl(Char *ccls, int lenccl, int *fwd, int *bck, int llsiz,
 117             int 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                                 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(int tch, int *fwd, int *bck)
 211         {
 212         /* If until now the character has been a proper subset of
 213          * an equivalence class, break it away to create a new ec
 214          */
 215
 216         if ( fwd[tch] != NIL )
 217                 bck[fwd[tch]] = bck[tch];
 218
 219         if ( bck[tch] != NIL )
 220                 fwd[bck[tch]] = fwd[tch];
 221
 222         fwd[tch] = NIL;
 223         bck[tch] = NIL;
 224         }