home *** CD-ROM | disk | FTP | other *** search
/ Frozen Fish 1: Amiga / FrozenFish-Apr94.iso / bbs / alib / d1xx / d156 / flex.lha / Flex / CommonFiles / ecs.c < prev    next >
C/C++ Source or Header  |  1988-10-02  |  5KB  |  203 lines
  1. /* ecs - equivalence class routines */
  2.  
  3. /*
  4.  * Copyright (c) 1987, the University of California
  5.  * 
  6.  * The United States Government has rights in this work pursuant to
  7.  * contract no. DE-AC03-76SF00098 between the United States Department of
  8.  * Energy and the University of California.
  9.  * 
  10.  * This program may be redistributed.  Enhancements and derivative works
  11.  * may be created provided the new works, if made available to the general
  12.  * public, are made available for use by anyone.
  13.  */
  14.  
  15. #include "flexdef.h"
  16.  
  17. /* ccl2ecl - convert character classes to set of equivalence classes
  18.  *
  19.  * synopsis
  20.  *    ccl2ecl();
  21.  */
  22.  
  23. ccl2ecl()
  24.  
  25.     {
  26.     int i, ich, newlen, cclp, ccls, cclmec;
  27.  
  28.     for ( i = 1; i <= lastccl; ++i )
  29.     {
  30.     /* we loop through each character class, and for each character
  31.      * in the class, add the character's equivalence class to the
  32.      * new "character" class we are creating.  Thus when we are all
  33.      * done, character classes will really consist of collections
  34.      * of equivalence classes
  35.      */
  36.  
  37.     newlen = 0;
  38.     cclp = cclmap[i];
  39.  
  40.     for ( ccls = 0; ccls < ccllen[i]; ++ccls )
  41.         {
  42.         ich = ccltbl[cclp + ccls];
  43.         cclmec = ecgroup[ich];
  44.         if ( cclmec > 0 )
  45.         {
  46.         ccltbl[cclp + newlen] = cclmec;
  47.         ++newlen;
  48.         }
  49.         }
  50.  
  51.     ccllen[i] = newlen;
  52.     }
  53.     }
  54.  
  55.  
  56. /* cre8ecs - associate equivalence class numbers with class members
  57.  *
  58.  * synopsis
  59.  *    int cre8ecs();
  60.  *    number of classes = cre8ecs( fwd, bck, num );
  61.  *
  62.  *  fwd is the forward linked-list of equivalence class members.  bck
  63.  *  is the backward linked-list, and num is the number of class members.
  64.  *  Returned is the number of classes.
  65.  */
  66.  
  67. int cre8ecs( fwd, bck, num )
  68. int fwd[], bck[], num;
  69.  
  70.     {
  71.     int i, j, numcl;
  72.  
  73.     numcl = 0;
  74.  
  75.     /* create equivalence class numbers.  From now on, abs( bck(x) )
  76.      * is the equivalence class number for object x.  If bck(x)
  77.      * is positive, then x is the representative of its equivalence
  78.      * class.
  79.      */
  80.  
  81.     for ( i = 1; i <= num; ++i )
  82.     if ( bck[i] == NIL )
  83.         {
  84.         bck[i] = ++numcl;
  85.         for ( j = fwd[i]; j != NIL; j = fwd[j] )
  86.         bck[j] = -numcl;
  87.         }
  88.  
  89.     return ( numcl );
  90.     }
  91.  
  92.  
  93. /* mkeccl - update equivalence classes based on character class xtions
  94.  *
  95.  * synopsis
  96.  *    char ccls[];
  97.  *    int lenccl, fwd[llsiz], bck[llsiz], llsiz;
  98.  *    mkeccl( ccls, lenccl, fwd, bck, llsiz );
  99.  *
  100.  * where ccls contains the elements of the character class, lenccl is the
  101.  * number of elements in the ccl, fwd is the forward link-list of equivalent
  102.  * characters, bck is the backward link-list, and llsiz size of the link-list
  103.  */
  104.  
  105. mkeccl( ccls, lenccl, fwd, bck, llsiz )
  106. char ccls[];
  107. int lenccl, fwd[], bck[], llsiz;
  108.  
  109.     {
  110.     int cclp, oldec, newec;
  111.     int cclm, i, j;
  112.  
  113.     /* note that it doesn't matter whether or not the character class is
  114.      * negated.  The same results will be obtained in either case.
  115.      */
  116.  
  117.     cclp = 0;
  118.  
  119.     while ( cclp < lenccl )
  120.     {
  121.     cclm = ccls[cclp];
  122.     oldec = bck[cclm];
  123.     newec = cclm;
  124.  
  125.     j = cclp + 1;
  126.  
  127.     for ( i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i] )
  128.         { /* look for the symbol in the character class */
  129.         for ( ; j < lenccl && ccls[j] <= i; ++j )
  130.         if ( ccls[j] == i )
  131.             {
  132.             /* we found an old companion of cclm in the ccl.
  133.              * link it into the new equivalence class and flag it as
  134.              * having been processed
  135.              */
  136.  
  137.             bck[i] = newec;
  138.             fwd[newec] = i;
  139.             newec = i;
  140.             ccls[j] = -i;    /* set flag so we don't reprocess */
  141.  
  142.             /* get next equivalence class member */
  143.             /* next 2 */ goto next_pt;
  144.             }
  145.  
  146.         /* symbol isn't in character class.  Put it in the old equivalence
  147.          * class
  148.          */
  149.  
  150.         bck[i] = oldec;
  151.  
  152.         if ( oldec != NIL )
  153.         fwd[oldec] = i;
  154.  
  155.         oldec = i;
  156. next_pt:
  157.         ;
  158.         }
  159.  
  160.     if ( bck[cclm] != NIL || oldec != bck[cclm] )
  161.         {
  162.         bck[cclm] = NIL;
  163.         fwd[oldec] = NIL;
  164.         }
  165.  
  166.     fwd[newec] = NIL;
  167.  
  168.     /* find next ccl member to process */
  169.  
  170.     for ( ++cclp; ccls[cclp] < 0 && cclp < lenccl; ++cclp )
  171.         {
  172.         /* reset "doesn't need processing" flag */
  173.         ccls[cclp] = -ccls[cclp];
  174.         }
  175.     }
  176.     }
  177.  
  178.  
  179. /* mkechar - create equivalence class for single character
  180.  *
  181.  * synopsis
  182.  *    int tch, fwd[], bck[];
  183.  *    mkechar( tch, fwd, bck );
  184.  */
  185.  
  186. mkechar( tch, fwd, bck )
  187. int tch, fwd[], bck[];
  188.  
  189.     {
  190.     /* if until now the character has been a proper subset of
  191.      * an equivalence class, break it away to create a new ec
  192.      */
  193.  
  194.     if ( fwd[tch] != NIL )
  195.     bck[fwd[tch]] = bck[tch];
  196.  
  197.     if ( bck[tch] != NIL )
  198.     fwd[bck[tch]] = fwd[tch];
  199.  
  200.     fwd[tch] = NIL;
  201.     bck[tch] = NIL;
  202.     }
  203.