1 /* pMARS -- a portable Memory Array Redcode Simulator
2 * Copyright (C) 1993-1996 Albert Ma, Na'ndor Sieben, Stefan Strack and Mintardjo Wangsawidjaja
3 * Copyright (C) 2000 Ilmari Karonen
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
18 */
19
20 /*
21 * eval.c: expression evaluator used by assembler and debugger
22 * $Id: eval.c,v 1.3 2000/12/25 00:49:08 iltzu Exp $
23 */
24
25 #include <ctype.h>
26
27 #include "global.h"
28
29 /*
30 * eval_expr - arithmetic expression evaluator
31 * by Stefan Strack, version 3 (pMARS v0.4.0+)
32 *
33 * usage:
34 *
35 * int eval_expr(char *expr, long *result); returns 0 if expression is ok, -1 if
36 * bad, -2 if attempted division by zero expr must be null-terminated and can
37 * contain whitespace characters (\t \n)
38 *
39 * -recursion-based -supports arbitrary levels of precedence and parentheses
40 * -supports nested unary minus and plus: 3--2 = 3-(-2) = 5
41 * -arithmetic operators: +,-,*,/,%,=
42 * -26 registers named "a" thru "z", assignment operator =
43 * -C-like comparison and logic operators: ==,!=,<,>,<=,>=,&&,||
44 *
45 */
46
47 #define STANDALONE 0
48 #define BIGNUM 20 /* largest number taken */
49
50 /* two-char operators */
51 enum {
52 EQUAL, NEQU, GTE, LTE, AND, OR, IDENT
53 };
54
55 #ifdef DEBUG
56 #define X(c) (c==IDENT ? '#' :\
57 (c==EQUAL ? '=' :\
58 (c==AND ? '&' :\
59 (c==OR ? '|' :\
60 (c)))))
61 #endif
62
63 #define TERMINAL(c) (((c)==')' || !(c)) ? 1 : 0)
64 /* order of precedence (high to low):
65 * / %
66 + -
67 > < == != >= <=
68 &&
69 ||
70 =
71 */
72 #define PRECEDENCE(op) (op=='*' || op=='/' || op=='%' ? 5 :\
73 (op=='+' || op=='-' ? 4 :\
74 (op=='>' || op=='<' || op==EQUAL || op==NEQU\
75 || op==GTE || op==LTE ? 3 :\
76 (op==AND ? 2 : (op==OR ? 1 : 0)))))
77 #define SKIP_SPACE(e) while(isspace(*(e))) ++(e)
78
79 /* function prototypes */
80 #ifdef NEW_STYLE
81 char *eval(int prevPrec, long val, char operator, char *expr, long *result);
82 char *getreg(char *expr, int regId, long *val);
83 char *getval(char *expr, long *val);
84 char *getop(char *expr, char *op);
85 long calc(long x, long y, int op);
86 #else
87 char *eval();
88 char *getreg();
89 char *getval();
90 char *getop();
91 long calc();
92 #endif
93
94 /* global error flag */
95 int evalerr;
96
97 /* registers */
98
99 static long regAr[26];
100
101 /* kludge to implement several precedence levels */
102
103 char saveOper = 0;
104
105 /*--------------------*/
106 long
calc(x,y,op)107 calc(x, y, op)
108 long x;
109 long y;
110 int op;
111 {
112 long z;
113
114 switch (op) {
115 case '+':
116 if (evalerr == OK_EXPR && (x > 0 ?
117 y > 0 && x > LONG_MAX - y :
118 y < 0 && x < LONG_MIN - y ))
119 evalerr = OVERFLOW;
120 z = x + y;
121 break;
122 case '-':
123 if (evalerr == OK_EXPR && (x > 0 ?
124 y < 0 && x > LONG_MAX + y :
125 y > 0 && x < LONG_MIN + y ))
126 evalerr = OVERFLOW;
127 z = x - y;
128 break;
129 case '/':
130 if (y == 0) {
131 evalerr = DIV_ZERO;
132 z = 0;
133 } else
134 z = x / y;
135 break;
136 case '*':
137 if (evalerr == OK_EXPR && x != 0 && y != 0 &&
138 x != -1 && y != -1 && /* LONG_MIN/(-1) causes FP error! */
139 ((x > 0) == (y > 0) ?
140 LONG_MAX / y / x == 0 :
141 LONG_MIN / y / x == 0 ))
142 evalerr = OVERFLOW;
143 z = x * y;
144 break;
145 case '%':
146 if (y == 0) {
147 evalerr = DIV_ZERO;
148 z = 0;
149 } else
150 z = x % y;
151 break;
152 case AND:
153 z = x && y;
154 break;
155 case OR:
156 z = x || y;
157 break;
158 case EQUAL:
159 z = x == y;
160 break;
161 case NEQU:
162 z = x != y;
163 break;
164 case '<':
165 z = x < y;
166 break;
167 case '>':
168 z = x > y;
169 break;
170 case LTE:
171 z = x <= y;
172 break;
173 case GTE:
174 z = x >= y;
175 break;
176 case IDENT: /* the right-identity operator, used for
177 * initial call to eval() */
178 z = y;
179 break;
180 default:
181 z = 0;
182 evalerr = BAD_EXPR;
183 }
184 return z;
185 }
186
187 /*--------------------*/
188 char *
getop(expr,oper)189 getop(expr, oper)
190 char *expr;
191 char *oper;
192 {
193 char ch;
194 switch (ch = *(expr++)) {
195 case '&':
196 if (*(expr++) == '&')
197 *oper = AND;
198 break;
199 case '|':
200 if (*(expr++) == '|')
201 *oper = OR;
202 break;
203 case '=':
204 if (*(expr++) == '=')
205 *oper = EQUAL;
206 break;
207 case '!':
208 if (*(expr++) == '=')
209 *oper = NEQU;
210 break;
211 case '<':
212 if (*expr == '=') {
213 ++expr;
214 *oper = LTE;
215 } else
216 *oper = '<';
217 break;
218 case '>':
219 if (*expr == '=') {
220 ++expr;
221 *oper = GTE;
222 } else
223 *oper = '>';
224 break;
225 default:
226 *oper = ch;
227 break;
228 }
229 return expr;
230 }
231 /*--------------------*/
232 char *
getreg(expr,regId,val)233 getreg(expr, regId, val)
234 char *expr;
235 int regId;
236 long *val;
237 {
238 SKIP_SPACE(expr);
239 if (*expr == '=' && *(expr + 1) != '=') { /* assignment, not equality */
240 expr = eval(-1, 0L, IDENT, expr + 1, val);
241 regAr[regId] = *val;
242 } else
243 *val = regAr[regId];
244 return expr;
245 }
246
247 /*--------------------*/
248 char *
getval(expr,val)249 getval(expr, val)
250 char *expr;
251 long *val;
252 {
253 char buffer[BIGNUM];
254 int regId;
255 int bufptr = 0;
256 long accum;
257
258 SKIP_SPACE(expr);
259 if (*expr == '(') { /* parenthetical expression */
260 expr = eval(-1, 0L, IDENT, expr + 1, val);
261 if (*expr != ')')
262 evalerr = BAD_EXPR;
263 return expr + 1;
264 }
265 if (*expr == '-') { /* unary minus */
266 expr = getval(expr + 1, &accum);
267 *val = accum * -1;
268 return expr;
269 } else if (*expr == '!') { /* logical NOT */
270 expr = getval(expr + 1, &accum);
271 *val = (accum ? 0 : 1);
272 return expr;
273 } else if (*expr == '+') /* unary plus */
274 return getval(expr + 1, val);
275 else if (((regId = (int) toupper(*expr)) >= 'A') && (regId <= 'Z'))
276 return getreg(expr + 1, regId - 'A', val);
277 else
278 while (isdigit(*expr))
279 buffer[bufptr++] = *expr++;
280 if (bufptr == 0)
281 evalerr = BAD_EXPR; /* no digits */
282 buffer[bufptr] = 0;
283 sscanf(buffer, "%ld", val);
284 return expr;
285 }
286
287 /*--------------------*/
288 #ifdef NEW_STYLE
289 char *
eval(int prevPrec,long val1,char oper1,char * expr,long * result)290 eval(int prevPrec, long val1, char oper1, char *expr, long *result)
291 #else
292 char *
293 eval(prevPrec, val1, oper1, expr, result)
294 int prevPrec;
295 char oper1, *expr;
296 long val1, *result;
297 #endif
298 {
299 long result2, val2;
300 char oper2;
301 int prec1, prec2;
302
303
304 expr = getval(expr, &val2);
305 SKIP_SPACE(expr);
306 if (TERMINAL(*expr)) { /* trivial: expr is number or () */
307 *result = calc(val1, val2, oper1);
308 return expr;
309 }
310 expr = getop(expr, &oper2);
311 saveOper = 0;
312
313 if ((prec1 = PRECEDENCE(oper1)) >= (prec2 = PRECEDENCE(oper2))) {
314 if (prec2 >= prevPrec || prec1 <= prevPrec) {
315 expr = eval(prec1, calc(val1, val2, oper1), oper2, expr, result);
316 #if 0
317 if (saveOper && PRECEDENCE(saveOper) >= prevPrec) {
318 expr = eval(prec2, *result, saveOper, expr, result);
319 saveOper = 0;
320 printf("Umpff!\n");
321 }
322 #endif
323 #ifdef DEBUG
324 fprintf(stderr, "%ld = ((%ld %c %ld) %c ..)\n", *result, val1, X(oper1), val2, X(oper2));
325 #endif
326 } else {
327 *result = calc(val1, val2, oper1);
328 saveOper = oper2;
329 #ifdef DEBUG
330 fprintf(stderr, "%ld = (%ld %c %ld)\n", *result, val1, X(oper1), val2);
331 #endif
332 }
333 } else {
334 expr = eval(prec1, val2, oper2, expr, &result2);
335 *result = calc(val1, result2, oper1);
336
337 if (saveOper && PRECEDENCE(saveOper) >= prevPrec) {
338 expr = eval(prec2, *result, saveOper, expr, result);
339 saveOper = 0;
340 #ifdef DEBUG
341 fprintf(stderr, "%ld = .. ? (%ld %c (%ld %c ..))\n", *result,
342 val1, X(oper1), val2, X(oper2));
343 #endif
344 }
345 #ifdef DEBUG
346 else
347 fprintf(stderr, "%ld = (%ld %c (%ld %c ..))\n", *result, val1, X(oper1), val2, X(oper2));
348 #endif
349 }
350
351 return expr;
352 }
353
354 /*--------------------*/
355 void
reset_regs()356 reset_regs()
357 {
358 register int idx;
359
360 for (idx = 0; idx < 26; ++idx)
361 regAr[idx] = 0L;
362 }
363
364 /*--------------------*/
365
366 void
set_reg(regChr,val)367 set_reg(regChr, val)
368 char regChr;
369 long val;
370 {
371 regAr[regChr - 'A'] = val;
372 }
373
374 /*--------------------*/
375 int
eval_expr(expr,result)376 eval_expr(expr, result) /* wrapper for eval() */
377 char *expr;
378 long *result;
379 {
380 evalerr = OK_EXPR;
381 if (*eval(-1, 0L, IDENT, expr, result) != 0)
382 evalerr = BAD_EXPR; /* still chars left */
383 return (evalerr);
384 }
385
386 #if STANDALONE
387 /*--------------------*/
388 void
main()389 main()
390 { /* test evaluator */
391 char expr[80];
392 long result;
393 int err;
394
395 printf("Enter infix expression: ");
396 gets(expr);
397
398 if ((err = eval_expr(expr, &result)) >= OK_EXPR)
399 printf("Evaluation result: %ld\n", result);
400 else if (err == DIV_ZERO)
401 printf("Division by zero in %s\n", expr);
402 else if (err == BAD_EXPR)
403 printf("Bad expression %s\n", expr);
404 }
405 #endif
406