Home | History | Annotate | Line # | Download | only in m4
expr.c revision 1.5 
      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
     38 static 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 
    101 static char *nxtch;		       /* Parser scan pointer */
    102 
    103 static int query __P((void));
    104 static int lor __P((void));
    105 static int land __P((void));
    106 static int bor __P((void));
    107 static int bxor __P((void));
    108 static int band __P((void));
    109 static int eql __P((void));
    110 static int relat __P((void));
    111 static int shift __P((void));
    112 static int primary __P((void));
    113 static int term __P((void));
    114 static int unary __P((void));
    115 static int factor __P((void));
    116 static int constant __P((void));
    117 static int num __P((void));
    118 static int geteql __P((void));
    119 static int getrel __P((void));
    120 static int skipws __P((void));
    121 static void experr __P((char *));
    122 
    123 /*
    124  * For longjmp
    125  */
    126 #include <setjmp.h>
    127 static 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 
    137 int
    138 expr(expbuf)
    139 char *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  */
    158 static int
    159 query()
    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  */
    180 static int
    181 lor()
    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  */
    200 static int
    201 land()
    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  */
    220 static int
    221 bor()
    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  */
    241 static int
    242 bxor()
    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  */
    259 static int
    260 band()
    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  */
    280 static int
    281 eql()
    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  */
    305 static int
    306 relat()
    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  */
    336 static int
    337 shift()
    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  */
    360 static int
    361 primary()
    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  */
    381 static int
    382 term()
    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  */
    409 static int
    410 unary()
    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  */
    434 static int
    435 factor()
    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  */
    454 static int
    455 constant()
    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  */
    515 static int
    516 num()
    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  */
    542 static int
    543 geteql()
    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  */
    574 static int
    575 getrel()
    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  */
    606 static int
    607 skipws()
    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  */
    620 static void
    621 experr(msg)
    622 char *msg;
    623 {
    624 	printf("m4: %s in expr.\n", msg);
    625 	longjmp(expjump, -1);
    626 }
    627