![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to expr.y CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / d / bin / expr|
Return to expr.y CVS log | Up to [MW Coherent from dump] / coherent / d / bin / expr |
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.