Return to grep2.c CVS log

Up to [MW Coherent from dump] / coherent / d / bin / grep

Annotation of coherent/d/bin/grep/grep2.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Regular expression routines.
        !             3:  * These routines are currently used by grep but
        !             4:  * they are somewhat general and thus could be
        !             5:  * used elsewhere.
        !             6:  */
        !             7: 
        !             8: #include <stdio.h>
        !             9: #include <ctype.h>
        !            10: #include "grep.h"
        !            11: 
        !            12: char   *newcc();
        !            13: char   *e_exec();
        !            14: 
        !            15: 
        !            16: static char    repri[] = {
        !            17:        0 /* REEND */,  2 /* STEND */,
        !            18:        3 /* OR */,     6 /* LPAR */,
        !            19:        1 /* RPAR */,   5 /* CLOS */,
        !            20:        5 /* NECLOS */, 5 /* ZORO */,
        !            21:        4 /* CONC */
        !            22: };
        !            23: 
        !            24: RE     **rebuild();
        !            25: RE     *renode();
        !            26: static union rebit     relval;
        !            27: static char    cc[NCLASS];
        !            28: static (*reinf)();
        !            29: static (*reunf)();
        !            30: static char    *rein;
        !            31: 
        !            32: static char    resyn[] = "Regular expression syntax error";
        !            33: static char    reoflo[] = "Regular expression overflow";
        !            34: static char    nospace[] = "Out of space";
        !            35: 
        !            36: char   *reerror;               /* Erro code */
        !            37: int    redual;                 /* Set for dual-case comparisons */
        !            38: int    refull;                 /* Full expressions accepted */
        !            39: 
        !            40: /*
        !            41:  * Lexical token reader for
        !            42:  * regular expressions.
        !            43:  */
        !            44: static
        !            45: relex(ec)
        !            46: {
        !            47:        register c;
        !            48: 
        !            49:        if ((c = (*reinf)()) == ec)
        !            50:                return (REEND);
        !            51:        switch (c) {
        !            52:        case EOF:
        !            53:        case '\n':
        !            54:                reerror = "Non-terminated regular expression";
        !            55:                return (REEND);
        !            56: 
        !            57:        case '[':
        !            58:                return (cclass(ec));
        !            59: 
        !            60:        case '^':
        !            61:                return (BOL);
        !            62: 
        !            63:        case '$':
        !            64:                return (EOL);
        !            65: 
        !            66:        case '(':
        !            67:                if (!refull)
        !            68:                        goto def;
        !            69:                return (LPAR);
        !            70: 
        !            71:        case ')':
        !            72:                if (!refull)
        !            73:                        goto def;
        !            74:                return (RPAR);
        !            75: 
        !            76:        case '.':
        !            77:                return (ANY);
        !            78: 
        !            79:        case '|':
        !            80:                if (!refull)
        !            81:                        goto def;
        !            82:                return (OR);
        !            83: 
        !            84:        case '*':
        !            85:                return (CLOS);
        !            86: 
        !            87:        case '?':
        !            88:                if (!refull)
        !            89:                        goto def;
        !            90:                return (ZORO);
        !            91: 
        !            92:        case '+':
        !            93:                if (!refull)
        !            94:                        goto def;
        !            95:                return (NECLOS);
        !            96: 
        !            97:        case '\\':
        !            98:                c = (*reinf)();
        !            99:        default:
        !           100:        def:
        !           101:                relval.u_ival = c;
        !           102:                return (redual ? DCONC : CONC);
        !           103:        }
        !           104: }
        !           105: 
        !           106: /*
        !           107:  * Read in a character class from
        !           108:  * an RE (called from relex).
        !           109:  */
        !           110: static
        !           111: cclass(ec)
        !           112: int ec;
        !           113: {
        !           114:        register c, i, pc;
        !           115:        int comp;
        !           116: 
        !           117:        for (i=0; i<sizeof cc; i++)
        !           118:                cc[i] = 0;
        !           119:        if ((c = (*reinf)()) != '^') {
        !           120:                comp = 0;
        !           121:                (*reunf)(c);
        !           122:        } else
        !           123:                comp = 1;
        !           124:        pc = ec;
        !           125:        while ((c = (*reinf)()) != ']') {
        !           126:                if (c == ec) {
        !           127:                        reerror = "Non-terminated character class";
        !           128:                        return (REEND);
        !           129:                }
        !           130:                if (c=='-' && pc!=ec) {
        !           131:                        if ((c = (*reinf)()) == ']')
        !           132:                                break;
        !           133:                        for (i=pc; i<=c; i++)
        !           134:                                cc[i/NBPC] |= 1<<(i%NBPC);
        !           135:                        pc = ec;
        !           136:                } else {
        !           137:                        cc[c/NBPC] |= 1<<(c%NBPC);
        !           138:                        pc = c;
        !           139:                }
        !           140:        }
        !           141:        if (comp)
        !           142:                for (i=0; i<sizeof cc; i++)
        !           143:                        cc[i] ^= -1;
        !           144:        if ((relval.u_cptr = newcc(cc)) == NULL)
        !           145:                return (REEND);
        !           146:        return (redual ? DCCLASS : CCLASS);
        !           147: }
        !           148: 
        !           149: /*
        !           150:  * Allocate space for a new character class
        !           151:  * and copy into it.
        !           152:  */
        !           153: static char *
        !           154: newcc(occ)
        !           155: register char *occ;
        !           156: {
        !           157:        register char *ncc;
        !           158:        register unsigned n;
        !           159:        char *rcc;
        !           160: 
        !           161:        n = NCLASS;
        !           162:        if ((rcc = ncc = malloc(n)) == NULL) {
        !           163:                reerror = nospace;
        !           164:                return (NULL);
        !           165:        }
        !           166:        do {
        !           167:                *ncc++ = *occ++;
        !           168:        } while (--n);
        !           169:        return (rcc);
        !           170: }
        !           171: 
        !           172: /*
        !           173:  * Parse a regular expression.
        !           174:  * The arguments are an input string to parse (`in'),
        !           175:  * the end character to terminated the expression (`ec'),
        !           176:  * and (if `in' is NULL) functions to get and unget characters,
        !           177:  * getf and ungetf, respectively.
        !           178:  */
        !           179: RE *
        !           180: reparse(in, ec, getf, ungetf)
        !           181: char *in;
        !           182: int (*getf)(), (*ungetf)();
        !           183: {
        !           184:        RE *restk[NRE];
        !           185:        struct opstk {
        !           186:                char    o_op;
        !           187:                char    o_pri;
        !           188:        } opstk[NRE];
        !           189:        register struct opstk *osp;
        !           190:        register op;
        !           191:        register RE **rsp;
        !           192:        int concflg, op1, pri;
        !           193: 
        !           194:        if ((rein = in) != NULL) {
        !           195:                reinf = reget;
        !           196:                reunf = reunget;
        !           197:        } else {
        !           198:                reinf = getf;
        !           199:                reunf = ungetf;
        !           200:        }
        !           201:        reerror = NULL;
        !           202:        concflg = 0;
        !           203:        osp = opstk;
        !           204:        osp->o_op = STEND;
        !           205:        osp->o_pri = repri[STEND];
        !           206:        rsp = restk;
        !           207:        *rsp++ = NULL;
        !           208: 
        !           209:        for (;;) {
        !           210:                if (termop(op = relex(ec))) {
        !           211:                        if ((*rsp++ = renode(op, relval.u_cptr, NULL)) == NULL)
        !           212:                                return (NULL);
        !           213:                        if (rsp >= &restk[NRE-1]) {
        !           214:                                reerror = reoflo;
        !           215:                                return (NULL);
        !           216:                        }
        !           217:                        if (!concflg) {
        !           218:                                concflg++;
        !           219:                                continue;
        !           220:                        } else
        !           221:                                op = CONC;
        !           222:                } else if (op == OR) {
        !           223:                        if (!concflg) {
        !           224:                                reerror = resyn;
        !           225:                                return (NULL);
        !           226:                        }
        !           227:                        concflg = 0;
        !           228:                } else if (op==CLOS || op==NECLOS || op==ZORO) {
        !           229:                        if (!concflg) {
        !           230:                                reerror = resyn;
        !           231:                                return (NULL);
        !           232:                        }
        !           233:                } else if (op == LPAR) {
        !           234:                        if (concflg) {
        !           235:                                (++osp)->o_op = CONC;
        !           236:                                osp->o_pri = repri[CONC];
        !           237:                                concflg = 0;
        !           238:                        }
        !           239:                }
        !           240:                pri = repri[op];
        !           241:                for (;;) {
        !           242:                        if (reerror != NULL)
        !           243:                                return (NULL);
        !           244:                        if (pri>osp->o_pri || (op==CONC && osp->o_op==CONC)) {
        !           245:                                if (op == LPAR)
        !           246:                                        pri = repri[RPAR];
        !           247:                                if (osp >= &opstk[NRE-1]) {
        !           248:                                        reerror = reoflo;
        !           249:                                        return (NULL);
        !           250:                                }
        !           251:                                (++osp)->o_op = op;
        !           252:                                osp->o_pri = pri;
        !           253:                                if (!postop(op))
        !           254:                                        break;
        !           255:                                else
        !           256:                                        pri = repri[REEND];
        !           257:                        }
        !           258:                        switch (op1 = (osp--)->o_op) {
        !           259:                        case STEND:
        !           260:                                if (op == REEND)
        !           261:                                        return (*--rsp);
        !           262:                                osp++;
        !           263:                                break;
        !           264: 
        !           265:                        case LPAR:
        !           266:                                if (op != RPAR) {
        !           267:                                        reerror = "Unbalanced parentheses";
        !           268:                                        return (NULL);
        !           269:                                }
        !           270:                                break;
        !           271: 
        !           272:                        default:
        !           273:                                rsp = rebuild(rsp, op1);
        !           274:                                continue;
        !           275:                        }
        !           276:                        break;
        !           277:                }
        !           278:        }
        !           279: }
        !           280: 
        !           281: 
        !           282: static RE **
        !           283: rebuild(rsp, op)
        !           284: register RE **rsp;
        !           285: {
        !           286:        register RE *left, *right;
        !           287: 
        !           288:        switch (op) {
        !           289:        case OR:
        !           290:                right = *--rsp;
        !           291:                left = *--rsp;
        !           292:                break;
        !           293: 
        !           294:        case CLOS:
        !           295:        case NECLOS:
        !           296:        case ZORO:
        !           297:                left = *--rsp;
        !           298:                right = NULL;
        !           299:                break;
        !           300: 
        !           301:        case CONC:
        !           302:                right = *--rsp;
        !           303:                left = *--rsp;
        !           304:                if (left->r_next == NULL)
        !           305:                        left->r_next = right;
        !           306:                else {
        !           307:                        for (; left->r_next->r_next!=NULL; left = left->r_next)
        !           308:                                ;
        !           309:                        left->r_next->r_next = right;
        !           310:                }
        !           311:                return (++rsp);
        !           312: 
        !           313:        default:
        !           314:                reerror = "RE botch in rebuild";
        !           315:        }
        !           316:        *rsp++ = renode(op, left, right);
        !           317:        return (rsp);
        !           318: }
        !           319: 
        !           320: /*
        !           321:  * Build regular expression node.
        !           322:  */
        !           323: static RE *
        !           324: renode(op, left, right)
        !           325: RE *left, *right;
        !           326: {
        !           327:        register RE *rep;
        !           328: 
        !           329:        if ((rep = (RE *)malloc(sizeof (RE))) == NULL) {
        !           330:                reerror = nospace;
        !           331:                return (NULL);
        !           332:        }
        !           333:        rep->r_next = (RE*)NULL;
        !           334:        rep->r_op = op;
        !           335:        rep->r_left.u_re = left;
        !           336:        rep->r_right.u_re = right;
        !           337:        return (rep);
        !           338: }
        !           339: 
        !           340: static char    *sb;            /* string beginning */
        !           341: 
        !           342: /*
        !           343:  * User-callable driver for regular expression
        !           344:  * execution.  Called with regular expression code and
        !           345:  * text string.
        !           346:  */
        !           347: reinterp(rep, s)
        !           348: RE *rep;
        !           349: register char *s;
        !           350: {
        !           351:        sb = s;
        !           352:        if (rep!=NULL && rep->r_op==BOL)
        !           353:                return(e_exec(rep, s) != NULL);
        !           354:        for (; *s!='\0'; s++)
        !           355:                if (e_exec(rep, s) != NULL)
        !           356:                        return (1);
        !           357:        return (0);
        !           358: }
        !           359: 
        !           360: /*
        !           361:  * Internal regular expression
        !           362:  * execution routines
        !           363:  */
        !           364: static char *
        !           365: e_exec(rep, s)
        !           366: register RE *rep;
        !           367: register char *s;
        !           368: {
        !           369:        register c;
        !           370:        char *ss, *es;
        !           371: 
        !           372:        for ( ; rep!=NULL; rep = rep->r_next)
        !           373:                switch (rep->r_op) {
        !           374:                case BOL:
        !           375:                        if (s != sb)
        !           376:                                return (NULL);
        !           377:                        break;
        !           378: 
        !           379:                case EOL:
        !           380:                        if (*s != '\0')
        !           381:                                return (NULL);
        !           382:                        break;
        !           383: 
        !           384:                case ANY:
        !           385:                        if (*s++ == '\0')
        !           386:                                return (NULL);
        !           387:                        break;
        !           388: 
        !           389:                case CONC:
        !           390:                        if (*s++ != rep->r_left.u_ival)
        !           391:                                return (NULL);
        !           392:                        break;
        !           393: 
        !           394:                case DCONC:
        !           395:                        if (islower(rep->r_left.u_ival)) {
        !           396:                                if (isupper(c = *s++))
        !           397:                                        c = tolower(c);
        !           398:                                if (c != rep->r_left.u_ival)
        !           399:                                        return (NULL);
        !           400:                        } else
        !           401:                                if (*s++ != rep->r_left.u_ival)
        !           402:                                        return (NULL);
        !           403:                        break;
        !           404: 
        !           405:                case CCLASS:
        !           406:                        c = *s++;
        !           407:                        if ((rep->r_left.u_cptr[c/NBPC] & (1<<(c%NBPC))) == 0)
        !           408:                                return (NULL);
        !           409:                        break;
        !           410: 
        !           411:                case DCCLASS:
        !           412:                        if ((c = *s++)>='A' && c<='Z')
        !           413:                                c |= 'a'-'A';
        !           414:                        if ((rep->r_left.u_cptr[c/NBPC] & (1<<(c%NBPC))) == 0)
        !           415:                                return (NULL);
        !           416:                        break;
        !           417: 
        !           418:                case OR:
        !           419:                        ss = s;
        !           420:                        if ((s = e_exec(rep->r_left.u_re, s)) == NULL)
        !           421:                                if ((s = e_exec(rep->r_right.u_re, ss))==NULL)
        !           422:                                        return (NULL);
        !           423:                        break;
        !           424: 
        !           425:                case CLOS:
        !           426:                        ss = s;
        !           427:                        while ((es = e_exec(rep->r_left.u_re, s)) != NULL)
        !           428:                                s = es;
        !           429:                        while (s >= ss)
        !           430:                                if ((es = e_exec(rep->r_next, s--))!=NULL)
        !           431:                                        return(es);
        !           432:                        return (NULL);
        !           433: 
        !           434:                case NECLOS:
        !           435:                        ss = s;
        !           436:                        while ((es = e_exec(rep->r_left.u_re, s)) != NULL)
        !           437:                                s = es;
        !           438:                        while (s > ss)
        !           439:                                if ((es = e_exec(rep->r_next, s--))!=NULL)
        !           440:                                        return (es);
        !           441:                        return (NULL);
        !           442: 
        !           443:                case ZORO:
        !           444:                        ss = s;
        !           445:                        if ((es = e_exec(rep->r_left.u_re, s)) != NULL)
        !           446:                                s = es;
        !           447:                        while (s >= ss)
        !           448:                                if ((es = e_exec(rep->r_next, s--))!=NULL)
        !           449:                                        return (es);
        !           450:                        return (NULL);
        !           451: 
        !           452:                default:
        !           453:                        fprintf(stderr, "Regular expression botch\n");
        !           454:                        exit(2);
        !           455:                }
        !           456:        return (s);
        !           457: }
        !           458: 
        !           459: /*
        !           460:  * Default functions to get and unget
        !           461:  * characters from the regular expression.
        !           462:  */
        !           463: static
        !           464: reget()
        !           465: {
        !           466:        return (*rein++);
        !           467: }
        !           468: 
        !           469: static
        !           470: reunget(c)
        !           471: {
        !           472:        --rein;
        !           473: }

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