home *** CD-ROM | disk | FTP | other *** search
/ Stars of Shareware: Raytrace & Morphing / SOS-RAYTRACE.ISO / programm / source / radsrc22 / src / rt / calexpr.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-11-10  |  13.2 KB  |  768 lines
  1. /* Copyright (c) 1992 Regents of the University of California */
  2.  
  3. #ifndef lint
  4. static char SCCSid[] = "@(#)calexpr.c 2.10 11/10/92 LBL";
  5. #endif
  6.  
  7. /*
  8.  *  Compute data values using expression parser
  9.  *
  10.  *  7/1/85  Greg Ward
  11.  *
  12.  *  11/11/85  Made channel input conditional with (INCHAN) compiles.
  13.  *
  14.  *  4/2/86  Added conditional compiles for function definitions (FUNCTION).
  15.  *
  16.  *  1/29/87  Made variables conditional (VARIABLE)
  17.  *
  18.  *  5/19/88  Added constant subexpression elimination (RCONST)
  19.  */
  20.  
  21. #include  <stdio.h>
  22.  
  23. #include  <ctype.h>
  24.  
  25. #include  <errno.h>
  26.  
  27. #include  <math.h>
  28.  
  29. #include  "calcomp.h"
  30.  
  31. #define     MAXLINE    256        /* maximum line length */
  32.  
  33. #define     newnode()    (EPNODE *)ecalloc(1, sizeof(EPNODE))
  34.  
  35. #define     isdecimal(c)    (isdigit(c) || (c) == '.')
  36.  
  37. #ifndef atof
  38. extern double  atof();
  39. #endif
  40. extern char  *fgets(), *savestr();
  41. extern char  *emalloc(), *ecalloc();
  42. extern EPNODE  *curfunc;
  43. extern double  efunc(), evariable();
  44. static double  euminus(), echannel(), eargument(), enumber();
  45. static double  eadd(), esubtr(), emult(), edivi(), epow();
  46. static double  ebotch();
  47.  
  48. int  nextc;                /* lookahead character */
  49.  
  50. double    (*eoper[])() = {        /* expression operations */
  51.     ebotch,
  52. #ifdef    VARIABLE
  53.     evariable,
  54. #else
  55.     ebotch,
  56. #endif
  57.     enumber,
  58.     euminus,
  59. #ifdef    INCHAN
  60.     echannel,
  61. #else
  62.     ebotch,
  63. #endif
  64. #ifdef    FUNCTION
  65.     efunc,
  66.     eargument,
  67. #else
  68.     ebotch,
  69.     ebotch,
  70. #endif
  71.     ebotch,
  72.     ebotch,
  73.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  74.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  75.     emult,
  76.     eadd,
  77.     0,
  78.     esubtr,
  79.     0,
  80.     edivi,
  81.     0,0,0,0,0,0,0,0,0,0,
  82.     ebotch,
  83.     0,0,
  84.     ebotch,
  85.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  86.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  87.     epow,
  88. };
  89.  
  90. static FILE  *infp;            /* input file pointer */
  91. static char  *linbuf;            /* line buffer */
  92. static char  *infile;            /* input file name */
  93. static int  lineno;            /* input line number */
  94. static int  linepos;            /* position in buffer */
  95.  
  96.  
  97. EPNODE *
  98. eparse(expr)            /* parse an expression string */
  99. char  *expr;
  100. {
  101.     EPNODE  *ep;
  102.  
  103.     initstr(expr, NULL, 0);
  104. #if  defined(VARIABLE) && defined(FUNCTION)
  105.     curfunc = NULL;
  106. #endif
  107.     ep = getE1();
  108.     if (nextc != EOF)
  109.     syntax("unexpected character");
  110.     return(ep);
  111. }
  112.  
  113.  
  114. double
  115. eval(expr)            /* evaluate an expression string */
  116. char  *expr;
  117. {
  118.     register EPNODE  *ep;
  119.     double  rval;
  120.  
  121.     ep = eparse(expr);
  122.     rval = evalue(ep);
  123.     epfree(ep);
  124.     return(rval);
  125. }
  126.  
  127.  
  128. epfree(epar)            /* free a parse tree */
  129. register EPNODE     *epar;
  130. {
  131.     register EPNODE  *ep, *epn;
  132.  
  133.     switch (epar->type) {
  134.  
  135. #if  defined(VARIABLE) || defined(FUNCTION)
  136.     case VAR:
  137.         varfree(epar->v.ln);
  138.         break;
  139.         
  140.     case SYM:
  141.         freestr(epar->v.name);
  142.         break;
  143. #endif
  144.  
  145.     case NUM:
  146.     case CHAN:
  147.     case ARG:
  148.     case TICK:
  149.         break;
  150.  
  151.     default:
  152.         for (ep = epar->v.kid; ep != NULL; ep = epn) {
  153.         epn = ep->sibling;
  154.         epfree(ep);
  155.         }
  156.         break;
  157.  
  158.     }
  159.  
  160.     efree((char *)epar);
  161. }
  162.  
  163.                 /* the following used to be a switch */
  164. #ifdef    FUNCTION
  165. static double
  166. eargument(ep)
  167. EPNODE    *ep;
  168. {
  169.     return(argument(ep->v.chan));
  170. }
  171. #endif
  172.  
  173. static double
  174. enumber(ep)
  175. EPNODE    *ep;
  176. {
  177.     return(ep->v.num);
  178. }
  179.  
  180. static double
  181. euminus(ep)
  182. EPNODE    *ep;
  183. {
  184.     register EPNODE  *ep1 = ep->v.kid;
  185.  
  186.     return(-evalue(ep1));
  187. }
  188.  
  189. #ifdef    INCHAN
  190. static double
  191. echannel(ep)
  192. EPNODE    *ep;
  193. {
  194.     return(chanvalue(ep->v.chan));
  195. }
  196. #endif
  197.  
  198. static double
  199. eadd(ep)
  200. EPNODE    *ep;
  201. {
  202.     register EPNODE  *ep1 = ep->v.kid;
  203.  
  204.     return(evalue(ep1) + evalue(ep1->sibling));
  205. }
  206.  
  207. static double
  208. esubtr(ep)
  209. EPNODE    *ep;
  210. {
  211.     register EPNODE  *ep1 = ep->v.kid;
  212.  
  213.     return(evalue(ep1) - evalue(ep1->sibling));
  214. }
  215.  
  216. static double
  217. emult(ep)
  218. EPNODE    *ep;
  219. {
  220.     register EPNODE  *ep1 = ep->v.kid;
  221.  
  222.     return(evalue(ep1) * evalue(ep1->sibling));
  223. }
  224.  
  225. static double
  226. edivi(ep)
  227. EPNODE    *ep;
  228. {
  229.     register EPNODE  *ep1 = ep->v.kid;
  230.     double  d;
  231.  
  232.     d = evalue(ep1->sibling);
  233.     if (d == 0.0) {
  234.     wputs("Division by zero\n");
  235.     errno = ERANGE;
  236.     return(0.0);
  237.     }
  238.     return(evalue(ep1) / d);
  239. }
  240.  
  241. static double
  242. epow(ep)
  243. EPNODE    *ep;
  244. {
  245.     register EPNODE  *ep1 = ep->v.kid;
  246.     double  d;
  247.     int     lasterrno;
  248.  
  249.     lasterrno = errno;
  250.     errno = 0;
  251.     d = pow(evalue(ep1), evalue(ep1->sibling));
  252. #ifdef    IEEE
  253.     if (!finite(d))
  254.     errno = EDOM;
  255. #endif
  256.     if (errno) {
  257.     wputs("Illegal power\n");
  258.     return(0.0);
  259.     }
  260.     errno = lasterrno;
  261.     return(d);
  262. }
  263.  
  264. static double
  265. ebotch(ep)
  266. EPNODE    *ep;
  267. {
  268.     eputs("Bad expression!\n");
  269.     quit(1);
  270. }
  271.  
  272.  
  273. EPNODE *
  274. ekid(ep, n)            /* return pointer to a node's nth kid */
  275. register EPNODE     *ep;
  276. register int  n;
  277. {
  278.  
  279.     for (ep = ep->v.kid; ep != NULL; ep = ep->sibling)
  280.     if (--n < 0)
  281.         break;
  282.  
  283.     return(ep);
  284. }
  285.  
  286.  
  287. int
  288. nekids(ep)            /* return # of kids for node ep */
  289. register EPNODE     *ep;
  290. {
  291.     register int  n = 0;
  292.  
  293.     for (ep = ep->v.kid; ep != NULL; ep = ep->sibling)
  294.     n++;
  295.  
  296.     return(n);
  297. }
  298.  
  299.  
  300. initfile(fp, fn, ln)        /* prepare input file */
  301. FILE  *fp;
  302. char  *fn;
  303. int  ln;
  304. {
  305.     static char     inpbuf[MAXLINE];
  306.  
  307.     infp = fp;
  308.     linbuf = inpbuf;
  309.     infile = fn;
  310.     lineno = ln;
  311.     linepos = 0;
  312.     inpbuf[0] = '\0';
  313.     scan();
  314. }
  315.  
  316.  
  317. initstr(s, fn, ln)        /* prepare input string */
  318. char  *s;
  319. char  *fn;
  320. int  ln;
  321. {
  322.     infp = NULL;
  323.     infile = fn;
  324.     lineno = ln;
  325.     linbuf = s;
  326.     linepos = 0;
  327.     scan();
  328. }
  329.  
  330.  
  331. getscanpos(fnp, lnp, spp, fpp)    /* return current scan position */
  332. char  **fnp;
  333. int  *lnp;
  334. char  **spp;
  335. FILE  **fpp;
  336. {
  337.     if (fnp != NULL) *fnp = infile;
  338.     if (lnp != NULL) *lnp = lineno;
  339.     if (spp != NULL) *spp = linbuf+linepos;
  340.     if (fpp != NULL) *fpp = infp;
  341. }
  342.  
  343.  
  344. int
  345. scan()                /* scan next character, return literal next */
  346. {
  347.     register int  lnext = 0;
  348.  
  349.     do {
  350.     if (linbuf[linepos] == '\0')
  351.         if (infp == NULL || fgets(linbuf, MAXLINE, infp) == NULL)
  352.         nextc = EOF;
  353.         else {
  354.         nextc = linbuf[0];
  355.         lineno++;
  356.         linepos = 1;
  357.         }
  358.     else
  359.         nextc = linbuf[linepos++];
  360.     if (!lnext)
  361.         lnext = nextc;
  362.     if (nextc == '{') {
  363.         scan();
  364.         while (nextc != '}')
  365.         if (nextc == EOF)
  366.             syntax("'}' expected");
  367.         else
  368.             scan();
  369.         scan();
  370.     }
  371.     } while (isspace(nextc));
  372.     return(lnext);
  373. }
  374.  
  375.  
  376. char *
  377. long2ascii(l)                  /* convert long to ascii */
  378. long  l;
  379. {
  380.     static char     buf[16];
  381.     register char  *cp;
  382.     int     neg = 0;
  383.  
  384.     if (l == 0)
  385.     return("0");
  386.     if (l < 0) {
  387.     l = -l;
  388.     neg++;
  389.     }
  390.     cp = buf + sizeof(buf);
  391.     *--cp = '\0';
  392.     while (l) {
  393.     *--cp = l % 10 + '0';
  394.     l /= 10;
  395.     }
  396.     if (neg)
  397.     *--cp = '-';
  398.     return(cp);
  399. }
  400.  
  401.  
  402. syntax(err)            /* report syntax error and quit */
  403. char  *err;
  404. {
  405.     register int  i;
  406.  
  407.     if (infile != NULL || lineno != 0) {
  408.     if (infile != NULL) eputs(infile);
  409.     if (lineno != 0) {
  410.         eputs(infile != NULL ? ", line " : "line ");
  411.         eputs(long2ascii((long)lineno));
  412.     }
  413.     eputs(":\n");
  414.     }
  415.     eputs(linbuf);
  416.     if (linbuf[strlen(linbuf)-1] != '\n')
  417.     eputs("\n");
  418.     for (i = 0; i < linepos-1; i++)
  419.     eputs(linbuf[i] == '\t' ? "\t" : " ");
  420.     eputs("^ ");
  421.     eputs(err);
  422.     eputs("\n");
  423.     quit(1);
  424. }
  425.  
  426.  
  427. addekid(ep, ekid)            /* add a child to ep */
  428. register EPNODE     *ep;
  429. EPNODE    *ekid;
  430. {
  431.     if (ep->v.kid == NULL)
  432.     ep->v.kid = ekid;
  433.     else {
  434.     for (ep = ep->v.kid; ep->sibling != NULL; ep = ep->sibling)
  435.         ;
  436.     ep->sibling = ekid;
  437.     }
  438.     ekid->sibling = NULL;
  439. }
  440.  
  441.  
  442. #if  defined(VARIABLE) || defined(FUNCTION)
  443. char *
  444. getname()            /* scan an identifier */
  445. {
  446.     static char     str[MAXWORD+1];
  447.     register int  i, lnext;
  448.  
  449.     lnext = nextc;
  450.     for (i = 0; i < MAXWORD && isid(lnext); i++, lnext = scan())
  451.     str[i] = lnext;
  452.     str[i] = '\0';
  453.     while (isid(lnext))        /* skip rest of name */
  454.     lnext = scan();
  455.  
  456.     return(str);
  457. }
  458. #endif
  459.  
  460.  
  461. int
  462. getinum()            /* scan a positive integer */
  463. {
  464.     register int  n, lnext;
  465.  
  466.     n = 0;
  467.     lnext = nextc;
  468.     while (isdigit(lnext)) {
  469.     n = n * 10 + lnext - '0';
  470.     lnext = scan();
  471.     }
  472.     return(n);
  473. }
  474.  
  475.  
  476. double
  477. getnum()            /* scan a positive float */
  478. {
  479.     register int  i, lnext;
  480.     char  str[MAXWORD+1];
  481.  
  482.     i = 0;
  483.     lnext = nextc;
  484.     while (isdigit(lnext) && i < MAXWORD) {
  485.     str[i++] = lnext;
  486.     lnext = scan();
  487.     }
  488.     if (lnext == '.' && i < MAXWORD) {
  489.     str[i++] = lnext;
  490.     lnext = scan();
  491.     while (isdigit(lnext) && i < MAXWORD) {
  492.         str[i++] = lnext;
  493.         lnext = scan();
  494.     }
  495.     }
  496.     if ((lnext == 'e' || lnext == 'E') && i < MAXWORD) {
  497.     str[i++] = lnext;
  498.     lnext = scan();
  499.     if ((lnext == '-' || lnext == '+') && i < MAXWORD) {
  500.         str[i++] = lnext;
  501.         lnext = scan();
  502.     }
  503.     while (isdigit(lnext) && i < MAXWORD) {
  504.         str[i++] = lnext;
  505.         lnext = scan();
  506.     }
  507.     }
  508.     str[i] = '\0';
  509.  
  510.     return(atof(str));
  511. }
  512.  
  513.  
  514. EPNODE *
  515. getE1()                /* E1 -> E1 ADDOP E2 */
  516.                 /*     E2 */
  517. {
  518.     register EPNODE  *ep1, *ep2;
  519.  
  520.     ep1 = getE2();
  521.     while (nextc == '+' || nextc == '-') {
  522.     ep2 = newnode();
  523.     ep2->type = nextc;
  524.     scan();
  525.     addekid(ep2, ep1);
  526.     addekid(ep2, getE2());
  527. #ifdef    RCONST
  528.     if (ep1->type == NUM && ep1->sibling->type == NUM)
  529.         ep2 = rconst(ep2);
  530. #endif
  531.     ep1 = ep2;
  532.     }
  533.     return(ep1);
  534. }
  535.  
  536.  
  537. EPNODE *
  538. getE2()                /* E2 -> E2 MULOP E3 */
  539.                 /*     E3 */
  540. {
  541.     register EPNODE  *ep1, *ep2;
  542.  
  543.     ep1 = getE3();
  544.     while (nextc == '*' || nextc == '/') {
  545.     ep2 = newnode();
  546.     ep2->type = nextc;
  547.     scan();
  548.     addekid(ep2, ep1);
  549.     addekid(ep2, getE3());
  550. #ifdef    RCONST
  551.     if (ep1->type == NUM && ep1->sibling->type == NUM)
  552.         ep2 = rconst(ep2);
  553. #endif
  554.     ep1 = ep2;
  555.     }
  556.     return(ep1);
  557. }
  558.  
  559.  
  560. EPNODE *
  561. getE3()                /* E3 -> E4 ^ E3 */
  562.                 /*     E4 */
  563. {
  564.     register EPNODE  *ep1, *ep2;
  565.  
  566.     ep1 = getE4();
  567.     if (nextc == '^') {
  568.     ep2 = newnode();
  569.     ep2->type = nextc;
  570.     scan();
  571.     addekid(ep2, ep1);
  572.     addekid(ep2, getE3());
  573. #ifdef    RCONST
  574.     if (ep1->type == NUM && ep1->sibling->type == NUM)
  575.         ep2 = rconst(ep2);
  576. #endif
  577.     return(ep2);
  578.     }
  579.     return(ep1);
  580. }
  581.  
  582.  
  583. EPNODE *
  584. getE4()                /* E4 -> ADDOP E5 */
  585.                 /*     E5 */
  586. {
  587.     register EPNODE  *ep1, *ep2;
  588.  
  589.     if (nextc == '-') {
  590.     scan();
  591.     ep2 = getE5();
  592.     if (ep2->type == NUM) {
  593.         ep2->v.num = -ep2->v.num;
  594.         return(ep2);
  595.     }
  596.     if (ep2->type == UMINUS) {    /* don't generate -(-E5) */
  597.         efree((char *)ep2);
  598.         return(ep2->v.kid);
  599.     }
  600.     ep1 = newnode();
  601.     ep1->type = UMINUS;
  602.     addekid(ep1, ep2);
  603.     return(ep1);
  604.     }
  605.     if (nextc == '+')
  606.     scan();
  607.     return(getE5());
  608. }
  609.  
  610.  
  611. EPNODE *
  612. getE5()                /* E5 -> (E1) */
  613.                 /*     VAR */
  614.                 /*     NUM */
  615.                 /*     $N */
  616.                 /*     FUNC(E1,..) */
  617.                 /*     ARG */
  618. {
  619.     int     i;
  620.     char  *nam;
  621.     register EPNODE  *ep1, *ep2;
  622.  
  623.     if (nextc == '(') {
  624.     scan();
  625.     ep1 = getE1();
  626.     if (nextc != ')')
  627.         syntax("')' expected");
  628.     scan();
  629.     return(ep1);
  630.     }
  631.  
  632. #ifdef    INCHAN
  633.     if (nextc == '$') {
  634.     scan();
  635.     ep1 = newnode();
  636.     ep1->type = CHAN;
  637.     ep1->v.chan = getinum();
  638.     return(ep1);
  639.     }
  640. #endif
  641.  
  642. #if  defined(VARIABLE) || defined(FUNCTION)
  643.     if (isalpha(nextc) || nextc == CNTXMARK) {
  644.     nam = getname();
  645. #if  defined(VARIABLE) && defined(FUNCTION)
  646.     ep1 = NULL;
  647.     if (curfunc != NULL)
  648.         for (i = 1, ep2 = curfunc->v.kid->sibling;
  649.                 ep2 != NULL; i++, ep2 = ep2->sibling)
  650.         if (!strcmp(ep2->v.name, nam)) {
  651.             ep1 = newnode();
  652.             ep1->type = ARG;
  653.             ep1->v.chan = i;
  654.             break;
  655.         }
  656.     if (ep1 == NULL)
  657. #endif
  658.     {
  659.         ep1 = newnode();
  660.         ep1->type = VAR;
  661.         ep1->v.ln = varinsert(nam);
  662.     }
  663. #ifdef    FUNCTION
  664.     if (nextc == '(') {
  665.         ep2 = newnode();
  666.         ep2->type = FUNC;
  667.         addekid(ep2, ep1);
  668.         ep1 = ep2;
  669.         do {
  670.         scan();
  671.         addekid(ep1, getE1());
  672.         } while (nextc == ',');
  673.         if (nextc != ')')
  674.         syntax("')' expected");
  675.         scan();
  676.     }
  677. #ifndef     VARIABLE
  678.     else
  679.         syntax("'(' expected");
  680. #endif
  681. #endif
  682. #ifdef    RCONST
  683.     if (isconstvar(ep1))
  684.         ep1 = rconst(ep1);
  685. #endif
  686.     return(ep1);
  687.     }
  688. #endif
  689.  
  690.     if (isdecimal(nextc)) {
  691.     ep1 = newnode();
  692.     ep1->type = NUM;
  693.     ep1->v.num = getnum();
  694.     return(ep1);
  695.     }
  696.     syntax("unexpected character");
  697. }
  698.  
  699.  
  700. #ifdef    RCONST
  701. EPNODE *
  702. rconst(epar)            /* reduce a constant expression */
  703. register EPNODE     *epar;
  704. {
  705.     register EPNODE  *ep;
  706.  
  707.     ep = newnode();
  708.     ep->type = NUM;
  709.     errno = 0;
  710.     ep->v.num = evalue(epar);
  711.     if (errno)
  712.     syntax("bad constant expression");
  713.     epfree(epar);
  714.  
  715.     return(ep);
  716. }
  717.  
  718.  
  719. isconstvar(ep)            /* is ep linked to a constant expression? */
  720. register EPNODE     *ep;
  721. {
  722. #ifdef    VARIABLE
  723.     register EPNODE  *ep1;
  724. #ifdef    FUNCTION
  725.  
  726.     if (ep->type == FUNC) {
  727.     if (!isconstfun(ep->v.kid))
  728.         return(0);
  729.     for (ep1 = ep->v.kid->sibling; ep1 != NULL; ep1 = ep1->sibling)
  730.         if (ep1->type != NUM && !isconstfun(ep1))
  731.         return(0);
  732.     return(1);
  733.     }
  734. #endif
  735.     if (ep->type != VAR)
  736.     return(0);
  737.     ep1 = ep->v.ln->def;
  738.     if (ep1 == NULL || ep1->type != ':')
  739.     return(0);
  740. #ifdef    FUNCTION
  741.     if (ep1->v.kid->type != SYM)
  742.     return(0);
  743. #endif
  744.     return(1);
  745. #else
  746.     return(ep->type == FUNC);
  747. #endif
  748. }
  749.  
  750.  
  751. #if  defined(FUNCTION) && defined(VARIABLE)
  752. isconstfun(ep)            /* is ep linked to a constant function? */
  753. register EPNODE     *ep;
  754. {
  755.     register EPNODE  *dp;
  756.     register LIBR  *lp;
  757.  
  758.     if (ep->type != VAR)
  759.     return(0);
  760.     if ((dp = ep->v.ln->def) != NULL && dp->v.kid->type == FUNC)
  761.     return(dp->type == ':');
  762.     if ((lp = ep->v.ln->lib) != NULL)
  763.     return(lp->atyp == ':');
  764.     return(0);
  765. }
  766. #endif
  767. #endif
  768.