Return to b.c CVS log

Up to [Research Unix] / researchv8dc / cmd / awk

Annotation of researchv8dc/cmd/awk/b.c, revision 1.1

1.1     ! root        1: #define        DEBUG
        !             2: 
        !             3: #include "awk.h"
        !             4: #include "ctype.h"
        !             5: #include "stdio.h"
        !             6: #include "y.tab.h"
        !             7: 
        !             8: extern Node *op2();
        !             9: #define MAXLIN 256
        !            10: 
        !            11: #define type(v)        v->nobj
        !            12: #define left(v)        v->narg[0]
        !            13: #define right(v)       v->narg[1]
        !            14: #define parent(v)      v->nnext
        !            15: 
        !            16: #define LEAF   case CCL: case NCCL: case CHAR: case DOT: case FINAL: case ALL:
        !            17: #define UNARY  case STAR: case PLUS: case QUEST:
        !            18: 
        !            19: /* encoding in tree Nodes:
        !            20:        leaf (CCL, NCCL, CHAR, DOT, FINAL, ALL): left is index, right contains value or pointer to value
        !            21:        unary (STAR, PLUS, QUEST): left is child, right is null
        !            22:        binary (CAT, OR): left and right are children
        !            23:        parent contains pointer to parent
        !            24: */
        !            25: 
        !            26: 
        !            27: char   chars[MAXLIN];
        !            28: int    setvec[MAXLIN];
        !            29: Node   *point[MAXLIN];
        !            30: 
        !            31: int    rtok;
        !            32: int    rlxval;
        !            33: char   *prestr;
        !            34: 
        !            35: int    setcnt;
        !            36: static int line;
        !            37: 
        !            38: char   *patbeg;
        !            39: int    patlen;
        !            40: 
        !            41: fa *makedfa(p, anchor) /* returns dfa for tree pointed to by p */
        !            42: Node *p;       /* anchor = 1 for anchored matches, else 0 */
        !            43: int anchor;
        !            44: {
        !            45:        Node *p1;
        !            46:        fa *f;
        !            47:        int i;
        !            48:        fcell *pf;
        !            49: 
        !            50:        p1 = op2(CAT, op2(STAR, op2(ALL, (Node *) 0, (Node *) 0), (Node *) 0), p);
        !            51:                /* put ALL STAR in front of reg.  exp. */
        !            52:        p1 = op2(CAT, p1, op2(FINAL, (Node *) 0, (Node *) 0));
        !            53:                /* put FINAL after reg.  exp. */
        !            54: 
        !            55:        line = 0;
        !            56:        penter(p1);     /* enter parent pointers and leaf indices */
        !            57:        if ((f = (fa *) Calloc (1, sizeof(fa) + (line-1)*sizeof(rrow))) == NULL)
        !            58:                overflo("no room for fa");
        !            59:        cfoll(f, p1);   /* set up follow sets */
        !            60:        freetr(p1);
        !            61:        f->accept = line-1;
        !            62: /*
        !            63: printf("retab %o:\n", f->re);
        !            64: printf("       ltype   lval    lfollow\n");
        !            65: for (i=0; i<line; i++) {
        !            66:        printf("%d      %d      %c      %o\n", i, f->re[i].ltype, f->re[i].lval, f->re[i].lfollow);
        !            67:        pf = f->re[i].lfollow;
        !            68:        while (pf != 0) {
        !            69:                printf("                                %o: %d  %o\n", pf, pf->info, pf->link);
        !            70:                pf = pf->link;
        !            71:        }
        !            72: }
        !            73: */
        !            74:        f->initstat = makeinit(f, anchor);
        !            75:        f->reset = 0;
        !            76:        return f;
        !            77: }
        !            78: 
        !            79: int makeinit(f, anchor)
        !            80: fa *f;
        !            81: int anchor;
        !            82: {
        !            83:        register i;
        !            84:        fcell *pf;
        !            85: 
        !            86:        f->curstat = 2;
        !            87:        f->out[2] = 0;
        !            88:        pf = f->posns[2] = f->re[0].lfollow;
        !            89:        while (pf != 0) {
        !            90:                if (pf->info == f->accept) {
        !            91:                        f->out[2] = 1;
        !            92:                        break;
        !            93:                }
        !            94:                pf = pf->link;
        !            95:        }
        !            96:        for (i=0; i<NCHARS; i++)
        !            97:                f->gototab[2][i] = 0;
        !            98:        f->curstat = cgoto(f, 2, HAT);
        !            99:        if (anchor) {
        !           100:                f->posns[1] = 0;
        !           101:                f->posns[0] = f->posns[2] = f->posns[2]->link;
        !           102:                f->out[0] = f->out[2];
        !           103:                if (f->curstat != 2)
        !           104:                        f->posns[f->curstat] = f->posns[f->curstat]->link;
        !           105:        }
        !           106:        return f->curstat;
        !           107: }
        !           108: 
        !           109: penter(p)      /* set up parent pointers and leaf indices */
        !           110: Node *p;
        !           111: {
        !           112:        switch(type(p)) {
        !           113:                LEAF
        !           114:                        left(p) = (Node *) line;
        !           115:                        point[line++] = p;
        !           116:                        break;
        !           117:                UNARY
        !           118:                        penter(left(p));
        !           119:                        parent(left(p)) = p;
        !           120:                        break;
        !           121:                case CAT:
        !           122:                case OR:
        !           123:                        penter(left(p));
        !           124:                        penter(right(p));
        !           125:                        parent(left(p)) = p;
        !           126:                        parent(right(p)) = p;
        !           127:                        break;
        !           128:                default:
        !           129:                        error(FATAL, "unknown type %d in penter\n", type(p));
        !           130:                        break;
        !           131:        }
        !           132: }
        !           133: 
        !           134: freetr(p)      /* free parse tree and follow sets */
        !           135: Node *p;
        !           136: {
        !           137:        switch(type(p)) {
        !           138:                LEAF
        !           139:                        xfree(p);
        !           140:                        break;
        !           141:                UNARY
        !           142:                        freetr(left(p));
        !           143:                        xfree(p);
        !           144:                        break;
        !           145:                case CAT:
        !           146:                case OR:
        !           147:                        freetr(left(p));
        !           148:                        freetr(right(p));
        !           149:                        xfree(p);
        !           150:                        break;
        !           151:                default:
        !           152:                        error(FATAL, "unknown type %d in freetr", type(p));
        !           153:                        break;
        !           154:        }
        !           155: }
        !           156: 
        !           157: char *cclenter(p)
        !           158: register char *p;
        !           159: {
        !           160:        register i, c;
        !           161:        char *op;
        !           162: 
        !           163:        op = p;
        !           164:        i = 0;
        !           165:        while ((c = *p++) != 0) {
        !           166:                if (c == '-' && i > 0 && chars[i-1] != 0) {
        !           167:                        if (*p != 0) {
        !           168:                                c = chars[i-1];
        !           169:                                while (c < *p) {
        !           170:                                        if (i >= MAXLIN)
        !           171:                                                overflo("character class too big");
        !           172:                                        chars[i++] = ++c;
        !           173:                                }
        !           174:                                p++;
        !           175:                                continue;
        !           176:                        }
        !           177:                }
        !           178:                if (i >= MAXLIN)
        !           179:                        overflo("character class too big");
        !           180:                chars[i++] = c;
        !           181:        }
        !           182:        chars[i++] = '\0';
        !           183:        dprintf("cclenter: in = |%s|, out = |%s|\n", op, chars, NULL);
        !           184:        xfree(op);
        !           185:        return(tostring(chars));
        !           186: }
        !           187: 
        !           188: overflo(s)
        !           189:        char *s;
        !           190: {
        !           191:        error(FATAL, "regular expression too big: %s", s);
        !           192: }
        !           193: 
        !           194: cfoll(f, v)            /* enter follow set of each leaf of vertex v into lfollow[leaf] */
        !           195: fa *f;
        !           196: register Node *v;
        !           197: {
        !           198:        register i;
        !           199:        fcell **prev;
        !           200:        fcell *p;
        !           201: 
        !           202:        switch(type(v)) {
        !           203:                LEAF
        !           204:                        f->re[(int) left(v)].ltype = type(v);
        !           205:                        f->re[(int) left(v)].lval = (int) right(v);
        !           206:                        for (i=0; i<line; i++)
        !           207:                                setvec[i] = 0;
        !           208:                        follow(v);
        !           209:                        prev = &(f->re[(int) left(v)].lfollow);
        !           210:                        for (i=0; i<line; i++)
        !           211:                                if (setvec[i] == 1) {
        !           212:                                        if ((p = (fcell *) Malloc(sizeof(struct fcell))) == NULL)
        !           213:                                                overflo("follow set overflow");
        !           214:                                        p->info = i;
        !           215:                                        *prev = p;
        !           216:                                        prev = &(p->link);
        !           217:                                }
        !           218:                        *prev = (fcell *) 0;
        !           219:                        break;
        !           220:                UNARY
        !           221:                        cfoll(f,left(v));
        !           222:                        break;
        !           223:                case CAT:
        !           224:                case OR:
        !           225:                        cfoll(f,left(v));
        !           226:                        cfoll(f,right(v));
        !           227:                        break;
        !           228:                default:
        !           229:                        error(FATAL, "unknown type %d in cfoll", type(v));
        !           230:        }
        !           231: }
        !           232: 
        !           233: first(p)                       /* collects initially active leaves of p into setvec */
        !           234: register Node *p;              /* returns 0 or 1 depending on whether p matches empty string */
        !           235: {
        !           236:        register b;
        !           237: 
        !           238:        switch(type(p)) {
        !           239:                LEAF
        !           240:                        if (setvec[(int) left(p)] != 1) {
        !           241:                                setvec[(int) left(p)] = 1;
        !           242:                                setcnt++;
        !           243:                        }
        !           244:                        if (type(p) == CCL && (*(char *) right(p)) == '\0')
        !           245:                                return(0);              /* empty CCL */
        !           246:                        else return(1);
        !           247:                case PLUS:
        !           248:                        if (first(left(p)) == 0) return(0);
        !           249:                        return(1);
        !           250:                case STAR:
        !           251:                case QUEST:
        !           252:                        first(left(p));
        !           253:                        return(0);
        !           254:                case CAT:
        !           255:                        if (first(left(p)) == 0 && first(right(p)) == 0) return(0);
        !           256:                        return(1);
        !           257:                case OR:
        !           258:                        b = first(right(p));
        !           259:                        if (first(left(p)) == 0 || b == 0) return(0);
        !           260:                        return(1);
        !           261:        }
        !           262:        error(FATAL, "unknown type %d in first\n", type(p));
        !           263:        return(-1);
        !           264: }
        !           265: 
        !           266: follow(v)
        !           267: Node *v;               /* collects leaves that can follow v into setvec */
        !           268: {
        !           269:        Node *p;
        !           270: 
        !           271:        if (type(v) == FINAL)
        !           272:                return;
        !           273:        p = parent(v);
        !           274:        switch (type(p)) {
        !           275:                case STAR:
        !           276:                case PLUS:      first(v);
        !           277:                                follow(p);
        !           278:                                return;
        !           279: 
        !           280:                case OR:
        !           281:                case QUEST:     follow(p);
        !           282:                                return;
        !           283: 
        !           284:                case CAT:       if (v == left(p)) {     /* v is left child of p */
        !           285:                                        if (first(right(p)) == 0) {
        !           286:                                                follow(p);
        !           287:                                                return;
        !           288:                                        }
        !           289:                                }
        !           290:                                else            /* v is right child */
        !           291:                                        follow(p);
        !           292:                                return;
        !           293:        }
        !           294: }
        !           295: 
        !           296: member(c, s)   /* is c in s? */
        !           297: register char c, *s;
        !           298: {
        !           299:        while (*s)
        !           300:                if (c == *s++)
        !           301:                        return(1);
        !           302:        return(0);
        !           303: }
        !           304: 
        !           305: 
        !           306: match(f, p)
        !           307: register fa *f;
        !           308: register char *p;
        !           309: {
        !           310:        register s,ns;
        !           311: 
        !           312:        s = (f->reset)?makeinit(f,0):f->initstat;
        !           313:        if (f->out[s])
        !           314:                return(1);
        !           315:        do {
        !           316:                if (ns=f->gototab[s][*p])
        !           317:                        s=ns;
        !           318:                else
        !           319:                        s=cgoto(f,s,*p);
        !           320:                if (f->out[s])
        !           321:                        return(1);
        !           322:        } while(*p++ != 0);
        !           323:        return(0);
        !           324: }
        !           325: 
        !           326: pmatch(f, p)
        !           327: register fa *f;
        !           328: register char *p;
        !           329: {
        !           330:        register s, ns;
        !           331:        register char *q;
        !           332:        extern char *patbeg;
        !           333:        extern int patlen;
        !           334:        int i;
        !           335: 
        !           336:        s = (f->reset)?makeinit(f,1):f->initstat;
        !           337:        patlen = -1;
        !           338:        do {
        !           339:                q = p;
        !           340:                do {
        !           341: /*
        !           342: fcell *pp;
        !           343: printf("pmatch: p = %o, *p = %c, q = %o, *q = %c\n", p, *p, q, *q);
        !           344: printf("state %d: ", s);
        !           345: pp = f->posns[s];
        !           346: while (pp != 0) {
        !           347:        printf(" %d", pp->info);
        !           348:        pp = pp->link;
        !           349: }
        !           350: printf("       out = %d\n", f->out[s]);
        !           351: */
        !           352:                        if (f->out[s])          /* final state */
        !           353:                                patlen = q-p;
        !           354: /*
        !           355: printf("       g(%d, %c) = ", s, *q);
        !           356: */
        !           357:                        if (ns=f->gototab[s][*q])
        !           358:                                s=ns;
        !           359:                        else
        !           360:                                s=cgoto(f,s,*q);
        !           361: /*
        !           362: printf("%d\n", s);
        !           363: */
        !           364:                        if (s==1)       /* no transition */
        !           365:                                if (patlen >= 0) {
        !           366:                                        patbeg = p;
        !           367:                                        return(1);
        !           368:                                }
        !           369:                                else
        !           370:                                        goto nextin;    /* no match */
        !           371:                } while (*q++ != 0);
        !           372:                if (f->out[s])
        !           373:                        patlen  = q-p;
        !           374:                if (patlen >=0 ) {
        !           375:                        patbeg = p;
        !           376:                        return(1);
        !           377:                }
        !           378:        nextin:
        !           379:                s = 2;
        !           380:                if (f->reset) {
        !           381:                        s = f->initstat = f->curstat = 2;
        !           382:                        f->posns[2] = f->posns[0];
        !           383:                        f->out[2] = f->out[0];
        !           384:                        for (i=0; i<NCHARS; i++)
        !           385:                                f->gototab[2][i] = 0;
        !           386:                }
        !           387:        } while (*p++ != 0);
        !           388:        return (0);
        !           389: }
        !           390: 
        !           391: nematch(f, p)
        !           392: register fa *f;
        !           393: register char *p;
        !           394: {
        !           395:        register s, ns;
        !           396:        register char *q;
        !           397:        extern char *patbeg;
        !           398:        extern int patlen;
        !           399:        int i;
        !           400: 
        !           401:        s = (f->reset)?makeinit(f,1):f->initstat;
        !           402:        patlen = -1;
        !           403:        while (*p) {
        !           404:                q = p;
        !           405:                do {
        !           406:                        if (f->out[s])          /* final state */
        !           407:                                patlen = q-p;
        !           408:                        if (ns=f->gototab[s][*q])
        !           409:                                s=ns;
        !           410:                        else
        !           411:                                s=cgoto(f,s,*q);
        !           412:                        if (s==1)       /* no transition */
        !           413:                                if (patlen > 0) {
        !           414:                                        patbeg = p;
        !           415:                                        return(1);
        !           416:                                }
        !           417:                                else
        !           418:                                        goto nnextin;   /* no nonempty match */
        !           419:                } while (*q++ != 0);
        !           420:                if (f->out[s])
        !           421:                        patlen  = q-p;
        !           422:                if (patlen >0 ) {
        !           423:                        patbeg = p;
        !           424:                        return(1);
        !           425:                }
        !           426:        nnextin:
        !           427:                s = 2;
        !           428:                if (f->reset) {
        !           429:                        s = f->initstat = f->curstat = 2;
        !           430:                        f->posns[2] = f->posns[0];
        !           431:                        f->out[2] = f->out[0];
        !           432:                        for (i=0; i<NCHARS; i++)
        !           433:                                f->gototab[2][i] = 0;
        !           434:                }
        !           435:        p++;
        !           436:        }
        !           437:        return (0);
        !           438: }
        !           439: 
        !           440: Node *regexp(), *primary(), *concat(), *alt(), *unary();
        !           441: 
        !           442: Node *reparse(p)
        !           443: char *p;
        !           444: {
        !           445:        /* parses regular expression pointed to by p */
        !           446:        /* uses relex() to scan regular expression */
        !           447:        Node *np;
        !           448: 
        !           449:        dprintf("reparse <%s>\n", p);
        !           450:        prestr = p;             /* prestr points to string to be parsed */
        !           451:        rtok = relex();
        !           452:        if (rtok == '\0')
        !           453:                error(FATAL, "empty regular expression");
        !           454:        np = regexp();
        !           455:        if (rtok == '\0') return(np);
        !           456:        else
        !           457:                error(FATAL, "syntax error in regular expression");
        !           458: }
        !           459: Node *regexp(){
        !           460:        return (alt(concat(primary())));
        !           461: }
        !           462: Node *primary(){
        !           463:        Node *np;
        !           464:        switch(rtok){
        !           465:        case CHAR:
        !           466:                np = op2(CHAR, (Node *) 0, rlxval);
        !           467:                rtok = relex();
        !           468:                return (unary(np));
        !           469:        case ALL:
        !           470:                rtok = relex();
        !           471:                return (unary(op2(ALL, (Node *) 0, (Node *) 0)));
        !           472:        case DOT:
        !           473:                rtok = relex();
        !           474:                return (unary(op2(DOT, (Node *) 0, (Node *) 0)));
        !           475:        case CCL:
        !           476:                np = op2(CCL, (Node *) 0, cclenter(rlxval));
        !           477:                rtok = relex();
        !           478:                return (unary(np));
        !           479:        case NCCL:
        !           480:                np = op2(NCCL, (Node *) 0, cclenter(rlxval));
        !           481:                rtok = relex();
        !           482:                return (unary(np));
        !           483:        case '^':
        !           484:                rtok = relex();
        !           485:                return (unary(op2(CHAR, (Node *) 0, HAT)));
        !           486:        case '$':
        !           487:                rtok = relex();
        !           488:                return (unary(op2(CHAR, (Node *) 0, (Node *) 0)));
        !           489:        case '(':
        !           490:                rtok = relex();
        !           491:                if (rtok == ')') {      /* special pleading for () */
        !           492:                        rtok = relex();
        !           493:                        return unary(op2(CCL, (Node *) 0, tostring("")));
        !           494:                }
        !           495:                np = regexp();
        !           496:                if (rtok==')') {
        !           497:                        rtok = relex();
        !           498:                        return (unary(np));
        !           499:                }
        !           500:                else
        !           501:                        error(FATAL, "syntax error in regular expression");
        !           502:        }
        !           503: }
        !           504: Node *concat(np)
        !           505: Node *np;
        !           506: {
        !           507:        switch(rtok){
        !           508:        case CHAR: case DOT: case ALL: case CCL: case NCCL: case '$': case '(':
        !           509:                return (concat(op2(CAT, np, primary())));
        !           510:        default:
        !           511:                return (np);
        !           512:        }
        !           513: }
        !           514: Node *alt(np)
        !           515: Node *np;
        !           516: {
        !           517:        if (rtok == OR) {
        !           518:                rtok = relex();
        !           519:                return (alt(op2(OR, np, concat(primary()))));
        !           520:        }
        !           521:        return (np);
        !           522: }
        !           523: Node *unary(np)
        !           524: Node *np;
        !           525: {
        !           526:        switch(rtok){
        !           527:        case STAR:
        !           528:                rtok = relex();
        !           529:                return (unary(op2(STAR, np, (Node *) 0)));
        !           530:        case PLUS:
        !           531:                rtok = relex();
        !           532:                return (unary(op2(PLUS, np, (Node *) 0)));
        !           533:        case QUEST:
        !           534:                rtok = relex();
        !           535:                return (unary(op2(QUEST, np, (Node *) 0)));
        !           536:        default:
        !           537:                return (np);
        !           538:        }
        !           539: }
        !           540: 
        !           541: relex()                /* lexical analyzer for reparse */
        !           542: {
        !           543:        extern int rlxval;
        !           544:        register int c;
        !           545:        char cbuf[150];
        !           546:        int clen, cflag;
        !           547:        switch (c = *prestr++) {
        !           548:                case '|': return OR;
        !           549:                case '*': return STAR;
        !           550:                case '+': return PLUS;
        !           551:                case '?': return QUEST;
        !           552:                case '.': return DOT;
        !           553:                case '\0': return '\0';
        !           554:                case '^':
        !           555:                case '$':
        !           556:                case '(':
        !           557:                case ')':
        !           558:                        return c;
        !           559:                case '\\':
        !           560:                        if ((c = *prestr++) == 't')
        !           561:                                c = '\t';
        !           562:                        else if (c == 'n')
        !           563:                                c = '\n';
        !           564:                        else if (c == 'f')
        !           565:                                c = '\f';
        !           566:                        else if (c == 'r')
        !           567:                                c = '\r';
        !           568:                        else if (c == 'b')
        !           569:                                c = '\b';
        !           570:                        else if (c == '\\')
        !           571:                                c = '\\';
        !           572:                        else if (isdigit(c)) {
        !           573:                                int n = c - '0';
        !           574:                                if (isdigit(*prestr)) {
        !           575:                                        n = 8 * n + *prestr++ - '0';
        !           576:                                        if (isdigit(*prestr))
        !           577:                                                n = 8 * n + *prestr++ - '0';
        !           578:                                }
        !           579:                                c = n;
        !           580:                        } /* else it's now in c */
        !           581:                        rlxval = c;
        !           582:                        return CHAR;
        !           583:                default:
        !           584:                        rlxval = c;
        !           585:                        return CHAR;
        !           586:                case '[': 
        !           587:                        clen = 0;
        !           588:                        if (*prestr == '^') {
        !           589:                                cflag = 1;
        !           590:                                prestr++;
        !           591:                        }
        !           592:                        else
        !           593:                                cflag = 0;
        !           594:                        for (;;) {
        !           595:                                if ((c = *prestr++) == '\\') {
        !           596:                                        if ((c = *prestr++) == 't')
        !           597:                                                cbuf[clen++] = '\t';
        !           598:                                        else if (c == 'n')
        !           599:                                                cbuf[clen++] = '\n';
        !           600:                                        else if (c == 'f')
        !           601:                                                cbuf[clen++] = '\f';
        !           602:                                        else if (c == 'r')
        !           603:                                                cbuf[clen++] = '\r';
        !           604:                                        else if (c == 'b')
        !           605:                                                cbuf[clen++] = '\b';
        !           606:                                        else if (c == '\\')
        !           607:                                                cbuf[clen++] = '\\';
        !           608:                                        else if (isdigit(c)) {
        !           609:                                                int n = c - '0';
        !           610:                                                if (isdigit(*prestr)) {
        !           611:                                                        n = 8 * n + *prestr++ - '0';
        !           612:                                                        if (isdigit(*prestr))
        !           613:                                                                n = 8 * n + *prestr++ - '0';
        !           614:                                                }
        !           615:                                                cbuf[clen++] = n;
        !           616:                                        } else
        !           617:                                                cbuf[clen++] = c;
        !           618:                                } else if (c == ']') {
        !           619:                                        cbuf[clen] = 0;
        !           620:                                        rlxval = (int) tostring(cbuf);
        !           621:                                        if (cflag == 0)
        !           622:                                                return CCL;
        !           623:                                        else
        !           624:                                                return NCCL;
        !           625:                                } else if (c == '\n') {
        !           626:                                        error(FATAL, "newline in character class");
        !           627:                                } else if (c == '\0') {
        !           628:                                        error(FATAL, "non-terminated character class");
        !           629:                                } else
        !           630:                                        cbuf[clen++] = c;
        !           631:                        }
        !           632:        }
        !           633: }
        !           634: 
        !           635: 
        !           636: int cgoto(f, s, c)
        !           637: fa *f;
        !           638: int s;
        !           639: char c;
        !           640: {
        !           641:        register int i, j, k;
        !           642:        register fcell *p, *q;
        !           643:        fcell *listbeg;
        !           644:        fcell **prev;
        !           645:        int curvec[MAXLIN];
        !           646:        int fline;
        !           647: 
        !           648:        fline = f->accept;
        !           649:        for (i=0; i<=fline; i++)
        !           650:                curvec[i] = 0;
        !           651:        /* compute positions of state s into curvec */
        !           652:        p = f->posns[s];
        !           653:        while (p != 0) {
        !           654:                curvec[p->info] = 1;
        !           655:                p = p->link;
        !           656:        }
        !           657:        for (i=0; i<=fline; i++)
        !           658:                setvec[i] = 0;
        !           659:        /* compute positions of gototab[s,c] into setvec */
        !           660:        for (i=0; i<=fline; i++)
        !           661:                if (curvec[i])
        !           662:                        if ((k = f->re[i].ltype) != FINAL) {
        !           663:                                if (k == CHAR && c == f->re[i].lval
        !           664:                                 || k == DOT && c != 0 && c != HAT
        !           665:                                 || k == ALL && c != 0
        !           666:                                 || k == CCL && member(c, (char *) f->re[i].lval)
        !           667:                                 || k == NCCL && !member(c, (char *) f->re[i].lval) && c != 0) {
        !           668:                                        p = f->re[i].lfollow;
        !           669:                                        while (p != 0) {
        !           670:                                                setvec[p->info] = 1;
        !           671:                                                p = p->link;
        !           672:                                        }
        !           673:                                }
        !           674:                        }
        !           675:        /* determine if setvec is a previous state */
        !           676:        prev = &listbeg;
        !           677:        for (i=0; i<=fline; i++) {
        !           678:                if (setvec[i]) {
        !           679:                        if ((p = (fcell *) Malloc(sizeof(struct fcell))) == NULL)
        !           680:                                overflo("out of space in cgoto");
        !           681:                        p->info = i;
        !           682:                        *prev = p;
        !           683:                        prev = &p->link;
        !           684:                }
        !           685:        }
        !           686:        *prev = (fcell *) 0;
        !           687:        for (i=1; i<= f->curstat; i++) {
        !           688:                p = f->posns[i];
        !           689:                q = listbeg;
        !           690:                while (p != 0) {
        !           691:                        if ((p->info != q->info) || (q == 0))
        !           692:                                goto different;
        !           693:                        p = p->link;
        !           694:                        q = q->link;
        !           695:                }
        !           696:                if (q != 0)
        !           697:                        goto different;
        !           698:                /* setvec is state i */
        !           699:                f->gototab[s][c] = i;
        !           700: /*     printf("g[%d][%c] = %d\n", s, c, i);    */
        !           701:        p = listbeg;
        !           702:        while (p != 0) {
        !           703:                q = p->link;
        !           704:                Free(p);
        !           705:                p = q;
        !           706:        }
        !           707:                return i;
        !           708:        different:;
        !           709:        }
        !           710:        /* setvec is notin current set of states */
        !           711:        if (f->curstat >= NSTATES-1) {
        !           712:                f->curstat = 2;
        !           713:                f->reset = 1;
        !           714:        }
        !           715:        else
        !           716:                ++(f->curstat);
        !           717:        for (i=0; i<NCHARS; i++)
        !           718:                f->gototab[f->curstat][i] = 0;
        !           719:        f->posns[f->curstat] = listbeg;
        !           720:        f->gototab[s][c] = f->curstat;
        !           721: /*     printf("g[%d, %c] = %d\n", s, c, f->curstat);   */
        !           722:        if (setvec[fline])
        !           723:                f->out[f->curstat] = 1;
        !           724:        else
        !           725:                f->out[f->curstat] = 0;
        !           726:        return f->curstat;
        !           727: }
        !           728: 
        !           729: freefa(f)
        !           730: struct fa *f;
        !           731: {
        !           732:        register fcell *p, *q;
        !           733:        register int i;
        !           734: 
        !           735:        /* free posns */
        !           736:        for (i=0; i < NSTATES; i++) {
        !           737:                p = f->posns[i];
        !           738:                while (p != 0) {
        !           739:                        q = p->link;
        !           740:                        Free(p);
        !           741:                        p = q;
        !           742:                }
        !           743:        }
        !           744:        /* free re */
        !           745:        for (i=0; i<line; i++) {
        !           746:                p = f->re[i].lfollow;
        !           747:                while (p != 0) {
        !           748:                        q = p->link;
        !           749:                        Free(p);
        !           750:                        p = q;
        !           751:                }
        !           752:        }
        !           753:        Free(f);
        !           754: }

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