xref: /original-bsd/bin/expr/expr.y (revision 2d1a7683) 
1 /*-
2  * Copyright (c) 1991 The Regents of the University of California.
3  * All rights reserved.
4  *
5  * %sccs.include.redist.c%
6  */
7 
8 /* Yacc productions for "expr" command: */
9 %{
10 typedef char *yystype;
11 #define	YYSTYPE yystype
12 %}
13 
14 %token OR AND ADD SUBT MULT DIV REM EQ GT GEQ LT LEQ NEQ
15 %token A_STRING SUBSTR LENGTH INDEX NOARG MATCH
16 
17 /* operators listed below in increasing precedence: */
18 %left OR
19 %left AND
20 %left EQ LT GT GEQ LEQ NEQ
21 %left ADD SUBT
22 %left MULT DIV REM
23 %left MCH
24 %left MATCH
25 %left SUBSTR
26 %left LENGTH INDEX
27 %%
28 
29 /* a single `expression' is evaluated and printed: */
30 
31 expression:	expr NOARG = {
32 			printf("%s\n", $1);
33 			exit((!strcmp($1,"0")||!strcmp($1,"\0"))? 1: 0);
34 			}
35 	;
36 
37 
38 expr:	'(' expr ')' = { $$ = $2; }
39 	| expr OR expr   = { $$ = conj(OR, $1, $3); }
40 	| expr AND expr   = { $$ = conj(AND, $1, $3); }
41 	| expr EQ expr   = { $$ = rel(EQ, $1, $3); }
42 	| expr GT expr   = { $$ = rel(GT, $1, $3); }
43 	| expr GEQ expr   = { $$ = rel(GEQ, $1, $3); }
44 	| expr LT expr   = { $$ = rel(LT, $1, $3); }
45 	| expr LEQ expr   = { $$ = rel(LEQ, $1, $3); }
46 	| expr NEQ expr   = { $$ = rel(NEQ, $1, $3); }
47 	| expr ADD expr   = { $$ = arith(ADD, $1, $3); }
48 	| expr SUBT expr   = { $$ = arith(SUBT, $1, $3); }
49 	| expr MULT expr   = { $$ = arith(MULT, $1, $3); }
50 	| expr DIV expr   = { $$ = arith(DIV, $1, $3); }
51 	| expr REM expr   = { $$ = arith(REM, $1, $3); }
52 	| expr MCH expr	 = { $$ = match($1, $3); }
53 	| MATCH expr expr = { $$ = match($2, $3); }
54 	| SUBSTR expr expr expr = { $$ = substr($2, $3, $4); }
55 	| LENGTH expr       = { $$ = length($2); }
56 	| INDEX expr expr = { $$ = index($2, $3); }
57 	| A_STRING
58 	;
59 %%
60 /*	expression command */
61 
62 #ifndef lint
63 char copyright[] =
64 "@(#) Copyright (c) 1991 The Regents of the University of California.\n\
65  All rights reserved.\n";
66 #endif /* not lint */
67 
68 #ifndef lint
69 static char sccsid[] = "@(#)expr.y	5.1 (Berkeley) 04/08/91";
70 #endif /* not lint */
71 
72 #include <stdio.h>
73 #define ESIZE	256
74 #define error(c)	errxx(c)
75 #define EQL(x,y) !strcmp(x,y)
76 long atol();
77 char	**Av;
78 int	Ac;
79 int	Argi;
80 
81 char Mstring[1][128];
82 char *malloc();
83 extern int nbra;
84 
85 main(argc, argv) char **argv; {
86 	Ac = argc;
87 	Argi = 1;
88 	Av = argv;
89 	yyparse();
90 }
91 
92 char *operators[] = { "|", "&", "+", "-", "*", "/", "%", ":",
93 	"=", "==", "<", "<=", ">", ">=", "!=",
94 	"match", "substr", "length", "index", "\0" };
95 int op[] = { OR, AND, ADD,  SUBT, MULT, DIV, REM, MCH,
96 	EQ, EQ, LT, LEQ, GT, GEQ, NEQ,
97 	MATCH, SUBSTR, LENGTH, INDEX };
98 yylex() {
99 	register char *p;
100 	register i;
101 
102 	if(Argi >= Ac) return NOARG;
103 
104 	p = Av[Argi++];
105 
106 	if(*p == '(' || *p == ')')
107 		return (int)*p;
108 	for(i = 0; *operators[i]; ++i)
109 		if(EQL(operators[i], p))
110 			return op[i];
111 
112 	yylval = p;
113 	return A_STRING;
114 }
115 
116 char *rel(op, r1, r2) register char *r1, *r2; {
117 	register long i;
118 
119 	if(ematch(r1, "-*[0-9]*$") && ematch(r2, "[0-9]*$"))
120 		i = atol(r1) - atol(r2);
121 	else
122 		i = strcmp(r1, r2);
123 	switch(op) {
124 	case EQ: i = i==0; break;
125 	case GT: i = i>0; break;
126 	case GEQ: i = i>=0; break;
127 	case LT: i = i<0; break;
128 	case LEQ: i = i<=0; break;
129 	case NEQ: i = i!=0; break;
130 	}
131 	return i? "1": "0";
132 }
133 
134 char *arith(op, r1, r2) char *r1, *r2; {
135 	long i1, i2;
136 	register char *rv;
137 
138 	if(!((ematch(r1, "[0-9]*$") || ematch(r1, "-[0-9]*$")) &&
139 	     (ematch(r2, "[0-9]*$") || ematch(r2, "-[0-9]*$"))))
140 		yyerror("non-numeric argument");
141 	i1 = atol(r1);
142 	i2 = atol(r2);
143 
144 	switch(op) {
145 	case ADD: i1 = i1 + i2; break;
146 	case SUBT: i1 = i1 - i2; break;
147 	case MULT: i1 = i1 * i2; break;
148 	case DIV: i1 = i1 / i2; break;
149 	case REM: i1 = i1 % i2; break;
150 	}
151 	rv = malloc(16);
152 	(void)sprintf(rv, "%ld", i1);
153 	return rv;
154 }
155 char *conj(op, r1, r2) char *r1, *r2; {
156 	register char *rv;
157 
158 	switch(op) {
159 
160 	case OR:
161 		if(EQL(r1, "0")
162 		|| EQL(r1, ""))
163 			if(EQL(r2, "0")
164 			|| EQL(r2, ""))
165 				rv = "0";
166 			else
167 				rv = r2;
168 		else
169 			rv = r1;
170 		break;
171 	case AND:
172 		if(EQL(r1, "0")
173 		|| EQL(r1, ""))
174 			rv = "0";
175 		else if(EQL(r2, "0")
176 		|| EQL(r2, ""))
177 			rv = "0";
178 		else
179 			rv = r1;
180 		break;
181 	}
182 	return rv;
183 }
184 
185 char *substr(v, s, w) char *v, *s, *w; {
186 register si, wi;
187 register char *res;
188 
189 	si = atol(s);
190 	wi = atol(w);
191 	while(--si) if(*v) ++v;
192 
193 	res = v;
194 
195 	while(wi--) if(*v) ++v;
196 
197 	*v = '\0';
198 	return res;
199 }
200 
201 char *length(s) register char *s; {
202 	register i = 0;
203 	register char *rv;
204 
205 	while(*s++) ++i;
206 
207 	rv = malloc(8);
208 	(void)sprintf(rv, "%d", i);
209 	return rv;
210 }
211 
212 char *index(s, t) char *s, *t; {
213 	register i, j;
214 	register char *rv;
215 
216 	for(i = 0; s[i] ; ++i)
217 		for(j = 0; t[j] ; ++j)
218 			if(s[i]==t[j]) {
219 				(void)sprintf(rv = malloc(8), "%d", ++i);
220 				return rv;
221 			}
222 	return "0";
223 }
224 
225 char *match(s, p)
226 {
227 	register char *rv;
228 
229 	(void)sprintf(rv = malloc(8), "%d", ematch(s, p));
230 	if(nbra) {
231 		rv = malloc(strlen(Mstring[0])+1);
232 		strcpy(rv, Mstring[0]);
233 	}
234 	return rv;
235 }
236 
237 #define INIT	register char *sp = instring;
238 #define GETC()		(*sp++)
239 #define PEEKC()		(*sp)
240 #define UNGETC(c)	(--sp)
241 #define RETURN(c)	return
242 #define ERROR(c)	errxx(c)
243 
244 
245 ematch(s, p)
246 char *s;
247 register char *p;
248 {
249 	static char expbuf[ESIZE];
250 	char *compile();
251 	register num;
252 	extern char *braslist[], *braelist[], *loc2;
253 
254 	compile(p, expbuf, &expbuf[ESIZE], 0);
255 	if(nbra > 1)
256 		yyerror("Too many '\\('s");
257 	if(advance(s, expbuf)) {
258 		if(nbra == 1) {
259 			p = braslist[0];
260 			num = braelist[0] - p;
261 			strncpy(Mstring[0], p, num);
262 			Mstring[0][num] = '\0';
263 		}
264 		return(loc2-s);
265 	}
266 	return(0);
267 }
268 
269 errxx(c)
270 {
271 	yyerror("RE error");
272 }
273 
274 #define	CBRA	2
275 #define	CCHR	4
276 #define	CDOT	8
277 #define	CCL	12
278 #define	CDOL	20
279 #define	CEOF	22
280 #define	CKET	24
281 #define	CBACK	36
282 
283 #define	STAR	01
284 #define RNGE	03
285 
286 #define	NBRA	9
287 
288 #define PLACE(c)	ep[c >> 3] |= bittab[c & 07]
289 #define ISTHERE(c)	(ep[c >> 3] & bittab[c & 07])
290 
291 char	*braslist[NBRA];
292 char	*braelist[NBRA];
293 int	nbra;
294 char *loc1, *loc2, *locs;
295 int	sed;
296 
297 int	circf;
298 int	low;
299 int	size;
300 
301 char	bittab[] = {
302 	1,
303 	2,
304 	4,
305 	8,
306 	16,
307 	32,
308 	64,
309 	128
310 };
311 
312 char *
313 compile(instring, ep, endbuf, seof)
314 register char *ep;
315 char *instring, *endbuf;
316 {
317 	INIT	/* Dependent declarations and initializations */
318 	register c;
319 	register eof = seof;
320 	char *lastep = instring;
321 	int cclcnt;
322 	char bracket[NBRA], *bracketp;
323 	int closed;
324 	char neg;
325 	int lc;
326 	int i, cflg;
327 
328 	lastep = 0;
329 	if((c = GETC()) == eof) {
330 		if(*ep == 0 && !sed)
331 			ERROR(41);
332 		RETURN(ep);
333 	}
334 	bracketp = bracket;
335 	circf = closed = nbra = 0;
336 	if (c == '^')
337 		circf++;
338 	else
339 		UNGETC(c);
340 	for (;;) {
341 		if (ep >= endbuf)
342 			ERROR(50);
343 		if((c = GETC()) != '*' && ((c != '\\') || (PEEKC() != '{')))
344 			lastep = ep;
345 		if (c == eof) {
346 			*ep++ = CEOF;
347 			RETURN(ep);
348 		}
349 		switch (c) {
350 
351 		case '.':
352 			*ep++ = CDOT;
353 			continue;
354 
355 		case '\n':
356 			ERROR(36);
357 		case '*':
358 			if (lastep==0 || *lastep==CBRA || *lastep==CKET)
359 				goto defchar;
360 			*lastep |= STAR;
361 			continue;
362 
363 		case '$':
364 			if(PEEKC() != eof)
365 				goto defchar;
366 			*ep++ = CDOL;
367 			continue;
368 
369 		case '[':
370 			if(&ep[17] >= endbuf)
371 				ERROR(50);
372 
373 			*ep++ = CCL;
374 			lc = 0;
375 			for(i = 0; i < 16; i++)
376 				ep[i] = 0;
377 
378 			neg = 0;
379 			if((c = GETC()) == '^') {
380 				neg = 1;
381 				c = GETC();
382 			}
383 
384 			do {
385 				if(c == '\0' || c == '\n')
386 					ERROR(49);
387 				if(c == '-' && lc != 0) {
388 					if ((c = GETC()) == ']') {
389 						PLACE('-');
390 						break;
391 					}
392 					while(lc < c) {
393 						PLACE(lc);
394 						lc++;
395 					}
396 				}
397 				lc = c;
398 				PLACE(c);
399 			} while((c = GETC()) != ']');
400 			if(neg) {
401 				for(cclcnt = 0; cclcnt < 16; cclcnt++)
402 					ep[cclcnt] ^= -1;
403 				ep[0] &= 0376;
404 			}
405 
406 			ep += 16;
407 
408 			continue;
409 
410 		case '\\':
411 			switch(c = GETC()) {
412 
413 			case '(':
414 				if(nbra >= NBRA)
415 					ERROR(43);
416 				*bracketp++ = nbra;
417 				*ep++ = CBRA;
418 				*ep++ = nbra++;
419 				continue;
420 
421 			case ')':
422 				if(bracketp <= bracket)
423 					ERROR(42);
424 				*ep++ = CKET;
425 				*ep++ = *--bracketp;
426 				closed++;
427 				continue;
428 
429 			case '{':
430 				if(lastep == (char *) (0))
431 					goto defchar;
432 				*lastep |= RNGE;
433 				cflg = 0;
434 			nlim:
435 				c = GETC();
436 				i = 0;
437 				do {
438 					if ('0' <= c && c <= '9')
439 						i = 10 * i + c - '0';
440 					else
441 						ERROR(16);
442 				} while(((c = GETC()) != '\\') && (c != ','));
443 				if (i > 255)
444 					ERROR(11);
445 				*ep++ = i;
446 				if (c == ',') {
447 					if(cflg++)
448 						ERROR(44);
449 					if((c = GETC()) == '\\')
450 						*ep++ = 255;
451 					else {
452 						UNGETC(c);
453 						goto nlim; /* get 2'nd number */
454 					}
455 				}
456 				if(GETC() != '}')
457 					ERROR(45);
458 				if(!cflg)	/* one number */
459 					*ep++ = i;
460 				else if((ep[-1] & 0377) < (ep[-2] & 0377))
461 					ERROR(46);
462 				continue;
463 
464 			case '\n':
465 				ERROR(36);
466 
467 			case 'n':
468 				c = '\n';
469 				goto defchar;
470 
471 			default:
472 				if(c >= '1' && c <= '9') {
473 					if((c -= '1') >= closed)
474 						ERROR(25);
475 					*ep++ = CBACK;
476 					*ep++ = c;
477 					continue;
478 				}
479 			}
480 			/* Drop through to default to use \ to turn off special chars */
481 
482 		defchar:
483 		default:
484 			lastep = ep;
485 			*ep++ = CCHR;
486 			*ep++ = c;
487 		}
488 	}
489 }
490 
491 step(p1, p2)
492 register char *p1, *p2;
493 {
494 	register c;
495 
496 	if (circf) {
497 		loc1 = p1;
498 		return(advance(p1, p2));
499 	}
500 	/* fast check for first character */
501 	if (*p2==CCHR) {
502 		c = p2[1];
503 		do {
504 			if (*p1 != c)
505 				continue;
506 			if (advance(p1, p2)) {
507 				loc1 = p1;
508 				return(1);
509 			}
510 		} while (*p1++);
511 		return(0);
512 	}
513 		/* regular algorithm */
514 	do {
515 		if (advance(p1, p2)) {
516 			loc1 = p1;
517 			return(1);
518 		}
519 	} while (*p1++);
520 	return(0);
521 }
522 
523 advance(lp, ep)
524 register char *lp, *ep;
525 {
526 	register char *curlp;
527 	char c;
528 	char *bbeg;
529 	int ct;
530 
531 	for (;;) switch (*ep++) {
532 
533 	case CCHR:
534 		if (*ep++ == *lp++)
535 			continue;
536 		return(0);
537 
538 	case CDOT:
539 		if (*lp++)
540 			continue;
541 		return(0);
542 
543 	case CDOL:
544 		if (*lp==0)
545 			continue;
546 		return(0);
547 
548 	case CEOF:
549 		loc2 = lp;
550 		return(1);
551 
552 	case CCL:
553 		c = *lp++ & 0177;
554 		if(ISTHERE(c)) {
555 			ep += 16;
556 			continue;
557 		}
558 		return(0);
559 	case CBRA:
560 		braslist[*ep++] = lp;
561 		continue;
562 
563 	case CKET:
564 		braelist[*ep++] = lp;
565 		continue;
566 
567 	case CCHR|RNGE:
568 		c = *ep++;
569 		getrnge(ep);
570 		while(low--)
571 			if(*lp++ != c)
572 				return(0);
573 		curlp = lp;
574 		while(size--)
575 			if(*lp++ != c)
576 				break;
577 		if(size < 0)
578 			lp++;
579 		ep += 2;
580 		goto star;
581 
582 	case CDOT|RNGE:
583 		getrnge(ep);
584 		while(low--)
585 			if(*lp++ == '\0')
586 				return(0);
587 		curlp = lp;
588 		while(size--)
589 			if(*lp++ == '\0')
590 				break;
591 		if(size < 0)
592 			lp++;
593 		ep += 2;
594 		goto star;
595 
596 	case CCL|RNGE:
597 		getrnge(ep + 16);
598 		while(low--) {
599 			c = *lp++ & 0177;
600 			if(!ISTHERE(c))
601 				return(0);
602 		}
603 		curlp = lp;
604 		while(size--) {
605 			c = *lp++ & 0177;
606 			if(!ISTHERE(c))
607 				break;
608 		}
609 		if(size < 0)
610 			lp++;
611 		ep += 18;		/* 16 + 2 */
612 		goto star;
613 
614 	case CBACK:
615 		bbeg = braslist[*ep];
616 		ct = braelist[*ep++] - bbeg;
617 
618 		if(ecmp(bbeg, lp, ct)) {
619 			lp += ct;
620 			continue;
621 		}
622 		return(0);
623 
624 	case CBACK|STAR:
625 		bbeg = braslist[*ep];
626 		ct = braelist[*ep++] - bbeg;
627 		curlp = lp;
628 		while(ecmp(bbeg, lp, ct))
629 			lp += ct;
630 
631 		while(lp >= curlp) {
632 			if(advance(lp, ep))	return(1);
633 			lp -= ct;
634 		}
635 		return(0);
636 
637 
638 	case CDOT|STAR:
639 		curlp = lp;
640 		while (*lp++);
641 		goto star;
642 
643 	case CCHR|STAR:
644 		curlp = lp;
645 		while (*lp++ == *ep);
646 		ep++;
647 		goto star;
648 
649 	case CCL|STAR:
650 		curlp = lp;
651 		do {
652 			c = *lp++ & 0177;
653 		} while(ISTHERE(c));
654 		ep += 16;
655 		goto star;
656 
657 	star:
658 		do {
659 			if(--lp == locs)
660 				break;
661 			if (advance(lp, ep))
662 				return(1);
663 		} while (lp > curlp);
664 		return(0);
665 
666 	}
667 }
668 
669 getrnge(str)
670 register char *str;
671 {
672 	low = *str++ & 0377;
673 	size = (*str & 0377) == 255 ? 20000 : (*str & 0377) - low;
674 }
675 
676 ecmp(a, b, count)
677 register char	*a, *b;
678 register	count;
679 {
680 	if(a == b) /* should have been caught in compile() */
681 		error(51);
682 	while(count--)
683 		if(*a++ != *b++)	return(0);
684 	return(1);
685 }
686 
687 yyerror(s)
688 
689 {
690 	fprintf(stderr, "%s\n", s);
691 	exit(2);
692 }
693