1#include <stdlib.h>
2#include <ctype.h>
3#include "pleval.h"
4
5/*
6grammar:
7
8Start = Expr ';'
9Expr = Or | Or '?' Expr ':' Expr
10Or = And | Or '||' And
11And = Eq | And '&&' Eq
12Eq = Rel | Eq '==' Rel | Eq '!=' Rel
13Rel = Add | Rel '<=' Add | Rel '>=' Add | Rel '<' Add | Rel '>' Add
14Add = Mul | Add '+' Mul | Add '-' Mul
15Mul = Prim | Mul '*' Prim | Mul '/' Prim | Mul '%' Prim
16Prim = '(' Expr ')' | '!' Prim | decimal | 'n'
17
18internals:
19
20recursive descent expression evaluator with stack depth limit.
21for binary operators an operator-precedence parser is used.
22eval* functions store the result of the parsed subexpression
23and return a pointer to the next non-space character.
24*/
25
26struct st {
27 unsigned long r;
28 unsigned long n;
29 int op;
30};
31
32static const char *skipspace(const char *s)
33{
34 while (isspace(*s)) s++;
35 return s;
36}
37
38static const char *evalexpr(struct st *st, const char *s, int d);
39
40static 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
67static 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
88static 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
110static 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
134static 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
152unsigned 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}