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