home *** CD-ROM | disk | FTP | other *** search
/ Black Box 4 / BlackBox.cdr / progc / snip1091.arj / INTERP.C < prev    next >
Text File  |  1991-09-24  |  16KB  |  598 lines
  1. /*
  2.  *
  3.  * INTERP.C  - An arithmetic expression interpreter in ANSI C.
  4.  *
  5.  * Written September, 1991 by Jonathan Guthrie and placed in the public domain
  6.  *
  7.  */
  8.  
  9. #include    <setjmp.h>
  10. #include    <stdlib.h>
  11. #include    <ctype.h>
  12. #include    <float.h>
  13. #include    <math.h>
  14.  
  15. #ifdef  DEBUG
  16. #include    <stdio.h>
  17. #endif  /* DEBUG */
  18.  
  19. #include    "interp.h"
  20.  
  21. /*
  22. This is the EBNF grammar of the language handled by the interpreter.
  23.  
  24. NOTE:  What I'm calling a number is slightly different from what C
  25. calls a float.  I did this to make the number recognizer easier to
  26. write.
  27.  
  28. expression = factor {("+"|"-") factor}.
  29. factor = power {("*"|"/") power}.
  30. power = {value "^"} value.
  31. value = number | ("(" expression ")") | ("+"|"-" value).
  32. number = digit {digit} ["." {digit}] [("E"|"e") ["+"|"-"] digit {digit}].
  33.  
  34. Implementation:  The evaluator is implemented as a recursive
  35. evaluator. I did this because recursive evaluators are straightforward
  36. to code and simple to explain.  Basically, each one of the productions
  37. above, except for number, has a function.  If a production involves a
  38. nonterminal (a nonterminal is something that appears on the left side of
  39. a production) then the function handling the production calls the
  40. function that handles the nonterminal's production.  Terminals (quoted
  41. strings, in the grammar) and numbers are handled by gettoken.
  42.  
  43. Numbers are handled differently because recognizing a number is more
  44. properly the domain of a lexical analyzer than a parser.  Basically,
  45. I only include the numbers in the grammar in order to show what _I_
  46. am calling a number.  In the code, numbers are treated as terminals.
  47. */
  48.  
  49. #define PAREN       0x8000
  50. #define RPAREN      0x4000
  51. #define UNARY       0x2000
  52. #define POWER       0x1000
  53. #define MULTOP      0x0800
  54. #define ADDOP       0x0400
  55. #define NUMBER      0x0200
  56. #define ERROR       0x0100
  57.  
  58. #define ISPAREN(x)  ((x) & PAREN)
  59. #define ISUNARY(x)  ((x) & UNARY)
  60. #define ISPOWER(x)  ((x) & POWER)
  61. #define ISMULTOP(x) ((x) & MULTOP)
  62. #define ISADDOP(x)  ((x) & ADDOP)
  63. #define ISNUMBER(x) ((x) & NUMBER)
  64.  
  65. #define LPAREN      PAREN
  66. #define UNPLUS      UNARY
  67. #define UNMINUS     UNARY + 1
  68. #define STAR        MULTOP
  69. #define SLASH       MULTOP + 1
  70. #define PLUS        ADDOP
  71. #define MINUS       ADDOP + 1
  72.  
  73. typedef struct
  74. {
  75.     unsigned    type;
  76.     double      value;
  77. }   TOKEN;
  78.  
  79. #ifndef TRUE
  80. #define TRUE        1
  81. #endif
  82.  
  83. #ifndef FALSE
  84. #define FALSE       0
  85. #endif
  86.  
  87. /*
  88.  * For error handling by longjmp()
  89.  */
  90. static jmp_buf  error;
  91.  
  92. /*
  93.  * To avoid needing an unget().
  94.  */
  95. static TOKEN    old_token;
  96.  
  97. /*
  98.  * To avoid passing input_func back and forth.
  99.  */
  100. static int  (*input_func)(void);
  101.  
  102. /*
  103.  * I need this one prototype because expression is called recursively
  104.  */
  105. static void expression(TOKEN *out);
  106.  
  107. /*
  108.  * It's just a big size.  Numbers are limited to no more than 100 characters
  109.  * long.  NOTE:  The length is checked to prevent buffer overruns.
  110.  */
  111. #define BUFFLEN     100
  112.  
  113. /*
  114.  * getnumber() recognizes a number in the input stream.  The number is
  115.  * returned in value, the first character of the number is passed in
  116.  * pushback which also passes back the first character after the number.
  117.  *
  118.  * getnumber() returns a status code which tells whether the number is
  119.  * ill-formed or not.
  120.  *
  121.  * Implementation:  getnumber() is coded as a deterministic finite-state-
  122.  * machine with six states.  State 0 is the start state, and state 5 is
  123.  * the end state.  Each state gets a case in the main switch statement.
  124.  * The cases are explained as they appear.
  125.  */
  126. static int  getnumber(double *value, int *pushback)
  127. {
  128. int     i, c, state, error;
  129. char    buff[BUFFLEN];
  130.  
  131.     i = state = error = 0;
  132.     c = buff[i++] = *pushback;
  133.     while(state != 5)
  134.     {
  135.         c = input_func();
  136.         buff[i++] = c;
  137.         if((BUFFLEN-1) <= i)
  138.             state = 4;
  139.  
  140.         switch(state)
  141.         {
  142.             /*
  143.                 In state 0, the function has seen no decimal points or
  144.                 exponents, just an initial string of numbers.
  145.             */
  146.             case 0:
  147.                 if(!isdigit(c))
  148.                 {
  149.                     if('.' == c)
  150.                         state = 1;
  151.                     else if('E' == toupper(c))
  152.                         state = 2;
  153.                     else
  154.                     {
  155.                         *pushback = c;
  156.                         state = 5;
  157.                     }
  158.                 }
  159.                 break;
  160.  
  161.             /*
  162.                 In state 1, the function has seen a decimal point, but
  163.                 no exponent.
  164.             */
  165.             case 1:
  166.                 if(!isdigit(c))
  167.                 {
  168.                     if('E' == toupper(c))
  169.                         state = 2;
  170.                     else
  171.                     {
  172.                         *pushback = c;
  173.                         state = 5;
  174.                     }
  175.                 }
  176.                 break;
  177.  
  178.             /*
  179.                 In state 2, the function has seen an exponent, and needs
  180.                 to see either a digit or a + or a - or there's an error.
  181.             */
  182.             case 2:
  183.                 if(isdigit(c))
  184.                 {
  185.                     state = 4;
  186.                 }
  187.                 else if (('+' == c) || ('-' == c))
  188.                 {
  189.                     state = 3;
  190.                 }
  191.                 else
  192.                 {
  193.                     *pushback = c;
  194.                     error = 1;
  195.                     state = 5;
  196.                 }
  197.                 break;
  198.  
  199.             /*
  200.                 In state 3, the function has seen an exponent and
  201.                 a + or - and it needs to see a digit or there's an
  202.                 error
  203.             */
  204.             case 3:
  205.                 if(isdigit(c))
  206.                 {
  207.                     state = 4;
  208.                 }
  209.                 else
  210.                 {
  211.                     *pushback = c;
  212.                     error = 1;
  213.                     state = 5;
  214.                 }
  215.  
  216.                 break;
  217.  
  218.             /*
  219.                 In state 4, the function is looking for a trailing string
  220.                 of digits.
  221.             */
  222.             case 4:
  223.                 if(!isdigit(c))
  224.                 {
  225.                     *pushback = c;
  226.                     state = 5;
  227.                 }
  228.                 break;
  229.  
  230.             /*
  231.                 None of the other states are valid.  Flag an error if
  232.                 you see them. (State 5 doesn't get a case because it
  233.                 should be filtered out at the top of the loop.)
  234.             */
  235.             default:
  236.                 state = 5;
  237.                 error = 1;
  238.         }
  239.     }
  240.  
  241.     /* Now, convert the found string to a number */
  242.     buff[i] = 0;
  243.     if(!error)
  244.         *value = strtod(buff, NULL);
  245.  
  246.     return error;
  247. }
  248.  
  249.  
  250. /*
  251.  * This is the function that handles getting nonterminals or "tokens"
  252.  * as well as numbers.  Since all tokens are either numbers (which
  253.  * all begin with digits, strangely enough) or single characters, I don't
  254.  * go to a whole lot of trouble checking things.  Whitespace is ignored.
  255.  * If it sees a character it doesn't recognize, it returns the error
  256.  * token.
  257.  *
  258.  * One bit of wierdness:  The unary_flag indicates whether or not "+" and
  259.  * "-" represent unary operators or binary operators.  Since that is
  260.  * context-dependant, gettoken would otherwise have difficulty telling.
  261.  *
  262.  * gettoken() returns TRUE if an error occurred, else it returns FALSE.
  263.  * The token itself is returned in token.
  264.  */
  265. static int  gettoken(TOKEN *token, int unary_flag)
  266. {
  267. int     c;
  268. static int  pushback = 0;
  269.  
  270.     if(pushback)
  271.     {
  272.         c = pushback;
  273.     }
  274.     else
  275.     {
  276.         do
  277.         {
  278.             c = input_func();
  279.         } while(isspace(c));
  280.     }
  281.  
  282.     if(isdigit(c))
  283.     {
  284.         pushback = c;
  285.         if(getnumber(&(token->value), &pushback))
  286.             token->type = ERROR;
  287.         else
  288.             token->type = NUMBER;
  289.  
  290.         pushback = isspace(pushback) ? 0 : pushback;
  291.     }
  292.     else
  293.     {
  294.         pushback = 0;
  295.         switch(c)
  296.         {
  297.             case '+':
  298.                 token->type = ((unary_flag) ? UNPLUS : PLUS);
  299.                 break;
  300.  
  301.             case '-':
  302.                 token->type = ((unary_flag) ? UNMINUS : MINUS);
  303.                 break;
  304.  
  305.             case '*':
  306.                 token->type = STAR;
  307.                 break;
  308.  
  309.             case '/':
  310.                 token->type = SLASH;
  311.                 break;
  312.  
  313.             case '^':
  314.                 token->type = POWER;
  315.                 break;
  316.  
  317.             case '(':
  318.                 token->type = LPAREN;
  319.                 break;
  320.  
  321.             case ')':
  322.                 token->type = RPAREN;
  323.                 break;
  324.  
  325.             default:
  326.                 token->type = ERROR;
  327.         }
  328.     }
  329.     return  ERROR == token->type;
  330. }
  331.  
  332. /*
  333.  * This is the function that handles the value nonterminal.  It does
  334.  * unary operators, parentheses, and getting numbers.  In fact, this
  335.  * function is the one that gets most of the tokens from the list.
  336.  */
  337.  
  338. static void value(TOKEN *out)
  339. {
  340. TOKEN   in;
  341.  
  342.     gettoken(out, TRUE);
  343.     if(ISUNARY(out->type))
  344.     {
  345.         value(&in);
  346.         if(!ISNUMBER(in.type))
  347.             longjmp(error, EV_BADVAL);
  348.         out->value = (UNMINUS == out->type) ? -1 * in.value : in.value;
  349.         out->type = NUMBER;
  350.     }
  351.     else if(ISPAREN(out->type))
  352.     {
  353.         expression(out);
  354.         if(!ISNUMBER(out->type))
  355.             longjmp(error, EV_BADEXP);
  356.  
  357.         if(RPAREN != old_token.type)
  358.             longjmp(error, EV_BADPAREN);        /* error */
  359.     }
  360.     else if(!ISNUMBER(out->type))
  361.         longjmp(error, EV_BADNUM);              /* error */
  362. }
  363.  
  364.  
  365. /*
  366.  * This function is the same as a pow() function, but it checks for
  367.  * overflow and domain errors before executing the calculation.
  368.  *
  369.  * NOTE:  This function is considerably more limited than C's pow()
  370.  * function.  src1 is not allowed to be negative even if src2 is an
  371.  * integer.  Also it will reject, as overflows, some calculations
  372.  * that would not overflow pow().  However, it will do most calcs
  373.  * properly.
  374.  */
  375. static int  bp_pow(double src1, double src2, double *dest)
  376. {
  377. int     exp1;
  378.  
  379.     if(0.0 > src1)
  380.         return TRUE;
  381.  
  382.     frexp(src1, &exp1);
  383.     if(DBL_MAX_EXP < fabs(src2 * exp1))
  384.         return TRUE;
  385.  
  386.     *dest = pow(src1, src2);
  387.     return FALSE;
  388. }
  389.  
  390. /*
  391.  * This is the function that handles the power nonterminal.  "Powers" are
  392.  * strings of values separated by "^"s.  Note that this function is
  393.  * recursive because strings of powers are normally evaluated right-to-left
  394.  * rather than the usual left to right.
  395.  */
  396.  
  397. static void power(TOKEN *out)
  398. {
  399. TOKEN   in1, in2;
  400.  
  401.     value(out);
  402.     if(!ISNUMBER(out->type))
  403.         longjmp(error, EV_BADVAL);
  404.  
  405.     gettoken(&in1, FALSE);
  406.     if(ISPOWER(in1.type))
  407.     {
  408.         power(&in2);
  409.         if(!ISNUMBER(out->type))
  410.             longjmp(error, EV_BADPOW);
  411.  
  412.         if(bp_pow(out->value, in2.value, &(out->value)))
  413.             longjmp(error, EV_OVERFLOW);
  414.  
  415.         out->type = NUMBER;
  416.     }
  417.     else
  418.         old_token = in1;
  419. }
  420.  
  421.  
  422. /*
  423.  * This function multiplies two numbers together, first checking them
  424.  * for overflow.  If the multiplication would overflow, TRUE is returned.
  425.  * Else, FALSE is returned and the product is returned in dest.
  426.  */
  427.  
  428. static int  bp_mul(double src1, double src2, double *dest)
  429. {
  430. int     exp1, exp2;
  431.  
  432.     frexp(src1, &exp1);
  433.     frexp(src2, &exp2);
  434.  
  435.     if(DBL_MAX_EXP < abs(exp1 + exp2))
  436.         return TRUE;
  437.  
  438.     *dest = src1 * src2;
  439.     return FALSE;
  440. }
  441.  
  442.  
  443. /*
  444.  * This function divides one number into another, first checking
  445.  * for overflow and division by zero.  If an error is detected, TRUE
  446.  * is returned.  Else, FALSE is returned and the result is returned
  447.  * in dest.
  448.  */
  449.  
  450. int     bp_div(double src1, double src2, double *dest)
  451. {
  452. int     exp1, exp2;
  453.  
  454.     frexp(src1, &exp1);
  455.     frexp(src2, &exp2);
  456.  
  457.     if((DBL_MAX_EXP < abs(exp1 - exp2)) || (0.0 == src2))
  458.         return TRUE;
  459.  
  460.     *dest = src1 / src2;
  461.     return FALSE;
  462. }
  463.  
  464. /*
  465.  * This function handles the factor nonterminal.  Factors are strings of
  466.  * powers separated by "/" and "*".
  467.  */
  468.  
  469. static void factor(TOKEN *out)
  470. {
  471. TOKEN   in;
  472. int     oldtype;
  473.  
  474.     power(out);
  475.     if(!ISNUMBER(out->type))
  476.         longjmp(error, EV_BADPOW);
  477.  
  478.     while(ISMULTOP(old_token.type))
  479.     {
  480.         oldtype = old_token.type;
  481.         power(&in);
  482.         if(!ISNUMBER(in.type))
  483.             longjmp(error, EV_BADPOW);
  484.  
  485.         if(STAR == oldtype)
  486.         {
  487.             if(bp_mul(out->value, in.value, &(out->value)))
  488.                 longjmp(error, EV_OVERFLOW);
  489.         }
  490.         else
  491.         {
  492.             if(0.0 == in.value)
  493.                 longjmp(error, EV_DIV0);
  494.  
  495.             if(bp_div(out->value, in.value, &(out->value)))
  496.                 longjmp(error, EV_OVERFLOW);
  497.         }
  498.  
  499.         out->type = NUMBER;
  500.     }
  501. }
  502.  
  503.  
  504. /*
  505.  * This function handles the expression nonterminal.  Expressions are
  506.  * strings of factors separated by "+" and "-".  Addition and subtraction
  507.  * are not checked for overflow because I deem that it would be more
  508.  * trouble than it's worth.  If you know of a simple way to check an
  509.  * addition or subtraction for overflow, let me know.
  510.  */
  511.  
  512. static void expression(TOKEN *out)
  513. {
  514. TOKEN   in;
  515. int     oldtype;
  516.  
  517.     factor(out);
  518.     if(!ISNUMBER(out->type))
  519.         longjmp(error, EV_BADFACT);
  520.  
  521.     while(ISADDOP(old_token.type))
  522.     {
  523.         oldtype = old_token.type;
  524.         factor(&in);
  525.         if(!ISNUMBER(in.type))
  526.             longjmp(error, EV_BADFACT);
  527.  
  528.         out->value = (PLUS == oldtype) ?
  529.                 out->value + in.value : out->value - in.value;
  530.         out->type = NUMBER;
  531.     }
  532. }
  533.  
  534.  
  535. /*
  536.  * This is the main function for the evaluator.  The two parameters are
  537.  * a pointer to where the result should be stored and a pointer to the
  538.  * input function.  The input function can be literally anything that
  539.  * returns a single character every time it's called.  The example code
  540.  * contains an appropriate function for evaluating the expression
  541.  * stored in a string.
  542.  *
  543.  * This function returns an error code as defined in interp.h.
  544.  */
  545. int     eval(double *answer, int (*get_a_char)(void))
  546. {
  547. TOKEN   result;
  548. int     errcode;
  549.  
  550.     if(EV_RES_OK == (errcode = setjmp(error)))
  551.     {
  552.         input_func = get_a_char;
  553.         expression(&result);
  554.         if(ISNUMBER(result.type))
  555.         {
  556.             errcode = EV_RES_OK;
  557.             *answer = result.value;
  558.         }
  559.         else
  560.             errcode = EV_BADEXP;
  561.     }
  562.     return  errcode;
  563. }
  564.  
  565.  
  566. /* What follows is example/test code */
  567. #ifdef  DEBUG
  568. int     charcount;
  569. const char  *eval_string;
  570.  
  571.  
  572. /* This is the testing "input function" */
  573. static int  gchar()
  574. {
  575.     return eval_string[charcount++];
  576. }
  577.  
  578.  
  579. int     main()
  580. {
  581. char    buffer[100];
  582. double  result;
  583. int     errcode;
  584.  
  585.     fputs("What is the expression?  ", stdout);
  586.     fgets(buffer, 100, stdin);
  587.  
  588.     eval_string = buffer;
  589.     charcount = 0;
  590.     errcode = eval(&result, gchar);
  591.     if(errcode)
  592.         printf("Error: %s\n", EV_results[errcode]);
  593.     else
  594.         printf("\n\nThe result is: %f\n", result);
  595.     return(EXIT_SUCCESS);
  596. }
  597. #endif  /* DEBUG */
  598.