![[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.