expr.c revision 8874 
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    :       not { "&&" not }
54 *	not	:	eqrel
55 *		|	'!' not
56 *      eqrel   :       shift { eqrelop shift }
57 *      shift   :       primary { shop primary }
58 *      primary :       term { addop term }
59 *      term    :       exp { mulop exp }
60 *	exp	:	unary { expop unary }
61 *      unary   :       factor
62 *              |       unop unary
63 *      factor  :       constant
64 *              |       "(" query ")"
65 *      constant:       num
66 *              |       "'" CHAR "'"
67 *      num     :       DIGIT
68 *              |       DIGIT num
69 *      shop    :       "<<"
70 *              |       ">>"
71 *      eqrel   :       "="
72 *              |       "=="
73 *              |       "!="
74 *      	|       "<"
75 *              |       ">"
76 *              |       "<="
77 *              |       ">="
78 *
79 *
80 *      This expression evaluator is lifted from a public-domain
81 *      C Pre-Processor included with the DECUS C Compiler distribution.
82 *      It is hacked somewhat to be suitable for m4.
83 *
84 *      Originally by:  Mike Lutz
85 *                      Bob Harper
86 */
87
88#define TRUE    1
89#define FALSE   0
90#define EOS     (char) 0
91#define EQL     0
92#define NEQ     1
93#define LSS     2
94#define LEQ     3
95#define GTR     4
96#define GEQ     5
97#define OCTAL   8
98#define DECIMAL 10
99
100static char *nxtch;		       /* Parser scan pointer */
101
102static int query __P((void));
103static int lor __P((void));
104static int land __P((void));
105static int not __P((void));
106static int eqrel __P((void));
107static int shift __P((void));
108static int primary __P((void));
109static int term __P((void));
110static int exp __P((void));
111static int unary __P((void));
112static int factor __P((void));
113static int constant __P((void));
114static int num __P((void));
115static int geteqrel __P((void));
116static int skipws __P((void));
117static void experr __P((char *));
118
119/*
120 * For longjmp
121 */
122#include <setjmp.h>
123static jmp_buf expjump;
124
125/*
126 * macros:
127 *      ungetch - Put back the last character examined.
128 *      getch   - return the next character from expr string.
129 */
130#define ungetch()       nxtch--
131#define getch()         *nxtch++
132
133int
134expr(expbuf)
135char *expbuf;
136{
137	register int rval;
138
139	nxtch = expbuf;
140	if (setjmp(expjump) != 0)
141		return FALSE;
142
143	rval = query();
144	if (skipws() == EOS)
145		return rval;
146
147	printf("m4: ill-formed expression.\n");
148	return FALSE;
149}
150
151/*
152 * query : lor | lor '?' query ':' query
153 */
154static int
155query()
156{
157	register int bool, true_val, false_val;
158
159	bool = lor();
160	if (skipws() != '?') {
161		ungetch();
162		return bool;
163	}
164
165	true_val = query();
166	if (skipws() != ':')
167		experr("bad query");
168
169	false_val = query();
170	return bool ? true_val : false_val;
171}
172
173/*
174 * lor : land { '||' land }
175 */
176static int
177lor()
178{
179	register int c, vl, vr;
180
181	vl = land();
182	while ((c = skipws()) == '|') {
183		if (getch() != '|')
184			ungetch();
185		vr = land();
186		vl = vl || vr;
187	}
188
189	ungetch();
190	return vl;
191}
192
193/*
194 * land : not { '&&' not }
195 */
196static int
197land()
198{
199	register int c, vl, vr;
200
201	vl = not();
202	while ((c = skipws()) == '&') {
203		if (getch() != '&')
204			ungetch();
205		vr = not();
206		vl = vl && vr;
207	}
208
209	ungetch();
210	return vl;
211}
212
213/*
214 * not : eqrel | '!' not
215 */
216static int
217not()
218{
219	register int val, c;
220
221	if ((c = skipws()) == '!' && getch() != '=') {
222		ungetch();
223		val = not();
224		return !val;
225	}
226
227	if (c == '!')
228		ungetch();
229	ungetch();
230	return eqrel();
231}
232
233/*
234 * eqrel : shift { eqrelop shift }
235 */
236static int
237eqrel()
238{
239	register int vl, vr, eqrel;
240
241	vl = shift();
242	while ((eqrel = geteqrel()) != -1) {
243		vr = shift();
244
245		switch (eqrel) {
246
247		case EQL:
248			vl = (vl == vr);
249			break;
250		case NEQ:
251			vl = (vl != vr);
252			break;
253
254		case LEQ:
255			vl = (vl <= vr);
256			break;
257		case LSS:
258			vl = (vl < vr);
259			break;
260		case GTR:
261			vl = (vl > vr);
262			break;
263		case GEQ:
264			vl = (vl >= vr);
265			break;
266		}
267	}
268	return vl;
269}
270
271/*
272 * shift : primary { shop primary }
273 */
274static int
275shift()
276{
277	register int vl, vr, c;
278
279	vl = primary();
280	while (((c = skipws()) == '<' || c == '>') && getch() == c) {
281		vr = primary();
282
283		if (c == '<')
284			vl <<= vr;
285		else
286			vl >>= vr;
287	}
288
289	if (c == '<' || c == '>')
290		ungetch();
291	ungetch();
292	return vl;
293}
294
295/*
296 * primary : term { addop term }
297 */
298static int
299primary()
300{
301	register int c, vl, vr;
302
303	vl = term();
304	while ((c = skipws()) == '+' || c == '-') {
305		vr = term();
306
307		if (c == '+')
308			vl += vr;
309		else
310			vl -= vr;
311	}
312
313	ungetch();
314	return vl;
315}
316
317/*
318 * <term> := <exp> { <mulop> <exp> }
319 */
320static int
321term()
322{
323	register int c, vl, vr;
324
325	vl = exp();
326	while ((c = skipws()) == '*' || c == '/' || c == '%') {
327		vr = exp();
328
329		switch (c) {
330		case '*':
331			vl *= vr;
332			break;
333		case '/':
334			vl /= vr;
335			break;
336		case '%':
337			vl %= vr;
338			break;
339		}
340	}
341	ungetch();
342	return vl;
343}
344
345/*
346 * <term> := <unary> { <expop> <unary> }
347 */
348static int
349exp()
350{
351	register c, vl, vr, n;
352
353	vl = unary();
354	switch (c = skipws()) {
355
356	case '*':
357		if (getch() != '*') {
358			ungetch();
359			break;
360		}
361
362	case '^':
363		vr = exp();
364		n = 1;
365		while (vr-- > 0)
366			n *= vl;
367		return n;
368	}
369
370	ungetch();
371	return vl;
372}
373
374/*
375 * unary : factor | unop unary
376 */
377static int
378unary()
379{
380	register int val, c;
381
382	if ((c = skipws()) == '+' || c == '-' || c == '~') {
383		val = unary();
384
385		switch (c) {
386		case '+':
387			return val;
388		case '-':
389			return -val;
390		case '~':
391			return ~val;
392		}
393	}
394
395	ungetch();
396	return factor();
397}
398
399/*
400 * factor : constant | '(' query ')'
401 */
402static int
403factor()
404{
405	register int val;
406
407	if (skipws() == '(') {
408		val = query();
409		if (skipws() != ')')
410			experr("bad factor");
411		return val;
412	}
413
414	ungetch();
415	return constant();
416}
417
418/*
419 * constant: num | 'char'
420 * Note: constant() handles multi-byte constants
421 */
422static int
423constant()
424{
425	register int i;
426	register int value;
427	register char c;
428	int v[sizeof(int)];
429
430	if (skipws() != '\'') {
431		ungetch();
432		return num();
433	}
434	for (i = 0; i < sizeof(int); i++) {
435		if ((c = getch()) == '\'') {
436			ungetch();
437			break;
438		}
439		if (c == '\\') {
440			switch (c = getch()) {
441			case '0':
442			case '1':
443			case '2':
444			case '3':
445			case '4':
446			case '5':
447			case '6':
448			case '7':
449				ungetch();
450				c = num();
451				break;
452			case 'n':
453				c = 012;
454				break;
455			case 'r':
456				c = 015;
457				break;
458			case 't':
459				c = 011;
460				break;
461			case 'b':
462				c = 010;
463				break;
464			case 'f':
465				c = 014;
466				break;
467			}
468		}
469		v[i] = c;
470	}
471	if (i == 0 || getch() != '\'')
472		experr("illegal character constant");
473	for (value = 0; --i >= 0;) {
474		value <<= 8;
475		value += v[i];
476	}
477	return value;
478}
479
480/*
481 * num : digit | num digit
482 */
483static int
484num()
485{
486	register int rval, c, base;
487	int ndig;
488
489	base = ((c = skipws()) == '0') ? OCTAL : DECIMAL;
490	rval = 0;
491	ndig = 0;
492	while (c >= '0' && c <= (base == OCTAL ? '7' : '9')) {
493		rval *= base;
494		rval += (c - '0');
495		c = getch();
496		ndig++;
497	}
498	ungetch();
499
500	if (ndig == 0)
501		experr("bad constant");
502
503	return rval;
504
505}
506
507/*
508 * eqrel : '=' | '==' | '!=' | '<' | '>' | '<=' | '>='
509 */
510static int
511geteqrel()
512{
513	register int c1, c2;
514
515	c1 = skipws();
516	c2 = getch();
517
518	switch (c1) {
519
520	case '=':
521		if (c2 != '=')
522			ungetch();
523		return EQL;
524
525	case '!':
526		if (c2 == '=')
527			return NEQ;
528		ungetch();
529		ungetch();
530		return -1;
531
532	case '<':
533		if (c2 == '=')
534			return LEQ;
535		ungetch();
536		return LSS;
537
538	case '>':
539		if (c2 == '=')
540			return GEQ;
541		ungetch();
542		return GTR;
543
544	default:
545		ungetch();
546		ungetch();
547		return -1;
548	}
549}
550
551/*
552 * Skip over any white space and return terminating char.
553 */
554static int
555skipws()
556{
557	register char c;
558
559	while ((c = getch()) <= ' ' && c > EOS)
560		;
561	return c;
562}
563
564/*
565 * resets environment to eval(), prints an error
566 * and forces eval to return FALSE.
567 */
568static void
569experr(msg)
570char *msg;
571{
572	printf("m4: %s in expr.\n", msg);
573	longjmp(expjump, -1);
574}
575