expr.c revision 1591 
1/*
2 * Copyright (c) 1989, 1993
3 *	The Regents of the University of California.  All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Ozan Yigit at York University.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 *    notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 * 3. All advertising materials mentioning features or use of this software
17 *    must display the following acknowledgement:
18 *	This product includes software developed by the University of
19 *	California, Berkeley and its contributors.
20 * 4. Neither the name of the University nor the names of its contributors
21 *    may be used to endorse or promote products derived from this software
22 *    without specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * SUCH DAMAGE.
35 */
36
37#ifndef lint
38static char sccsid[] = "@(#)expr.c	8.1 (Berkeley) 6/6/93";
39#endif /* not lint */
40
41#include <sys/cdefs.h>
42#include <stdio.h>
43
44/*
45 *      expression evaluator: performs a standard recursive
46 *      descent parse to evaluate any expression permissible
47 *      within the following grammar:
48 *
49 *      expr    :       query EOS
50 *      query   :       lor
51 *              |       lor "?" query ":" query
52 *      lor     :       land { "||" land }
53 *      land    :       bor { "&&" bor }
54 *      bor     :       bxor { "|" bxor }
55 *      bxor    :       band { "^" band }
56 *      band    :       eql { "&" eql }
57 *      eql     :       relat { eqrel relat }
58 *      relat   :       shift { rel shift }
59 *      shift   :       primary { shop primary }
60 *      primary :       term { addop term }
61 *      term    :       unary { mulop unary }
62 *      unary   :       factor
63 *              |       unop unary
64 *      factor  :       constant
65 *              |       "(" query ")"
66 *      constant:       num
67 *              |       "'" CHAR "'"
68 *      num     :       DIGIT
69 *              |       DIGIT num
70 *      shop    :       "<<"
71 *              |       ">>"
72 *      eqlrel  :       "="
73 *              |       "=="
74 *              |       "!="
75 *      rel     :       "<"
76 *              |       ">"
77 *              |       "<="
78 *              |       ">="
79 *
80 *
81 *      This expression evaluator is lifted from a public-domain
82 *      C Pre-Processor included with the DECUS C Compiler distribution.
83 *      It is hacked somewhat to be suitable for m4.
84 *
85 *      Originally by:  Mike Lutz
86 *                      Bob Harper
87 */
88
89#define TRUE    1
90#define FALSE   0
91#define EOS     (char) 0
92#define EQL     0
93#define NEQ     1
94#define LSS     2
95#define LEQ     3
96#define GTR     4
97#define GEQ     5
98#define OCTAL   8
99#define DECIMAL 10
100
101static char *nxtch;		       /* Parser scan pointer */
102
103static int query __P((void));
104static int lor __P((void));
105static int land __P((void));
106static int bor __P((void));
107static int bxor __P((void));
108static int band __P((void));
109static int eql __P((void));
110static int relat __P((void));
111static int shift __P((void));
112static int primary __P((void));
113static int term __P((void));
114static int unary __P((void));
115static int factor __P((void));
116static int constant __P((void));
117static int num __P((void));
118static int geteql __P((void));
119static int getrel __P((void));
120static int skipws __P((void));
121static void experr __P((char *));
122
123/*
124 * For longjmp
125 */
126#include <setjmp.h>
127static jmp_buf expjump;
128
129/*
130 * macros:
131 *      ungetch - Put back the last character examined.
132 *      getch   - return the next character from expr string.
133 */
134#define ungetch()       nxtch--
135#define getch()         *nxtch++
136
137int
138expr(expbuf)
139char *expbuf;
140{
141	register int rval;
142
143	nxtch = expbuf;
144	if (setjmp(expjump) != 0)
145		return FALSE;
146
147	rval = query();
148	if (skipws() == EOS)
149		return rval;
150
151	printf("m4: ill-formed expression.\n");
152	return FALSE;
153}
154
155/*
156 * query : lor | lor '?' query ':' query
157 */
158static int
159query()
160{
161	register int bool, true_val, false_val;
162
163	bool = lor();
164	if (skipws() != '?') {
165		ungetch();
166		return bool;
167	}
168
169	true_val = query();
170	if (skipws() != ':')
171		experr("bad query");
172
173	false_val = query();
174	return bool ? true_val : false_val;
175}
176
177/*
178 * lor : land { '||' land }
179 */
180static int
181lor()
182{
183	register int c, vl, vr;
184
185	vl = land();
186	while ((c = skipws()) == '|' && getch() == '|') {
187		vr = land();
188		vl = vl || vr;
189	}
190
191	if (c == '|')
192		ungetch();
193	ungetch();
194	return vl;
195}
196
197/*
198 * land : bor { '&&' bor }
199 */
200static int
201land()
202{
203	register int c, vl, vr;
204
205	vl = bor();
206	while ((c = skipws()) == '&' && getch() == '&') {
207		vr = bor();
208		vl = vl && vr;
209	}
210
211	if (c == '&')
212		ungetch();
213	ungetch();
214	return vl;
215}
216
217/*
218 * bor : bxor { '|' bxor }
219 */
220static int
221bor()
222{
223	register int vl, vr, c;
224
225	vl = bxor();
226	while ((c = skipws()) == '|' && getch() != '|') {
227		ungetch();
228		vr = bxor();
229		vl |= vr;
230	}
231
232	if (c == '|')
233		ungetch();
234	ungetch();
235	return vl;
236}
237
238/*
239 * bxor : band { '^' band }
240 */
241static int
242bxor()
243{
244	register int vl, vr;
245
246	vl = band();
247	while (skipws() == '^') {
248		vr = band();
249		vl ^= vr;
250	}
251
252	ungetch();
253	return vl;
254}
255
256/*
257 * band : eql { '&' eql }
258 */
259static int
260band()
261{
262	register int vl, vr, c;
263
264	vl = eql();
265	while ((c = skipws()) == '&' && getch() != '&') {
266		ungetch();
267		vr = eql();
268		vl &= vr;
269	}
270
271	if (c == '&')
272		ungetch();
273	ungetch();
274	return vl;
275}
276
277/*
278 * eql : relat { eqrel relat }
279 */
280static int
281eql()
282{
283	register int vl, vr, rel;
284
285	vl = relat();
286	while ((rel = geteql()) != -1) {
287		vr = relat();
288
289		switch (rel) {
290
291		case EQL:
292			vl = (vl == vr);
293			break;
294		case NEQ:
295			vl = (vl != vr);
296			break;
297		}
298	}
299	return vl;
300}
301
302/*
303 * relat : shift { rel shift }
304 */
305static int
306relat()
307{
308	register int vl, vr, rel;
309
310	vl = shift();
311	while ((rel = getrel()) != -1) {
312
313		vr = shift();
314		switch (rel) {
315
316		case LEQ:
317			vl = (vl <= vr);
318			break;
319		case LSS:
320			vl = (vl < vr);
321			break;
322		case GTR:
323			vl = (vl > vr);
324			break;
325		case GEQ:
326			vl = (vl >= vr);
327			break;
328		}
329	}
330	return vl;
331}
332
333/*
334 * shift : primary { shop primary }
335 */
336static int
337shift()
338{
339	register int vl, vr, c;
340
341	vl = primary();
342	while (((c = skipws()) == '<' || c == '>') && c == getch()) {
343		vr = primary();
344
345		if (c == '<')
346			vl <<= vr;
347		else
348			vl >>= vr;
349	}
350
351	if (c == '<' || c == '>')
352		ungetch();
353	ungetch();
354	return vl;
355}
356
357/*
358 * primary : term { addop term }
359 */
360static int
361primary()
362{
363	register int c, vl, vr;
364
365	vl = term();
366	while ((c = skipws()) == '+' || c == '-') {
367		vr = term();
368		if (c == '+')
369			vl += vr;
370		else
371			vl -= vr;
372	}
373
374	ungetch();
375	return vl;
376}
377
378/*
379 * <term> := <unary> { <mulop> <unary> }
380 */
381static int
382term()
383{
384	register int c, vl, vr;
385
386	vl = unary();
387	while ((c = skipws()) == '*' || c == '/' || c == '%') {
388		vr = unary();
389
390		switch (c) {
391		case '*':
392			vl *= vr;
393			break;
394		case '/':
395			vl /= vr;
396			break;
397		case '%':
398			vl %= vr;
399			break;
400		}
401	}
402	ungetch();
403	return vl;
404}
405
406/*
407 * unary : factor | unop unary
408 */
409static int
410unary()
411{
412	register int val, c;
413
414	if ((c = skipws()) == '!' || c == '~' || c == '-') {
415		val = unary();
416
417		switch (c) {
418		case '!':
419			return !val;
420		case '~':
421			return ~val;
422		case '-':
423			return -val;
424		}
425	}
426
427	ungetch();
428	return factor();
429}
430
431/*
432 * factor : constant | '(' query ')'
433 */
434static int
435factor()
436{
437	register int val;
438
439	if (skipws() == '(') {
440		val = query();
441		if (skipws() != ')')
442			experr("bad factor");
443		return val;
444	}
445
446	ungetch();
447	return constant();
448}
449
450/*
451 * constant: num | 'char'
452 * Note: constant() handles multi-byte constants
453 */
454static int
455constant()
456{
457	register int i;
458	register int value;
459	register char c;
460	int v[sizeof(int)];
461
462	if (skipws() != '\'') {
463		ungetch();
464		return num();
465	}
466	for (i = 0; i < sizeof(int); i++) {
467		if ((c = getch()) == '\'') {
468			ungetch();
469			break;
470		}
471		if (c == '\\') {
472			switch (c = getch()) {
473			case '0':
474			case '1':
475			case '2':
476			case '3':
477			case '4':
478			case '5':
479			case '6':
480			case '7':
481				ungetch();
482				c = num();
483				break;
484			case 'n':
485				c = 012;
486				break;
487			case 'r':
488				c = 015;
489				break;
490			case 't':
491				c = 011;
492				break;
493			case 'b':
494				c = 010;
495				break;
496			case 'f':
497				c = 014;
498				break;
499			}
500		}
501		v[i] = c;
502	}
503	if (i == 0 || getch() != '\'')
504		experr("illegal character constant");
505	for (value = 0; --i >= 0;) {
506		value <<= 8;
507		value += v[i];
508	}
509	return value;
510}
511
512/*
513 * num : digit | num digit
514 */
515static int
516num()
517{
518	register int rval, c, base;
519	int ndig;
520
521	base = ((c = skipws()) == '0') ? OCTAL : DECIMAL;
522	rval = 0;
523	ndig = 0;
524	while (c >= '0' && c <= (base == OCTAL ? '7' : '9')) {
525		rval *= base;
526		rval += (c - '0');
527		c = getch();
528		ndig++;
529	}
530	ungetch();
531
532	if (ndig == 0)
533		experr("bad constant");
534
535	return rval;
536
537}
538
539/*
540 * eqlrel : '=' | '==' | '!='
541 */
542static int
543geteql()
544{
545	register int c1, c2;
546
547	c1 = skipws();
548	c2 = getch();
549
550	switch (c1) {
551
552	case '=':
553		if (c2 != '=')
554			ungetch();
555		return EQL;
556
557	case '!':
558		if (c2 == '=')
559			return NEQ;
560		ungetch();
561		ungetch();
562		return -1;
563
564	default:
565		ungetch();
566		ungetch();
567		return -1;
568	}
569}
570
571/*
572 * rel : '<' | '>' | '<=' | '>='
573 */
574static int
575getrel()
576{
577	register int c1, c2;
578
579	c1 = skipws();
580	c2 = getch();
581
582	switch (c1) {
583
584	case '<':
585		if (c2 == '=')
586			return LEQ;
587		ungetch();
588		return LSS;
589
590	case '>':
591		if (c2 == '=')
592			return GEQ;
593		ungetch();
594		return GTR;
595
596	default:
597		ungetch();
598		ungetch();
599		return -1;
600	}
601}
602
603/*
604 * Skip over any white space and return terminating char.
605 */
606static int
607skipws()
608{
609	register char c;
610
611	while ((c = getch()) <= ' ' && c > EOS)
612		;
613	return c;
614}
615
616/*
617 * resets environment to eval(), prints an error
618 * and forces eval to return FALSE.
619 */
620static void
621experr(msg)
622char *msg;
623{
624	printf("m4: %s in expr.\n", msg);
625	longjmp(expjump, -1);
626}
627