home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / flex254.zip / ecs.c < prev    next >
C/C++ Source or Header  |  1997-07-26  |  6KB  |  226 lines
  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 with or without
  15.  * modification are permitted provided that: (1) source distributions retain
  16.  * this entire copyright notice and comment, and (2) distributions including
  17.  * binaries display the following acknowledgement:  ``This product includes
  18.  * software developed by the University of California, Berkeley and its
  19.  * contributors'' in the documentation or other materials provided with the
  20.  * distribution and in all advertising materials mentioning features or use
  21.  * of this software.  Neither the name of the University nor the names of
  22.  * its contributors may be used to endorse or promote products derived from
  23.  * this software without 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.  
  31. #include "flexdef.h"
  32.  
  33. /* ccl2ecl - convert character classes to set of equivalence classes */
  34.  
  35. void ccl2ecl()
  36.     {
  37.     int i, ich, newlen, cclp, ccls, cclmec;
  38.  
  39.     for ( i = 1; i <= lastccl; ++i )
  40.         {
  41.         /* We loop through each character class, and for each character
  42.          * in the class, add the character's equivalence class to the
  43.          * new "character" class we are creating.  Thus when we are all
  44.          * done, character classes will really consist of collections
  45.          * of equivalence classes
  46.          */
  47.  
  48.         newlen = 0;
  49.         cclp = cclmap[i];
  50.  
  51.         for ( ccls = 0; ccls < ccllen[i]; ++ccls )
  52.             {
  53.             ich = ccltbl[cclp + ccls];
  54.             cclmec = ecgroup[ich];
  55.  
  56.             if ( cclmec > 0 )
  57.                 {
  58.                 ccltbl[cclp + newlen] = cclmec;
  59.                 ++newlen;
  60.                 }
  61.             }
  62.  
  63.         ccllen[i] = newlen;
  64.         }
  65.     }
  66.  
  67.  
  68. /* cre8ecs - associate equivalence class numbers with class members
  69.  *
  70.  * fwd is the forward linked-list of equivalence class members.  bck
  71.  * is the backward linked-list, and num is the number of class members.
  72.  *
  73.  * Returned is the number of classes.
  74.  */
  75.  
  76. int cre8ecs( fwd, bck, num )
  77. int fwd[], bck[], num;
  78.     {
  79.     int i, j, numcl;
  80.  
  81.     numcl = 0;
  82.  
  83.     /* Create equivalence class numbers.  From now on, ABS( bck(x) )
  84.      * is the equivalence class number for object x.  If bck(x)
  85.      * is positive, then x is the representative of its equivalence
  86.      * class.
  87.      */
  88.     for ( i = 1; i <= num; ++i )
  89.         if ( bck[i] == NIL )
  90.             {
  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.  
  115. void 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.         {
  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.                 register 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( tch, fwd, bck )
  211. int tch, fwd[], bck[];
  212.     {
  213.     /* If until now the character has been a proper subset of
  214.      * an equivalence class, break it away to create a new ec
  215.      */
  216.  
  217.     if ( fwd[tch] != NIL )
  218.         bck[fwd[tch]] = bck[tch];
  219.  
  220.     if ( bck[tch] != NIL )
  221.         fwd[bck[tch]] = fwd[tch];
  222.  
  223.     fwd[tch] = NIL;
  224.     bck[tch] = NIL;
  225.     }
  226.