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