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