home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / m4-1.0.3 / eval.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-12-19  |  10.4 KB  |  611 lines
  1. /*
  2.  * GNU m4 -- A simple macro processor
  3.  * Copyright (C) 1989-1992 Free Software Foundation, Inc.
  4.  *
  5.  * This program is free software; you can redistribute it and/or modify
  6.  * it under the terms of the GNU General Public License as published by
  7.  * the Free Software Foundation; either version 2, or (at your option)
  8.  * any later version.
  9.  *
  10.  * This program is distributed in the hope that it will be useful,
  11.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.  * GNU General Public License for more details.
  14.  *
  15.  * You should have received a copy of the GNU General Public License
  16.  * along with this program; if not, write to the Free Software
  17.  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  */
  19.  
  20. /*
  21.  * This file contains the functions to evaluate integer expressions for
  22.  * the "eval" macro.  It is a little, fairly self-contained module, with
  23.  * its own scanner, and a recursive descent parser.  The only entry
  24.  * point is evaluate ().
  25.  */
  26.  
  27. #include "m4.h"
  28.  
  29. /*
  30.  * Evaluates token types.
  31.  */
  32. typedef enum eval_token
  33.   {
  34.     ERROR,
  35.     PLUS, MINUS,
  36.     EXPONENT,
  37.     TIMES, DIVIDE, MODULO,
  38.     EQ, NOTEQ, GT, GTEQ, LS, LSEQ,
  39.     NOT,
  40.     LAND, LOR,
  41.     AND, OR,
  42.     LEFTP, RIGHTP,
  43.     NUMBER, EOTEXT
  44.   }
  45. eval_token;
  46.  
  47. /*
  48.  * Error types.
  49.  */
  50. typedef enum eval_error
  51.   {
  52.     NO_ERROR,
  53.     MISSING_RIGHT,
  54.     SYNTAX_ERROR,
  55.     UNKNOWN_INPUT,
  56.     DIVIDE_ZERO,
  57.     MODULO_ZERO
  58.   }
  59. eval_error;
  60.  
  61. static eval_error logical_or_term ();
  62. static eval_error logical_and_term ();
  63. static eval_error or_term ();
  64. static eval_error and_term ();
  65. static eval_error not_term ();
  66. static eval_error cmp_term ();
  67. static eval_error add_term ();
  68. static eval_error mult_term ();
  69. static eval_error exp_term ();
  70. static eval_error unary_term ();
  71. static eval_error simple_term ();
  72.  
  73. /*
  74.  * Lexical functions.
  75.  */
  76.  
  77. /* Pointer to next character of input text.  */
  78. static char *eval_text;
  79.  
  80. /* Value of eval_text, from before last call of eval_lex ().  This is so we
  81.    can back up, if we have read too much.  */
  82. static char *last_text;
  83.  
  84. static void
  85. eval_init_lex (char *text)
  86. {
  87.   eval_text = text;
  88.   last_text = NULL;
  89. }
  90.  
  91. static void
  92. eval_undo (void)
  93. {
  94.   eval_text = last_text;
  95. }
  96.  
  97.  
  98. /* VAL is numerical value, if any.  */
  99.  
  100. static eval_token
  101. eval_lex (int *val)
  102. {
  103.   while (isspace (*eval_text))
  104.     eval_text++;
  105.  
  106.   last_text = eval_text;
  107.  
  108.   if (*eval_text == '\0')
  109.     return EOTEXT;
  110.  
  111.   if (isdigit (*eval_text))
  112.     {
  113.       char *digits, *tmp;
  114.       int base;
  115.  
  116.       if (*eval_text == '0')
  117.     {
  118.       if (*++eval_text == 'x' || *eval_text == 'X')
  119.         {
  120.           base = 16;
  121.           digits = "0123456789abcdef";
  122.           eval_text++;
  123.         }
  124.       else
  125.         {
  126.           base = 8;
  127.           digits = "01234567";
  128.         }
  129.     }
  130.       else
  131.     {
  132.       base = 10;
  133.       digits = "0123456789";
  134.     }
  135.       (*val) = 0;
  136.       while (*eval_text && (tmp = index (digits, *eval_text)) != NULL)
  137.     {
  138.       (*val) = (*val) * base + (tmp - digits);
  139.       eval_text++;
  140.     }
  141.       return NUMBER;
  142.     }
  143.  
  144.   switch (*eval_text++)
  145.     {
  146.     case '+':
  147.       return PLUS;
  148.     case '-':
  149.       return MINUS;
  150.     case '*':
  151.       if (*eval_text == '*')
  152.     {
  153.       eval_text++;
  154.       return EXPONENT;
  155.     }
  156.       else
  157.     return TIMES;
  158.     case '^':
  159.       return EXPONENT;
  160.     case '/':
  161.       return DIVIDE;
  162.     case '%':
  163.       return MODULO;
  164.     case '=':
  165.       if (*eval_text == '=')
  166.     eval_text++;
  167.       return EQ;
  168.     case '!':
  169.       if (*eval_text == '=')
  170.     {
  171.       eval_text++;
  172.       return NOTEQ;
  173.     }
  174.       else
  175.     return NOT;
  176.     case '>':
  177.       if (*eval_text == '=')
  178.     {
  179.       eval_text++;
  180.       return GTEQ;
  181.     }
  182.       else
  183.     return GT;
  184.     case '<':
  185.       if (*eval_text == '=')
  186.     {
  187.       eval_text++;
  188.       return LSEQ;
  189.     }
  190.       else
  191.     return LS;
  192.     case '&':
  193.       if (*eval_text == '&')
  194.     {
  195.       eval_text++;
  196.       return LAND;
  197.     }
  198.       else
  199.     return AND;
  200.     case '|':
  201.       if (*eval_text == '|')
  202.     {
  203.       eval_text++;
  204.       return LOR;
  205.     }
  206.       else
  207.     return OR;
  208.     case '(':
  209.       return LEFTP;
  210.     case ')':
  211.       return RIGHTP;
  212.     default:
  213.       return ERROR;
  214.     }
  215. }
  216.  
  217. /*
  218.  * Main entry point, called from "eval".
  219.  */
  220. boolean
  221. evaluate (char *expr, int *val)
  222. {
  223.   eval_token et;
  224.   eval_error err;
  225.  
  226.   eval_init_lex (expr);
  227.   et = eval_lex (val);
  228.   err = logical_or_term (et, val);
  229.  
  230.   switch (err)
  231.     {
  232.     case NO_ERROR:
  233.       break;
  234.     case MISSING_RIGHT:
  235.       error ("bad expression in eval (missing right paren): %s", expr);
  236.       break;
  237.     case SYNTAX_ERROR:
  238.       error ("bad expression in eval: %s", expr);
  239.       break;
  240.     case UNKNOWN_INPUT:
  241.       error ("bad expression in eval (bad input): %s", expr);
  242.       break;
  243.     case DIVIDE_ZERO:
  244.       error ("divide by zero in eval: %s", expr);
  245.       break;
  246.     case MODULO_ZERO:
  247.       error ("modulo by zero in eval: %s", expr);
  248.       break;
  249.     default:
  250.       internal_error ("Bad error code in evaluate ()");
  251.       break;
  252.     }
  253.  
  254.   return (boolean) (err != NO_ERROR);
  255. }
  256.  
  257. /*
  258.  * Recursive descent parser.
  259.  */
  260. static eval_error
  261. logical_or_term (eval_token et, int *v1)
  262. {
  263.   int v2;
  264.   eval_error er;
  265.  
  266.   if ((er = logical_and_term (et, v1)) != NO_ERROR)
  267.     return er;
  268.  
  269.   while ((et = eval_lex (&v2)) == LOR)
  270.     {
  271.       et = eval_lex (&v2);
  272.       if (et == ERROR)
  273.     return UNKNOWN_INPUT;
  274.  
  275.       if ((er = logical_and_term (et, &v2)) != NO_ERROR)
  276.     return er;
  277.  
  278.       *v1 = *v1 || v2;
  279.     }
  280.   if (et == ERROR)
  281.     return UNKNOWN_INPUT;
  282.  
  283.   eval_undo ();
  284.   return NO_ERROR;
  285. }
  286.  
  287. static eval_error
  288. logical_and_term (eval_token et, int *v1)
  289. {
  290.   int v2;
  291.   eval_error er;
  292.  
  293.   if ((er = or_term (et, v1)) != NO_ERROR)
  294.     return er;
  295.  
  296.   while ((et = eval_lex (&v2)) == LAND)
  297.     {
  298.       et = eval_lex (&v2);
  299.       if (et == ERROR)
  300.     return UNKNOWN_INPUT;
  301.  
  302.       if ((er = or_term (et, &v2)) != NO_ERROR)
  303.     return er;
  304.  
  305.       *v1 = *v1 && v2;
  306.     }
  307.   if (et == ERROR)
  308.     return UNKNOWN_INPUT;
  309.  
  310.   eval_undo ();
  311.   return NO_ERROR;
  312. }
  313.  
  314. static eval_error
  315. or_term (eval_token et, int *v1)
  316. {
  317.   int v2;
  318.   eval_error er;
  319.  
  320.   if ((er = and_term (et, v1)) != NO_ERROR)
  321.     return er;
  322.  
  323.   while ((et = eval_lex (&v2)) == OR)
  324.     {
  325.       et = eval_lex (&v2);
  326.       if (et == ERROR)
  327.     return UNKNOWN_INPUT;
  328.  
  329.       if ((er = and_term (et, &v2)) != NO_ERROR)
  330.     return er;
  331.  
  332.       *v1 = *v1 | v2;
  333.     }
  334.   if (et == ERROR)
  335.     return UNKNOWN_INPUT;
  336.  
  337.   eval_undo ();
  338.   return NO_ERROR;
  339. }
  340.  
  341. static eval_error
  342. and_term (eval_token et, int *v1)
  343. {
  344.   int v2;
  345.   eval_error er;
  346.  
  347.   if ((er = not_term (et, v1)) != NO_ERROR)
  348.     return er;
  349.  
  350.   while ((et = eval_lex (&v2)) == AND)
  351.     {
  352.       et = eval_lex (&v2);
  353.       if (et == ERROR)
  354.     return UNKNOWN_INPUT;
  355.  
  356.       if ((er = not_term (et, &v2)) != NO_ERROR)
  357.     return er;
  358.  
  359.       *v1 = *v1 & v2;
  360.     }
  361.   if (et == ERROR)
  362.     return UNKNOWN_INPUT;
  363.  
  364.   eval_undo ();
  365.   return NO_ERROR;
  366. }
  367.  
  368. static eval_error
  369. not_term (eval_token et, int *v1)
  370. {
  371.   eval_error er;
  372.  
  373.   if (et == NOT)
  374.     {
  375.       et = eval_lex (v1);
  376.       if (et == ERROR)
  377.     return UNKNOWN_INPUT;
  378.  
  379.       if ((er = not_term (et, v1)) != NO_ERROR)
  380.     return er;
  381.       *v1 = !*v1;
  382.     }
  383.   else
  384.     if ((er = cmp_term (et, v1)) != NO_ERROR)
  385.       return er;
  386.  
  387.   return NO_ERROR;
  388. }
  389.  
  390. static eval_error
  391. cmp_term (eval_token et, int *v1)
  392. {
  393.   eval_token op;
  394.   int v2;
  395.   eval_error er;
  396.  
  397.   if ((er = add_term (et, v1)) != NO_ERROR)
  398.     return er;
  399.  
  400.   while ((op = eval_lex (&v2)) == EQ || op == NOTEQ
  401.      || op == GT || op == GTEQ
  402.      || op == LS || op == LSEQ)
  403.     {
  404.  
  405.       et = eval_lex (&v2);
  406.       if (et == ERROR)
  407.     return UNKNOWN_INPUT;
  408.  
  409.       if ((er = add_term (et, &v2)) != NO_ERROR)
  410.     return er;
  411.  
  412.       switch (op)
  413.     {
  414.     case EQ:
  415.       *v1 = *v1 == v2;
  416.       break;
  417.     case NOTEQ:
  418.       *v1 = *v1 != v2;
  419.       break;
  420.     case GT:
  421.       *v1 = *v1 > v2;
  422.       break;
  423.     case GTEQ:
  424.       *v1 = *v1 >= v2;
  425.       break;
  426.     case LS:
  427.       *v1 = *v1 < v2;
  428.       break;
  429.     case LSEQ:
  430.       *v1 = *v1 <= v2;
  431.       break;
  432.     default:
  433.       internal_error ("Bad comparison operator in cmp_term ()");
  434.       break;
  435.     }
  436.     }
  437.   if (op == ERROR)
  438.     return UNKNOWN_INPUT;
  439.  
  440.   eval_undo ();
  441.   return NO_ERROR;
  442. }
  443.  
  444. static eval_error
  445. add_term (eval_token et, int *v1)
  446. {
  447.   eval_token op;
  448.   int v2;
  449.   eval_error er;
  450.  
  451.   if ((er = mult_term (et, v1)) != NO_ERROR)
  452.     return er;
  453.  
  454.   while ((op = eval_lex (&v2)) == PLUS || op == MINUS)
  455.     {
  456.       et = eval_lex (&v2);
  457.       if (et == ERROR)
  458.     return UNKNOWN_INPUT;
  459.  
  460.       if ((er = mult_term (et, &v2)) != NO_ERROR)
  461.     return er;
  462.  
  463.       if (op == PLUS)
  464.     *v1 = *v1 + v2;
  465.       else
  466.     *v1 = *v1 - v2;
  467.     }
  468.   if (op == ERROR)
  469.     return UNKNOWN_INPUT;
  470.  
  471.   eval_undo ();
  472.   return NO_ERROR;
  473. }
  474.  
  475. static eval_error
  476. mult_term (eval_token et, int *v1)
  477. {
  478.   eval_token op;
  479.   int v2;
  480.   eval_error er;
  481.  
  482.   if ((er = exp_term (et, v1)) != NO_ERROR)
  483.     return er;
  484.  
  485.   while ((op = eval_lex (&v2)) == TIMES || op == DIVIDE || op == MODULO)
  486.     {
  487.       et = eval_lex (&v2);
  488.       if (et == ERROR)
  489.     return UNKNOWN_INPUT;
  490.  
  491.       if ((er = exp_term (et, &v2)) != NO_ERROR)
  492.     return er;
  493.  
  494.       switch (op)
  495.     {
  496.     case TIMES:
  497.       *v1 = *v1 * v2;
  498.       break;
  499.     case DIVIDE:
  500.       if (v2 == 0)
  501.         return DIVIDE_ZERO;
  502.       else
  503.         *v1 = *v1 / v2;
  504.       break;
  505.     case MODULO:
  506.       if (v2 == 0)
  507.         return MODULO_ZERO;
  508.       else
  509.         *v1 = *v1 % v2;
  510.       break;
  511.     default:
  512.       internal_error ("Bad operator in mult_term ()");
  513.       break;
  514.     }
  515.     }
  516.   if (op == ERROR)
  517.     return UNKNOWN_INPUT;
  518.  
  519.   eval_undo ();
  520.   return NO_ERROR;
  521. }
  522.  
  523. static eval_error
  524. exp_term (eval_token et, int *v1)
  525. {
  526.   register int result;
  527.   int v2;
  528.   eval_error er;
  529.  
  530.   if ((er = unary_term (et, v1)) != NO_ERROR)
  531.     return er;
  532.   result = *v1;
  533.  
  534.   while ((et = eval_lex (&v2)) == EXPONENT)
  535.     {
  536.       et = eval_lex (&v2);
  537.       if (et == ERROR)
  538.     return UNKNOWN_INPUT;
  539.  
  540.       if ((er = exp_term (et, &v2)) != NO_ERROR)
  541.     return er;
  542.  
  543.       result = 1;
  544.       while (v2-- > 0)
  545.     result *= *v1;
  546.       *v1 = result;
  547.     }
  548.   if (et == ERROR)
  549.     return UNKNOWN_INPUT;
  550.  
  551.   eval_undo ();
  552.   return NO_ERROR;
  553. }
  554.  
  555. static eval_error
  556. unary_term (eval_token et, int *v1)
  557. {
  558.   eval_token et2 = et;
  559.   eval_error er;
  560.  
  561.   if (et == PLUS || et == MINUS)
  562.     {
  563.       et2 = eval_lex (v1);
  564.       if (et2 == ERROR)
  565.     return UNKNOWN_INPUT;
  566.  
  567.       if ((er = simple_term (et2, v1)) != NO_ERROR)
  568.     return er;
  569.  
  570.       if (et == MINUS)
  571.     *v1 = -*v1;
  572.     }
  573.   else
  574.     if ((er = simple_term (et, v1)) != NO_ERROR)
  575.       return er;
  576.  
  577.   return NO_ERROR;
  578. }
  579.  
  580. static eval_error
  581. simple_term (eval_token et, int *v1)
  582. {
  583.   int v2;
  584.   eval_error er;
  585.  
  586.   switch (et)
  587.     {
  588.     case LEFTP:
  589.       et = eval_lex (v1);
  590.       if (et == ERROR)
  591.     return UNKNOWN_INPUT;
  592.  
  593.       if ((er = logical_or_term (et, v1)) != NO_ERROR)
  594.     return er;
  595.  
  596.       et = eval_lex (&v2);
  597.       if (et == ERROR)
  598.     return UNKNOWN_INPUT;
  599.  
  600.       if (et != RIGHTP)
  601.     return MISSING_RIGHT;
  602.  
  603.       break;
  604.     case NUMBER:
  605.       break;
  606.     default:
  607.       return SYNTAX_ERROR;
  608.     }
  609.   return NO_ERROR;
  610. }
  611.