Return to ecs.c CVS log

Up to [Research Unix] / researchv10dc / cmd / flex

Annotation of researchv10dc/cmd/flex/ecs.c, revision 1.1

1.1     ! root        1: /* ecs - equivalence class routines */
        !             2: 
        !             3: /*
        !             4:  * Copyright (c) 1989 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 to
        !            11:  * contract no. DE-AC03-76SF00098 between the United States Department of
        !            12:  * Energy and the University of California.
        !            13:  *
        !            14:  * Redistribution and use in source and binary forms are permitted
        !            15:  * provided that the above copyright notice and this paragraph are
        !            16:  * duplicated in all such forms and that any documentation,
        !            17:  * advertising materials, and other materials related to such
        !            18:  * distribution and use acknowledge that the software was developed
        !            19:  * by the University of California, Berkeley.  The name of the
        !            20:  * University may not be used to endorse or promote products derived
        !            21:  * from this software without specific prior written permission.
        !            22:  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
        !            23:  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
        !            24:  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
        !            25:  */
        !            26: 
        !            27: #ifndef lint
        !            28: 
        !            29: static char copyright[] =
        !            30:     "@(#) Copyright (c) 1989 The Regents of the University of California.\n";
        !            31: static char CR_continuation[] = "@(#) All rights reserved.\n";
        !            32: 
        !            33: static char rcsid[] =
        !            34:     "@(#) $Header: ecs.c,v 2.0 89/06/20 15:49:39 vern Locked $ (LBL)";
        !            35: 
        !            36: #endif
        !            37: 
        !            38: #include "flexdef.h"
        !            39: 
        !            40: /* ccl2ecl - convert character classes to set of equivalence classes
        !            41:  *
        !            42:  * synopsis
        !            43:  *    ccl2ecl();
        !            44:  */
        !            45: 
        !            46: ccl2ecl()
        !            47: 
        !            48:     {
        !            49:     int i, ich, newlen, cclp, ccls, cclmec;
        !            50: 
        !            51:     for ( i = 1; i <= lastccl; ++i )
        !            52:        {
        !            53:        /* we loop through each character class, and for each character
        !            54:         * in the class, add the character's equivalence class to the
        !            55:         * new "character" class we are creating.  Thus when we are all
        !            56:         * done, character classes will really consist of collections
        !            57:         * of equivalence classes
        !            58:         */
        !            59: 
        !            60:        newlen = 0;
        !            61:        cclp = cclmap[i];
        !            62: 
        !            63:        for ( ccls = 0; ccls < ccllen[i]; ++ccls )
        !            64:            {
        !            65:            ich = ccltbl[cclp + ccls];
        !            66:            cclmec = ecgroup[ich];
        !            67:            if ( cclmec > 0 )
        !            68:                {
        !            69:                ccltbl[cclp + newlen] = cclmec;
        !            70:                ++newlen;
        !            71:                }
        !            72:            }
        !            73: 
        !            74:        ccllen[i] = newlen;
        !            75:        }
        !            76:     }
        !            77: 
        !            78: 
        !            79: /* cre8ecs - associate equivalence class numbers with class members
        !            80:  *
        !            81:  * synopsis
        !            82:  *    int cre8ecs();
        !            83:  *    number of classes = cre8ecs( fwd, bck, num );
        !            84:  *
        !            85:  *  fwd is the forward linked-list of equivalence class members.  bck
        !            86:  *  is the backward linked-list, and num is the number of class members.
        !            87:  *  Returned is the number of classes.
        !            88:  */
        !            89: 
        !            90: int cre8ecs( fwd, bck, num )
        !            91: int fwd[], bck[], num;
        !            92: 
        !            93:     {
        !            94:     int i, j, numcl;
        !            95: 
        !            96:     numcl = 0;
        !            97: 
        !            98:     /* create equivalence class numbers.  From now on, abs( bck(x) )
        !            99:      * is the equivalence class number for object x.  If bck(x)
        !           100:      * is positive, then x is the representative of its equivalence
        !           101:      * class.
        !           102:      */
        !           103: 
        !           104:     for ( i = 1; i <= num; ++i )
        !           105:        if ( bck[i] == NIL )
        !           106:            {
        !           107:            bck[i] = ++numcl;
        !           108:            for ( j = fwd[i]; j != NIL; j = fwd[j] )
        !           109:                bck[j] = -numcl;
        !           110:            }
        !           111: 
        !           112:     return ( numcl );
        !           113:     }
        !           114: 
        !           115: 
        !           116: /* mkeccl - update equivalence classes based on character class xtions
        !           117:  *
        !           118:  * synopsis
        !           119:  *    char ccls[];
        !           120:  *    int lenccl, fwd[llsiz], bck[llsiz], llsiz;
        !           121:  *    mkeccl( ccls, lenccl, fwd, bck, llsiz );
        !           122:  *
        !           123:  * where ccls contains the elements of the character class, lenccl is the
        !           124:  * number of elements in the ccl, fwd is the forward link-list of equivalent
        !           125:  * characters, bck is the backward link-list, and llsiz size of the link-list
        !           126:  */
        !           127: 
        !           128: mkeccl( ccls, lenccl, fwd, bck, llsiz )
        !           129: char ccls[];
        !           130: int lenccl, fwd[], bck[], llsiz;
        !           131: 
        !           132:     {
        !           133:     int cclp, oldec, newec;
        !           134:     int cclm, i, j;
        !           135: 
        !           136: #define PROCFLG 0x80
        !           137: 
        !           138:     /* note that it doesn't matter whether or not the character class is
        !           139:      * negated.  The same results will be obtained in either case.
        !           140:      */
        !           141: 
        !           142:     cclp = 0;
        !           143: 
        !           144:     while ( cclp < lenccl )
        !           145:        {
        !           146:        cclm = ccls[cclp];
        !           147:        oldec = bck[cclm];
        !           148:        newec = cclm;
        !           149: 
        !           150:        j = cclp + 1;
        !           151: 
        !           152:        for ( i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i] )
        !           153:            { /* look for the symbol in the character class */
        !           154:            for ( ; j < lenccl && (ccls[j] <= i || (ccls[j] & PROCFLG)); ++j )
        !           155:                if ( ccls[j] == i )
        !           156:                    {
        !           157:                    /* we found an old companion of cclm in the ccl.
        !           158:                     * link it into the new equivalence class and flag it as
        !           159:                     * having been processed
        !           160:                     */
        !           161: 
        !           162:                    bck[i] = newec;
        !           163:                    fwd[newec] = i;
        !           164:                    newec = i;
        !           165:                    ccls[j] |= PROCFLG; /* set flag so we don't reprocess */
        !           166: 
        !           167:                    /* get next equivalence class member */
        !           168:                    /* continue 2 */
        !           169:                    goto next_pt;
        !           170:                    }
        !           171: 
        !           172:            /* symbol isn't in character class.  Put it in the old equivalence
        !           173:             * class
        !           174:             */
        !           175: 
        !           176:            bck[i] = oldec;
        !           177: 
        !           178:            if ( oldec != NIL )
        !           179:                fwd[oldec] = i;
        !           180: 
        !           181:            oldec = i;
        !           182: next_pt:
        !           183:            ;
        !           184:            }
        !           185: 
        !           186:        if ( bck[cclm] != NIL || oldec != bck[cclm] )
        !           187:            {
        !           188:            bck[cclm] = NIL;
        !           189:            fwd[oldec] = NIL;
        !           190:            }
        !           191: 
        !           192:        fwd[newec] = NIL;
        !           193: 
        !           194:        /* find next ccl member to process */
        !           195: 
        !           196:        for ( ++cclp; (ccls[cclp] & PROCFLG) && cclp < lenccl; ++cclp )
        !           197:            {
        !           198:            /* reset "doesn't need processing" flag */
        !           199:            ccls[cclp] &= ~PROCFLG;
        !           200:            }
        !           201:        }
        !           202:     }
        !           203: 
        !           204: 
        !           205: /* mkechar - create equivalence class for single character
        !           206:  *
        !           207:  * synopsis
        !           208:  *    int tch, fwd[], bck[];
        !           209:  *    mkechar( tch, fwd, bck );
        !           210:  */
        !           211: 
        !           212: mkechar( tch, fwd, bck )
        !           213: int tch, fwd[], bck[];
        !           214: 
        !           215:     {
        !           216:     /* if until now the character has been a proper subset of
        !           217:      * an equivalence class, break it away to create a new ec
        !           218:      */
        !           219: 
        !           220:     if ( fwd[tch] != NIL )
        !           221:        bck[fwd[tch]] = bck[tch];
        !           222: 
        !           223:     if ( bck[tch] != NIL )
        !           224:        fwd[bck[tch]] = fwd[tch];
        !           225: 
        !           226:     fwd[tch] = NIL;
        !           227:     bck[tch] = NIL;
        !           228:     }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.