home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / m4-1.4-src.tgz / tar.out / fsf / m4 / src / eval.c < prev    next >
C/C++ Source or Header  |  1996-09-28  |  14KB  |  775 lines
  1. /* GNU m4 -- A simple macro processor
  2.    Copyright (C) 1989, 90, 91, 92, 93, 94 Free Software Foundation, Inc.
  3.   
  4.    This program is free software; you can redistribute it and/or modify
  5.    it under the terms of the GNU General Public License as published by
  6.    the Free Software Foundation; either version 2, or (at your option)
  7.    any later version.
  8.   
  9.    This program is distributed in the hope that it will be useful,
  10.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.    GNU General Public License for more details.
  13.   
  14.    You should have received a copy of the GNU General Public License
  15.    along with this program; if not, write to the Free Software
  16.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17. */
  18.  
  19. /* This file contains the functions to evaluate integer expressions for
  20.    the "eval" macro.  It is a little, fairly self-contained module, with
  21.    its own scanner, and a recursive descent parser.  The only entry point
  22.    is evaluate ().  */
  23.  
  24. #include "m4.h"
  25.  
  26. /* Evaluates token types.  */
  27.  
  28. typedef enum eval_token
  29.   {
  30.     ERROR,
  31.     PLUS, MINUS,
  32.     EXPONENT,
  33.     TIMES, DIVIDE, MODULO,
  34.     EQ, NOTEQ, GT, GTEQ, LS, LSEQ,
  35.     LSHIFT, RSHIFT,
  36.     LNOT, LAND, LOR,
  37.     NOT, AND, OR, XOR,
  38.     LEFTP, RIGHTP,
  39.     NUMBER, EOTEXT
  40.   }
  41. eval_token;
  42.  
  43. /* Error types.  */
  44.  
  45. typedef enum eval_error
  46.   {
  47.     NO_ERROR,
  48.     MISSING_RIGHT,
  49.     SYNTAX_ERROR,
  50.     UNKNOWN_INPUT,
  51.     EXCESS_INPUT,
  52.     DIVIDE_ZERO,
  53.     MODULO_ZERO
  54.   }
  55. eval_error;
  56.  
  57. static eval_error logical_or_term _((eval_token, eval_t *));
  58. static eval_error logical_and_term _((eval_token, eval_t *));
  59. static eval_error or_term _((eval_token, eval_t *));
  60. static eval_error xor_term _((eval_token, eval_t *));
  61. static eval_error and_term _((eval_token, eval_t *));
  62. static eval_error not_term _((eval_token, eval_t *));
  63. static eval_error logical_not_term _((eval_token, eval_t *));
  64. static eval_error cmp_term _((eval_token, eval_t *));
  65. static eval_error shift_term _((eval_token, eval_t *));
  66. static eval_error add_term _((eval_token, eval_t *));
  67. static eval_error mult_term _((eval_token, eval_t *));
  68. static eval_error exp_term _((eval_token, eval_t *));
  69. static eval_error unary_term _((eval_token, eval_t *));
  70. static eval_error simple_term _((eval_token, eval_t *));
  71.  
  72. /*--------------------.
  73. | Lexical functions.  |
  74. `--------------------*/
  75.  
  76. /* Pointer to next character of input text.  */
  77. static const char *eval_text;
  78.  
  79. /* Value of eval_text, from before last call of eval_lex ().  This is so we
  80.    can back up, if we have read too much.  */
  81. static const char *last_text;
  82.  
  83. static void
  84. eval_init_lex (const char *text)
  85. {
  86.   eval_text = text;
  87.   last_text = NULL;
  88. }
  89.  
  90. static void
  91. eval_undo (void)
  92. {
  93.   eval_text = last_text;
  94. }
  95.  
  96. /* VAL is numerical value, if any.  */
  97.  
  98. static eval_token
  99. eval_lex (eval_t *val)
  100. {
  101.   while (isspace (*eval_text))
  102.     eval_text++;
  103.  
  104.   last_text = eval_text;
  105.  
  106.   if (*eval_text == '\0')
  107.     return EOTEXT;
  108.  
  109.   if (isdigit (*eval_text))
  110.     {
  111.       int base, digit;
  112.  
  113.       if (*eval_text == '0')
  114.     {
  115.       eval_text++;
  116.       switch (*eval_text)
  117.         {
  118.         case 'x':
  119.         case 'X':
  120.           base = 16;
  121.           eval_text++;
  122.           break;
  123.  
  124.         case 'b':
  125.         case 'B':
  126.           base = 2;
  127.           eval_text++;
  128.           break;
  129.  
  130.         case 'r':
  131.         case 'R':
  132.           base = 0;
  133.           eval_text++;
  134.           while (isdigit (*eval_text) && base <= 36)
  135.         base = 10 * base + *eval_text++ - '0';
  136.           if (base == 0 || base > 36 || *eval_text != ':')
  137.         return ERROR;
  138.           eval_text++;
  139.           break;
  140.  
  141.         default:
  142.           base = 8;
  143.         }
  144.     }
  145.       else
  146.     base = 10;
  147.  
  148.       (*val) = 0;
  149.       for (; *eval_text; eval_text++)
  150.     {
  151.       if (isdigit (*eval_text))
  152.         digit = *eval_text - '0';
  153.       else if (islower (*eval_text))
  154.         digit = *eval_text - 'a' + 10;
  155.       else if (isupper (*eval_text))
  156.         digit = *eval_text - 'A' + 10;
  157.       else
  158.         break;
  159.  
  160.       if (digit >= base)
  161.         break;
  162.  
  163.       (*val) = (*val) * base + digit;
  164.     }
  165.       return NUMBER;
  166.     }
  167.  
  168.   switch (*eval_text++)
  169.     {
  170.     case '+':
  171.       return PLUS;
  172.     case '-':
  173.       return MINUS;
  174.     case '*':
  175.       if (*eval_text == '*')
  176.     {
  177.       eval_text++;
  178.       return EXPONENT;
  179.     }
  180.       else
  181.     return TIMES;
  182.     case '/':
  183.       return DIVIDE;
  184.     case '%':
  185.       return MODULO;
  186.     case '=':
  187.       if (*eval_text == '=')
  188.     eval_text++;
  189.       return EQ;
  190.     case '!':
  191.       if (*eval_text == '=')
  192.     {
  193.       eval_text++;
  194.       return NOTEQ;
  195.     }
  196.       else
  197.     return LNOT;
  198.     case '>':
  199.       if (*eval_text == '=')
  200.     {
  201.       eval_text++;
  202.       return GTEQ;
  203.     }
  204.       else if (*eval_text == '>')
  205.     {
  206.       eval_text++;
  207.       return RSHIFT;
  208.     }
  209.       else
  210.     return GT;
  211.     case '<':
  212.       if (*eval_text == '=')
  213.     {
  214.       eval_text++;
  215.       return LSEQ;
  216.     }
  217.       else if (*eval_text == '<')
  218.     {
  219.       eval_text++;
  220.       return LSHIFT;
  221.     }
  222.       else
  223.     return LS;
  224.     case '^':
  225.       return XOR;
  226.     case '~':
  227.       return NOT;
  228.     case '&':
  229.       if (*eval_text == '&')
  230.     {
  231.       eval_text++;
  232.       return LAND;
  233.     }
  234.       else
  235.     return AND;
  236.     case '|':
  237.       if (*eval_text == '|')
  238.     {
  239.       eval_text++;
  240.       return LOR;
  241.     }
  242.       else
  243.     return OR;
  244.     case '(':
  245.       return LEFTP;
  246.     case ')':
  247.       return RIGHTP;
  248.     default:
  249.       return ERROR;
  250.     }
  251. }
  252.  
  253. /*---------------------------------------.
  254. | Main entry point, called from "eval".     |
  255. `---------------------------------------*/
  256.  
  257. boolean
  258. evaluate (const char *expr, eval_t *val)
  259. {
  260.   eval_token et;
  261.   eval_error err;
  262.  
  263.   eval_init_lex (expr);
  264.   et = eval_lex (val);
  265.   err = logical_or_term (et, val);
  266.  
  267.   if (err == NO_ERROR && *eval_text != '\0')
  268.     err = EXCESS_INPUT;
  269.     
  270.   switch (err)
  271.     {
  272.     case NO_ERROR:
  273.       break;
  274.  
  275.     case MISSING_RIGHT:
  276.       M4ERROR ((warning_status, 0,
  277.         "Bad expression in eval (missing right parenthesis): %s",
  278.         expr));
  279.       break;
  280.  
  281.     case SYNTAX_ERROR:
  282.       M4ERROR ((warning_status, 0,
  283.         "Bad expression in eval: %s", expr));
  284.       break;
  285.  
  286.     case UNKNOWN_INPUT:
  287.       M4ERROR ((warning_status, 0,
  288.         "Bad expression in eval (bad input): %s", expr));
  289.       break;
  290.  
  291.     case EXCESS_INPUT:
  292.       M4ERROR ((warning_status, 0,
  293.         "Bad expression in eval (excess input): %s", expr));
  294.       break;
  295.  
  296.     case DIVIDE_ZERO:
  297.       M4ERROR ((warning_status, 0,
  298.         "Divide by zero in eval: %s", expr));
  299.       break;
  300.  
  301.     case MODULO_ZERO:
  302.       M4ERROR ((warning_status, 0,
  303.         "Modulo by zero in eval: %s", expr));
  304.       break;
  305.  
  306.     default:
  307.       M4ERROR ((warning_status, 0,
  308.         "INTERNAL ERROR: Bad error code in evaluate ()"));
  309.       abort ();
  310.     }
  311.  
  312.   return (boolean) (err != NO_ERROR);
  313. }
  314.  
  315. /*---------------------------.
  316. | Recursive descent parser.  |
  317. `---------------------------*/
  318.  
  319. static eval_error
  320. logical_or_term (eval_token et, eval_t *v1)
  321. {
  322.   eval_t v2;
  323.   eval_error er;
  324.  
  325.   if ((er = logical_and_term (et, v1)) != NO_ERROR)
  326.     return er;
  327.  
  328.   while ((et = eval_lex (&v2)) == LOR)
  329.     {
  330.       et = eval_lex (&v2);
  331.       if (et == ERROR)
  332.     return UNKNOWN_INPUT;
  333.  
  334.       if ((er = logical_and_term (et, &v2)) != NO_ERROR)
  335.     return er;
  336.  
  337.       *v1 = *v1 || v2;
  338.     }
  339.   if (et == ERROR)
  340.     return UNKNOWN_INPUT;
  341.  
  342.   eval_undo ();
  343.   return NO_ERROR;
  344. }
  345.  
  346. static eval_error
  347. logical_and_term (eval_token et, eval_t *v1)
  348. {
  349.   eval_t v2;
  350.   eval_error er;
  351.  
  352.   if ((er = or_term (et, v1)) != NO_ERROR)
  353.     return er;
  354.  
  355.   while ((et = eval_lex (&v2)) == LAND)
  356.     {
  357.       et = eval_lex (&v2);
  358.       if (et == ERROR)
  359.     return UNKNOWN_INPUT;
  360.  
  361.       if ((er = or_term (et, &v2)) != NO_ERROR)
  362.     return er;
  363.  
  364.       *v1 = *v1 && v2;
  365.     }
  366.   if (et == ERROR)
  367.     return UNKNOWN_INPUT;
  368.  
  369.   eval_undo ();
  370.   return NO_ERROR;
  371. }
  372.  
  373. static eval_error
  374. or_term (eval_token et, eval_t *v1)
  375. {
  376.   eval_t v2;
  377.   eval_error er;
  378.  
  379.   if ((er = xor_term (et, v1)) != NO_ERROR)
  380.     return er;
  381.  
  382.   while ((et = eval_lex (&v2)) == OR)
  383.     {
  384.       et = eval_lex (&v2);
  385.       if (et == ERROR)
  386.     return UNKNOWN_INPUT;
  387.  
  388.       if ((er = xor_term (et, &v2)) != NO_ERROR)
  389.     return er;
  390.  
  391.       *v1 = *v1 | v2;
  392.     }
  393.   if (et == ERROR)
  394.     return UNKNOWN_INPUT;
  395.  
  396.   eval_undo ();
  397.   return NO_ERROR;
  398. }
  399.  
  400. static eval_error
  401. xor_term (eval_token et, eval_t *v1)
  402. {
  403.   eval_t v2;
  404.   eval_error er;
  405.  
  406.   if ((er = and_term (et, v1)) != NO_ERROR)
  407.     return er;
  408.  
  409.   while ((et = eval_lex (&v2)) == XOR)
  410.     {
  411.       et = eval_lex (&v2);
  412.       if (et == ERROR)
  413.     return UNKNOWN_INPUT;
  414.  
  415.       if ((er = and_term (et, &v2)) != NO_ERROR)
  416.     return er;
  417.  
  418.       *v1 = *v1 ^ v2;
  419.     }
  420.   if (et == ERROR)
  421.     return UNKNOWN_INPUT;
  422.  
  423.   eval_undo ();
  424.   return NO_ERROR;
  425. }
  426.  
  427. static eval_error
  428. and_term (eval_token et, eval_t *v1)
  429. {
  430.   eval_t v2;
  431.   eval_error er;
  432.  
  433.   if ((er = not_term (et, v1)) != NO_ERROR)
  434.     return er;
  435.  
  436.   while ((et = eval_lex (&v2)) == AND)
  437.     {
  438.       et = eval_lex (&v2);
  439.       if (et == ERROR)
  440.     return UNKNOWN_INPUT;
  441.  
  442.       if ((er = not_term (et, &v2)) != NO_ERROR)
  443.     return er;
  444.  
  445.       *v1 = *v1 & v2;
  446.     }
  447.   if (et == ERROR)
  448.     return UNKNOWN_INPUT;
  449.  
  450.   eval_undo ();
  451.   return NO_ERROR;
  452. }
  453.  
  454. static eval_error
  455. not_term (eval_token et, eval_t *v1)
  456. {
  457.   eval_error er;
  458.  
  459.   if (et == NOT)
  460.     {
  461.       et = eval_lex (v1);
  462.       if (et == ERROR)
  463.     return UNKNOWN_INPUT;
  464.  
  465.       if ((er = not_term (et, v1)) != NO_ERROR)
  466.     return er;
  467.       *v1 = ~*v1;
  468.     }
  469.   else
  470.     if ((er = logical_not_term (et, v1)) != NO_ERROR)
  471.       return er;
  472.  
  473.   return NO_ERROR;
  474. }
  475.  
  476. static eval_error
  477. logical_not_term (eval_token et, eval_t *v1)
  478. {
  479.   eval_error er;
  480.  
  481.   if (et == LNOT)
  482.     {
  483.       et = eval_lex (v1);
  484.       if (et == ERROR)
  485.     return UNKNOWN_INPUT;
  486.  
  487.       if ((er = logical_not_term (et, v1)) != NO_ERROR)
  488.     return er;
  489.       *v1 = !*v1;
  490.     }
  491.   else
  492.     if ((er = cmp_term (et, v1)) != NO_ERROR)
  493.       return er;
  494.  
  495.   return NO_ERROR;
  496. }
  497.  
  498. static eval_error
  499. cmp_term (eval_token et, eval_t *v1)
  500. {
  501.   eval_token op;
  502.   eval_t v2;
  503.   eval_error er;
  504.  
  505.   if ((er = shift_term (et, v1)) != NO_ERROR)
  506.     return er;
  507.  
  508.   while ((op = eval_lex (&v2)) == EQ || op == NOTEQ
  509.      || op == GT || op == GTEQ
  510.      || op == LS || op == LSEQ)
  511.     {
  512.  
  513.       et = eval_lex (&v2);
  514.       if (et == ERROR)
  515.     return UNKNOWN_INPUT;
  516.  
  517.       if ((er = shift_term (et, &v2)) != NO_ERROR)
  518.     return er;
  519.  
  520.       switch (op)
  521.     {
  522.     case EQ:
  523.       *v1 = *v1 == v2;
  524.       break;
  525.  
  526.     case NOTEQ:
  527.       *v1 = *v1 != v2;
  528.       break;
  529.  
  530.     case GT:
  531.       *v1 = *v1 > v2;
  532.       break;
  533.  
  534.     case GTEQ:
  535.       *v1 = *v1 >= v2;
  536.       break;
  537.  
  538.     case LS:
  539.       *v1 = *v1 < v2;
  540.       break;
  541.  
  542.     case LSEQ:
  543.       *v1 = *v1 <= v2;
  544.       break;
  545.  
  546.     default:
  547.       M4ERROR ((warning_status, 0,
  548.             "INTERNAL ERROR: Bad comparison operator in cmp_term ()"));
  549.       abort ();
  550.     }
  551.     }
  552.   if (op == ERROR)
  553.     return UNKNOWN_INPUT;
  554.  
  555.   eval_undo ();
  556.   return NO_ERROR;
  557. }
  558.  
  559. static eval_error
  560. shift_term (eval_token et, eval_t *v1)
  561. {
  562.   eval_token op;
  563.   eval_t v2;
  564.   eval_error er;
  565.  
  566.   if ((er = add_term (et, v1)) != NO_ERROR)
  567.     return er;
  568.  
  569.   while ((op = eval_lex (&v2)) == LSHIFT || op == RSHIFT)
  570.     {
  571.  
  572.       et = eval_lex (&v2);
  573.       if (et == ERROR)
  574.     return UNKNOWN_INPUT;
  575.  
  576.       if ((er = add_term (et, &v2)) != NO_ERROR)
  577.     return er;
  578.  
  579.       switch (op)
  580.     {
  581.     case LSHIFT:
  582.       *v1 = *v1 << v2;
  583.       break;
  584.  
  585.     case RSHIFT:
  586.       *v1 = *v1 >> v2;
  587.       break;
  588.  
  589.     default:
  590.       M4ERROR ((warning_status, 0,
  591.             "INTERNAL ERROR: Bad shift operator in shift_term ()"));
  592.       abort ();
  593.     }
  594.     }
  595.   if (op == ERROR)
  596.     return UNKNOWN_INPUT;
  597.  
  598.   eval_undo ();
  599.   return NO_ERROR;
  600. }
  601.  
  602. static eval_error
  603. add_term (eval_token et, eval_t *v1)
  604. {
  605.   eval_token op;
  606.   eval_t v2;
  607.   eval_error er;
  608.  
  609.   if ((er = mult_term (et, v1)) != NO_ERROR)
  610.     return er;
  611.  
  612.   while ((op = eval_lex (&v2)) == PLUS || op == MINUS)
  613.     {
  614.       et = eval_lex (&v2);
  615.       if (et == ERROR)
  616.     return UNKNOWN_INPUT;
  617.  
  618.       if ((er = mult_term (et, &v2)) != NO_ERROR)
  619.     return er;
  620.  
  621.       if (op == PLUS)
  622.     *v1 = *v1 + v2;
  623.       else
  624.     *v1 = *v1 - v2;
  625.     }
  626.   if (op == ERROR)
  627.     return UNKNOWN_INPUT;
  628.  
  629.   eval_undo ();
  630.   return NO_ERROR;
  631. }
  632.  
  633. static eval_error
  634. mult_term (eval_token et, eval_t *v1)
  635. {
  636.   eval_token op;
  637.   eval_t v2;
  638.   eval_error er;
  639.  
  640.   if ((er = exp_term (et, v1)) != NO_ERROR)
  641.     return er;
  642.  
  643.   while ((op = eval_lex (&v2)) == TIMES || op == DIVIDE || op == MODULO)
  644.     {
  645.       et = eval_lex (&v2);
  646.       if (et == ERROR)
  647.     return UNKNOWN_INPUT;
  648.  
  649.       if ((er = exp_term (et, &v2)) != NO_ERROR)
  650.     return er;
  651.  
  652.       switch (op)
  653.     {
  654.     case TIMES:
  655.       *v1 = *v1 * v2;
  656.       break;
  657.  
  658.     case DIVIDE:
  659.       if (v2 == 0)
  660.         return DIVIDE_ZERO;
  661.       else
  662.         *v1 = *v1 / v2;
  663.       break;
  664.  
  665.     case MODULO:
  666.       if (v2 == 0)
  667.         return MODULO_ZERO;
  668.       else
  669.         *v1 = *v1 % v2;
  670.       break;
  671.  
  672.     default:
  673.       M4ERROR ((warning_status, 0,
  674.             "INTERNAL ERROR: Bad operator in mult_term ()"));
  675.       abort ();
  676.     }
  677.     }
  678.   if (op == ERROR)
  679.     return UNKNOWN_INPUT;
  680.  
  681.   eval_undo ();
  682.   return NO_ERROR;
  683. }
  684.  
  685. static eval_error
  686. exp_term (eval_token et, eval_t *v1)
  687. {
  688.   register eval_t result;
  689.   eval_t v2;
  690.   eval_error er;
  691.  
  692.   if ((er = unary_term (et, v1)) != NO_ERROR)
  693.     return er;
  694.   result = *v1;
  695.  
  696.   while ((et = eval_lex (&v2)) == EXPONENT)
  697.     {
  698.       et = eval_lex (&v2);
  699.       if (et == ERROR)
  700.     return UNKNOWN_INPUT;
  701.  
  702.       if ((er = exp_term (et, &v2)) != NO_ERROR)
  703.     return er;
  704.  
  705.       result = 1;
  706.       while (v2-- > 0)
  707.     result *= *v1;
  708.       *v1 = result;
  709.     }
  710.   if (et == ERROR)
  711.     return UNKNOWN_INPUT;
  712.  
  713.   eval_undo ();
  714.   return NO_ERROR;
  715. }
  716.  
  717. static eval_error
  718. unary_term (eval_token et, eval_t *v1)
  719. {
  720.   eval_token et2 = et;
  721.   eval_error er;
  722.  
  723.   if (et == PLUS || et == MINUS)
  724.     {
  725.       et2 = eval_lex (v1);
  726.       if (et2 == ERROR)
  727.     return UNKNOWN_INPUT;
  728.  
  729.       if ((er = simple_term (et2, v1)) != NO_ERROR)
  730.     return er;
  731.  
  732.       if (et == MINUS)
  733.     *v1 = -*v1;
  734.     }
  735.   else
  736.     if ((er = simple_term (et, v1)) != NO_ERROR)
  737.       return er;
  738.  
  739.   return NO_ERROR;
  740. }
  741.  
  742. static eval_error
  743. simple_term (eval_token et, eval_t *v1)
  744. {
  745.   eval_t v2;
  746.   eval_error er;
  747.  
  748.   switch (et)
  749.     {
  750.     case LEFTP:
  751.       et = eval_lex (v1);
  752.       if (et == ERROR)
  753.     return UNKNOWN_INPUT;
  754.  
  755.       if ((er = logical_or_term (et, v1)) != NO_ERROR)
  756.     return er;
  757.  
  758.       et = eval_lex (&v2);
  759.       if (et == ERROR)
  760.     return UNKNOWN_INPUT;
  761.  
  762.       if (et != RIGHTP)
  763.     return MISSING_RIGHT;
  764.  
  765.       break;
  766.  
  767.     case NUMBER:
  768.       break;
  769.  
  770.     default:
  771.       return SYNTAX_ERROR;
  772.     }
  773.   return NO_ERROR;
  774. }
  775.