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