source: BAORadio/libindi/v1.0.1/tools/compiler.c@ 650

Last change on this file since 650 was 490, checked in by campagne, 15 years ago

import libindi (JEC)
File size: 17.5 KB
Line 
1/* module to compile and execute a c-style arithmetic expression made of INDI
2 * operands. operand names must contain 2 dots and be surrounded by quotes.
3 * The expression is compiled and the names of each operand are stored. The
4 * values of an operand can be set later by name. Evaluation uses the last
5 * known operand value.
6 *
7 * one reason this is so nice and tight is that all opcodes are the same size
8 * (an int) and the tokens the parser returns are directly usable as opcodes.
9 * constants and variables are compiled as an opcode with an offset into the
10 * auxiliary consts and vars arrays.
11 *
12 * this is not reentrant, but new expressions can be compiled as desired.
13 */
14
15#include <stdio.h>
16#include <math.h>
17#include <ctype.h>
18#include <stdlib.h>
19#include <string.h>
20
21static int next_token (void);
22static int chk_funcs (void);
23static void skip_double (void);
24static int compile (int prec);
25static int execute (double *result);
26static int parse_fieldname (char name[], int len);
27
28/* parser tokens and opcodes, as necessary */
29enum {
30 HALT, /* HALT = 0 serves as good initial default */
31
32 /* binary operators (precedences in table, below) */
33 ADD,
34 SUB,
35 MULT,
36 DIV,
37 AND,
38 OR,
39 GT,
40 GE,
41 EQ,
42 NE,
43 LT,
44 LE,
45
46 /* unary ops, precedence all UNI_PREC */
47 NEG,
48 NOT,
49
50 /* symantically operands, ie, constants, variables and all functions */
51 CONST,
52 VAR,
53 ABS,
54 FLOOR,
55 SIN,
56 COS,
57 TAN,
58 ASIN,
59 ACOS,
60 ATAN,
61 PITOK, /* built-in constant, pi */
62 DEGRAD,
63 RADDEG,
64 LOG,
65 LOG10,
66 EXP,
67 SQRT,
68 POW,
69 ATAN2,
70};
71
72/* purely tokens - never get compiled as such */
73#define LPAREN 255
74#define RPAREN 254
75#define COMMA 253
76#define ERR (-1)
77
78/* precedence of each of the binary operators.
79 * in case of a tie, compiler associates left-to-right.
80 * N.B. each entry's index must correspond to its #define!
81 */
82static int precedence[] = {0,5,5,6,6,2,1,4,4,3,3,4,4};
83#define UNI_PREC 7 /* unary ops have highest precedence */
84
85/* execute-time operand stack */
86#define MAX_STACK 32
87static double stack[MAX_STACK], *sp;
88
89/* space for compiled opcodes - the "program".
90 * opcodes go in lower 8 bits.
91 * when an opcode has an operand (as CONST and VAR) it is really an array
92 * index in the remaining upper bits.
93 */
94#define MAX_PROG 32
95static int program[MAX_PROG], *pc;
96#define OP_SHIFT 8
97#define OP_MASK 0xff
98
99/* auxiliary operand info.
100 * the operands (all but lower 8 bits) of CONST and VAR are really indeces
101 * into these arrays. thus, no point in making them any longer than you have
102 * bits more than 8 in your machine's int to index into it, ie, make
103 * MAX_OPX < 1 << ((sizeof(int)-1)*8)
104 */
105#define MAX_OPX 64 /* max number of operands */
106#define MAXFLDLEN 64 /* longest allowed operand name */
107typedef struct {
108 int set; /* 1 when v has been set */
109 char name[MAXFLDLEN]; /* name of operand */
110 double v; /* last known value of this operand */
111} Var;
112static Var vars[MAX_OPX]; /* operands */
113static int nvars; /* number of vars[] in actual use */
114static double consts[MAX_OPX]; /* constants */
115static int nconsts; /* number of consts[] in actual use */
116
117/* these are global just for easy/rapid access */
118static int parens_nest; /* to check that parens end up nested */
119static char *err_msg; /* caller provides storage; we point at it with this */
120static char *cexpr, *lcexpr; /* pointers that move along caller's expression */
121
122/* compile the given c-style expression.
123 * return 0 if ok, else return -1 and a reason message in errbuf.
124 */
125int
126compileExpr (char *exp, char *errbuf)
127{
128 /* init the globals.
129 * also delete any flogs used in the previous program.
130 */
131 cexpr = exp;
132 err_msg = errbuf;
133 pc = program;
134 nvars = nconsts = 0;
135 parens_nest = 0;
136
137 pc = program;
138 if (compile(0) == ERR) {
139 (void) sprintf (err_msg + strlen(err_msg), " near `%.10s'", lcexpr);
140 return (-1);
141 }
142 if (pc == program) {
143 (void) sprintf (err_msg, "Null program");
144 return (-1);
145 }
146 *pc++ = HALT;
147 return (0);
148}
149
150/* execute the expression previously compiled with compileExpr().
151 * return 0 with *vp set to the answer if ok, else return -1 with a reason
152 * why not message in errbuf.
153 */
154int
155evalExpr (double *vp, char *errbuf)
156{
157 err_msg = errbuf;
158 sp = stack + MAX_STACK; /* grows towards lower addresses */
159 pc = program;
160 return (execute(vp));
161}
162
163/* set the value for an operand with the given name to the given value.
164 * return 0 if found else -1.
165 */
166int
167setOperand (char *name, double valu)
168{
169 int i;
170
171 for (i = 0; i < nvars; i++) {
172 if (strcmp (name, vars[i].name) == 0) {
173 vars[i].v = valu;
174 vars[i].set = 1;
175 return(0);
176 }
177 }
178
179 return (-1);
180}
181
182/* return 0 if all operands are set, else -1 */
183int
184allOperandsSet ()
185{
186 int i;
187
188 for (i = 0; i < nvars; i++)
189 if (!vars[i].set)
190 return (-1);
191 return (0);
192}
193
194/* return a malloced array of each operand name.
195 * N.B. caller must free array, and not modify names.
196 */
197int
198getAllOperands (char ***ops)
199{
200 int i;
201
202 *ops = (char **) malloc (nvars * sizeof(char *));
203
204 for (i = 0; i < nvars; i++)
205 (*ops)[i] = vars[i].name;
206
207 return (nvars);
208}
209
210/* return a malloced array of each initialized operand name.
211 * N.B. caller must free array, and not modify the names.
212 */
213int
214getSetOperands (char ***ops)
215{
216 int i, n;
217
218 *ops = (char **) malloc (nvars * sizeof(char *));
219
220 for (n = i = 0; i < nvars; i++)
221 if (vars[i].set)
222 (*ops)[n++] = vars[i].name;
223
224 return (n);
225}
226
227/* return a malloced array of each uninitialized operand name.
228 * N.B. caller must free array, and not modify the names.
229 */
230int
231getUnsetOperands (char ***ops)
232{
233 int i, n;
234
235 *ops = (char **) malloc (nvars * sizeof(char *));
236
237 for (n = i = 0; i < nvars; i++)
238 if (!vars[i].set)
239 (*ops)[n++] = vars[i].name;
240
241 return (n);
242}
243
244/* called when each different field is written.
245 * this is just called by srch_log() to hide the fact from users of srch*
246 * that srch is really using our vars array to store values.
247 * since this gets called for all fields, it's not an error to not find name.
248 * don't stop when see the first one because a term might appear more than once.
249 */
250void
251compiler_log (name, value)
252char *name;
253double value;
254{
255 Var *vp;
256
257 for (vp = vars; vp < &vars[nvars]; vp++)
258 if (vp->name && strcmp (vp->name, name) == 0)
259 vp->v = value;
260}
261
262/* get and return the opcode corresponding to the next token.
263 * leave with lcexpr pointing at the new token, cexpr just after it.
264 * also watch for mismatches parens and proper operator/operand alternation.
265 */
266static int
267next_token ()
268{
269 static char toomv[] = "More than %d variables";
270 static char toomc[] = "More than %d constants";
271 static char badop[] = "Illegal operator";
272 int tok = ERR; /* just something illegal */
273 char c;
274
275 while (isspace(c = *cexpr))
276 cexpr++;
277 lcexpr = cexpr++;
278
279 /* mainly check for a binary operator */
280 switch (c) {
281 case ',': tok = COMMA; break;
282 case '\0': --cexpr; tok = HALT; break; /* keep returning HALT */
283 case '+': tok = ADD; break; /* compiler knows when it's really unary */
284 case '-': tok = SUB; break; /* compiler knows when it's really negate */
285 case '*': tok = MULT; break;
286 case '/': tok = DIV; break;
287 case '(': parens_nest++; tok = LPAREN; break;
288 case ')':
289 if (--parens_nest < 0) {
290 (void) sprintf (err_msg, "Too many right parens");
291 return (ERR);
292 } else
293 tok = RPAREN;
294 break;
295 case '|':
296 if (*cexpr == '|') { cexpr++; tok = OR; }
297 else { (void) sprintf (err_msg, badop); return (ERR); }
298 break;
299 case '&':
300 if (*cexpr == '&') { cexpr++; tok = AND; }
301 else { (void) sprintf (err_msg, badop); return (ERR); }
302 break;
303 case '=':
304 if (*cexpr == '=') { cexpr++; tok = EQ; }
305 else { (void) sprintf (err_msg, badop); return (ERR); }
306 break;
307 case '!':
308 if (*cexpr == '=') { cexpr++; tok = NE; } else { tok = NOT; }
309 break;
310 case '<':
311 if (*cexpr == '=') { cexpr++; tok = LE; }
312 else tok = LT;
313 break;
314 case '>':
315 if (*cexpr == '=') { cexpr++; tok = GE; }
316 else tok = GT;
317 break;
318 }
319
320 if (tok != ERR)
321 return (tok);
322
323 /* not op so check for a constant, variable or function */
324 if (isdigit(c) || c == '.') {
325 /* looks like a constant.
326 * leading +- already handled
327 */
328 if (nconsts > MAX_OPX) {
329 (void) sprintf (err_msg, toomc, MAX_OPX);
330 return (ERR);
331 }
332 consts[nconsts] = atof (lcexpr);
333 tok = CONST | (nconsts++ << OP_SHIFT);
334 skip_double();
335 } else if (isalpha(c)) {
336 /* check list of functions */
337 tok = chk_funcs();
338 if (tok == ERR) {
339 (void) sprintf (err_msg, "Bad function");
340 return (ERR);
341 }
342 } else if (c == '"') {
343 /* a variable */
344 if (nvars > MAX_OPX) {
345 (void) sprintf (err_msg, toomv, MAX_OPX);
346 return (ERR);
347 }
348 if (parse_fieldname (vars[nvars].name, MAXFLDLEN) < 0) {
349 (void) sprintf (err_msg, "Bad field");
350 return (ERR);
351 } else
352 tok = VAR | (nvars++ << OP_SHIFT);
353 }
354
355 if (tok != ERR)
356 return (tok);
357
358 /* what the heck is it? */
359 (void) sprintf (err_msg, "Syntax error");
360 return (ERR);
361}
362
363/* return funtion token, else ERR.
364 * if find one, update cexpr too.
365 */
366static int
367chk_funcs()
368{
369 static struct {
370 char *st_name;
371 int st_tok;
372 } symtab[] = {
373 /* be sure to put short names AFTER longer ones.
374 * otherwise, order does not matter.
375 */
376 {"abs", ABS}, {"floor", FLOOR}, {"acos", ACOS},
377 {"asin", ASIN}, {"atan2", ATAN2}, {"atan", ATAN},
378 {"cos", COS}, {"degrad", DEGRAD}, {"exp", EXP},
379 {"log10", LOG10}, {"log", LOG}, {"pi", PITOK},
380 {"pow", POW}, {"raddeg", RADDEG}, {"sin", SIN},
381 {"sqrt", SQRT}, {"tan", TAN},
382 };
383 int i;
384
385 for (i = 0; i < sizeof(symtab)/sizeof(symtab[0]); i++) {
386 int l = strlen (symtab[i].st_name);
387 if (strncmp (lcexpr, symtab[i].st_name, l) == 0) {
388 cexpr += l-1;
389 return (symtab[i].st_tok);
390 }
391 }
392 return (ERR);
393}
394
395/* move cexpr on past a double.
396 * allow sci notation.
397 * no need to worry about a leading '-' or '+' but allow them after an 'e'.
398 * TODO: this handles all the desired cases, but also admits a bit too much
399 * such as things like 1eee2...3. geeze; to skip a double right you almost
400 * have to go ahead and crack it!
401 */
402static void
403skip_double()
404{
405 int sawe = 0; /* so we can allow '-' or '+' right after an 'e' */
406
407 for (;;) {
408 char c = *cexpr;
409 if (isdigit(c) || c=='.' || (sawe && (c=='-' || c=='+'))) {
410 sawe = 0;
411 cexpr++;
412 } else if (c == 'e') {
413 sawe = 1;
414 cexpr++;
415 } else
416 break;
417 }
418}
419
420/* call this whenever you want to dig out the next (sub)expression.
421 * keep compiling instructions as long as the operators are higher precedence
422 * than prec (or until see HALT, COMMA or RPAREN) then return that
423 * "look-ahead" token.
424 * if error, fill in a message in err_msg[] and return ERR.
425 */
426static int
427compile (prec)
428int prec;
429{
430 int expect_binop = 0; /* set after we have seen any operand.
431 * used by SUB so it can tell if it really
432 * should be taken to be a NEG instead.
433 */
434 int tok = next_token ();
435 int *oldpc;
436
437 for (;;) {
438 int p;
439 if (tok == ERR)
440 return (ERR);
441 if (pc - program >= MAX_PROG) {
442 (void) sprintf (err_msg, "Program is too long");
443 return (ERR);
444 }
445
446 /* check for special things like functions, constants and parens */
447 switch (tok & OP_MASK) {
448 case COMMA: return (tok);
449 case HALT: return (tok);
450 case ADD:
451 if (expect_binop)
452 break; /* procede with binary addition */
453 /* just skip a unary positive(?) */
454 tok = next_token();
455 if (tok == HALT) {
456 (void) sprintf (err_msg, "Term expected after unary +");
457 return (ERR);
458 }
459 continue;
460 case SUB:
461 if (expect_binop)
462 break; /* procede with binary subtract */
463 oldpc = pc;
464 tok = compile (UNI_PREC);
465 if (oldpc == pc) {
466 (void) sprintf (err_msg, "Term expected after unary -");
467 return (ERR);
468 }
469 *pc++ = NEG;
470 expect_binop = 1;
471 continue;
472 case NOT:
473 oldpc = pc;
474 tok = compile (UNI_PREC);
475 if (oldpc == pc) {
476 (void) sprintf (err_msg, "Term expected after unary !");
477 return (ERR);
478 }
479 *pc++ = NOT;
480 expect_binop = 1;
481 continue;
482 /* one-arg functions */
483 case ABS: case FLOOR: case SIN: case COS: case TAN: case ASIN:
484 case ACOS: case ATAN: case DEGRAD: case RADDEG: case LOG:
485 case LOG10: case EXP: case SQRT:
486 /* eat up the function's parenthesized argument */
487 if (next_token() != LPAREN) {
488 (void) sprintf (err_msg, "expecting '(' after function");
489 return (ERR);
490 }
491 oldpc = pc;
492 if (compile (0) != RPAREN || oldpc == pc) {
493 (void) sprintf (err_msg, "1-arg function arglist error");
494 return (ERR);
495 }
496 *pc++ = tok;
497 tok = next_token();
498 expect_binop = 1;
499 continue;
500 /* two-arg functions */
501 case POW: case ATAN2:
502 /* eat up the function's parenthesized arguments */
503 if (next_token() != LPAREN) {
504 (void) sprintf (err_msg, "Saw a built-in function: expecting (");
505 return (ERR);
506 }
507 oldpc = pc;
508 if (compile (0) != COMMA || oldpc == pc) {
509 (void) sprintf (err_msg, "1st of 2-arg function arglist error");
510 return (ERR);
511 }
512 oldpc = pc;
513 if (compile (0) != RPAREN || oldpc == pc) {
514 (void) sprintf (err_msg, "2nd of 2-arg function arglist error");
515 return (ERR);
516 }
517 *pc++ = tok;
518 tok = next_token();
519 expect_binop = 1;
520 continue;
521 /* constants and variables are just like 0-arg functions w/o ()'s */
522 case CONST:
523 case PITOK:
524 case VAR:
525 *pc++ = tok;
526 tok = next_token();
527 expect_binop = 1;
528 continue;
529 case LPAREN:
530 oldpc = pc;
531 if (compile (0) != RPAREN) {
532 (void) sprintf (err_msg, "Unmatched left paren");
533 return (ERR);
534 }
535 if (oldpc == pc) {
536 (void) sprintf (err_msg, "Null expression");
537 return (ERR);
538 }
539 tok = next_token();
540 expect_binop = 1;
541 continue;
542 case RPAREN:
543 return (RPAREN);
544 }
545
546 /* everything else is a binary operator */
547 if (tok < ADD || tok > LE) {
548 printf ("Bug! Bogus token: %d\n", tok);
549 abort();
550 }
551 p = precedence[tok];
552 if (p > prec) {
553 int newtok;
554 oldpc = pc;
555 newtok = compile (p);
556 if (newtok == ERR)
557 return (ERR);
558 if (oldpc == pc) {
559 (void) strcpy (err_msg, "Term or factor expected");
560 return (ERR);
561 }
562 *pc++ = tok;
563 expect_binop = 1;
564 tok = newtok;
565 } else
566 return (tok);
567 }
568}
569
570/* "run" the program[] compiled with compile().
571 * if ok, return 0 and the final result,
572 * else return -1 with a reason why not message in err_msg.
573 */
574static int
575execute(result)
576double *result;
577{
578 int instr;
579
580 do {
581 instr = *pc++;
582 switch (instr & OP_MASK) {
583 /* put these in numberic order so hopefully even the dumbest
584 * compiler will choose to use a jump table, not a cascade of ifs.
585 */
586 case HALT: break; /* outer loop will stop us */
587 case ADD: sp[1] = sp[1] + sp[0]; sp++; break;
588 case SUB: sp[1] = sp[1] - sp[0]; sp++; break;
589 case MULT: sp[1] = sp[1] * sp[0]; sp++; break;
590 case DIV: sp[1] = sp[1] / sp[0]; sp++; break;
591 case AND: sp[1] = sp[1] && sp[0] ? 1 : 0; sp++; break;
592 case OR: sp[1] = sp[1] || sp[0] ? 1 : 0; sp++; break;
593 case GT: sp[1] = sp[1] > sp[0] ? 1 : 0; sp++; break;
594 case GE: sp[1] = sp[1] >= sp[0] ? 1 : 0; sp++; break;
595 case EQ: sp[1] = sp[1] == sp[0] ? 1 : 0; sp++; break;
596 case NE: sp[1] = sp[1] != sp[0] ? 1 : 0; sp++; break;
597 case LT: sp[1] = sp[1] < sp[0] ? 1 : 0; sp++; break;
598 case LE: sp[1] = sp[1] <= sp[0] ? 1 : 0; sp++; break;
599 case NEG: *sp = -*sp; break;
600 case NOT: *sp = (double)(*sp==0); break;
601 case CONST: *--sp = consts[instr >> OP_SHIFT]; break;
602 case VAR: *--sp = vars[instr>>OP_SHIFT].v; break;
603 case PITOK: *--sp = 4.0*atan(1.0); break;
604 case ABS: *sp = fabs (*sp); break;
605 case FLOOR: *sp = floor (*sp); break;
606 case SIN: *sp = sin (*sp); break;
607 case COS: *sp = cos (*sp); break;
608 case TAN: *sp = tan (*sp); break;
609 case ASIN: *sp = asin (*sp); break;
610 case ACOS: *sp = acos (*sp); break;
611 case ATAN: *sp = atan (*sp); break;
612 case DEGRAD:*sp *= atan(1.0)/45.0; break;
613 case RADDEG:*sp *= 45.0/atan(1.0); break;
614 case LOG: *sp = log (*sp); break;
615 case LOG10: *sp = log10 (*sp); break;
616 case EXP: *sp = exp (*sp); break;
617 case SQRT: *sp = sqrt (*sp); break;
618 case POW: sp[1] = pow (sp[1], sp[0]); sp++; break;
619 case ATAN2: sp[1] = atan2 (sp[1], sp[0]); sp++; break;
620 default:
621 (void) sprintf (err_msg, "Bug! bad opcode: 0x%x", instr);
622 return (-1);
623 }
624 if (sp < stack) {
625 (void) sprintf (err_msg, "Runtime stack overflow");
626 return (-1);
627 } else if (sp - stack > MAX_STACK) {
628 (void) sprintf (err_msg, "Bug! runtime stack underflow");
629 return (-1);
630 }
631 } while (instr != HALT);
632
633 /* result should now be on top of stack */
634 if (sp != &stack[MAX_STACK - 1]) {
635 (void) sprintf (err_msg, "Bug! stack has %d items",
636 MAX_STACK - (sp-stack));
637 return (-1);
638 }
639 *result = *sp;
640 return (0);
641}
642
643/* starting with lcexpr pointing at a string expected to be a field name,
644 * ie, at a '"', fill into up to the next '"' into name[], including trailing 0.
645 * if there IS no '"' within len-1 chars, return -1, else 0.
646 * the only sanity check is the string contains two dots.
647 * when return, leave lcexpr alone but move cexpr to just after the second '"'.
648 */
649static int
650parse_fieldname (name, len)
651char name[];
652int len;
653{
654 char c = '\0';
655 int ndots = 0;
656
657 cexpr = lcexpr + 1;
658 while (--len > 0 && (c = *cexpr++) != '"' && c) {
659 *name++ = c;
660 ndots += c == '.';
661 }
662 if (len == 0 || c != '"' || ndots != 2)
663 return (-1);
664 *name = '\0';
665 return (0);
666}
667
668/* For RCS Only -- Do Not Edit */
669static char *rcsid[2] = {(char *)rcsid, "@(#) $RCSfile: compiler.c,v $ $Date: 2005/11/21 21:33:32 $ $Revision: 1.1 $ $Name: $"};
Note: See TracBrowser for help on using the repository browser.