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.2 2003/06/17 04:29:27 dillon Exp $ */
  32
  33 #include "flexdef.h"
  34
  35 /* ccl2ecl - convert character classes to set of equivalence classes */
  36
  37 void ccl2ecl()
  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( fwd, bck, num )
  79 int fwd[], bck[], num;
  80         {
  81         int i, j, numcl;
  82
  83         numcl = 0;
  84
  85         /* Create equivalence class numbers.  From now on, ABS( bck(x) )
  86          * is the equivalence class number for object x.  If bck(x)
  87          * is positive, then x is the representative of its equivalence
  88          * class.
  89          */
  90         for ( i = 1; i <= num; ++i )
  91                 if ( bck[i] == NIL )
  92                         {
  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                 {
 133                 cclm = ccls[cclp];
 134
 135                 if ( NUL_mapping && cclm == 0 )
 136                         cclm = NUL_mapping;
 137
 138                 oldec = bck[cclm];
 139                 newec = cclm;
 140
 141                 j = cclp + 1;
 142
 143                 for ( i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i] )
 144                         { /* look for the symbol in the character class */
 145                         for ( ; j < lenccl; ++j )
 146                                 {
 147                                 register int ccl_char;
 148
 149                                 if ( NUL_mapping && ccls[j] == 0 )
 150                                         ccl_char = NUL_mapping;
 151                                 else
 152                                         ccl_char = ccls[j];
 153
 154                                 if ( ccl_char > i )
 155                                         break;
 156
 157                                 if ( ccl_char == i && ! cclflags[j] )
 158                                         {
 159                                         /* We found an old companion of cclm
 160                                          * in the ccl.  Link it into the new
 161                                          * equivalence class and flag it as
 162                                          * having been processed.
 163                                          */
 164
 165                                         bck[i] = newec;
 166                                         fwd[newec] = i;
 167                                         newec = i;
 168                                         /* Set flag so we don't reprocess. */
 169                                         cclflags[j] = 1;
 170
 171                                         /* Get next equivalence class member. */
 172                                         /* continue 2 */
 173                                         goto next_pt;
 174                                         }
 175                                 }
 176
 177                         /* Symbol isn't in character class.  Put it in the old
 178                          * equivalence class.
 179                          */
 180
 181                         bck[i] = oldec;
 182
 183                         if ( oldec != NIL )
 184                                 fwd[oldec] = i;
 185
 186                         oldec = i;
 187
 188                         next_pt: ;
 189                         }
 190
 191                 if ( bck[cclm] != NIL || oldec != bck[cclm] )
 192                         {
 193                         bck[cclm] = NIL;
 194                         fwd[oldec] = NIL;
 195                         }
 196
 197                 fwd[newec] = NIL;
 198
 199                 /* Find next ccl member to process. */
 200
 201                 for ( ++cclp; cclflags[cclp] && cclp < lenccl; ++cclp )
 202                         {
 203                         /* Reset "doesn't need processing" flag. */
 204                         cclflags[cclp] = 0;
 205                         }
 206                 }
 207         }
 208
 209
 210 /* mkechar - create equivalence class for single character */
 211
 212 void mkechar( tch, fwd, bck )
 213 int tch, fwd[], bck[];
 214         {
 215         /* If until now the character has been a proper subset of
 216          * an equivalence class, break it away to create a new ec
 217          */
 218
 219         if ( fwd[tch] != NIL )
 220                 bck[fwd[tch]] = bck[tch];
 221
 222         if ( bck[tch] != NIL )
 223                 fwd[bck[tch]] = fwd[tch];
 224
 225         fwd[tch] = NIL;
 226         bck[tch] = NIL;
 227         }