Home | History | Annotate | Line # | Download | only in m4
expr.c revision 1.6 
      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    :       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 
    100 static char *nxtch;		       /* Parser scan pointer */
    101 
    102 static int query __P((void));
    103 static int lor __P((void));
    104 static int land __P((void));
    105 static int not __P((void));
    106 static int eqrel __P((void));
    107 static int shift __P((void));
    108 static int primary __P((void));
    109 static int term __P((void));
    110 static int exp __P((void));
    111 static int unary __P((void));
    112 static int factor __P((void));
    113 static int constant __P((void));
    114 static int num __P((void));
    115 static int geteqrel __P((void));
    116 static int skipws __P((void));
    117 static void experr __P((char *));
    118 
    119 /*
    120  * For longjmp
    121  */
    122 #include <setjmp.h>
    123 static 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 
    133 int
    134 expr(expbuf)
    135 char *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  */
    154 static int
    155 query()
    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  */
    176 static int
    177 lor()
    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  */
    196 static int
    197 land()
    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  */
    216 static int
    217 not()
    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  */
    236 static int
    237 eqrel()
    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  */
    274 static int
    275 shift()
    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  */
    298 static int
    299 primary()
    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  */
    320 static int
    321 term()
    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  */
    348 static int
    349 exp()
    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  */
    377 static int
    378 unary()
    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  */
    402 static int
    403 factor()
    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  */
    422 static int
    423 constant()
    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  */
    483 static int
    484 num()
    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  */
    510 static int
    511 geteqrel()
    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  */
    554 static int
    555 skipws()
    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  */
    568 static void
    569 experr(msg)
    570 char *msg;
    571 {
    572 	printf("m4: %s in expr.\n", msg);
    573 	longjmp(expjump, -1);
    574 }
    575