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