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