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