![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to egrep.y CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv8dc / cmd|
Return to egrep.y CVS log | Up to [Research Unix] / researchv8dc / cmd |
1.1 root 1: /*
2: * egrep -- print lines containing (or not containing) a regular expression
3: *
4: * status returns:
5: * 0 - ok, and some matches
6: * 1 - ok, but no matches
7: * 2 - some error; matches irrelevant
8: */
9: %token CHAR DOT CCL NCCL OR CAT STAR PLUS QUEST
10: %left OR
11: %left CHAR DOT CCL NCCL '('
12: %left CAT
13: %left STAR PLUS QUEST
14:
15: %{
16: #include <stdio.h>
17: #include <ctype.h>
18:
19: #define BLKSIZE 512 /* size of reported disk blocks */
20: #define MAXLIN 1000
21: #define MAXPOS 10000
22: #define NCHARS 128
23: #define NSTATES 128
24: #define FINAL -1
25: #define LEFT '\177' /* serves as ^ */
26: #define RIGHT '\n' /* serves as record separator and as $ */
27: char gotofn[NSTATES][NCHARS];
28: int state[NSTATES];
29: char out[NSTATES];
30: int line = 1;
31: int name[MAXLIN];
32: int left[MAXLIN];
33: int right[MAXLIN];
34: int parent[MAXLIN];
35: int foll[MAXLIN];
36: int positions[MAXPOS];
37: char chars[MAXLIN];
38: int nxtpos = 0;
39: int inxtpos;
40: int nxtchar = 0;
41: int tmpstat[MAXLIN];
42: int initstat[MAXLIN];
43: int istat;
44: int nstate = 1;
45: int xstate;
46: int count;
47: int icount;
48: char *input;
49:
50: char reinit = 0;
51:
52: long lnum;
53: int bflag;
54: int cflag;
55: int fflag;
56: int lflag;
57: int nflag;
58: int hflag = 1;
59: int iflag;
60: int sflag;
61: int vflag;
62: int nfile;
63: long blkno;
64: long tln;
65: int nsucc;
66: int badbotch;
67:
68: int f;
69: FILE *expfile;
70: %}
71:
72: %%
73: s: t
74: ={ unary(FINAL, $1);
75: line--;
76: }
77: ;
78: t: b r
79: ={ $$ = node(CAT, $1, $2); }
80: | OR b r OR
81: ={ $$ = node(CAT, $2, $3); }
82: | OR b r
83: ={ $$ = node(CAT, $2, $3); }
84: | b r OR
85: ={ $$ = node(CAT, $1, $2); }
86: ;
87: b:
88: ={ $$ = enter(DOT);
89: $$ = unary(STAR, $$); }
90: ;
91: r: CHAR
92: ={ $$ = enter($1); }
93: | DOT
94: ={ $$ = enter(DOT); }
95: | CCL
96: ={ $$ = cclenter(CCL); }
97: | NCCL
98: ={ $$ = cclenter(NCCL); }
99: ;
100:
101: r: r OR r
102: ={ $$ = node(OR, $1, $3); }
103: | r r %prec CAT
104: ={ $$ = node(CAT, $1, $2); }
105: | r STAR
106: ={ $$ = unary(STAR, $1); }
107: | r PLUS
108: ={ $$ = unary(PLUS, $1); }
109: | r QUEST
110: ={ $$ = unary(QUEST, $1); }
111: | '(' r ')'
112: ={ $$ = $2; }
113: | error
114: ;
115:
116: %%
117: yyerror(s) {
118: fprintf(stderr, "egrep: %s\n", s);
119: exit(2);
120: }
121:
122: yylex() {
123: extern int yylval;
124: int cclcnt, x;
125: register char c, d;
126: switch(c = nextch()) {
127: case '^': c = LEFT;
128: goto defchar;
129: case '$': c = RIGHT;
130: goto defchar;
131: case '|': return (OR);
132: case '*': return (STAR);
133: case '+': return (PLUS);
134: case '?': return (QUEST);
135: case '(': return (c);
136: case ')': return (c);
137: case '.': return (DOT);
138: case '\0': return (0);
139: case RIGHT: return (OR);
140: case '[':
141: x = CCL;
142: cclcnt = 0;
143: count = nxtchar++;
144: if ((c = nextch()) == '^') {
145: x = NCCL;
146: c = nextch();
147: }
148: do {
149: if (c == '\0') synerror();
150: if (c == '-' && cclcnt > 0 && chars[nxtchar-1] != 0) {
151: if ((d = nextch()) != 0) {
152: c = chars[nxtchar-1];
153: while (c < d) {
154: if (nxtchar >= MAXLIN) overflo();
155: chars[nxtchar++] = ++c;
156: cclcnt++;
157: }
158: continue;
159: }
160: }
161: if (nxtchar >= MAXLIN) overflo();
162: chars[nxtchar++] = c;
163: cclcnt++;
164: } while ((c = nextch()) != ']');
165: chars[count] = cclcnt;
166: return (x);
167: case '\\':
168: if ((c = nextch()) == '\0') synerror();
169: defchar:
170: default: yylval = c; return (CHAR);
171: }
172: }
173: nextch() {
174: register char c;
175: if (fflag) {
176: if ((c = getc(expfile)) == EOF) return(0);
177: }
178: else c = *input++;
179: return(iflag? tolower(c): c);
180: }
181:
182: synerror() {
183: fprintf(stderr, "egrep: syntax error\n");
184: exit(2);
185: }
186:
187: enter(x) int x; {
188: if(line >= MAXLIN) overflo();
189: name[line] = x;
190: left[line] = 0;
191: right[line] = 0;
192: return(line++);
193: }
194:
195: cclenter(x) int x; {
196: register linno;
197: linno = enter(x);
198: right[linno] = count;
199: return (linno);
200: }
201:
202: node(x, l, r) {
203: if(line >= MAXLIN) overflo();
204: name[line] = x;
205: left[line] = l;
206: right[line] = r;
207: parent[l] = line;
208: parent[r] = line;
209: return(line++);
210: }
211:
212: unary(x, d) {
213: if(line >= MAXLIN) overflo();
214: name[line] = x;
215: left[line] = d;
216: right[line] = 0;
217: parent[d] = line;
218: return(line++);
219: }
220: overflo() {
221: fprintf(stderr, "egrep: regular expression too long\n");
222: exit(2);
223: }
224:
225: cfoll(v) {
226: register i;
227: if (left[v] == 0) {
228: count = 0;
229: for (i=1; i<=line; i++) tmpstat[i] = 0;
230: follow(v);
231: add(foll, v);
232: }
233: else if (right[v] == 0) cfoll(left[v]);
234: else {
235: cfoll(left[v]);
236: cfoll(right[v]);
237: }
238: }
239: cgotofn() {
240: register i;
241: count = 0;
242: inxtpos = nxtpos;
243: for (i=3; i<=line; i++) tmpstat[i] = 0;
244: if (cstate(line-1)==0) {
245: tmpstat[line] = 1;
246: count++;
247: out[1] = 1;
248: }
249: for (i=3; i<=line; i++) initstat[i] = tmpstat[i];
250: count--; /*leave out position 1 */
251: icount = count;
252: tmpstat[1] = 0;
253: add(state, 1);
254: istat = nxtst(1,LEFT);
255: }
256:
257: nxtst(s,c)
258: char c;
259: {
260: register i, num, k;
261: int pos, curpos, number, newpos;
262: num = positions[state[s]];
263: count = icount;
264: for (i=3; i<=line; i++) tmpstat[i] = initstat[i];
265: pos = state[s] + 1;
266: for (i=0; i<num; i++) {
267: curpos = positions[pos];
268: if ((k = name[curpos]) >= 0)
269: if (
270: (k == c)
271: | (k == DOT && c != LEFT && c != RIGHT)
272: | (k == CCL && member(c, right[curpos], 1))
273: | (k == NCCL && member(c, right[curpos], 0) && c != LEFT && c != RIGHT)
274: ) {
275: number = positions[foll[curpos]];
276: newpos = foll[curpos] + 1;
277: for (k=0; k<number; k++) {
278: if (tmpstat[positions[newpos]] != 1) {
279: tmpstat[positions[newpos]] = 1;
280: count++;
281: }
282: newpos++;
283: }
284: }
285: pos++;
286: }
287: if (notin(nstate)) {
288: if (++nstate >= NSTATES) {
289: for (i=1; i<NSTATES; i++)
290: out[i] = 0;
291: for (i=1; i<NSTATES; i++)
292: for (k=0; k<NCHARS; k++)
293: gotofn[i][k] = 0;
294: nstate = 1;
295: nxtpos = inxtpos;
296: reinit = 1;
297: add(state, nstate);
298: if (tmpstat[line] == 1) out[nstate] = 1;
299: return nstate;
300: }
301: add(state, nstate);
302: if (tmpstat[line] == 1) out[nstate] = 1;
303: gotofn[s][c] = nstate;
304: return nstate;
305: }
306: else {
307: gotofn[s][c] = xstate;
308: return xstate;
309: }
310: }
311:
312:
313: cstate(v) {
314: register b;
315: if (left[v] == 0) {
316: if (tmpstat[v] != 1) {
317: tmpstat[v] = 1;
318: count++;
319: }
320: return(1);
321: }
322: else if (right[v] == 0) {
323: if (cstate(left[v]) == 0) return (0);
324: else if (name[v] == PLUS) return (1);
325: else return (0);
326: }
327: else if (name[v] == CAT) {
328: if (cstate(left[v]) == 0 && cstate(right[v]) == 0) return (0);
329: else return (1);
330: }
331: else { /* name[v] == OR */
332: b = cstate(right[v]);
333: if (cstate(left[v]) == 0 || b == 0) return (0);
334: else return (1);
335: }
336: }
337:
338:
339: member(symb, set, torf) {
340: register i, num, pos;
341: num = chars[set];
342: pos = set + 1;
343: for (i=0; i<num; i++)
344: if (symb == chars[pos++]) return (torf);
345: return (!torf);
346: }
347:
348: notin(n) {
349: register i, j, pos;
350: for (i=1; i<=n; i++) {
351: if (positions[state[i]] == count) {
352: pos = state[i] + 1;
353: for (j=0; j < count; j++)
354: if (tmpstat[positions[pos++]] != 1) goto nxt;
355: xstate = i;
356: return (0);
357: }
358: nxt: ;
359: }
360: return (1);
361: }
362:
363: add(array, n) int *array; {
364: register i;
365: if (nxtpos + count >= MAXPOS) overflo();
366: array[n] = nxtpos;
367: positions[nxtpos++] = count;
368: for (i=3; i <= line; i++) {
369: if (tmpstat[i] == 1) {
370: positions[nxtpos++] = i;
371: }
372: }
373: }
374:
375: follow(v) int v; {
376: int p;
377: if (v == line) return;
378: p = parent[v];
379: switch(name[p]) {
380: case STAR:
381: case PLUS: cstate(v);
382: follow(p);
383: return;
384:
385: case OR:
386: case QUEST: follow(p);
387: return;
388:
389: case CAT: if (v == left[p]) {
390: if (cstate(right[p]) == 0) {
391: follow(p);
392: return;
393: }
394: }
395: else follow(p);
396: return;
397: case FINAL: if (tmpstat[line] != 1) {
398: tmpstat[line] = 1;
399: count++;
400: }
401: return;
402: }
403: }
404:
405:
406: main(argc, argv)
407: char **argv;
408: {
409: while (--argc > 0 && (++argv)[0][0]=='-')
410: switch (argv[0][1]) {
411:
412: case 's':
413: sflag++;
414: continue;
415:
416: case 'h':
417: hflag = 0;
418: continue;
419:
420: case 'i':
421: iflag++;
422: continue;
423:
424: case 'b':
425: bflag++;
426: continue;
427:
428: case 'c':
429: cflag++;
430: continue;
431:
432: case 'e':
433: argc--;
434: argv++;
435: goto cut;
436:
437: case 'f':
438: fflag++;
439: continue;
440:
441: case 'l':
442: lflag++;
443: continue;
444:
445: case 'n':
446: nflag++;
447: continue;
448:
449: case 'v':
450: vflag++;
451: continue;
452:
453: default:
454: fprintf(stderr, "egrep: unknown flag\n");
455: continue;
456: }
457: cut:
458: if (argc<=0)
459: exit(2);
460: if (fflag) {
461: if ((expfile = fopen(*argv, "r")) == NULL) {
462: fprintf(stderr, "egrep: can't open %s\n", *argv);
463: exit(2);
464: }
465: }
466: else input = *argv;
467: argc--;
468: argv++;
469:
470: yyparse();
471:
472: cfoll(line-1);
473: cgotofn();
474: nfile = argc;
475: if (argc<=0) {
476: if (lflag) exit(1);
477: execute(0);
478: }
479: else while (--argc >= 0) {
480: execute(*argv);
481: argv++;
482: }
483: exit(badbotch ? 2 : nsucc==0);
484: }
485:
486: execute(file)
487: char *file;
488: {
489: register char *p;
490: register cstat;
491: register c;
492: register t;
493: int ccount;
494: char buf[2*BUFSIZ];
495: char *nlp;
496: if (file) {
497: if ((f = open(file, 0)) < 0) {
498: fprintf(stderr, "egrep: can't open %s\n", file);
499: badbotch=1;
500: return;
501: }
502: }
503: else f = 0;
504: ccount = 0;
505: lnum = 1;
506: tln = 0;
507: p = buf;
508: nlp = p;
509: if ((ccount = read(f,p,BUFSIZ))<=0) goto done;
510: blkno = ccount;
511: cstat = istat;
512: if (out[cstat]) goto found;
513: for (;;) {
514: c = *p&0377;
515: if(iflag && c>='A' && c<='Z')
516: c += 'a'-'A';
517: if ((t = gotofn[cstat][c]) == 0)
518: cstat = nxtst(cstat,c);
519: else
520: cstat = t;
521: if (out[cstat]) {
522: found: for(;;) {
523: if (*p++ == RIGHT) {
524: if (vflag == 0) {
525: succeed: nsucc = 1;
526: if (cflag) tln++;
527: else if (sflag)
528: ; /* ugh */
529: else if (lflag) {
530: printf("%s\n", file);
531: close(f);
532: return;
533: }
534: else {
535: if (nfile > 1 && hflag) printf("%s:", file);
536: if (bflag) printf("%ld:", (blkno-ccount-1)/BLKSIZE);
537: if (nflag) printf("%ld:", lnum);
538: if (p <= nlp) {
539: while (nlp < &buf[2*BUFSIZ]) putchar(*nlp++);
540: nlp = buf;
541: }
542: while (nlp < p) putchar(*nlp++);
543: }
544: }
545: lnum++;
546: nlp = p;
547: if (reinit == 1) {
548: clearg();
549: }
550: if ((out[(cstat=istat)]) == 0) goto brk2;
551: }
552: cfound:
553: if (--ccount <= 0) {
554: if (p <= &buf[BUFSIZ]) {
555: if ((ccount = read(f, p, BUFSIZ)) <= 0) goto done;
556: }
557: else if (p == &buf[2*BUFSIZ]) {
558: p = buf;
559: if ((ccount = read(f, p, BUFSIZ)) <= 0) goto done;
560: }
561: else {
562: if ((ccount = read(f, p, &buf[2*BUFSIZ]-p)) <= 0) goto done;
563: }
564: if(nlp>p && nlp<=p+ccount)
565: nlp = p+ccount;
566: blkno += ccount;
567: }
568: }
569: }
570: if (*p++ == RIGHT) {
571: if (vflag) goto succeed;
572: else {
573: lnum++;
574: nlp = p;
575: if (reinit == 1) {
576: clearg();
577: }
578: if (out[(cstat=istat)]) goto cfound;
579: }
580: }
581: brk2:
582: if (--ccount <= 0) {
583: if (p <= &buf[BUFSIZ]) {
584: if ((ccount = read(f, p, BUFSIZ)) <= 0) break;
585: }
586: else if (p == &buf[2*BUFSIZ]) {
587: p = buf;
588: if ((ccount = read(f, p, BUFSIZ)) <= 0) break;
589: }
590: else {
591: if ((ccount = read(f, p, &buf[2*BUFSIZ] - p)) <= 0) break;
592: }
593: if(nlp>p && nlp<=p+ccount)
594: nlp = p+ccount;
595: blkno += ccount;
596: }
597: }
598: done: close(f);
599: if (cflag) {
600: if (nfile > 1)
601: printf("%s:", file);
602: printf("%ld\n", tln);
603: }
604: }
605:
606: clearg() {
607: register i, k;
608: for (i=1; i<NSTATES; i++)
609: out[i] = 0;
610: for (i=1; i<NSTATES; i++)
611: for (k=0; k<NCHARS; k++)
612: gotofn[i][k] = 0;
613: nstate = 1;
614: nxtpos = inxtpos;
615: reinit = 1;
616: count = 0;
617: for (i=3; i<=line; i++) tmpstat[i] = 0;
618: if (cstate(line-1)==0) {
619: tmpstat[line] = 1;
620: count++;
621: out[1] = 1;
622: }
623: for (i=3; i<=line; i++) initstat[i] = tmpstat[i];
624: count--; /*leave out position 1 */
625: icount = count;
626: tmpstat[1] = 0;
627: add(state, 1);
628: istat = nxtst(1,LEFT);
629: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.