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