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