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