|
|
1.1 ! root 1: /* ! 2: * cmd/expr.y ! 3: * yacc grammar for expr. ! 4: * Designed so no stdio is called, ! 5: * which makes the final object code about 1/3 smaller. ! 6: * To make, say ! 7: * yacc expr.y; cc -O -o expr y.tab.c; ! 8: */ ! 9: ! 10: %{ ! 11: ! 12: #include <ctype.h> ! 13: #include <stddef.h> ! 14: #include <stdlib.h> ! 15: #include <limits.h> ! 16: ! 17: #define LONGLEN 12 /* max length of NUL-terminated ASCII long */ ! 18: #define CODELEN 512 /* initial length of code buffer */ ! 19: #define CODEINC 128 /* code buffer length increment */ ! 20: ! 21: #define EOF (-1) ! 22: #define TRUE (0 == 0) ! 23: #define FALSE (0 != 0) ! 24: #define true(e) (*(e) == '\0' || (isnum(e) && atol(e) == 0) ? FALSE : TRUE) ! 25: ! 26: int exstat; /* exit status returned by main() */ ! 27: char *result; /* final expr printed by main */ ! 28: char s0[] = "0"; /* `0' integer - `false' expr */ ! 29: char s1[] = "1"; /* `1' integer - `true' expr */ ! 30: ! 31: char *regexp(), ! 32: *arithop(), ! 33: *relop(), ! 34: *ltoa(); ! 35: ! 36: ! 37: /* ! 38: * The following names are used by the regular expression operator. ! 39: */ ! 40: #define BRSIZE 10 /* Length of brace list */ ! 41: typedef struct { ! 42: char *b_bp; /* Ptr to start of string matched */ ! 43: char *b_ep; /* Ptr to end of string matched */ ! 44: } BRACE; ! 45: ! 46: #define CSNUL 000 /* End of expression */ ! 47: #define CSSOL 001 /* Match start of line */ ! 48: #define CSEOL 002 /* End of line */ ! 49: #define CSOPR 003 /* \( */ ! 50: #define CSCPR 004 /* \) */ ! 51: #define CSBRN 005 /* Match nth brace */ ! 52: #define CSDOT 006 /* Any character */ ! 53: #define CMDOT 007 /* Stream of any characters */ ! 54: #define CSCHR 010 /* Match given character */ ! 55: #define CMCHR 011 /* Match stream of given characters */ ! 56: #define CSCCL 014 /* Character class */ ! 57: #define CMCCL 015 /* Stream of character class */ ! 58: #define CSNCL 016 /* Not character class */ ! 59: #define CMNCL 017 /* Stream of not char class */ ! 60: ! 61: #define getx(c) *e++ ! 62: #define ungetx(c) --e ! 63: ! 64: BRACE brlist[BRSIZE]; /* brace list */ ! 65: int brcount; /* # of braces in reg_expr */ ! 66: char *codebuf; /* Ptr to a compiled regular expr */ ! 67: int cbsiz = CODELEN; /* Initial size of codebuf */ ! 68: ! 69: char *match(); ! 70: char *overflow(); ! 71: ! 72: %} ! 73: ! 74: ! 75: ! 76: ! 77: %union { ! 78: char *str; ! 79: } ! 80: ! 81: %token <str> STR ! 82: ! 83: %type <str> expr ! 84: ! 85: %left '|' ! 86: %left '&' ! 87: %left '<' '>' LE GE EQ NEQ /* relop tokens */ ! 88: %left '+' '-' /* arithop tokens */ ! 89: %left '*' '/' '%' /* arithop tokens */ ! 90: %left ':' /* regexp token */ ! 91: %right UMINUS '!' LEN /* uop tokens */ ! 92: ! 93: ! 94: ! 95: ! 96: %% ! 97: ! 98: ! 99: ! 100: ! 101: start: ! 102: expr { result = $1; exstat = true(result) ? 0 : 1; } ! 103: ; ! 104: ! 105: expr: ! 106: '(' expr ')' { $$ = $2; } ! 107: ! 108: | LEN expr { $$ = ltoa((long)strlen($2)); } ! 109: | '!' expr { $$ = true($2) ? s0 : s1; } ! 110: | '-' expr %prec UMINUS ! 111: { if (isnum($2)) ! 112: $$ = ltoa(-atol($2)); ! 113: else { ! 114: --avx; ! 115: yyerror(); ! 116: } ! 117: } ! 118: ! 119: | expr ':' expr { $$ = regexp($1, $3); } ! 120: ! 121: | expr '*' expr { $$ = arithop('*', $1, $3); } ! 122: | expr '/' expr { $$ = arithop('/', $1, $3); } ! 123: | expr '%' expr { $$ = arithop('%', $1, $3); } ! 124: | expr '+' expr { $$ = arithop('+', $1, $3); } ! 125: | expr '-' expr { $$ = arithop('-', $1, $3); } ! 126: ! 127: | expr '<' expr { $$ = relop('<', $1, $3); } ! 128: | expr '>' expr { $$ = relop('>', $1, $3); } ! 129: | expr LE expr { $$ = relop(LE, $1, $3); } ! 130: | expr GE expr { $$ = relop(GE, $1, $3); } ! 131: | expr EQ expr { $$ = relop(EQ, $1, $3); } ! 132: | expr NEQ expr { $$ = relop(NEQ, $1, $3); } ! 133: ! 134: | expr '&' expr { $$ = true($3) ? $1 : s0; } ! 135: | expr '|' expr { $$ = true($1) ? $1 : $3; } ! 136: ! 137: | '{' expr ',' expr '}' { $$ = true($2) ? $4 : s0; } ! 138: | '{' expr ',' expr ',' expr '}' { $$ = true($2) ? $4 : $6; } ! 139: ! 140: | STR { $$ = $1; } ! 141: | error { yyerror(); } ! 142: ; ! 143: ! 144: ! 145: ! 146: ! 147: %% ! 148: ! 149: ! 150: ! 151: ! 152: char **av; /* Global version of argv[] in main() */ ! 153: int avx; /* Index into av[] */ ! 154: ! 155: main(argc, argv) ! 156: int argc; ! 157: char **argv; ! 158: { ! 159: if (argc == 1) ! 160: return 2; ! 161: av = argv; ! 162: yyparse(); ! 163: output(result, 1); ! 164: output("\n", 1); ! 165: return exstat; ! 166: } ! 167: ! 168: ! 169: char * ! 170: arithop(op, e1, e2) ! 171: register int op; ! 172: register char *e1, *e2; ! 173: { ! 174: register long v1, v2; ! 175: ! 176: if (!isnum(e1)) { ! 177: avx -= 3; ! 178: yyerror(); ! 179: } ! 180: if (!isnum(e2)) { ! 181: --avx; ! 182: yyerror(); ! 183: } ! 184: ! 185: v1 = atol(e1); ! 186: v2 = atol(e2); ! 187: switch (op) { ! 188: case '+': ! 189: v1 += v2; ! 190: break; ! 191: case '-': ! 192: v1 -= v2; ! 193: break; ! 194: case '*': ! 195: v1 *= v2; ! 196: break; ! 197: case '/': ! 198: if (v2 == 0) { ! 199: divzero (); ! 200: v1 = LONG_MAX; ! 201: } else ! 202: v1 /= v2; ! 203: break; ! 204: case '%': ! 205: if (v2 == 0) { ! 206: divzero (); ! 207: v1 = 0; ! 208: } else ! 209: v1 %= v2; ! 210: break; ! 211: } ! 212: return ltoa(v1); ! 213: } ! 214: ! 215: char * ! 216: relop(op, e1, e2) ! 217: register int op; ! 218: register char *e1, *e2; ! 219: { ! 220: register int cmp; ! 221: register long v1, v2; ! 222: ! 223: if (!isnum(e1) || !isnum(e2)) ! 224: cmp = strcmp(e1, e2); ! 225: else { ! 226: v1 = atol(e1); ! 227: v2 = atol(e2); ! 228: cmp = (v1 > v2) ? 1 : (v1 == v2) ? 0 : -1; ! 229: } ! 230: switch (op) { ! 231: case '<': ! 232: return (cmp < 0) ? s1 : s0; ! 233: case '>': ! 234: return (cmp > 0) ? s1 : s0; ! 235: case LE: ! 236: return (cmp <= 0) ? s1 : s0; ! 237: case GE: ! 238: return (cmp >= 0) ? s1 : s0; ! 239: case EQ: ! 240: return (cmp == 0) ? s1 : s0; ! 241: case NEQ: ! 242: return (cmp != 0) ? s1 : s0; ! 243: } ! 244: } ! 245: ! 246: ! 247: char * ! 248: regexp(e1, e2) ! 249: char *e1, *e2; ! 250: { ! 251: register char *a = e1; ! 252: register char *b; ! 253: register BRACE *brp; ! 254: ! 255: codebuf = malloc(CODELEN); ! 256: compile(e2); ! 257: if (brcount > 0) /* brcount is now the number of braces in e2 */ ! 258: brlist[brcount].b_bp = brlist[brcount].b_ep = NULL; ! 259: #if 1 ! 260: /* Posix P1003.2 4.22.7.1: pattern search is anchored to beginning. */ ! 261: b = match(a, codebuf); ! 262: #else ! 263: /* This code searches for unanchored match. */ ! 264: if (codebuf[0] == CSSOL) ! 265: b = match(a, codebuf + 1); ! 266: else ! 267: for ( ; *a != '\0'; ++a) ! 268: if ((b = match(a, codebuf)) != NULL) ! 269: break; ! 270: #endif ! 271: if (b == NULL) ! 272: #if 1 ! 273: /* If \(\) used, string-valued return */ ! 274: return brcount == 0 ? "0" : ""; ! 275: #else ! 276: return "0"; ! 277: #endif ! 278: if (brcount == 0) ! 279: return ltoa((long)(b - a)); ! 280: ! 281: /* Remaining case is extraction of fields */ ! 282: for (a = e1, brp = brlist; (b = brp->b_bp) != NULL; ++brp) ! 283: while (b < brp->b_ep) ! 284: *a++ = *b++; ! 285: *a = '\0'; ! 286: free (codebuf); ! 287: return e1; ! 288: } ! 289: ! 290: ! 291: isnum(e) ! 292: register char *e; ! 293: { ! 294: register int c; ! 295: ! 296: if ((c = * e ++) == '-') /* || c == '+' Removed for POSIX */ ! 297: c = * e ++; ! 298: do ! 299: if (! isdigit (c)) ! 300: return FALSE; ! 301: while ((c = * e ++) != 0); ! 302: return TRUE; ! 303: } ! 304: ! 305: /* ! 306: * Convert long to ascii. Return pointer to the necessary malloced storage. ! 307: */ ! 308: char * ! 309: ltoa(n) ! 310: register long n; ! 311: { ! 312: char buf[LONGLEN]; ! 313: register char *bp = buf; ! 314: register char *ep; ! 315: register char *e; ! 316: ! 317: e = ep = malloc(LONGLEN); ! 318: if (n < 0) { ! 319: *ep++ = '-'; ! 320: n = -n; ! 321: } ! 322: do { ! 323: *bp++ = (n % 10) + '0'; ! 324: n /= 10; ! 325: } while (n > 0); ! 326: while (bp > buf) ! 327: *ep++ = *--bp; ! 328: *ep = '\0'; ! 329: return e; ! 330: } ! 331: ! 332: ! 333: /* ! 334: * Compile the regular expression e into codebuf. ! 335: * Invoke regerror() on a regular expression syntax error. ! 336: */ ! 337: compile(e) ! 338: register char *e; ! 339: { ! 340: register int c; ! 341: register char *cp, *lcp; ! 342: int blevel, n, notflag, bstack[BRSIZE + 1]; ! 343: ! 344: brcount = 0; ! 345: blevel = 0; ! 346: cp = &codebuf[0]; ! 347: if ((c = getx(c)) == '^') { ! 348: *cp++ = CSSOL; ! 349: c = getx(c); ! 350: } ! 351: while (c != '\0') { ! 352: if (cp > &codebuf[cbsiz-4]) ! 353: cp = overflow(cp); ! 354: switch (c) { ! 355: case '*': ! 356: regerror(); ! 357: case '.': ! 358: if ((c = getx(c)) != '*') { ! 359: *cp++ = CSDOT; ! 360: continue; ! 361: } ! 362: *cp++ = CMDOT; ! 363: c = getx(c); ! 364: continue; ! 365: case '$': ! 366: if ((c = getx(c)) != '\0') { ! 367: ungetx(c); ! 368: c = '$'; ! 369: goto character; ! 370: } ! 371: *cp++ = CSEOL; ! 372: continue; ! 373: case '[': ! 374: /* ! 375: * lcp[0] will contain C<S|M><C|N>CL. lcp[1] will be ! 376: * the number of chars in the class. These are followed ! 377: * by the members of the class singly enumerated. ! 378: * ']' is valid only at the start of the member list. ! 379: * '-' is valid only at the end of the member list. ! 380: */ ! 381: lcp = cp; ! 382: if ((c = getx(c)) == '^') ! 383: notflag = TRUE; ! 384: else { ! 385: notflag = FALSE; ! 386: ungetx(c); ! 387: } ! 388: cp += 2; ! 389: if ((c = getx(c)) == ']') ! 390: *cp++ = c; ! 391: else ! 392: ungetx(c); ! 393: while ((c = getx(c)) != ']') { ! 394: if (c == '\0') ! 395: regerror(); ! 396: if (c!='-' || cp==lcp+2) { ! 397: if (cp >= &codebuf[cbsiz-4]) ! 398: cp = overflow(cp); ! 399: *cp++ = c; ! 400: continue; ! 401: } ! 402: ! 403: /* c = '-' now. Lookahead at the next char */ ! 404: if ((c = getx(c)) == '\0') ! 405: regerror(); ! 406: if (c == ']') { ! 407: *cp++ = '-'; ! 408: ungetx(c); ! 409: continue; ! 410: } ! 411: if ((n=cp[-1]) > c) ! 412: regerror(); ! 413: while (++n <= c) { ! 414: if (cp >= &codebuf[cbsiz-4]) ! 415: cp = overflow(cp); ! 416: *cp++ = n; ! 417: } ! 418: } ! 419: if ((c = getx(c)) == '*') { ! 420: lcp[0] = (notflag) ? CMNCL : CMCCL; ! 421: c = getx(c); ! 422: } ! 423: else ! 424: lcp[0] = (notflag) ? CSNCL : CSCCL; ! 425: if ((n=cp-(lcp+2)) > 255) ! 426: regerror(); ! 427: *++lcp = n; ! 428: continue; ! 429: case '\\': ! 430: switch (c = getx(c)) { ! 431: case '\0': ! 432: regerror(); ! 433: case '(': ! 434: *cp++ = CSOPR; ! 435: *cp++ = bstack[blevel++] = brcount++; ! 436: c = getx(c); ! 437: continue; ! 438: case ')': ! 439: if (blevel == 0) ! 440: regerror(); ! 441: *cp++ = CSCPR; ! 442: *cp++ = bstack[--blevel]; ! 443: c = getx(c); ! 444: continue; ! 445: default: ! 446: if (isascii(c) && isdigit(c)) { ! 447: *cp++ = CSBRN; ! 448: *cp++ = c-'0' - 1; ! 449: c = getx(c); ! 450: continue; ! 451: } ! 452: } ! 453: default: ! 454: character: ! 455: *cp++ = CSCHR; ! 456: *cp++ = c; ! 457: if ((c = getx(c)) == '*') { ! 458: cp[-2] = CMCHR; ! 459: c = getx(c); ! 460: } ! 461: } ! 462: } ! 463: *cp++ = CSNUL; ! 464: return; ! 465: } ! 466: ! 467: /* ! 468: * Given a pointer to a compiled expression `cp' and a pointer to a line `lp', ! 469: * return a ptr to the char following the last char of the match ! 470: * if successful, NULL otherwise. ! 471: */ ! 472: char * ! 473: match(lp, cp) ! 474: register char *lp, *cp; ! 475: { ! 476: register int n; ! 477: char *llp, *lcp; ! 478: ! 479: for (;;) { ! 480: switch (*cp++) { ! 481: case CSNUL: ! 482: return lp; ! 483: case CSEOL: ! 484: if (*lp) ! 485: return NULL; ! 486: return lp; ! 487: case CSOPR: ! 488: brlist[*cp++].b_bp = lp; ! 489: continue; ! 490: case CSCPR: ! 491: brlist[*cp++].b_ep = lp; ! 492: continue; ! 493: case CSBRN: ! 494: n = *cp++; ! 495: lcp = cp; ! 496: cp = brlist[n].b_bp; ! 497: n = brlist[n].b_ep - cp; ! 498: if (n > strlen(lp)) ! 499: return NULL; ! 500: while (n-- > 0) ! 501: if (*lp++ != *cp++) ! 502: return NULL; ! 503: cp = lcp; ! 504: continue; ! 505: case CSDOT: ! 506: if (*lp++ == '\0') ! 507: return NULL; ! 508: continue; ! 509: case CMDOT: ! 510: llp = lp; ! 511: while (*lp) ! 512: lp++; ! 513: goto star; ! 514: case CSCHR: ! 515: if (*cp++ != *lp++) ! 516: return NULL; ! 517: continue; ! 518: case CMCHR: ! 519: llp = lp; ! 520: while (*cp == *lp) ! 521: lp++; ! 522: cp++; ! 523: goto star; ! 524: case CSCCL: ! 525: n = *cp++; ! 526: while (*cp++ != *lp) ! 527: if (--n == 0) ! 528: return NULL; ! 529: lp++; ! 530: cp += n-1; ! 531: continue; ! 532: case CMCCL: ! 533: llp = lp; ! 534: lcp = cp; ! 535: while (*lp) { ! 536: cp = lcp; ! 537: n = *cp++; ! 538: while (*cp++ != *lp) ! 539: if (--n == 0) ! 540: goto star; ! 541: lp++; ! 542: } ! 543: cp = lcp + *lcp + 1; ! 544: goto star; ! 545: case CSNCL: ! 546: if (*lp == '\0') ! 547: return NULL; ! 548: n = *cp++; ! 549: while (n--) ! 550: if (*cp++ == *lp) ! 551: return NULL; ! 552: lp++; ! 553: continue; ! 554: case CMNCL: ! 555: llp = lp; ! 556: lcp = cp; ! 557: while (*lp) { ! 558: cp = lcp; ! 559: n = *cp++; ! 560: while (n--) { ! 561: if (*cp++ == *lp) { ! 562: cp = lcp + *lcp + 1; ! 563: goto star; ! 564: } ! 565: } ! 566: lp++; ! 567: } ! 568: cp = lcp + *lcp + 1; ! 569: star: ! 570: do { ! 571: if (lcp=match(lp, cp)) ! 572: return lcp; ! 573: } while (--lp >= llp); ! 574: return NULL; ! 575: } ! 576: } ! 577: } ! 578: ! 579: /* ! 580: * overflow enlarges codebuf by CODEINC bytes. The argument is a pointer ! 581: * to a position in codebuf - the function returns a pointer with the same ! 582: * relative position in the new buffer. ! 583: */ ! 584: char * ! 585: overflow(pc) ! 586: register char *pc; ! 587: { ! 588: register int posn = pc - codebuf; ! 589: ! 590: if ((codebuf = realloc(codebuf, cbsiz += CODEINC)) == NULL) ! 591: regerror(); ! 592: return codebuf + posn; ! 593: } ! 594: ! 595: /* ! 596: * An output function to avoid having to include stdio. ! 597: */ ! 598: output(s, fildes) ! 599: register char *s; ! 600: int fildes; ! 601: { ! 602: register int len; ! 603: ! 604: len = strlen(s); ! 605: if ((write(fildes, s, len)) != len) ! 606: exit(3); ! 607: } ! 608: ! 609: ! 610: yylex() ! 611: { ! 612: register int c; ! 613: ! 614: if ((yylval.str = av[++avx]) == NULL) ! 615: return EOF; ! 616: if (av[avx][1] == '\0') ! 617: switch (c = av[avx][0]) { ! 618: case '{': ! 619: case '}': ! 620: case ',': ! 621: case '|': ! 622: case '&': ! 623: case '<': ! 624: case '>': ! 625: case '+': ! 626: case '-': ! 627: case '*': ! 628: case '/': ! 629: case '%': ! 630: case ':': ! 631: case '!': ! 632: case '(': ! 633: case ')': ! 634: return c; ! 635: default: ! 636: return STR; ! 637: } ! 638: if (av[avx][1] == '=' && av[avx][2] == '\0') ! 639: switch (c = av[avx][0]) { ! 640: case '<': ! 641: return LE; ! 642: case '>': ! 643: return GE; ! 644: case '=': ! 645: return EQ; ! 646: case '!': ! 647: return NEQ; ! 648: default: ! 649: return STR; ! 650: } ! 651: return (strcmp(yylval.str, "len") == 0) ? LEN : STR; ! 652: } ! 653: ! 654: /* ! 655: * The common code between yyerror() and regerror() (in regexp.c) is split ! 656: * off into errexit(). ! 657: */ ! 658: yyerror() ! 659: { ! 660: output("expr: ", 2); ! 661: errexit(); ! 662: } ! 663: regerror() ! 664: { ! 665: output("expr: regular expression ", 2); ! 666: --avx; ! 667: errexit(); ! 668: } ! 669: void dieat () { ! 670: output(ltoa((long) avx), 2); ! 671: output("\n", 2); ! 672: exit(2); ! 673: } ! 674: divzero() { ! 675: output ("Attempt to divide by zero at argument # ", 2); ! 676: -- avx; ! 677: dieat (); ! 678: } ! 679: errexit() ! 680: { ! 681: output("syntax error at argument # ", 2); ! 682: dieat (); ! 683: } ! 684: ! 685: /* end of cmd/expr.y */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.