159 lines
3.3 KiB
C
159 lines
3.3 KiB
C
#include <stdlib.h>
|
|
#include <ctype.h>
|
|
#include "pleval.h"
|
|
|
|
/*
|
|
grammar:
|
|
|
|
Start = Expr ';'
|
|
Expr = Or | Or '?' Expr ':' Expr
|
|
Or = And | Or '||' And
|
|
And = Eq | And '&&' Eq
|
|
Eq = Rel | Eq '==' Rel | Eq '!=' Rel
|
|
Rel = Add | Rel '<=' Add | Rel '>=' Add | Rel '<' Add | Rel '>' Add
|
|
Add = Mul | Add '+' Mul | Add '-' Mul
|
|
Mul = Prim | Mul '*' Prim | Mul '/' Prim | Mul '%' Prim
|
|
Prim = '(' Expr ')' | '!' Prim | decimal | 'n'
|
|
|
|
internals:
|
|
|
|
recursive descent expression evaluator with stack depth limit.
|
|
for binary operators an operator-precedence parser is used.
|
|
eval* functions store the result of the parsed subexpression
|
|
and return a pointer to the next non-space character.
|
|
*/
|
|
|
|
struct st {
|
|
unsigned long r;
|
|
unsigned long n;
|
|
int op;
|
|
};
|
|
|
|
static const char *skipspace(const char *s)
|
|
{
|
|
while (isspace(*s)) s++;
|
|
return s;
|
|
}
|
|
|
|
static const char *evalexpr(struct st *st, const char *s, int d);
|
|
|
|
static const char *evalprim(struct st *st, const char *s, int d)
|
|
{
|
|
char *e;
|
|
if (--d < 0) return "";
|
|
s = skipspace(s);
|
|
if (isdigit(*s)) {
|
|
st->r = strtoul(s, &e, 10);
|
|
if (e == s || st->r == -1) return "";
|
|
return skipspace(e);
|
|
}
|
|
if (*s == 'n') {
|
|
st->r = st->n;
|
|
return skipspace(s+1);
|
|
}
|
|
if (*s == '(') {
|
|
s = evalexpr(st, s+1, d);
|
|
if (*s != ')') return "";
|
|
return skipspace(s+1);
|
|
}
|
|
if (*s == '!') {
|
|
s = evalprim(st, s+1, d);
|
|
st->r = !st->r;
|
|
return s;
|
|
}
|
|
return "";
|
|
}
|
|
|
|
static int binop(struct st *st, int op, unsigned long left)
|
|
{
|
|
unsigned long a = left, b = st->r;
|
|
switch (op) {
|
|
case 0: st->r = a||b; return 0;
|
|
case 1: st->r = a&&b; return 0;
|
|
case 2: st->r = a==b; return 0;
|
|
case 3: st->r = a!=b; return 0;
|
|
case 4: st->r = a>=b; return 0;
|
|
case 5: st->r = a<=b; return 0;
|
|
case 6: st->r = a>b; return 0;
|
|
case 7: st->r = a<b; return 0;
|
|
case 8: st->r = a+b; return 0;
|
|
case 9: st->r = a-b; return 0;
|
|
case 10: st->r = a*b; return 0;
|
|
case 11: if (b) {st->r = a%b; return 0;} return 1;
|
|
case 12: if (b) {st->r = a/b; return 0;} return 1;
|
|
}
|
|
return 1;
|
|
}
|
|
|
|
static const char *parseop(struct st *st, const char *s)
|
|
{
|
|
static const char opch[11] = "|&=!><+-*%/";
|
|
static const char opch2[6] = "|&====";
|
|
int i;
|
|
for (i=0; i<11; i++)
|
|
if (*s == opch[i]) {
|
|
/* note: >,< are accepted with or without = */
|
|
if (i<6 && s[1] == opch2[i]) {
|
|
st->op = i;
|
|
return s+2;
|
|
}
|
|
if (i>=4) {
|
|
st->op = i+2;
|
|
return s+1;
|
|
}
|
|
break;
|
|
}
|
|
st->op = 13;
|
|
return s;
|
|
}
|
|
|
|
static const char *evalbinop(struct st *st, const char *s, int minprec, int d)
|
|
{
|
|
static const char prec[14] = {1,2,3,3,4,4,4,4,5,5,6,6,6,0};
|
|
unsigned long left;
|
|
int op;
|
|
d--;
|
|
s = evalprim(st, s, d);
|
|
s = parseop(st, s);
|
|
for (;;) {
|
|
/*
|
|
st->r (left hand side value) and st->op are now set,
|
|
get the right hand side or back out if op has low prec,
|
|
if op was missing then prec[op]==0
|
|
*/
|
|
op = st->op;
|
|
if (prec[op] <= minprec)
|
|
return s;
|
|
left = st->r;
|
|
s = evalbinop(st, s, prec[op], d);
|
|
if (binop(st, op, left))
|
|
return "";
|
|
}
|
|
}
|
|
|
|
static const char *evalexpr(struct st *st, const char *s, int d)
|
|
{
|
|
unsigned long a, b;
|
|
if (--d < 0)
|
|
return "";
|
|
s = evalbinop(st, s, 0, d);
|
|
if (*s != '?')
|
|
return s;
|
|
a = st->r;
|
|
s = evalexpr(st, s+1, d);
|
|
if (*s != ':')
|
|
return "";
|
|
b = st->r;
|
|
s = evalexpr(st, s+1, d);
|
|
st->r = a ? b : st->r;
|
|
return s;
|
|
}
|
|
|
|
unsigned long __pleval(const char *s, unsigned long n)
|
|
{
|
|
struct st st;
|
|
st.n = n;
|
|
s = evalexpr(&st, s, 100);
|
|
return *s == ';' ? st.r : -1;
|
|
}
|