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
  32 #include "flexdef.h"
  33
  34 /* ccl2ecl - convert character classes to set of equivalence classes */
  35
  36 void ccl2ecl()
  37         {
  38         int i, ich, newlen, cclp, ccls, cclmec;
  39
  40         for ( i = 1; i <= lastccl; ++i )
  41                 {
  42                 /* We loop through each character class, and for each character
  43                  * in the class, add the character's equivalence class to the
  44                  * new "character" class we are creating.  Thus when we are all
  45                  * done, character classes will really consist of collections
  46                  * of equivalence classes
  47                  */
  48
  49                 newlen = 0;
  50                 cclp = cclmap[i];
  51
  52                 for ( ccls = 0; ccls < ccllen[i]; ++ccls )
  53                         {
  54                         ich = ccltbl[cclp + ccls];
  55                         cclmec = ecgroup[ich];
  56
  57                         if ( cclmec > 0 )
  58                                 {
  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
  77 int 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                         {
  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( ccls, lenccl, fwd, bck, llsiz, NUL_mapping )
 117 Char ccls[];
 118 int lenccl, fwd[], bck[], llsiz, NUL_mapping;
 119         {
 120         int cclp, oldec, newec;
 121         int cclm, i, j;
 122         static unsigned char cclflags[CSIZE];   /* initialized to all '\0' */
 123
 124         /* Note that it doesn't matter whether or not the character class is
 125          * negated.  The same results will be obtained in either case.
 126          */
 127
 128         cclp = 0;
 129
 130         while ( cclp < lenccl )
 131                 {
 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] )
 143                         { /* look for the symbol in the character class */
 144                         for ( ; j < lenccl; ++j )
 145                                 {
 146                                 register int ccl_char;
 147
 148                                 if ( NUL_mapping && ccls[j] == 0 )
 149                                         ccl_char = NUL_mapping;
 150                                 else
 151                                         ccl_char = ccls[j];
 152
 153                                 if ( ccl_char > i )
 154                                         break;
 155
 156                                 if ( ccl_char == i && ! cclflags[j] )
 157                                         {
 158                                         /* We found an old companion of cclm
 159                                          * in the ccl.  Link it into the new
 160                                          * equivalence class and flag it as
 161                                          * having been processed.
 162                                          */
 163
 164                                         bck[i] = newec;
 165                                         fwd[newec] = i;
 166                                         newec = i;
 167                                         /* Set flag so we don't reprocess. */
 168                                         cclflags[j] = 1;
 169
 170                                         /* Get next equivalence class member. */
 171                                         /* continue 2 */
 172                                         goto next_pt;
 173                                         }
 174                                 }
 175
 176                         /* Symbol isn't in character class.  Put it in the old
 177                          * equivalence class.
 178                          */
 179
 180                         bck[i] = oldec;
 181
 182                         if ( oldec != NIL )
 183                                 fwd[oldec] = i;
 184
 185                         oldec = i;
 186
 187                         next_pt: ;
 188                         }
 189
 190                 if ( bck[cclm] != NIL || oldec != bck[cclm] )
 191                         {
 192                         bck[cclm] = NIL;
 193                         fwd[oldec] = NIL;
 194                         }
 195
 196                 fwd[newec] = NIL;
 197
 198                 /* Find next ccl member to process. */
 199
 200                 for ( ++cclp; cclflags[cclp] && cclp < lenccl; ++cclp )
 201                         {
 202                         /* Reset "doesn't need processing" flag. */
 203                         cclflags[cclp] = 0;
 204                         }
 205                 }
 206         }
 207
 208
 209 /* mkechar - create equivalence class for single character */
 210
 211 void mkechar( tch, fwd, bck )
 212 int tch, fwd[], bck[];
 213         {
 214         /* If until now the character has been a proper subset of
 215          * an equivalence class, break it away to create a new ec
 216          */
 217
 218         if ( fwd[tch] != NIL )
 219                 bck[fwd[tch]] = bck[tch];
 220
 221         if ( bck[tch] != NIL )
 222                 fwd[bck[tch]] = fwd[tch];
 223
 224         fwd[tch] = NIL;
 225         bck[tch] = NIL;
 226         }