home *** CD-ROM | disk | FTP | other *** search
/ Collection of Education / collectionofeducationcarat1997.iso / SCIENCE / EPHEM421.ZIP / COMPILER.C < prev    next >
C/C++ Source or Header  |  1990-09-13  |  16KB  |  581 lines
  1. /* module to compile and execute a c-style arithmetic expression.
  2.  * public entry points are compile_expr() and execute_expr().
  3.  *
  4.  * one reason this is so nice and tight is that all opcodes are the same size
  5.  * (an int) and the tokens the parser returns are directly usable as opcodes,
  6.  * for the most part. constants and variables are compiled as an opcode
  7.  * with an offset into the auxiliary opcode tape, opx.
  8.  */
  9.  
  10. #include <math.h>
  11. #ifdef VMS
  12. #include <stdlib.h>
  13. #endif
  14. #include "screen.h"
  15.  
  16. /* parser tokens and opcodes, as necessary */
  17. #define    HALT    0    /* good value for HALT since program is inited to 0 */
  18. /* binary operators (precedences in table, below) */
  19. #define    ADD    1
  20. #define    SUB    2
  21. #define    MULT    3
  22. #define    DIV    4
  23. #define    AND    5
  24. #define    OR    6
  25. #define    GT    7
  26. #define    GE    8
  27. #define    EQ    9
  28. #define    NE    10
  29. #define    LT    11
  30. #define    LE    12
  31. /* unary op, precedence in NEG_PREC #define, below */
  32. #define    NEG    13
  33. /* symantically operands, ie, constants, variables and all functions */
  34. #define    CONST    14    
  35. #define    VAR    15
  36. #define    ABS    16    /* add functions if desired just like this is done */
  37. /* purely tokens - never get compiled as such */
  38. #define    LPAREN    255
  39. #define    RPAREN    254
  40. #define    ERR    (-1)
  41.  
  42. /* precedence of each of the binary operators.
  43.  * in case of a tie, compiler associates left-to-right.
  44.  * N.B. each entry's index must correspond to its #define!
  45.  */
  46. static int precedence[] = {0,5,5,6,6,2,1,4,4,3,3,4,4};
  47. #define    NEG_PREC    7    /* negation is highest */
  48.  
  49. /* execute-time operand stack */
  50. #define    MAX_STACK    16
  51. static double stack[MAX_STACK], *sp;
  52.  
  53. /* space for compiled opcodes - the "program".
  54.  * opcodes go in lower 8 bits.
  55.  * when an opcode has an operand (as CONST and VAR) it is really in opx[] and
  56.  *   the index is in the remaining upper bits.
  57.  */
  58. #define    MAX_PROG 32
  59. static int program[MAX_PROG], *pc;
  60. #define    OP_SHIFT    8
  61. #define    OP_MASK        0xff
  62.  
  63. /* auxiliary operand info.
  64.  * the operands (all but lower 8 bits) of CONST and VAR are really indeces
  65.  * into this array. thus, no point in making this any longer than you have
  66.  * bits more than 8 in your machine's int to index into it, ie, make
  67.  *    MAX_OPX <= 1 << ((sizeof(int)-1)*8)
  68.  * also, the fld's must refer to ones being flog'd, so not point in more
  69.  * of these then that might be used for plotting and srching combined.
  70.  */
  71. #define    MAX_OPX    16
  72. typedef union {
  73.     double opu_f;        /* value when opcode is CONST */
  74.     int opu_fld;        /* rcfpack() of field when opcode is VAR */
  75. } OpX;
  76. static OpX opx[MAX_OPX];
  77. static int opxidx;
  78.  
  79. /* these are global just for easy/rapid access */
  80. static int parens_nest;    /* to check that parens end up nested */
  81. static char *err_msg;    /* caller provides storage; we point at it with this */
  82. static char *cexpr, *lcexpr; /* pointers that move along caller's expression */
  83. static int good_prog;    /* != 0 when program appears to be good */
  84.  
  85. /* compile the given c-style expression.
  86.  * return 0 and set good_prog if ok,
  87.  * else return -1 and a reason message in errbuf.
  88.  */
  89. compile_expr (ex, errbuf)
  90. char *ex;
  91. char *errbuf;
  92. {
  93.     int instr;
  94.  
  95.     /* init the globals.
  96.      * also delete any flogs used in the previous program.
  97.      */
  98.     cexpr = ex;
  99.     err_msg = errbuf;
  100.     pc = program;
  101.     opxidx = 0;
  102.     parens_nest = 0;
  103.     do {
  104.         instr = *pc++;
  105.         if ((instr & OP_MASK) == VAR)
  106.         flog_delete (opx[instr >> OP_SHIFT].opu_fld);
  107.     } while (instr != HALT);
  108.  
  109.     pc = program;
  110.     if (compile(0) == ERR) {
  111.         (void) sprintf (err_msg + strlen(err_msg), " at \"%.10s\"", lcexpr);
  112.         good_prog = 0;
  113.         return (-1);
  114.     }
  115.     *pc++ = HALT;
  116.     good_prog = 1;
  117.     return (0);
  118. }
  119.  
  120. /* execute the expression previously compiled with compile_expr().
  121.  * return 0 with *vp set to the answer if ok, else return -1 with a reason
  122.  * why not message in errbuf.
  123.  */
  124. execute_expr (vp, errbuf)
  125. double *vp;
  126. char *errbuf;
  127. {
  128.     int s;
  129.  
  130.     err_msg = errbuf;
  131.     sp = stack + MAX_STACK;    /* grows towards lower addresses */
  132.     pc = program;
  133.     s = execute(vp);
  134.     if (s < 0)
  135.         good_prog = 0;
  136.     return (s);
  137. }
  138.  
  139. /* this is a way for the outside world to ask whether there is currently a
  140.  * reasonable program compiled and able to execute.
  141.  */
  142. prog_isgood()
  143. {
  144.     return (good_prog);
  145. }
  146.  
  147. /* get and return the opcode corresponding to the next token.
  148.  * leave with lcexpr pointing at the new token, cexpr just after it.
  149.  * also watch for mismatches parens and proper operator/operand alternation.
  150.  */
  151. static
  152. next_token ()
  153. {
  154.     static char toomt[] = "More than %d terms";
  155.     static char badop[] = "Illegal operator";
  156.     int tok = ERR;    /* just something illegal */
  157.     char c;
  158.  
  159.     while ((c = *cexpr) == ' ')
  160.         cexpr++;
  161.     lcexpr = cexpr++;
  162.  
  163.     /* mainly check for a binary operator */
  164.     switch (c) {
  165.     case '\0': --cexpr; tok = HALT; break; /* keep returning HALT */
  166.     case '+': tok = ADD; break; /* compiler knows when it's really unary */
  167.     case '-': tok = SUB; break; /* compiler knows when it's really negate */
  168.     case '*': tok = MULT; break;
  169.     case '/': tok = DIV; break;
  170.     case '(': parens_nest++; tok = LPAREN; break;
  171.     case ')':
  172.         if (--parens_nest < 0) {
  173.             (void) sprintf (err_msg, "Too many right parens");
  174.         return (ERR);
  175.         } else
  176.         tok = RPAREN;
  177.         break;
  178.     case '|':
  179.         if (*cexpr == '|') { cexpr++; tok = OR; }
  180.         else { (void) sprintf (err_msg, badop); return (ERR); }
  181.         break;
  182.     case '&':
  183.         if (*cexpr == '&') { cexpr++; tok = AND; }
  184.         else { (void) sprintf (err_msg, badop); return (ERR); }
  185.         break;
  186.     case '=':
  187.         if (*cexpr == '=') { cexpr++; tok = EQ; }
  188.         else { (void) sprintf (err_msg, badop); return (ERR); }
  189.         break;
  190.     case '!':
  191.         if (*cexpr == '=') { cexpr++; tok = NE; }
  192.         else { (void) sprintf (err_msg, badop); return (ERR); }
  193.         break;
  194.     case '<':
  195.         if (*cexpr == '=') { cexpr++; tok = LE; }
  196.         else tok = LT;
  197.         break;
  198.     case '>':
  199.         if (*cexpr == '=') { cexpr++; tok = GE; }
  200.         else tok = GT;
  201.         break;
  202.     }
  203.  
  204.     if (tok != ERR)
  205.         return (tok);
  206.  
  207.     /* not op so check for a constant, variable or function */
  208.     if (isdigit(c) || c == '.') {
  209.         if (opxidx > MAX_OPX) {
  210.         (void) sprintf (err_msg, toomt, MAX_OPX);
  211.         return (ERR);
  212.         }
  213.         opx[opxidx].opu_f = atof (lcexpr);
  214.         tok = CONST | (opxidx++ << OP_SHIFT);
  215.         skip_double();
  216.     } else if (isalpha(c)) {
  217.         /* check list of functions */
  218.         if (strncmp (lcexpr, "abs", 3) == 0) {
  219.         cexpr += 2;
  220.         tok = ABS;
  221.         } else {
  222.         /* not a function, so assume it's a variable */
  223.         int fld;
  224.         if (opxidx > MAX_OPX) {
  225.             (void) sprintf (err_msg, toomt, MAX_OPX);
  226.             return (ERR);
  227.         }
  228.         fld = parse_fieldname ();
  229.         if (fld < 0) {
  230.             (void) sprintf (err_msg, "Unknown field");
  231.             return (ERR);
  232.         } else {
  233.             if (flog_add (fld) < 0) { /* register with field logger */
  234.             (void) sprintf (err_msg, "Sorry; too many fields");
  235.             return (ERR);
  236.             }
  237.             opx[opxidx].opu_fld = fld;
  238.             tok = VAR | (opxidx++ << OP_SHIFT);
  239.         }
  240.         }
  241.     }
  242.  
  243.     return (tok);
  244. }
  245.  
  246. /* move cexpr on past a double.
  247.  * allow sci notation.
  248.  * no need to worry about a leading '-' or '+' but allow them after an 'e'.
  249.  * TODO: this handles all the desired cases, but also admits a bit too much
  250.  *   such as things like 1eee2...3. geeze; to skip a double right you almost
  251.  *   have to go ahead and crack it!
  252.  */
  253. static
  254. skip_double()
  255. {
  256.     int sawe = 0;    /* so we can allow '-' or '+' right after an 'e' */
  257.  
  258.     while (1) {
  259.         char c = *cexpr;
  260.         if (isdigit(c) || c=='.' || (sawe && (c=='-' || c=='+'))) {
  261.         sawe = 0;
  262.         cexpr++;
  263.         } else if (c == 'e') {
  264.         sawe = 1;
  265.         cexpr++;
  266.         } else
  267.         break;
  268.     }
  269. }
  270.  
  271. /* call this whenever you want to dig out the next (sub)expression.
  272.  * keep compiling instructions as long as the operators are higher precedence
  273.  * than prec, then return that "look-ahead" token that wasn't (higher prec).
  274.  * if error, fill in a message in err_msg[] and return ERR.
  275.  */
  276. static
  277. compile (prec)
  278. int prec;
  279. {
  280.     int expect_binop = 0;    /* set after we have seen any operand.
  281.                  * used by SUB so it can tell if it really 
  282.                  * should be taken to be a NEG instead.
  283.                  */
  284.     int tok = next_token ();
  285.  
  286.