pleval.c raw
1 #include <stdlib.h>
2 #include <ctype.h>
3 #include "pleval.h"
4
5 /*
6 grammar:
7
8 Start = Expr ';'
9 Expr = Or | Or '?' Expr ':' Expr
10 Or = And | Or '||' And
11 And = Eq | And '&&' Eq
12 Eq = Rel | Eq '==' Rel | Eq '!=' Rel
13 Rel = Add | Rel '<=' Add | Rel '>=' Add | Rel '<' Add | Rel '>' Add
14 Add = Mul | Add '+' Mul | Add '-' Mul
15 Mul = Prim | Mul '*' Prim | Mul '/' Prim | Mul '%' Prim
16 Prim = '(' Expr ')' | '!' Prim | decimal | 'n'
17
18 internals:
19
20 recursive descent expression evaluator with stack depth limit.
21 for binary operators an operator-precedence parser is used.
22 eval* functions store the result of the parsed subexpression
23 and return a pointer to the next non-space character.
24 */
25
26 struct st {
27 unsigned long r;
28 unsigned long n;
29 int op;
30 };
31
32 static const char *skipspace(const char *s)
33 {
34 while (isspace(*s)) s++;
35 return s;
36 }
37
38 static const char *evalexpr(struct st *st, const char *s, int d);
39
40 static const char *evalprim(struct st *st, const char *s, int d)
41 {
42 char *e;
43 if (--d < 0) return "";
44 s = skipspace(s);
45 if (isdigit(*s)) {
46 st->r = strtoul(s, &e, 10);
47 if (e == s || st->r == -1) return "";
48 return skipspace(e);
49 }
50 if (*s == 'n') {
51 st->r = st->n;
52 return skipspace(s+1);
53 }
54 if (*s == '(') {
55 s = evalexpr(st, s+1, d);
56 if (*s != ')') return "";
57 return skipspace(s+1);
58 }
59 if (*s == '!') {
60 s = evalprim(st, s+1, d);
61 st->r = !st->r;
62 return s;
63 }
64 return "";
65 }
66
67 static int binop(struct st *st, int op, unsigned long left)
68 {
69 unsigned long a = left, b = st->r;
70 switch (op) {
71 case 0: st->r = a||b; return 0;
72 case 1: st->r = a&&b; return 0;
73 case 2: st->r = a==b; return 0;
74 case 3: st->r = a!=b; return 0;
75 case 4: st->r = a>=b; return 0;
76 case 5: st->r = a<=b; return 0;
77 case 6: st->r = a>b; return 0;
78 case 7: st->r = a<b; return 0;
79 case 8: st->r = a+b; return 0;
80 case 9: st->r = a-b; return 0;
81 case 10: st->r = a*b; return 0;
82 case 11: if (b) {st->r = a%b; return 0;} return 1;
83 case 12: if (b) {st->r = a/b; return 0;} return 1;
84 }
85 return 1;
86 }
87
88 static const char *parseop(struct st *st, const char *s)
89 {
90 static const char opch[11] = "|&=!><+-*%/";
91 static const char opch2[6] = "|&====";
92 int i;
93 for (i=0; i<11; i++)
94 if (*s == opch[i]) {
95 /* note: >,< are accepted with or without = */
96 if (i<6 && s[1] == opch2[i]) {
97 st->op = i;
98 return s+2;
99 }
100 if (i>=4) {
101 st->op = i+2;
102 return s+1;
103 }
104 break;
105 }
106 st->op = 13;
107 return s;
108 }
109
110 static const char *evalbinop(struct st *st, const char *s, int minprec, int d)
111 {
112 static const char prec[14] = {1,2,3,3,4,4,4,4,5,5,6,6,6,0};
113 unsigned long left;
114 int op;
115 d--;
116 s = evalprim(st, s, d);
117 s = parseop(st, s);
118 for (;;) {
119 /*
120 st->r (left hand side value) and st->op are now set,
121 get the right hand side or back out if op has low prec,
122 if op was missing then prec[op]==0
123 */
124 op = st->op;
125 if (prec[op] <= minprec)
126 return s;
127 left = st->r;
128 s = evalbinop(st, s, prec[op], d);
129 if (binop(st, op, left))
130 return "";
131 }
132 }
133
134 static const char *evalexpr(struct st *st, const char *s, int d)
135 {
136 unsigned long a, b;
137 if (--d < 0)
138 return "";
139 s = evalbinop(st, s, 0, d);
140 if (*s != '?')
141 return s;
142 a = st->r;
143 s = evalexpr(st, s+1, d);
144 if (*s != ':')
145 return "";
146 b = st->r;
147 s = evalexpr(st, s+1, d);
148 st->r = a ? b : st->r;
149 return s;
150 }
151
152 unsigned long __pleval(const char *s, unsigned long n)
153 {
154 struct st st;
155 st.n = n;
156 s = evalexpr(&st, s, 100);
157 return *s == ';' ? st.r : -1;
158 }
159