home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume44 / a32src / part02 / cexpr.c next >
Encoding:
C/C++ Source or Header  |  1994-09-23  |  7.4 KB  |  303 lines
  1. /*    cexpr.c - constant-expression parser    */
  2.  
  3. /*
  4.     cexpr(string,symb) will evaluate any valid expression containing
  5.     constants and the C-language arithmetic operators. The expression
  6.     is terminated by ',', ';', '\n', or '\0'.
  7.     Character constants ('C') are permitted.
  8.     The value of the expression is returned in value, cexpr() returns
  9.     0 for success, ERR for errors, UNDEF for un-defined symbols.
  10.     Square brackets ('[', ']') are identical to parentheses ('(', ')').
  11.     symb=0 indicates symbols are not allowed (used by the pre-processor),
  12.     symb!=0 indicates symbols are allowed.
  13.  
  14.     Interface:
  15.         The following extern-s are used:
  16.  
  17.             long value;            all values passed here
  18.             int sym_val(string,&ptr)    gets symbol values
  19.             int isident(char)        test for legal chars
  20.                             in identifier
  21.         The follwing extern-s are defined:
  22.  
  23.             char *expr_end;            set to point to the
  24.                             char that
  25.                             ended the expression
  26.         
  27.  
  28.  
  29.     Known Bug: the ternary conditional operator (a?b:c) CANNOT be
  30.     nested without parentheses. This is an inherent limitation
  31.     of the parsing method.
  32.  
  33.     Token        Value    Precedence    Operation
  34.     -----        -----    ----------    ---------
  35.     ( [        28    28        parenthesis
  36.     !        27    25        logical NOT
  37.     ~        26    25        bitwise NOT
  38.     - (unary)    25    25        arithmetic NEG
  39.     *        24    22        multiply
  40.     /        23    22        divide
  41.     %        22    22        remainder
  42.     +        20    20        addition
  43.     -        20    20        subtraction
  44.     <<        19    18        left-shift (0 fill)
  45.     >>        18    18        right-shift (sign extend)
  46.     <        17    14        less-than
  47.     <=        16    14        less-than-or-equal
  48.     >        15    14        greater-than
  49.     >=        14    14        greater-than-or-equal
  50.     ==        13    12        equal-to
  51.     !=        12    12        not-equal-to
  52.     &        11    11        bitwise AND
  53.     ^        10    10        bitwise XOR
  54.     |        9    9        bitwise OR
  55.     &&        8    8        logical AND
  56.     ||        7    7        logical OR
  57.     :        6    6        conditional-op (a ? b : c)
  58.     ?        5    5
  59.     :-delayed    4    4            "        "
  60.     ?-delayed    3    3            "        "
  61.     ) ]        2    2        parenthesis
  62.     BOS        1    1        Beginning-Of-Statement
  63.     EOS        0    0        End-Of-Statement
  64.     <constant>    -1    <none>        integer (decimal, octal, hex)
  65.     <symbol>    -2    <none>        symbol (value treated as const)
  66.     <undef-symb>    -3    <none>        undefined symbol (treated as 0)
  67.     <error>        -99    <none>        illegal token
  68.  
  69.     Note that '(' is pushed onto the operator-stack as a ')',
  70.     so the precedence is correct when it is interpreted.
  71. */
  72. /**************
  73.  
  74. THIS SOFTWARE IS RELEASED "AS IS", WITH NO WARRANTY EXPRESSED OR IMPLIED.
  75. This software is copyright 1984, 1991, 1992, 1993, 1994 by Tom Roberts.
  76. License is granted for unlimited distribution, as long as the following
  77. conditions are met:
  78.   A. This notice is preserved intact.
  79.   B. No charge is made for the software (other than a reasonable
  80.      distribution/duplication fee).
  81.  
  82. ***************/
  83.  
  84. #include "port.h"
  85.  
  86. #define BOS 1
  87. #define EOS 0
  88. #define CONST (-1)
  89. #define SYMB (-2)
  90. #define UNDEF (-3)
  91. #define ERR (-99)
  92.  
  93. #define MAX_STACK 16
  94.  
  95. extern long value;    /* all values are passed here */
  96.  
  97. char *expr_end;        /* set to terminating char */
  98.  
  99.  
  100. static char prec[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,12,14,14,14,14,18,18,
  101.               20,20,22,22,22,25,25,25,28};
  102. static char op_stack[MAX_STACK+1], *op_sp;
  103. static long val_stack[MAX_STACK+1], *val_sp;
  104. static char *nextch;
  105. static int last_token;
  106. static int symb_ok;
  107. static int cexpr_lex();
  108.  
  109. int
  110. cexpr(string,symb)
  111. char *string;
  112. int symb;
  113. {
  114.     BEST int op;
  115.     long temp, temp1;
  116.     BEST int iop;
  117.     BEST int undef_sym;
  118.  
  119.     /* permit an initial '+' */
  120.     if(*string == '+')
  121.         ++string;
  122.     undef_sym = 0;
  123.     nextch = string;
  124.     symb_ok = symb;
  125.     expr_end = "";
  126.  
  127.     op_sp = op_stack;
  128.     val_sp = val_stack;
  129.  
  130.     op = *op_sp = BOS;
  131.     *val_sp = 0;
  132.  
  133.     for(;;) {
  134. next_op:    last_token = op;
  135.         if( (op_sp-op_stack) < 0 || (val_sp-val_stack) < 0)
  136.             goto err;
  137.         op = cexpr_lex();
  138.         if(op == CONST || op == SYMB || op == UNDEF) {
  139.             if(val_sp < &val_stack[MAX_STACK])
  140.                 *(++val_sp) = value;
  141.             else
  142.                 goto err;
  143.             if(op == UNDEF)
  144.                 ++undef_sym;
  145.         } else if(op < 0) {
  146.             goto err;
  147.         } else {
  148.             while (prec[op] <= prec[*op_sp]) {
  149.             iop = *op_sp--;
  150.             switch(iop) {
  151.             case 0: goto err;
  152.                 /* allow null-string (return 0) */
  153.             case 1: if(val_sp != &val_stack[1] && nextch != string)
  154.                     goto err;
  155.                 value = *val_sp;
  156.                 expr_end = nextch;
  157.                 if(undef_sym) {
  158.                     value = 0x80000000L;
  159.                     return(UNDEF);
  160.                 }
  161.                 return(0);
  162.             case 2:    if(op != 2) goto err;
  163.                 goto next_op;
  164.             case 3:    goto err;
  165.             case 4:    if(*op_sp-- != 3) goto err;
  166.                 temp = *val_sp--;
  167.                 temp1= *val_sp--;
  168.                 *val_sp = *val_sp ? temp1 : temp;
  169.                 break;
  170.             case 5:    goto err;
  171.             case 6:    goto err;
  172.             case 7:    temp = *val_sp--; *val_sp = *val_sp || temp;
  173.                 break;
  174.             case 8:    temp = *val_sp--; *val_sp = *val_sp && temp;
  175.                 break;
  176.             case 9:    temp = *val_sp--; *val_sp |= temp; break;
  177.             case 10:temp = *val_sp--; *val_sp ^= temp; break;
  178.             case 11:temp = *val_sp--; *val_sp &= temp; break;
  179.             case 12:temp = *val_sp--; *val_sp = *val_sp != temp;
  180.                 break;
  181.             case 13:temp = *val_sp--; *val_sp = *val_sp == temp;
  182.                 break;
  183.             case 14:temp = *val_sp--; *val_sp = *val_sp >= temp;
  184.                 break;
  185.             case 15:temp = *val_sp--; *val_sp = *val_sp > temp;
  186.                 break;
  187.             case 16:temp = *val_sp--; *val_sp = *val_sp <= temp;
  188.                 break;
  189.             case 17:temp = *val_sp--; *val_sp = *val_sp < temp;
  190.                 break;
  191.             case 18:temp = *val_sp--; *val_sp >>= temp; break;
  192.             case 19:temp = *val_sp--; *val_sp <<= temp; break;
  193.             case 20:temp = *val_sp--; *val_sp -= temp; break;
  194.             case 21:temp = *val_sp--; *val_sp += temp; break;
  195.             case 22:temp = *val_sp--; if(temp == 0l) goto div_0;
  196.                           *val_sp %= temp; break;
  197.             case 23:temp = *val_sp--; if(temp == 0l) goto div_0;
  198.                           *val_sp /= temp; break;
  199.             case 24:temp = *val_sp--; *val_sp *= temp; break;
  200.             case 25:*val_sp = - *val_sp; break;
  201.             case 26:*val_sp = ~ *val_sp; break;
  202.             case 27:*val_sp = ! *val_sp; break;
  203.             case 28:goto err;
  204.             default:goto err;
  205.             }
  206.             }
  207.             if(op_sp < &op_stack[MAX_STACK]) {
  208.             if(op == 28)    /* "(" -> ")" */
  209.                 op = 2;
  210.             if(op == 5)    /* "?" -> "?-delayed" */
  211.                 op = 3;
  212.             if(op == 6)    /* ":" -> ":-delayed" */
  213.                 op = 4;
  214.             *(++op_sp) = op;
  215.             } else {
  216.             goto err;
  217.             }
  218.         }
  219.     }
  220. err:
  221.     value = 0l;
  222.     return(ERR);
  223. div_0:
  224.     value = 0l;
  225.     return(ERR);
  226. }
  227.  
  228. static int
  229. cexpr_lex()
  230. {
  231.     extern long strtol();
  232.     BEST int ich;
  233.  
  234.     while(isspace(*nextch)) {
  235.         if(*nextch == '\n')
  236.             return(EOS);
  237.         ++nextch;
  238.     }
  239.  
  240.     if(isdigit(*nextch)) {
  241.         value = strtol(nextch,&nextch,0);
  242.         return(CONST);
  243.     } else if(isident(*nextch)) {
  244.         if(!symb_ok)
  245.             return(ERR);
  246.         if(sym_val(nextch,&nextch))
  247.             return(UNDEF);
  248.         return(SYMB);
  249.     }
  250.  
  251.     ich = *nextch++;
  252.     switch(ich) {
  253.     /* '\n' detected above */
  254.     case ';':
  255.     case ',':
  256.     case '\0':    --nextch; return(EOS);
  257.     case ']':
  258.     case ')':    return(2);
  259.     case '?':    return(5);
  260.     case ':':    return(6);
  261.     case '|':    if(*nextch == '|') {++nextch; return(7);}
  262.             return(9);
  263.     case '^':    return(10);
  264.     case '&':    if(*nextch == '&') {++nextch; return(8);}
  265.             return(11);
  266.     case '=':    if(*nextch++ == '=') return(13);
  267.             goto err;
  268.     case '>':    if(*nextch == '=') {++nextch; return(14);}
  269.             if(*nextch == '>') {++nextch; return(18);}
  270.             return(15);
  271.     case '<':    if(*nextch == '=') {++nextch; return(16);}
  272.             if(*nextch == '<') {++nextch; return(19);}
  273.             return(17);
  274.     case '-':    if(last_token > 0)
  275.                 return(25);
  276.             return(20);
  277.     case '+':    return(21);
  278.     case '%':    return(22);
  279.     case '/':    return(23);
  280.     case '*':    return(24);
  281.     case '~':    return(26);
  282.     case '!':    if(*nextch == '=') {++nextch; return(12);}
  283.             return(27);
  284.     case '[':
  285.     case '(':    return(28);
  286.     case '\'':    ich = *nextch++; ich &= 0xFF;
  287.             if(ich == '\\') {
  288.                 ich = *nextch++; ich &= 0xFF;
  289.                 switch(ich) {
  290.                 case 'n':  ich = '\n'; break;
  291.                 case 'r':  ich = '\r'; break;
  292.                 case 'f':  ich = '\f'; break;
  293.                 case '0':  ich = '\0'; break;
  294.                 }
  295.             }
  296.             if(*nextch++ != '\'')
  297.                 goto err;
  298.             value = ich;
  299.             return(CONST);
  300.     }
  301. err:    return(ERR);
  302. }
  303.