![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to egrep.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / d / bin|
Return to egrep.c CVS log | Up to [MW Coherent from dump] / coherent / d / bin |
1.1 ! root 1: /* ! 2: * egrep -- pattern matcher ! 3: * ! 4: * Lines of input are searched for the user-supplied extended ! 5: * regular expression. Command line options determine what "egrep" ! 6: * does on a match: usually the line is printed. Lines over BUFSIZ ! 7: * chars in length may be fatal when read from pipes or raw devices. ! 8: * The implementation goal is speed and, to this end, a DFA is ! 9: * employed. Two key strategies reduce the time spent constructing ! 10: * the DFA by a factor of 100, in typical cases: (1) the use of ! 11: * equivalence classes, (2) construction of the DFA dynamically. ! 12: * These strategies win because of the way "egrep" tends to be used. ! 13: * Most patterns use only 10-20 characters in the ASCII set of 128. ! 14: * Most input exercises only 10% of the total possible transitions ! 15: * (so why compute the remaining 90%?). As a side benefit, these ! 16: * strategies reduce "egrep"'s gigantic appetite for memory to merely ! 17: * huge. Strategy (2) has the important psychological effect of making ! 18: * "egrep" appear to start running instantly; the inevitable time spent ! 19: * constructing the DFA is amortized over the running time of the ! 20: * program. ! 21: */ ! 22: #include <stdio.h> ! 23: #include <ctype.h> ! 24: #ifdef COHERENT ! 25: #include <access.h> ! 26: #else ! 27: #define DOS 1 ! 28: #endif ! 29: ! 30: /* ! 31: ** rico.h ! 32: */ ! 33: #define bool char ! 34: #define TRUE 1 ! 35: #define FALSE 0 ! 36: ! 37: /* ! 38: ** egrep.h ! 39: */ ! 40: /* ! 41: * bit diddling ! 42: */ ! 43: #define NCHARS 128 /* chars in ASCII set */ ! 44: #define NBCHAR 8 /* bits per char */ ! 45: ! 46: #define bitset(c, p) ((p)[(c)>>3] |= bitmask[(c)&7]) ! 47: #define bitclr(c, p) ((p)[(c)>>3] &= ~bitmask[(c)&7]) ! 48: #define bitcom(c, p) ((p)[(c)>>3] ^= bitmask[(c)&7]) ! 49: #define bittst(c, p) ((p)[(c)>>3] & bitmask[(c)&7]) ! 50: ! 51: /* ! 52: * support for bitmaps ! 53: */ ! 54: readonly char bitmask[] = { ! 55: 0001, 0002, 0004, 0010, 0020, 0040, 0100, 0200 ! 56: }; ! 57: ! 58: ! 59: extern char *newbits(); ! 60: ! 61: /* ! 62: ** dragon.h ! 63: */ ! 64: /* ! 65: * DFA state ! 66: * The egrep DFA is composed of these structs. Operation of the DFA ! 67: * requires the use of d_success and d_p, only. ! 68: */ ! 69: struct dragon { ! 70: bool d_success; /* this is an accepting state */ ! 71: struct newt **d_s; /* set of NFA states (newts) */ ! 72: char *d_b; /* bitmap of d_s */ ! 73: int d_hash; /* hash of d_s */ ! 74: struct dragon *d_next; /* next dragon (or 0) */ ! 75: struct dragon *d_last; /* previous dragon (or 0) */ ! 76: struct dragon **d_p; /* transition vector */ ! 77: }; ! 78: ! 79: /* ! 80: ** newt.h ! 81: */ ! 82: /* ! 83: * NFA state ! 84: * The rex is converted into an NFA composed of these structs. ! 85: */ ! 86: struct newt { ! 87: char n_c; /* label for transition n_cp */ ! 88: char n_flags; /* [see below] */ ! 89: int n_uniq; /* unique # */ ! 90: int n_id; /* ID # of this newt */ ! 91: char *n_b; /* alternative label (char class) */ ! 92: struct newt *n_cp; /* transition labeled n_c */ ! 93: struct newt *n_ep; /* transition labeled EPSILON */ ! 94: struct newt *n_fp; /* final newt in this sub-goal */ ! 95: }; ! 96: ! 97: /* n_c ! 98: */ ! 99: #define EPSILON (-1) /* n_cp is an epsilon transition */ ! 100: ! 101: /* n_flags ! 102: */ ! 103: #define N_BOL 01 /* beginning-of-line */ ! 104: #define N_EOL 02 /* end-of-line */ ! 105: ! 106: /* ! 107: ** equiv.c ! 108: */ ! 109: /* ! 110: * equivalence class ! 111: * The set of ASCII chars is refined by the sets of chars used by ! 112: * the regular expression. The result is a set of equivalence classes: ! 113: * disjoint sets of chars, whose union is the ASCII set. ! 114: * An eclass struct describes one equivalence class. The structs ! 115: * are linked, and headed by `eclasses'. ! 116: */ ! 117: struct eclass { ! 118: char e_c; /* used if only one char in set */ ! 119: char e_class; /* ID # of this eclass */ ! 120: char *e_b; /* used if many chars in set */ ! 121: struct eclass *e_next; /* next eclass (or 0) */ ! 122: }; ! 123: ! 124: bool aflag; /* use emacs after file with hit */ ! 125: bool eflag; /* next arg is regular expression */ ! 126: bool fflag; /* next arg is file containing rex */ ! 127: bool vflag; /* line matches if rex NOT found */ ! 128: bool cflag; /* only print # matches */ ! 129: bool lflag; /* only print name of files that match */ ! 130: bool nflag; /* also print line # */ ! 131: bool bflag; /* also print block # */ ! 132: bool sflag; /* only provide exit status */ ! 133: bool hflag; /* do not print file names */ ! 134: bool yflag; /* lower case also matches upper case input */ ! 135: ! 136: int uniq, n_id, n_ec; ! 137: ! 138: FILE *ifp; /* input */ ! 139: FILE *tmpFile; /* tmp file for use with emacs */ ! 140: char *tmpFn = NULL; /* tmp file name */ ! 141: /* ! 142: * egrep ! 143: * Return 0 if any matches found in the input files, else 1. ! 144: */ ! 145: main(argc, argv) ! 146: char **argv; ! 147: { ! 148: register struct newt *np; ! 149: register struct dragon *dp; ! 150: struct newt *makenfa(); ! 151: struct newt *npolish(); ! 152: struct dragon *initdfa(); ! 153: int status; ! 154: char **init(); ! 155: bool search(); ! 156: ! 157: #ifdef MSDOS ! 158: msdoscvt("egrep", &argc, &argv); ! 159: #endif ! 160: argv = init(argc, argv ); ! 161: #ifdef MSDOS ! 162: /* ! 163: * On systems which distinguish between ASCII and binary streams, ! 164: * egrep reads its input as a binary stream, so it can be used to ! 165: * look for a string in an object file (for example). It also ! 166: * writes its output as a binary stream in most cases, so for ASCII ! 167: * input files newline mapping happens neither on input nor on output. ! 168: * However, "-c" and "-l" require ASCII output for newline mapping. ! 169: * Kludgy; one alternative is to have it read and write ASCII streams, ! 170: * forget about egrep'ing object files, and futz the seek count when ! 171: * it sees a newline in the input. ! 172: */ ! 173: if (!cflag && !lflag) ! 174: _setbinary(stdout); ! 175: #endif ! 176: ! 177: np = makenfa(); ! 178: ncheck(initdfa(np)->d_s); ! 179: np = npolish(np); ! 180: dp = initdfa(np); ! 181: ! 182: status = 1; ! 183: ! 184: if (*argv) ! 185: do { ! 186: if ((ifp = fopen(*argv, "rb")) == NULL) { ! 187: fprintf(stderr, ! 188: "egrep: can't open %s\n", *argv); ! 189: continue; ! 190: } ! 191: if (search(*argv, dp, np)) ! 192: status = 0; ! 193: fclose(ifp); ! 194: if (aflag && (NULL != tmpFn)) ! 195: emacs(*argv); ! 196: } while (*++argv); ! 197: else { ! 198: ifp = stdin; ! 199: #ifdef MSDOS ! 200: _setbinary(ifp); ! 201: #endif ! 202: if (search("(stdin)", dp, np)) ! 203: status = 0; ! 204: } ! 205: ! 206: return (status); ! 207: } ! 208: ! 209: /* ! 210: * initialization ! 211: * Process command line. Return `argv' pointing to first file arg. ! 212: */ ! 213: static char ** ! 214: init(argc, argv) ! 215: char **argv; ! 216: { ! 217: register char **av; ! 218: register char *a; ! 219: register bool gotrex; ! 220: extern char *regexp; ! 221: extern FILE *rexf; ! 222: ! 223: gotrex = FALSE; ! 224: av = &argv[1]; ! 225: ! 226: while (a = *av++) { ! 227: if (*a != '-') { ! 228: if (! gotrex) { ! 229: gotrex = TRUE; ! 230: regexp = a; ! 231: a = *av++; ! 232: } ! 233: break; ! 234: } ! 235: while (*++a) ! 236: switch (*a) { ! 237: case 'A': ! 238: aflag = TRUE; ! 239: break; ! 240: case 'e': ! 241: if (gotrex) ! 242: onlyone(); ! 243: if (*av == NULL) ! 244: fatal("missing arg to -e"); ! 245: regexp = *av++; ! 246: gotrex = TRUE; ! 247: break; ! 248: case 'f': ! 249: if (gotrex) ! 250: onlyone(); ! 251: if (*av == NULL) ! 252: fatal("missing arg to -f"); ! 253: rexf = fopen(*av, "r"); ! 254: if (rexf == NULL) ! 255: fatal("can't open %s", *av); ! 256: ++av; ! 257: gotrex = TRUE; ! 258: break; ! 259: case 'v': ! 260: vflag = TRUE; ! 261: break; ! 262: case 'c': ! 263: cflag = TRUE; ! 264: break; ! 265: case 'l': ! 266: lflag = TRUE; ! 267: break; ! 268: case 'n': ! 269: nflag = TRUE; ! 270: break; ! 271: case 'b': ! 272: bflag = TRUE; ! 273: break; ! 274: case 's': ! 275: sflag = TRUE; ! 276: break; ! 277: case 'h': ! 278: hflag = TRUE; ! 279: break; ! 280: case 'y': ! 281: case 'i': ! 282: yflag = TRUE; ! 283: break; ! 284: default: ! 285: fatal("no such flag -%c", *a); ! 286: } ! 287: } ! 288: ! 289: if (! gotrex) { ! 290: fprintf(stderr, ! 291: "Usage: egrep [ -bcefhlnsvy ] pattern [ file ...]\n"); ! 292: exit(2); ! 293: } ! 294: ! 295: --av; ! 296: if (argc-(av-argv) <= 1) ! 297: hflag = TRUE; ! 298: return (av); ! 299: } ! 300: ! 301: /* ! 302: * call emacs with tmpfile. ! 303: */ ! 304: emacs(arg) ! 305: char *arg; ! 306: { ! 307: #ifdef GEMDOS ! 308: #include <path.h> ! 309: extern char *path(), *getenv(); ! 310: extern char **environ; ! 311: static char* cmda[5] = { NULL, "-e", NULL, NULL, NULL }; ! 312: #endif ! 313: #ifdef MSDOS ! 314: char line[BUFSIZ]; ! 315: #endif ! 316: #ifdef COHERENT ! 317: char line[BUFSIZ]; ! 318: #endif ! 319: int quit; ! 320: ! 321: fclose(tmpFile); ! 322: #ifdef MSDOS ! 323: sprintf(line, "-e %s %s", tmpFn, arg); ! 324: if (0x7f == (quit = execall("me", line))) ! 325: #endif ! 326: #ifdef COHERENT ! 327: sprintf(line, "me -e %s %s ", tmpFn, arg); ! 328: if (0x7f == (quit = system(line))) ! 329: #endif ! 330: #ifdef GEMDOS ! 331: cmda[2] = tmpFn; ! 332: cmda[3] = arg; ! 333: if ((NULL == cmda[0]) && ! 334: (NULL == (cmda[0] = path(getenv("PATH"), "me.tos", 1)))) { ! 335: fprintf(stderr, "egrep: Cannot locate me.tos\n"); ! 336: quit = 1; ! 337: } ! 338: else if ((quit = execve(cmda[0], cmda, environ)) < 0) ! 339: #endif ! 340: fprintf(stderr, "egrep: cannot execute 'me'"); ! 341: unlink(tmpFn); ! 342: free(tmpFn); ! 343: tmpFn = NULL; ! 344: if (quit) ! 345: exit(0); ! 346: } ! 347: ! 348: static ! 349: onlyone() ! 350: { ! 351: fatal("exactly one pattern required"); ! 352: } ! 353: ! 354: ! 355: nomem() ! 356: { ! 357: ! 358: fatal("out of mem"); ! 359: } ! 360: ! 361: ! 362: /* ! 363: * fatal error ! 364: */ ! 365: fatal(arg0) ! 366: char *arg0; ! 367: { ! 368: fflush(stdout); ! 369: fprintf(stderr, "egrep: %r\n", &arg0); ! 370: exit(2); ! 371: } ! 372: ! 373: /* ! 374: ** nfa.c ! 375: */ ! 376: ! 377: ! 378: /* ! 379: * creation of the NFA ! 380: */ ! 381: ! 382: ! 383: /* only one is set by init() ! 384: */ ! 385: char *regexp; /* user's regular expression */ ! 386: FILE *rexf; /* file containing user's rex */ ! 387: ! 388: ! 389: static curc; /* current char from rex */ ! 390: ! 391: struct newt *getrex(); ! 392: struct newt *getterm(); ! 393: struct newt *getfac(); ! 394: struct newt *getatom(); ! 395: struct newt *newnewt(); ! 396: ! 397: ! 398: /* ! 399: * create NFA from rex ! 400: * A pointer to the NFA is returned. ! 401: */ ! 402: struct newt *makenfa() ! 403: { ! 404: register struct newt *p; ! 405: ! 406: advance(); ! 407: p = getrex(); ! 408: if (curc) ! 409: misplaced(curc); ! 410: if (p == NULL) ! 411: fatal("empty pattern"); ! 412: return (p); ! 413: } ! 414: ! 415: ! 416: /* ! 417: * check NFA semantics ! 418: * Ensure correct usage of '^' and '$'. ! 419: */ ! 420: ncheck(npp) ! 421: register struct newt **npp; ! 422: { ! 423: register struct newt *np; ! 424: ! 425: ++uniq; ! 426: ! 427: while (np = *npp++) ! 428: if (np->n_cp && np->n_c!=EPSILON) { ! 429: if (np->n_flags & N_EOL) ! 430: nbeeline(np); ! 431: nwalk(np->n_cp); ! 432: } ! 433: } ! 434: ! 435: ! 436: /* ! 437: * add finishing touch to NFA ! 438: * Prepend a sort of ".*" to the front of the NFA. ! 439: */ ! 440: struct newt *npolish(np) ! 441: register struct newt *np; ! 442: { ! 443: register struct newt *p; ! 444: ! 445: p = newnewt(); ! 446: p->n_b = newbits(TRUE); ! 447: p->n_cp = newnewt(); ! 448: p->n_cp->n_c = EPSILON; ! 449: p->n_cp->n_cp = p; ! 450: p->n_ep = np; ! 451: p->n_fp = np->n_fp; ! 452: return (p); ! 453: } ! 454: ! 455: ! 456: /* ! 457: * get regular expression ! 458: * A trailing '\n' is tolerated, to accommodate the "-f" option. ! 459: */ ! 460: static struct newt *getrex() ! 461: { ! 462: register struct newt *p; ! 463: register struct newt *q; ! 464: register struct newt *start; ! 465: struct newt *final; ! 466: ! 467: start = getterm(); ! 468: if (start == NULL) ! 469: return (start); ! 470: final = newnewt(); ! 471: start->n_fp->n_c = EPSILON; ! 472: start->n_fp->n_cp = final; ! 473: start->n_fp = final; ! 474: ! 475: for (; ; ) { ! 476: switch (curc) { ! 477: case '|': ! 478: advance(); ! 479: if (p = getterm()) ! 480: break; ! 481: misplaced('|'); ! 482: case '\n': ! 483: advance(); ! 484: if (p = getterm()) ! 485: break; ! 486: if (curc != '\0') ! 487: misplaced('\n'); ! 488: default: ! 489: return (start); ! 490: } ! 491: p->n_fp->n_c = EPSILON; ! 492: p->n_fp->n_cp = final; ! 493: q = newnewt(); ! 494: q->n_c = EPSILON; ! 495: q->n_cp = p; ! 496: q->n_ep = start; ! 497: q->n_fp = final; ! 498: start = q; ! 499: } ! 500: } ! 501: ! 502: ! 503: /* ! 504: * get term ! 505: */ ! 506: static struct newt * ! 507: getterm() ! 508: { ! 509: register struct newt *start; ! 510: register struct newt *p; ! 511: ! 512: start = getfac(); ! 513: if (start == NULL) ! 514: return (start); ! 515: ! 516: while (p = getfac()) { ! 517: start->n_fp->n_c = EPSILON; ! 518: start->n_fp->n_cp = p; ! 519: start->n_fp = p->n_fp; ! 520: } ! 521: ! 522: return (start); ! 523: } ! 524: ! 525: ! 526: /* ! 527: * get factor ! 528: */ ! 529: static struct newt *getfac() ! 530: { ! 531: register struct newt *p; ! 532: register struct newt *q; ! 533: register struct newt *start; ! 534: ! 535: start = getatom(); ! 536: if (start == NULL) ! 537: return (start); ! 538: p = start; ! 539: ! 540: if (curc == '*') { ! 541: advance(); ! 542: start = newnewt(); ! 543: q = newnewt(); ! 544: start->n_c = EPSILON; ! 545: start->n_cp = p; ! 546: start->n_ep = q; ! 547: p->n_fp->n_c = EPSILON; ! 548: p->n_fp->n_cp = q; ! 549: p->n_fp->n_ep = p; ! 550: start->n_fp = q; ! 551: } ! 552: else if (curc == '+') { ! 553: advance(); ! 554: q = newnewt(); ! 555: p->n_fp->n_c = EPSILON; ! 556: p->n_fp->n_cp = q; ! 557: p->n_fp->n_ep = p; ! 558: start->n_fp = q; ! 559: } ! 560: else if (curc == '?') { ! 561: advance(); ! 562: start = newnewt(); ! 563: start->n_c = EPSILON; ! 564: start->n_cp = p; ! 565: start->n_ep = p->n_fp; ! 566: start->n_fp = p->n_fp; ! 567: } ! 568: return (start); ! 569: } ! 570: ! 571: ! 572: /* ! 573: * get atom ! 574: * The interpretation of the "-y" option is given by this example: ! 575: * egrep -y 'R\i\c\o H[a-z]* Tudor' ! 576: * means ! 577: * egrep 'Rico H[A-Za-z]* T[Uu][Dd][Oo][Rr]' ! 578: */ ! 579: static struct newt *getatom() ! 580: { ! 581: register struct newt *start; ! 582: char *charclass(); ! 583: ! 584: start = newnewt(); ! 585: start->n_cp = newnewt(); ! 586: start->n_fp = start->n_cp; ! 587: ! 588: switch (curc) { ! 589: case '\0': ! 590: case '\n': ! 591: case '|': ! 592: case '*': ! 593: case ')': ! 594: case ']': ! 595: case '+': ! 596: case '?': ! 597: nonewts(start); ! 598: return (0); ! 599: case '.': ! 600: start->n_b = newbits(TRUE); ! 601: bitclr('\n', start->n_b); ! 602: equiv(start); ! 603: break; ! 604: case '^': ! 605: start->n_flags |= N_BOL; ! 606: start->n_c = '\n'; ! 607: equiv(start); ! 608: break; ! 609: case '$': ! 610: start->n_flags |= N_EOL; ! 611: #if DOS ! 612: start->n_c = '\r'; ! 613: #else ! 614: start->n_c = '\n'; ! 615: #endif ! 616: equiv(start); ! 617: break; ! 618: case '[': ! 619: advance(); ! 620: start->n_b = charclass(); ! 621: equiv(start); ! 622: break; ! 623: case '(': ! 624: advance(); ! 625: nonewts(start); ! 626: start = getrex(); ! 627: if (curc == '\0') ! 628: fatal("missing ')'"); ! 629: if ((start == NULL) || curc!=')') ! 630: misplaced(curc); ! 631: break; ! 632: case '\\': ! 633: advance(); ! 634: if (curc=='\0' || curc=='\n') ! 635: misplaced('\\'); ! 636: start->n_c = curc; ! 637: equiv(start); ! 638: break; ! 639: default: ! 640: if (yflag && islower(curc)) { ! 641: start->n_b = newbits(FALSE); ! 642: bitset(curc, start->n_b); ! 643: bitset(toupper(curc), start->n_b); ! 644: } ! 645: else ! 646: start->n_c = curc; ! 647: equiv(start); ! 648: } ! 649: advance(); ! 650: ! 651: return (start); ! 652: } ! 653: ! 654: ! 655: static char *charclass() ! 656: { ! 657: register char *p; ! 658: register c; ! 659: register bool compl; ! 660: ! 661: compl = FALSE; ! 662: p = newbits(FALSE); ! 663: if (curc == '^') { ! 664: compl = TRUE; ! 665: advance(); ! 666: } ! 667: if (curc == '\0') ! 668: badclass(); ! 669: ! 670: do { ! 671: c = curc; ! 672: advance(); ! 673: if (c == '\0') ! 674: badclass(); ! 675: if (curc == '-') { ! 676: advance(); ! 677: if (curc == '\0') ! 678: badclass(); ! 679: if (curc == ']') { ! 680: bitset('-', p); ! 681: bitset(c, p); ! 682: } ! 683: else if (c > curc) ! 684: fatal("bad char class range %c-%c", c, curc); ! 685: else { ! 686: do { ! 687: bitset(c, p); ! 688: } while (++c <= curc); ! 689: advance(); ! 690: } ! 691: } ! 692: else ! 693: bitset(c, p); ! 694: } while (curc != ']'); ! 695: ! 696: if (bittst('\n', p)) ! 697: misplaced('\n'); ! 698: if (yflag) ! 699: for (c='a'; c<='z'; ++c) ! 700: if (bittst(c, p)) ! 701: bitset(toupper(c), p); ! 702: if (compl) { ! 703: for (c=0; c<NCHARS; ++c) ! 704: bitcom(c, p); ! 705: bitclr('\n', p); ! 706: } ! 707: return (p); ! 708: } ! 709: ! 710: ! 711: /* ! 712: * allocate new newt struct ! 713: */ ! 714: static struct newt *newnewt() ! 715: { ! 716: register struct newt *p; ! 717: ! 718: p = malloc(sizeof *p); ! 719: if (p == NULL) ! 720: nomem(); ! 721: p->n_c = 0; ! 722: p->n_flags = 0; ! 723: p->n_b = NULL; ! 724: p->n_cp = NULL; ! 725: p->n_ep = NULL; ! 726: p->n_fp = NULL; ! 727: p->n_uniq = 0; ! 728: p->n_id = n_id++; ! 729: ! 730: return (p); ! 731: } ! 732: ! 733: ! 734: /* ! 735: * free newt structs ! 736: * Used to free unused atoms. ! 737: */ ! 738: static nonewts(np) ! 739: struct newt *np; ! 740: { ! 741: ! 742: free((char *)np->n_cp); ! 743: free((char *)np); ! 744: n_id -= 2; ! 745: } ! 746: ! 747: ! 748: /* ! 749: * get next char from rex ! 750: * The next char from the file or the string is placed in `curc'. ! 751: */ ! 752: static advance() ! 753: { ! 754: register c; ! 755: ! 756: if (regexp) ! 757: c = *regexp++; ! 758: else { ! 759: c = getc(rexf); ! 760: if (c == EOF) ! 761: c = '\0'; ! 762: } ! 763: curc = c & 0177; ! 764: } ! 765: ! 766: ! 767: /* ! 768: * report misplaced '^' ! 769: */ ! 770: static nwalk(np) ! 771: register struct newt *np; ! 772: { ! 773: ! 774: while (np->n_cp) { ! 775: if (np->n_uniq == uniq) ! 776: return; ! 777: np->n_uniq = uniq; ! 778: if (np->n_flags & N_EOL) ! 779: nbeeline(np); ! 780: if (np->n_flags & N_BOL) ! 781: misplaced('^'); ! 782: if (np->n_ep) ! 783: nwalk(np->n_ep); ! 784: np = np->n_cp; ! 785: } ! 786: } ! 787: ! 788: ! 789: /* ! 790: * report misplaced '$' ! 791: */ ! 792: static nbeeline(np) ! 793: register struct newt *np; ! 794: { ! 795: ! 796: while (np = np->n_cp) { ! 797: if ((np->n_cp && np->n_c!=EPSILON) ! 798: || (np->n_ep)) ! 799: misplaced('$'); ! 800: } ! 801: } ! 802: ! 803: ! 804: static misplaced(c) ! 805: { ! 806: static char s[] = "`c'"; ! 807: ! 808: s[1] = c; ! 809: fatal("misplaced %s in pattern", c=='\n'? "newline": s); ! 810: } ! 811: ! 812: ! 813: static badclass() ! 814: { ! 815: ! 816: fatal("non-terminated char class"); ! 817: } ! 818: /* ! 819: ** equiv.c ! 820: */ ! 821: ! 822: ! 823: /* ! 824: * equivalence classes ! 825: */ ! 826: ! 827: ! 828: char etab[NCHARS]; /* map ASCII to eclass # */ ! 829: struct eclass *eclasses; /* head of eclass list */ ! 830: ! 831: bool intersect(); ! 832: struct eclass *neweclass(); ! 833: ! 834: ! 835: /* ! 836: * check equivalence ! 837: * A set of eclasses must exist such that their union equals the ! 838: * chars in `np'. If not, the equivalence relation must be "refined". ! 839: */ ! 840: equiv(np) ! 841: register struct newt *np; ! 842: { ! 843: register struct eclass *ep; ! 844: register struct eclass *p; ! 845: struct eclass e; ! 846: ! 847: if (eclasses == NULL) { ! 848: eclasses = neweclass(); ! 849: eclasses->e_c = 0; ! 850: eclasses->e_b = newbits(TRUE); ! 851: eclasses->e_next = NULL; ! 852: eclasses->e_class = n_ec++; ! 853: } ! 854: ! 855: for (ep=eclasses; ep; ep=ep->e_next) { ! 856: if (! intersect(np, ep, &e)) ! 857: continue; ! 858: p = neweclass(); ! 859: *p = e; ! 860: p->e_class = n_ec++; ! 861: p->e_next = eclasses; ! 862: eclasses = p; ! 863: } ! 864: } ! 865: ! 866: ! 867: /* ! 868: * is there a transition? ! 869: * Return TRUE if there is a transition from `np' on the chars given ! 870: * by `ep'. ! 871: */ ! 872: bool eqtrans(ep, np) ! 873: register struct eclass *ep; ! 874: register struct newt *np; ! 875: { ! 876: register i; ! 877: ! 878: if (ep->e_b) { ! 879: if (np->n_b) { ! 880: for (i=0; i<NCHARS/NBCHAR; ++i) ! 881: if (ep->e_b[i] & np->n_b[i]) ! 882: return (TRUE); ! 883: } ! 884: else ! 885: return (bittst(np->n_c, ep->e_b)); ! 886: } ! 887: else { ! 888: if (np->n_b) ! 889: return (bittst(ep->e_c, np->n_b)); ! 890: else ! 891: return (ep->e_c == np->n_c); ! 892: } ! 893: return (FALSE); ! 894: } ! 895: ! 896: ! 897: /* ! 898: * intersect char sets ! 899: * If the intersection of `np' and `ep0' is a proper subset of `ep0', ! 900: * then store the intersection in `ep1', store the difference of ! 901: * `ep0' - `ep1' in `ep0' and return TRUE. ! 902: */ ! 903: static bool intersect(np, ep0, ep1) ! 904: register struct newt *np; ! 905: register struct eclass *ep0; ! 906: struct eclass *ep1; ! 907: { ! 908: register i; ! 909: bool classcheck(); ! 910: ! 911: if (ep0->e_b == NULL) ! 912: return (FALSE); ! 913: ! 914: if (np->n_b == NULL) { ! 915: i = np->n_c; ! 916: if (! bittst(i, ep0->e_b)) ! 917: return (FALSE); ! 918: bitclr(i, ep0->e_b); ! 919: ep1->e_c = i; ! 920: etab[i] = n_ec; ! 921: ep1->e_b = NULL; ! 922: } ! 923: else { ! 924: if (! classcheck(np->n_b, ep0->e_b)) ! 925: return (FALSE); ! 926: ep1->e_b = newbits(FALSE); ! 927: for (i=0; i<NCHARS/NBCHAR; ++i) { ! 928: ep1->e_b[i] = ep0->e_b[i] & np->n_b[i]; ! 929: ep0->e_b[i] &= ~np->n_b[i]; ! 930: } ! 931: for (i=0; i<NCHARS; ++i) ! 932: if (bittst(i, ep1->e_b)) ! 933: etab[i] = n_ec; ! 934: ep1->e_c = 0; ! 935: } ! 936: ! 937: return (TRUE); ! 938: } ! 939: ! 940: ! 941: /* ! 942: * check intersection ! 943: * Specific check for char sets represented as bitmaps. If the ! 944: * intersection of `p' and `q' is a proper subset of `q' return TRUE. ! 945: * Non-modifying nature of this routine is optimized for the "-y" option, ! 946: * where intersections of [Aa] and [Bb] are commonplace. ! 947: */ ! 948: static bool classcheck(p, q) ! 949: register char *p; ! 950: register char *q; ! 951: { ! 952: register i; ! 953: bool k1; ! 954: bool k2; ! 955: ! 956: k1 = FALSE; ! 957: k2 = FALSE; ! 958: ! 959: i = NCHARS / NBCHAR; ! 960: do { ! 961: if (*q & *p) ! 962: k1 = TRUE; ! 963: if (*q++ & ~*p++) ! 964: k2 = TRUE; ! 965: } while (--i); ! 966: ! 967: return (k1 && k2); ! 968: } ! 969: ! 970: ! 971: /* ! 972: * allocate new eclass ! 973: */ ! 974: static struct eclass *neweclass() ! 975: { ! 976: register struct eclass *ep; ! 977: ! 978: ep = malloc(sizeof *ep); ! 979: if (ep == NULL) ! 980: nomem(); ! 981: return (ep); ! 982: } ! 983: ! 984: /* ! 985: ** dfa.c ! 986: */ ! 987: ! 988: ! 989: /* ! 990: * creation of the DFA ! 991: */ ! 992: ! 993: static bmsize; /* size of bitmap `d_b' */ ! 994: static struct dragon d; /* prototype dragon */ ! 995: ! 996: static struct dragon *dragons; /* head of the dragon list */ ! 997: ! 998: struct dragon *member(); ! 999: struct dragon *enter(); ! 1000: ! 1001: ! 1002: /* ! 1003: * create the DFA start state ! 1004: */ ! 1005: struct dragon * ! 1006: initdfa(np) ! 1007: struct newt *np; ! 1008: { ! 1009: ! 1010: if (d.d_s) ! 1011: free((char *)d.d_s); ! 1012: d.d_s = malloc((n_id+1)*sizeof(*d.d_s)); ! 1013: if (d.d_s == NULL) ! 1014: nomem(); ! 1015: d.d_s[0] = np; ! 1016: d.d_s[1] = NULL; ! 1017: bmsize = (n_id+NBCHAR-1) / NBCHAR; ! 1018: if (d.d_b) ! 1019: free((char *)d.d_b); ! 1020: d.d_b = malloc(bmsize); ! 1021: if (d.d_b == NULL) ! 1022: nomem(); ! 1023: dragons = NULL; ! 1024: ++uniq; ! 1025: e_closure(); ! 1026: return (enter(np->n_fp)); ! 1027: } ! 1028: ! 1029: ! 1030: /* ! 1031: * construct the DFA ! 1032: * This task is done incrementally, after searching has started. ! 1033: * The current dragon `dp' needs a transition on the input `ec' given ! 1034: * the NFA `np'. The new dragon is determined, entered into `dp->d_p', ! 1035: * and returned. If the new dragon has never been encountered, it is ! 1036: * remembered. A special case arises if the current dragon is an accept ! 1037: * state: all transitions loop to itself. ! 1038: * Note that `ec' is an equivalence class, not a char. ! 1039: */ ! 1040: struct dragon * ! 1041: makedfa(dp, ec, np) ! 1042: struct dragon *dp; ! 1043: struct newt *np; ! 1044: { ! 1045: register struct eclass *ep; ! 1046: register struct dragon *p; ! 1047: extern struct eclass *eclasses; ! 1048: ! 1049: if (dp->d_success) { ! 1050: dp->d_p[ec] = dp; ! 1051: return (dp); ! 1052: } ! 1053: for (ep=eclasses; ep->e_class!=ec; ep=ep->e_next) ! 1054: ; ! 1055: ++uniq; ! 1056: gettrans(dp, ep); ! 1057: e_closure(); ! 1058: p = member(); ! 1059: if (p == NULL) ! 1060: p = enter(np->n_fp); ! 1061: dp->d_p[ec] = p; ! 1062: return (p); ! 1063: } ! 1064: ! 1065: ! 1066: /* ! 1067: * get transitions ! 1068: * Construct in `d.d_s' the set of newts to which there is a ! 1069: * transition on `ep' from some newt in `dp->d_s'. ! 1070: */ ! 1071: static gettrans(dp, ep) ! 1072: struct dragon *dp; ! 1073: struct eclass *ep; ! 1074: { ! 1075: register struct newt **pp; ! 1076: register struct newt *np; ! 1077: register struct newt *p; ! 1078: struct newt **npp; ! 1079: bool eqtrans(); ! 1080: ! 1081: npp = d.d_s; ! 1082: ! 1083: pp = dp->d_s; ! 1084: while (np = *pp++) ! 1085: if ((p = np->n_cp) ! 1086: && (np->n_c != EPSILON) ! 1087: && (eqtrans(ep, np))) { ! 1088: *npp++ = p; ! 1089: p->n_uniq = uniq; ! 1090: } ! 1091: *npp = NULL; ! 1092: } ! 1093: ! 1094: ! 1095: /* ! 1096: * locate a dragon ! 1097: * The set of newts given by `d.d_s' are sought in the DFA. The ! 1098: * appropriate dragon is returned, else 0. The use of bitmap `d_b' allows ! 1099: * comparing (unsorted) `d_s' sets in time O(N). Hashing of `d_s' and ! 1100: * "self-organizing" the DFA also help to keep things fast. ! 1101: */ ! 1102: static struct dragon *member() ! 1103: { ! 1104: register struct dragon *dp; ! 1105: register char *p; ! 1106: register char *q; ! 1107: int i; ! 1108: ! 1109: dp = dragons; ! 1110: ! 1111: do { ! 1112: if (dp->d_hash == d.d_hash) { ! 1113: p = dp->d_b; ! 1114: q = d.d_b; ! 1115: i = bmsize; do { ! 1116: if (*p++ != *q++) ! 1117: break; ! 1118: } while (--i); ! 1119: if (i == 0) { ! 1120: if (dp == dragons) ! 1121: break; ! 1122: if (dp->d_next) ! 1123: dp->d_next->d_last = dp->d_last; ! 1124: dp->d_last->d_next = dp->d_next; ! 1125: dragons->d_last = dp; ! 1126: dp->d_next = dragons; ! 1127: dp->d_last = NULL; ! 1128: dragons = dp; ! 1129: break; ! 1130: } ! 1131: } ! 1132: } while (dp = dp->d_next); ! 1133: ! 1134: return (dp); ! 1135: } ! 1136: ! 1137: ! 1138: /* ! 1139: * enter the dragon ! 1140: * The prototype dragon `d' is used to create a dragon, which is ! 1141: * entered in the DFA. ! 1142: */ ! 1143: static struct dragon * ! 1144: enter(finalnp) ! 1145: struct newt *finalnp; ! 1146: { ! 1147: register struct dragon *p; ! 1148: register i; ! 1149: ! 1150: p = malloc(sizeof *p); ! 1151: if (p == NULL) ! 1152: nomem(); ! 1153: p->d_success = FALSE; ! 1154: p->d_hash = d.d_hash; ! 1155: for (i=0; d.d_s[i]; ++i) ! 1156: if (d.d_s[i] == finalnp) ! 1157: p->d_success = TRUE; ! 1158: p->d_s = malloc((i+1)*sizeof(*p->d_s)); ! 1159: if (p->d_s == NULL) ! 1160: nomem(); ! 1161: for (i=0; p->d_s[i]=d.d_s[i]; ++i) ! 1162: ; ! 1163: p->d_b = malloc(bmsize); ! 1164: if (p->d_b == NULL) ! 1165: nomem(); ! 1166: for (i=0; i<bmsize; ++i) ! 1167: p->d_b[i] = d.d_b[i]; ! 1168: p->d_p = malloc(n_ec*sizeof(*p->d_p)); ! 1169: if (p->d_p == NULL) ! 1170: nomem(); ! 1171: for (i=0; i<n_ec; ++i) ! 1172: p->d_p[i] = NULL; ! 1173: if (dragons) ! 1174: dragons->d_last = p; ! 1175: p->d_next = dragons; ! 1176: dragons = p; ! 1177: p->d_last = NULL; ! 1178: return (p); ! 1179: } ! 1180: ! 1181: ! 1182: /* ! 1183: * perform epsilon-closure ! 1184: * Epsilon-transition `d.d_s' is computed and the result placed ! 1185: * in `d.d_s'. Ensuring a newt is not already on the list requires ! 1186: * time O(N), thanks to `uniq'. ! 1187: */ ! 1188: static ! 1189: e_closure() ! 1190: { ! 1191: register struct newt **nqq; ! 1192: register struct newt *np; ! 1193: register struct newt *p; ! 1194: struct newt **npp; ! 1195: ! 1196: d.d_hash = 0; ! 1197: for (nqq=d.d_s; *nqq++; ) ! 1198: ; ! 1199: --nqq; ! 1200: ! 1201: for (npp=d.d_s; npp<nqq; ) { ! 1202: np = *npp++; ! 1203: d.d_hash += (int)np; ! 1204: if ((p = np->n_cp) ! 1205: && (np->n_c == EPSILON) ! 1206: && (p->n_uniq != uniq)) { ! 1207: *nqq++ = p; ! 1208: p->n_uniq = uniq; ! 1209: } ! 1210: if ((p = np->n_ep) ! 1211: && (p->n_uniq != uniq)) { ! 1212: *nqq++ = p; ! 1213: p->n_uniq = uniq; ! 1214: } ! 1215: } ! 1216: *nqq = NULL; ! 1217: ! 1218: bmbuild(); ! 1219: } ! 1220: ! 1221: ! 1222: /* ! 1223: * build bitmap ! 1224: * A bitmap of `d.d_s' is built in `d.d_b'. ! 1225: */ ! 1226: static ! 1227: bmbuild() ! 1228: { ! 1229: register struct newt *np; ! 1230: register char *p; ! 1231: register i; ! 1232: ! 1233: p = d.d_b; ! 1234: i = bmsize; do { ! 1235: *p++ = 0; ! 1236: } while (--i); ! 1237: i = 0; ! 1238: while (np = d.d_s[i++]) ! 1239: bitset(np->n_id, d.d_b); ! 1240: } ! 1241: /* ! 1242: ** search.c ! 1243: */ ! 1244: /* ! 1245: * execution of the DFA ! 1246: */ ! 1247: ! 1248: ! 1249: static bool status; /* set TRUE if any matches */ ! 1250: static char cbuf[BUFSIZ]; /* first BUFSIZ chars of input line */ ! 1251: static char *file; /* input file name */ ! 1252: static long nlines; /* input line count */ ! 1253: static long seekpos; /* start of current line in file */ ! 1254: static long matches; /* # matches */ ! 1255: static struct dragon *dfa; /* DFA start state */ ! 1256: static struct newt *nfa; /* NFA */ ! 1257: ! 1258: ! 1259: /* ! 1260: * search a file ! 1261: * Return TRUE if any matches. ! 1262: */ ! 1263: bool ! 1264: search(fn, dp, np) ! 1265: char *fn; ! 1266: struct dragon *dp; ! 1267: struct newt *np; ! 1268: { ! 1269: bool match(); ! 1270: ! 1271: file = fn; ! 1272: dfa = dp; ! 1273: nfa = np; ! 1274: nlines = 0; ! 1275: seekpos = 0; ! 1276: matches = 0; ! 1277: status = FALSE; ! 1278: ! 1279: while (match()) ! 1280: ; ! 1281: ! 1282: if (! sflag && ! lflag && cflag) { ! 1283: printfile(); ! 1284: printf("%ld\n", matches); ! 1285: } ! 1286: return (status); ! 1287: } ! 1288: ! 1289: ! 1290: /* ! 1291: * look for a match ! 1292: */ ! 1293: bool ! 1294: match() ! 1295: { ! 1296: register struct dragon *dp; ! 1297: register c; ! 1298: register char *p; ! 1299: long nchars; ! 1300: struct dragon *dp2; ! 1301: extern char etab[]; ! 1302: bool success(); ! 1303: ! 1304: if ((dp=dfa->d_p[etab['\n']]) == NULL) ! 1305: dp = makedfa(dfa, etab['\n'], nfa); ! 1306: nchars = 0; ! 1307: p = cbuf; ! 1308: ! 1309: while ((c=getc(ifp)) != EOF) { ! 1310: ++nchars; ! 1311: c &= 0177; ! 1312: if (p < &cbuf[BUFSIZ]) ! 1313: *p++ = c; ! 1314: dp2 = dp; ! 1315: if ((dp=dp->d_p[etab[c]]) == NULL) ! 1316: dp = makedfa(dp2, etab[c], nfa); ! 1317: if (c == '\n') { ! 1318: ++nlines; ! 1319: if (vflag!=dp->d_success && ! success(file, p)) ! 1320: break; ! 1321: seekpos += nchars; ! 1322: if (dp->d_success) ! 1323: return (TRUE); ! 1324: nchars = 0; ! 1325: p = cbuf; ! 1326: } ! 1327: } ! 1328: ! 1329: return (FALSE); ! 1330: } ! 1331: ! 1332: ! 1333: /* ! 1334: * report a match ! 1335: * If the line is to be printed, and it is over BUFSIZ chars, the ! 1336: * input file better be seekable. ! 1337: */ ! 1338: bool ! 1339: success(file, p) ! 1340: char *file; ! 1341: char *p; ! 1342: { ! 1343: extern char *tempnam(); ! 1344: register char *q; ! 1345: register c; ! 1346: register n; ! 1347: ! 1348: ++matches; ! 1349: status = TRUE; ! 1350: if (sflag) ! 1351: return (FALSE); ! 1352: if (lflag) { ! 1353: printf("%s\n", file); ! 1354: return (FALSE); ! 1355: } ! 1356: if (aflag) { ! 1357: if ((NULL == tmpFn) && ! 1358: ((NULL == (tmpFn = tempnam(NULL, "egr"))) || ! 1359: (NULL == (tmpFile = fopen(tmpFn, "w"))))) { ! 1360: fprintf(stderr, "egrep: cant open tmp file"); ! 1361: exit(1); ! 1362: } ! 1363: fprintf(tmpFile, "%ld:%s: egrep\n", nlines, file); ! 1364: return (TRUE); ! 1365: } ! 1366: if (cflag) ! 1367: return (TRUE); ! 1368: printfile(); ! 1369: if (nflag) ! 1370: printf("%ld:", nlines); ! 1371: if (bflag) ! 1372: printf("%ld:", seekpos/BUFSIZ); ! 1373: q = cbuf; ! 1374: n = p - q; ! 1375: while (q < p) ! 1376: putchar(*q++); ! 1377: if (*--q != '\n') { ! 1378: if (fseek(ifp, seekpos+n, 0) == EOF) { ! 1379: putchar('\n'); ! 1380: fatal("line too long"); ! 1381: } ! 1382: do { ! 1383: c = getc(ifp); ! 1384: if (c == EOF) ! 1385: return (FALSE); ! 1386: putchar(c); ! 1387: } while (c != '\n'); ! 1388: } ! 1389: return (TRUE); ! 1390: } ! 1391: ! 1392: ! 1393: static ! 1394: printfile() ! 1395: { ! 1396: ! 1397: if (! hflag) ! 1398: printf("%s:", file); ! 1399: } ! 1400: ! 1401: /* ! 1402: ** bits.c ! 1403: */ ! 1404: ! 1405: ! 1406: /* ! 1407: * allocate bitmap for character class ! 1408: * If `setbits'==TRUE then the map is initialized to ones, else zeros. ! 1409: */ ! 1410: char * ! 1411: newbits(setbits) ! 1412: bool setbits; ! 1413: { ! 1414: register i; ! 1415: register c; ! 1416: register char *p; ! 1417: register char *q; ! 1418: ! 1419: p = malloc(NCHARS/NBCHAR); ! 1420: if (p == NULL) ! 1421: nomem(); ! 1422: c = 0; ! 1423: if (setbits) ! 1424: c = ~0; ! 1425: q = p; ! 1426: i = NCHARS / NBCHAR; ! 1427: do { ! 1428: *p++ = c; ! 1429: } while (--i); ! 1430: return (q); ! 1431: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.