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