| 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 |