xref: /original-bsd/bin/expr/expr.y (revision a5a45b47) 
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.2 (Berkeley) 05/16/92";
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:
149 		if (i2 != 0)
150 			i1 = i1 / i2;
151 		else
152 			yyerror("Divide by zero");
153 		break;
154 	case REM:
155 		if (i2 != 0)
156 			i1 = i1 % i2;
157 		else
158 			yyerror("Remainder by zero");
159 		break;
160 	}
161 	rv = malloc(16);
162 	(void)sprintf(rv, "%ld", i1);
163 	return rv;
164 }
165 char *conj(op, r1, r2) char *r1, *r2; {
166 	register char *rv;
167 
168 	switch(op) {
169 
170 	case OR:
171 		if(EQL(r1, "0")
172 		|| EQL(r1, ""))
173 			if(EQL(r2, "0")
174 			|| EQL(r2, ""))
175 				rv = "0";
176 			else
177 				rv = r2;
178 		else
179 			rv = r1;
180 		break;
181 	case AND:
182 		if(EQL(r1, "0")
183 		|| EQL(r1, ""))
184 			rv = "0";
185 		else if(EQL(r2, "0")
186 		|| EQL(r2, ""))
187 			rv = "0";
188 		else
189 			rv = r1;
190 		break;
191 	}
192 	return rv;
193 }
194 
195 char *substr(v, s, w) char *v, *s, *w; {
196 register si, wi;
197 register char *res;
198 
199 	si = atol(s);
200 	wi = atol(w);
201 	while(--si) if(*v) ++v;
202 
203 	res = v;
204 
205 	while(wi--) if(*v) ++v;
206 
207 	*v = '\0';
208 	return res;
209 }
210 
211 char *length(s) register char *s; {
212 	register i = 0;
213 	register char *rv;
214 
215 	while(*s++) ++i;
216 
217 	rv = malloc(8);
218 	(void)sprintf(rv, "%d", i);
219 	return rv;
220 }
221 
222 char *index(s, t) char *s, *t; {
223 	register i, j;
224 	register char *rv;
225 
226 	for(i = 0; s[i] ; ++i)
227 		for(j = 0; t[j] ; ++j)
228 			if(s[i]==t[j]) {
229 				(void)sprintf(rv = malloc(8), "%d", ++i);
230 				return rv;
231 			}
232 	return "0";
233 }
234 
235 char *match(s, p)
236 {
237 	register char *rv;
238 
239 	(void)sprintf(rv = malloc(8), "%d", ematch(s, p));
240 	if(nbra) {
241 		rv = malloc(strlen(Mstring[0])+1);
242 		strcpy(rv, Mstring[0]);
243 	}
244 	return rv;
245 }
246 
247 #define INIT	register char *sp = instring;
248 #define GETC()		(*sp++)
249 #define PEEKC()		(*sp)
250 #define UNGETC(c)	(--sp)
251 #define RETURN(c)	return
252 #define ERROR(c)	errxx(c)
253 
254 
255 ematch(s, p)
256 char *s;
257 register char *p;
258 {
259 	static char expbuf[ESIZE];
260 	char *compile();
261 	register num;
262 	extern char *braslist[], *braelist[], *loc2;
263 
264 	compile(p, expbuf, &expbuf[ESIZE], 0);
265 	if(nbra > 1)
266 		yyerror("Too many '\\('s");
267 	if(advance(s, expbuf)) {
268 		if(nbra == 1) {
269 			p = braslist[0];
270 			num = braelist[0] - p;
271 			strncpy(Mstring[0], p, num);
272 			Mstring[0][num] = '\0';
273 		}
274 		return(loc2-s);
275 	}
276 	return(0);
277 }
278 
279 errxx(c)
280 {
281 	yyerror("RE error");
282 }
283 
284 #define	CBRA	2
285 #define	CCHR	4
286 #define	CDOT	8
287 #define	CCL	12
288 #define	CDOL	20
289 #define	CEOF	22
290 #define	CKET	24
291 #define	CBACK	36
292 
293 #define	STAR	01
294 #define RNGE	03
295 
296 #define	NBRA	9
297 
298 #define PLACE(c)	ep[c >> 3] |= bittab[c & 07]
299 #define ISTHERE(c)	(ep[c >> 3] & bittab[c & 07])
300 
301 char	*braslist[NBRA];
302 char	*braelist[NBRA];
303 int	nbra;
304 char *loc1, *loc2, *locs;
305 int	sed;
306 
307 int	circf;
308 int	low;
309 int	size;
310 
311 char	bittab[] = {
312 	1,
313 	2,
314 	4,
315 	8,
316 	16,
317 	32,
318 	64,
319 	128
320 };
321 
322 char *
323 compile(instring, ep, endbuf, seof)
324 register char *ep;
325 char *instring, *endbuf;
326 {
327 	INIT	/* Dependent declarations and initializations */
328 	register c;
329 	register eof = seof;
330 	char *lastep = instring;
331 	int cclcnt;
332 	char bracket[NBRA], *bracketp;
333 	int closed;
334 	char neg;
335 	int lc;
336 	int i, cflg;
337 
338 	lastep = 0;
339 	if((c = GETC()) == eof) {
340 		if(*ep == 0 && !sed)
341 			ERROR(41);
342 		RETURN(ep);
343 	}
344 	bracketp = bracket;
345 	circf = closed = nbra = 0;
346 	if (c == '^')
347 		circf++;
348 	else
349 		UNGETC(c);
350 	for (;;) {
351 		if (ep >= endbuf)
352 			ERROR(50);
353 		if((c = GETC()) != '*' && ((c != '\\') || (PEEKC() != '{')))
354 			lastep = ep;
355 		if (c == eof) {
356 			*ep++ = CEOF;
357 			RETURN(ep);
358 		}
359 		switch (c) {
360 
361 		case '.':
362 			*ep++ = CDOT;
363 			continue;
364 
365 		case '\n':
366 			ERROR(36);
367 		case '*':
368 			if (lastep==0 || *lastep==CBRA || *lastep==CKET)
369 				goto defchar;
370 			*lastep |= STAR;
371 			continue;
372 
373 		case '$':
374 			if(PEEKC() != eof)
375 				goto defchar;
376 			*ep++ = CDOL;
377 			continue;
378 
379 		case '[':
380 			if(&ep[17] >= endbuf)
381 				ERROR(50);
382 
383 			*ep++ = CCL;
384 			lc = 0;
385 			for(i = 0; i < 16; i++)
386 				ep[i] = 0;
387 
388 			neg = 0;
389 			if((c = GETC()) == '^') {
390 				neg = 1;
391 				c = GETC();
392 			}
393 
394 			do {
395 				if(c == '\0' || c == '\n')
396 					ERROR(49);
397 				if(c == '-' && lc != 0) {
398 					if ((c = GETC()) == ']') {
399 						PLACE('-');
400 						break;
401 					}
402 					while(lc < c) {
403 						PLACE(lc);
404 						lc++;
405 					}
406 				}
407 				lc = c;
408 				PLACE(c);
409 			} while((c = GETC()) != ']');
410 			if(neg) {
411 				for(cclcnt = 0; cclcnt < 16; cclcnt++)
412 					ep[cclcnt] ^= -1;
413 				ep[0] &= 0376;
414 			}
415 
416 			ep += 16;
417 
418 			continue;
419 
420 		case '\\':
421 			switch(c = GETC()) {
422 
423 			case '(':
424 				if(nbra >= NBRA)
425 					ERROR(43);
426 				*bracketp++ = nbra;
427 				*ep++ = CBRA;
428 				*ep++ = nbra++;
429 				continue;
430 
431 			case ')':
432 				if(bracketp <= bracket)
433 					ERROR(42);
434 				*ep++ = CKET;
435 				*ep++ = *--bracketp;
436 				closed++;
437 				continue;
438 
439 			case '{':
440 				if(lastep == (char *) (0))
441 					goto defchar;
442 				*lastep |= RNGE;
443 				cflg = 0;
444 			nlim:
445 				c = GETC();
446 				i = 0;
447 				do {
448 					if ('0' <= c && c <= '9')
449 						i = 10 * i + c - '0';
450 					else
451 						ERROR(16);
452 				} while(((c = GETC()) != '\\') && (c != ','));
453 				if (i > 255)
454 					ERROR(11);
455 				*ep++ = i;
456 				if (c == ',') {
457 					if(cflg++)
458 						ERROR(44);
459 					if((c = GETC()) == '\\')
460 						*ep++ = 255;
461 					else {
462 						UNGETC(c);
463 						goto nlim; /* get 2'nd number */
464 					}
465 				}
466 				if(GETC() != '}')
467 					ERROR(45);
468 				if(!cflg)	/* one number */
469 					*ep++ = i;
470 				else if((ep[-1] & 0377) < (ep[-2] & 0377))
471 					ERROR(46);
472 				continue;
473 
474 			case '\n':
475 				ERROR(36);
476 
477 			case 'n':
478 				c = '\n';
479 				goto defchar;
480 
481 			default:
482 				if(c >= '1' && c <= '9') {
483 					if((c -= '1') >= closed)
484 						ERROR(25);
485 					*ep++ = CBACK;
486 					*ep++ = c;
487 					continue;
488 				}
489 			}
490 			/* Drop through to default to use \ to turn off special chars */
491 
492 		defchar:
493 		default:
494 			lastep = ep;
495 			*ep++ = CCHR;
496 			*ep++ = c;
497 		}
498 	}
499 }
500 
501 step(p1, p2)
502 register char *p1, *p2;
503 {
504 	register c;
505 
506 	if (circf) {
507 		loc1 = p1;
508 		return(advance(p1, p2));
509 	}
510 	/* fast check for first character */
511 	if (*p2==CCHR) {
512 		c = p2[1];
513 		do {
514 			if (*p1 != c)
515 				continue;
516 			if (advance(p1, p2)) {
517 				loc1 = p1;
518 				return(1);
519 			}
520 		} while (*p1++);
521 		return(0);
522 	}
523 		/* regular algorithm */
524 	do {
525 		if (advance(p1, p2)) {
526 			loc1 = p1;
527 			return(1);
528 		}
529 	} while (*p1++);
530 	return(0);
531 }
532 
533 advance(lp, ep)
534 register char *lp, *ep;
535 {
536 	register char *curlp;
537 	char c;
538 	char *bbeg;
539 	int ct;
540 
541 	for (;;) switch (*ep++) {
542 
543 	case CCHR:
544 		if (*ep++ == *lp++)
545 			continue;
546 		return(0);
547 
548 	case CDOT:
549 		if (*lp++)
550 			continue;
551 		return(0);
552 
553 	case CDOL:
554 		if (*lp==0)
555 			continue;
556 		return(0);
557 
558 	case CEOF:
559 		loc2 = lp;
560 		return(1);
561 
562 	case CCL:
563 		c = *lp++ & 0177;
564 		if(ISTHERE(c)) {
565 			ep += 16;
566 			continue;
567 		}
568 		return(0);
569 	case CBRA:
570 		braslist[*ep++] = lp;
571 		continue;
572 
573 	case CKET:
574 		braelist[*ep++] = lp;
575 		continue;
576 
577 	case CCHR|RNGE:
578 		c = *ep++;
579 		getrnge(ep);
580 		while(low--)
581 			if(*lp++ != c)
582 				return(0);
583 		curlp = lp;
584 		while(size--)
585 			if(*lp++ != c)
586 				break;
587 		if(size < 0)
588 			lp++;
589 		ep += 2;
590 		goto star;
591 
592 	case CDOT|RNGE:
593 		getrnge(ep);
594 		while(low--)
595 			if(*lp++ == '\0')
596 				return(0);
597 		curlp = lp;
598 		while(size--)
599 			if(*lp++ == '\0')
600 				break;
601 		if(size < 0)
602 			lp++;
603 		ep += 2;
604 		goto star;
605 
606 	case CCL|RNGE:
607 		getrnge(ep + 16);
608 		while(low--) {
609 			c = *lp++ & 0177;
610 			if(!ISTHERE(c))
611 				return(0);
612 		}
613 		curlp = lp;
614 		while(size--) {
615 			c = *lp++ & 0177;
616 			if(!ISTHERE(c))
617 				break;
618 		}
619 		if(size < 0)
620 			lp++;
621 		ep += 18;		/* 16 + 2 */
622 		goto star;
623 
624 	case CBACK:
625 		bbeg = braslist[*ep];
626 		ct = braelist[*ep++] - bbeg;
627 
628 		if(ecmp(bbeg, lp, ct)) {
629 			lp += ct;
630 			continue;
631 		}
632 		return(0);
633 
634 	case CBACK|STAR:
635 		bbeg = braslist[*ep];
636 		ct = braelist[*ep++] - bbeg;
637 		curlp = lp;
638 		while(ecmp(bbeg, lp, ct))
639 			lp += ct;
640 
641 		while(lp >= curlp) {
642 			if(advance(lp, ep))	return(1);
643 			lp -= ct;
644 		}
645 		return(0);
646 
647 
648 	case CDOT|STAR:
649 		curlp = lp;
650 		while (*lp++);
651 		goto star;
652 
653 	case CCHR|STAR:
654 		curlp = lp;
655 		while (*lp++ == *ep);
656 		ep++;
657 		goto star;
658 
659 	case CCL|STAR:
660 		curlp = lp;
661 		do {
662 			c = *lp++ & 0177;
663 		} while(ISTHERE(c));
664 		ep += 16;
665 		goto star;
666 
667 	star:
668 		do {
669 			if(--lp == locs)
670 				break;
671 			if (advance(lp, ep))
672 				return(1);
673 		} while (lp > curlp);
674 		return(0);
675 
676 	}
677 }
678 
679 getrnge(str)
680 register char *str;
681 {
682 	low = *str++ & 0377;
683 	size = (*str & 0377) == 255 ? 20000 : (*str & 0377) - low;
684 }
685 
686 ecmp(a, b, count)
687 register char	*a, *b;
688 register	count;
689 {
690 	if(a == b) /* should have been caught in compile() */
691 		error(51);
692 	while(count--)
693 		if(*a++ != *b++)	return(0);
694 	return(1);
695 }
696 
697 yyerror(s)
698 
699 {
700 	fprintf(stderr, "%s\n", s);
701 	exit(2);
702 }
703