expr.y revision 90109
1%{ 2/* Written by Pace Willisson (pace@blitz.com) 3 * and placed in the public domain. 4 * 5 * Largely rewritten by J.T. Conklin (jtc@wimsey.com) 6 * 7 * $FreeBSD: head/bin/expr/expr.y 90109 2002-02-02 06:36:49Z imp $ 8 */ 9 10#include <sys/types.h> 11#include <stdio.h> 12#include <stdlib.h> 13#include <string.h> 14#include <locale.h> 15#include <ctype.h> 16#include <err.h> 17#include <errno.h> 18#include <regex.h> 19#include <limits.h> 20 21enum valtype { 22 integer, numeric_string, string 23} ; 24 25struct val { 26 enum valtype type; 27 union { 28 char *s; 29 quad_t i; 30 } u; 31} ; 32 33struct val *result; 34 35int chk_div(quad_t, quad_t); 36int chk_minus(quad_t, quad_t, quad_t); 37int chk_plus(quad_t, quad_t, quad_t); 38int chk_times(quad_t, quad_t, quad_t); 39void free_value(struct val *); 40int is_zero_or_null(struct val *); 41int isstring(struct val *); 42struct val *make_integer(quad_t); 43struct val *make_str(const char *); 44struct val *op_and(struct val *, struct val *); 45struct val *op_colon(struct val *, struct val *); 46struct val *op_div(struct val *, struct val *); 47struct val *op_eq(struct val *, struct val *); 48struct val *op_ge(struct val *, struct val *); 49struct val *op_gt(struct val *, struct val *); 50struct val *op_le(struct val *, struct val *); 51struct val *op_lt(struct val *, struct val *); 52struct val *op_minus(struct val *, struct val *); 53struct val *op_ne(struct val *, struct val *); 54struct val *op_or(struct val *, struct val *); 55struct val *op_plus(struct val *, struct val *); 56struct val *op_rem(struct val *, struct val *); 57struct val *op_times(struct val *, struct val *); 58quad_t to_integer(struct val *); 59void to_string(struct val *); 60int yyerror(const char *); 61int yylex(void); 62int yyparse(void); 63 64char **av; 65%} 66 67%union 68{ 69 struct val *val; 70} 71 72%left <val> '|' 73%left <val> '&' 74%left <val> '=' '>' '<' GE LE NE 75%left <val> '+' '-' 76%left <val> '*' '/' '%' 77%left <val> ':' 78 79%token <val> TOKEN 80%type <val> start expr 81 82%% 83 84start: expr { result = $$; } 85 86expr: TOKEN 87 | '(' expr ')' { $$ = $2; } 88 | expr '|' expr { $$ = op_or ($1, $3); } 89 | expr '&' expr { $$ = op_and ($1, $3); } 90 | expr '=' expr { $$ = op_eq ($1, $3); } 91 | expr '>' expr { $$ = op_gt ($1, $3); } 92 | expr '<' expr { $$ = op_lt ($1, $3); } 93 | expr GE expr { $$ = op_ge ($1, $3); } 94 | expr LE expr { $$ = op_le ($1, $3); } 95 | expr NE expr { $$ = op_ne ($1, $3); } 96 | expr '+' expr { $$ = op_plus ($1, $3); } 97 | expr '-' expr { $$ = op_minus ($1, $3); } 98 | expr '*' expr { $$ = op_times ($1, $3); } 99 | expr '/' expr { $$ = op_div ($1, $3); } 100 | expr '%' expr { $$ = op_rem ($1, $3); } 101 | expr ':' expr { $$ = op_colon ($1, $3); } 102 ; 103 104 105%% 106 107struct val * 108make_integer(quad_t i) 109{ 110 struct val *vp; 111 112 vp = (struct val *) malloc (sizeof (*vp)); 113 if (vp == NULL) { 114 errx (2, "malloc() failed"); 115 } 116 117 vp->type = integer; 118 vp->u.i = i; 119 return vp; 120} 121 122struct val * 123make_str(const char *s) 124{ 125 struct val *vp; 126 size_t i; 127 int isint; 128 129 vp = (struct val *) malloc (sizeof (*vp)); 130 if (vp == NULL || ((vp->u.s = strdup (s)) == NULL)) { 131 errx (2, "malloc() failed"); 132 } 133 134 for(i = 1, isint = isdigit(s[0]) || s[0] == '-'; 135 isint && i < strlen(s); 136 i++) 137 { 138 if(!isdigit(s[i])) 139 isint = 0; 140 } 141 142 if (isint) 143 vp->type = numeric_string; 144 else 145 vp->type = string; 146 147 return vp; 148} 149 150 151void 152free_value(struct val *vp) 153{ 154 if (vp->type == string || vp->type == numeric_string) 155 free (vp->u.s); 156} 157 158 159quad_t 160to_integer(struct val *vp) 161{ 162 quad_t i; 163 164 if (vp->type == integer) 165 return 1; 166 167 if (vp->type == string) 168 return 0; 169 170 /* vp->type == numeric_string, make it numeric */ 171 errno = 0; 172 i = strtoq(vp->u.s, (char**)NULL, 10); 173 if (errno != 0) { 174 errx (2, "overflow"); 175 } 176 free (vp->u.s); 177 vp->u.i = i; 178 vp->type = integer; 179 return 1; 180} 181 182void 183to_string(struct val *vp) 184{ 185 char *tmp; 186 187 if (vp->type == string || vp->type == numeric_string) 188 return; 189 190 tmp = malloc ((size_t)25); 191 if (tmp == NULL) { 192 errx (2, "malloc() failed"); 193 } 194 195 sprintf (tmp, "%lld", (long long)vp->u.i); 196 vp->type = string; 197 vp->u.s = tmp; 198} 199 200 201int 202isstring(struct val *vp) 203{ 204 /* only TRUE if this string is not a valid integer */ 205 return (vp->type == string); 206} 207 208 209int 210yylex(void) 211{ 212 char *p; 213 214 if (*av == NULL) 215 return (0); 216 217 p = *av++; 218 219 if (strlen (p) == 1) { 220 if (strchr ("|&=<>+-*/%:()", *p)) 221 return (*p); 222 } else if (strlen (p) == 2 && p[1] == '=') { 223 switch (*p) { 224 case '>': return (GE); 225 case '<': return (LE); 226 case '!': return (NE); 227 } 228 } 229 230 yylval.val = make_str (p); 231 return (TOKEN); 232} 233 234int 235is_zero_or_null(struct val *vp) 236{ 237 if (vp->type == integer) { 238 return (vp->u.i == 0); 239 } else { 240 return (*vp->u.s == 0 || (to_integer (vp) && vp->u.i == 0)); 241 } 242 /* NOTREACHED */ 243} 244 245int 246main(int argc __unused, char *argv[]) 247{ 248 setlocale (LC_ALL, ""); 249 250 av = argv + 1; 251 252 yyparse (); 253 254 if (result->type == integer) 255 printf ("%lld\n", (long long)result->u.i); 256 else 257 printf ("%s\n", result->u.s); 258 259 return (is_zero_or_null (result)); 260} 261 262int 263yyerror(const char *s __unused) 264{ 265 errx (2, "syntax error"); 266} 267 268 269struct val * 270op_or(struct val *a, struct val *b) 271{ 272 if (is_zero_or_null (a)) { 273 free_value (a); 274 return (b); 275 } else { 276 free_value (b); 277 return (a); 278 } 279} 280 281struct val * 282op_and(struct val *a, struct val *b) 283{ 284 if (is_zero_or_null (a) || is_zero_or_null (b)) { 285 free_value (a); 286 free_value (b); 287 return (make_integer ((quad_t)0)); 288 } else { 289 free_value (b); 290 return (a); 291 } 292} 293 294struct val * 295op_eq(struct val *a, struct val *b) 296{ 297 struct val *r; 298 299 if (isstring (a) || isstring (b)) { 300 to_string (a); 301 to_string (b); 302 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) == 0)); 303 } else { 304 (void)to_integer(a); 305 (void)to_integer(b); 306 r = make_integer ((quad_t)(a->u.i == b->u.i)); 307 } 308 309 free_value (a); 310 free_value (b); 311 return r; 312} 313 314struct val * 315op_gt(struct val *a, struct val *b) 316{ 317 struct val *r; 318 319 if (isstring (a) || isstring (b)) { 320 to_string (a); 321 to_string (b); 322 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) > 0)); 323 } else { 324 (void)to_integer(a); 325 (void)to_integer(b); 326 r = make_integer ((quad_t)(a->u.i > b->u.i)); 327 } 328 329 free_value (a); 330 free_value (b); 331 return r; 332} 333 334struct val * 335op_lt(struct val *a, struct val *b) 336{ 337 struct val *r; 338 339 if (isstring (a) || isstring (b)) { 340 to_string (a); 341 to_string (b); 342 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) < 0)); 343 } else { 344 (void)to_integer(a); 345 (void)to_integer(b); 346 r = make_integer ((quad_t)(a->u.i < b->u.i)); 347 } 348 349 free_value (a); 350 free_value (b); 351 return r; 352} 353 354struct val * 355op_ge(struct val *a, struct val *b) 356{ 357 struct val *r; 358 359 if (isstring (a) || isstring (b)) { 360 to_string (a); 361 to_string (b); 362 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) >= 0)); 363 } else { 364 (void)to_integer(a); 365 (void)to_integer(b); 366 r = make_integer ((quad_t)(a->u.i >= b->u.i)); 367 } 368 369 free_value (a); 370 free_value (b); 371 return r; 372} 373 374struct val * 375op_le(struct val *a, struct val *b) 376{ 377 struct val *r; 378 379 if (isstring (a) || isstring (b)) { 380 to_string (a); 381 to_string (b); 382 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) <= 0)); 383 } else { 384 (void)to_integer(a); 385 (void)to_integer(b); 386 r = make_integer ((quad_t)(a->u.i <= b->u.i)); 387 } 388 389 free_value (a); 390 free_value (b); 391 return r; 392} 393 394struct val * 395op_ne(struct val *a, struct val *b) 396{ 397 struct val *r; 398 399 if (isstring (a) || isstring (b)) { 400 to_string (a); 401 to_string (b); 402 r = make_integer ((quad_t)(strcoll (a->u.s, b->u.s) != 0)); 403 } else { 404 (void)to_integer(a); 405 (void)to_integer(b); 406 r = make_integer ((quad_t)(a->u.i != b->u.i)); 407 } 408 409 free_value (a); 410 free_value (b); 411 return r; 412} 413 414int 415chk_plus(quad_t a, quad_t b, quad_t r) 416{ 417 /* sum of two positive numbers must be positive */ 418 if (a > 0 && b > 0 && r <= 0) 419 return 1; 420 /* sum of two negative numbers must be negative */ 421 if (a < 0 && b < 0 && r >= 0) 422 return 1; 423 /* all other cases are OK */ 424 return 0; 425} 426 427struct val * 428op_plus(struct val *a, struct val *b) 429{ 430 struct val *r; 431 432 if (!to_integer (a) || !to_integer (b)) { 433 errx (2, "non-numeric argument"); 434 } 435 436 r = make_integer (/*(quad_t)*/(a->u.i + b->u.i)); 437 if (chk_plus (a->u.i, b->u.i, r->u.i)) { 438 errx (2, "overflow"); 439 } 440 free_value (a); 441 free_value (b); 442 return r; 443} 444 445int 446chk_minus(quad_t a, quad_t b, quad_t r) 447{ 448 /* special case subtraction of QUAD_MIN */ 449 if (b == QUAD_MIN) { 450 if (a >= 0) 451 return 1; 452 else 453 return 0; 454 } 455 /* this is allowed for b != QUAD_MIN */ 456 return chk_plus (a, -b, r); 457} 458 459struct val * 460op_minus(struct val *a, struct val *b) 461{ 462 struct val *r; 463 464 if (!to_integer (a) || !to_integer (b)) { 465 errx (2, "non-numeric argument"); 466 } 467 468 r = make_integer (/*(quad_t)*/(a->u.i - b->u.i)); 469 if (chk_minus (a->u.i, b->u.i, r->u.i)) { 470 errx (2, "overflow"); 471 } 472 free_value (a); 473 free_value (b); 474 return r; 475} 476 477int 478chk_times(quad_t a, quad_t b, quad_t r) 479{ 480 /* special case: first operand is 0, no overflow possible */ 481 if (a == 0) 482 return 0; 483 /* cerify that result of division matches second operand */ 484 if (r / a != b) 485 return 1; 486 return 0; 487} 488 489struct val * 490op_times(struct val *a, struct val *b) 491{ 492 struct val *r; 493 494 if (!to_integer (a) || !to_integer (b)) { 495 errx (2, "non-numeric argument"); 496 } 497 498 r = make_integer (/*(quad_t)*/(a->u.i * b->u.i)); 499 if (chk_times (a->u.i, b->u.i, r->u.i)) { 500 errx (2, "overflow"); 501 } 502 free_value (a); 503 free_value (b); 504 return (r); 505} 506 507int 508chk_div(quad_t a, quad_t b) 509{ 510 /* div by zero has been taken care of before */ 511 /* only QUAD_MIN / -1 causes overflow */ 512 if (a == QUAD_MIN && b == -1) 513 return 1; 514 /* everything else is OK */ 515 return 0; 516} 517 518struct val * 519op_div(struct val *a, struct val *b) 520{ 521 struct val *r; 522 523 if (!to_integer (a) || !to_integer (b)) { 524 errx (2, "non-numeric argument"); 525 } 526 527 if (b->u.i == 0) { 528 errx (2, "division by zero"); 529 } 530 531 r = make_integer (/*(quad_t)*/(a->u.i / b->u.i)); 532 if (chk_div (a->u.i, b->u.i)) { 533 errx (2, "overflow"); 534 } 535 free_value (a); 536 free_value (b); 537 return r; 538} 539 540struct val * 541op_rem(struct val *a, struct val *b) 542{ 543 struct val *r; 544 545 if (!to_integer (a) || !to_integer (b)) { 546 errx (2, "non-numeric argument"); 547 } 548 549 if (b->u.i == 0) { 550 errx (2, "division by zero"); 551 } 552 553 r = make_integer (/*(quad_t)*/(a->u.i % b->u.i)); 554 /* chk_rem necessary ??? */ 555 free_value (a); 556 free_value (b); 557 return r; 558} 559 560struct val * 561op_colon(struct val *a, struct val *b) 562{ 563 regex_t rp; 564 regmatch_t rm[2]; 565 char errbuf[256]; 566 int eval; 567 struct val *v; 568 569 /* coerce to both arguments to strings */ 570 to_string(a); 571 to_string(b); 572 573 /* compile regular expression */ 574 if ((eval = regcomp (&rp, b->u.s, 0)) != 0) { 575 regerror (eval, &rp, errbuf, sizeof(errbuf)); 576 errx (2, "%s", errbuf); 577 } 578 579 /* compare string against pattern */ 580 /* remember that patterns are anchored to the beginning of the line */ 581 if (regexec(&rp, a->u.s, (size_t)2, rm, 0) == 0 && rm[0].rm_so == 0) { 582 if (rm[1].rm_so >= 0) { 583 *(a->u.s + rm[1].rm_eo) = '\0'; 584 v = make_str (a->u.s + rm[1].rm_so); 585 586 } else { 587 v = make_integer ((quad_t)(rm[0].rm_eo - rm[0].rm_so)); 588 } 589 } else { 590 if (rp.re_nsub == 0) { 591 v = make_integer ((quad_t)0); 592 } else { 593 v = make_str (""); 594 } 595 } 596 597 /* free arguments and pattern buffer */ 598 free_value (a); 599 free_value (b); 600 regfree (&rp); 601 602 return v; 603} 604