/* ecs - equivalence class routines */ /*- * Copyright (c) 1990 The Regents of the University of California. * All rights reserved. * * This code is derived from software contributed to Berkeley by * Vern Paxson. * * The United States Government has rights in this work pursuant * to contract no. DE-AC03-76SF00098 between the United States * Department of Energy and the University of California. * * Redistribution and use in source and binary forms are permitted provided * that: (1) source distributions retain this entire copyright notice and * comment, and (2) distributions including binaries display the following * acknowledgement: ``This product includes software developed by the * University of California, Berkeley and its contributors'' in the * documentation or other materials provided with the distribution and in * all advertising materials mentioning features or use of this software. * Neither the name of the University nor the names of its contributors may * be used to endorse or promote products derived from this software without * specific prior written permission. * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. */ /* $Header: /home/ncvs/src/usr.bin/lex/ecs.c,v 1.1.1.1 1994/08/24 13:10:33 csgr Exp $ */ #include "flexdef.h" /* ccl2ecl - convert character classes to set of equivalence classes */ void ccl2ecl() { int i, ich, newlen, cclp, ccls, cclmec; for ( i = 1; i <= lastccl; ++i ) { /* We loop through each character class, and for each character * in the class, add the character's equivalence class to the * new "character" class we are creating. Thus when we are all * done, character classes will really consist of collections * of equivalence classes */ newlen = 0; cclp = cclmap[i]; for ( ccls = 0; ccls < ccllen[i]; ++ccls ) { ich = ccltbl[cclp + ccls]; cclmec = ecgroup[ich]; if ( cclmec > 0 ) { ccltbl[cclp + newlen] = cclmec; ++newlen; } } ccllen[i] = newlen; } } /* cre8ecs - associate equivalence class numbers with class members * * fwd is the forward linked-list of equivalence class members. bck * is the backward linked-list, and num is the number of class members. * * Returned is the number of classes. */ int cre8ecs( fwd, bck, num ) int fwd[], bck[], num; { int i, j, numcl; numcl = 0; /* Create equivalence class numbers. From now on, ABS( bck(x) ) * is the equivalence class number for object x. If bck(x) * is positive, then x is the representative of its equivalence * class. */ for ( i = 1; i <= num; ++i ) if ( bck[i] == NIL ) { bck[i] = ++numcl; for ( j = fwd[i]; j != NIL; j = fwd[j] ) bck[j] = -numcl; } return numcl; } /* mkeccl - update equivalence classes based on character class xtions * * synopsis * Char ccls[]; * int lenccl, fwd[llsiz], bck[llsiz], llsiz, NUL_mapping; * void mkeccl( Char ccls[], int lenccl, int fwd[llsiz], int bck[llsiz], * int llsiz, int NUL_mapping ); * * ccls contains the elements of the character class, lenccl is the * number of elements in the ccl, fwd is the forward link-list of equivalent * characters, bck is the backward link-list, and llsiz size of the link-list. * * NUL_mapping is the value which NUL (0) should be mapped to. */ void mkeccl( ccls, lenccl, fwd, bck, llsiz, NUL_mapping ) Char ccls[]; int lenccl, fwd[], bck[], llsiz, NUL_mapping; { int cclp, oldec, newec; int cclm, i, j; static unsigned char cclflags[CSIZE]; /* initialized to all '\0' */ /* Note that it doesn't matter whether or not the character class is * negated. The same results will be obtained in either case. */ cclp = 0; while ( cclp < lenccl ) { cclm = ccls[cclp]; if ( NUL_mapping && cclm == 0 ) cclm = NUL_mapping; oldec = bck[cclm]; newec = cclm; j = cclp + 1; for ( i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i] ) { /* look for the symbol in the character class */ for ( ; j < lenccl; ++j ) { register int ccl_char; if ( NUL_mapping && ccls[j] == 0 ) ccl_char = NUL_mapping; else ccl_char = ccls[j]; if ( ccl_char > i ) break; if ( ccl_char == i && ! cclflags[j] ) { /* We found an old companion of cclm * in the ccl. Link it into the new * equivalence class and flag it as * having been processed. */ bck[i] = newec; fwd[newec] = i; newec = i; /* Set flag so we don't reprocess. */ cclflags[j] = 1; /* Get next equivalence class member. */ /* continue 2 */ goto next_pt; } } /* Symbol isn't in character class. Put it in the old * equivalence class. */ bck[i] = oldec; if ( oldec != NIL ) fwd[oldec] = i; oldec = i; next_pt: ; } if ( bck[cclm] != NIL || oldec != bck[cclm] ) { bck[cclm] = NIL; fwd[oldec] = NIL; } fwd[newec] = NIL; /* Find next ccl member to process. */ for ( ++cclp; cclflags[cclp] && cclp < lenccl; ++cclp ) { /* Reset "doesn't need processing" flag. */ cclflags[cclp] = 0; } } } /* mkechar - create equivalence class for single character */ void mkechar( tch, fwd, bck ) int tch, fwd[], bck[]; { /* If until now the character has been a proper subset of * an equivalence class, break it away to create a new ec */ if ( fwd[tch] != NIL ) bck[fwd[tch]] = bck[tch]; if ( bck[tch] != NIL ) fwd[bck[tch]] = fwd[tch]; fwd[tch] = NIL; bck[tch] = NIL; }