expr.cc

00001 /* expr.cc -- Expression Tree
00002    Copyright 2003 Free Software Foundation, Inc.
00003    Written by Stephane Carrez (stcarrez@nerim.fr)
00004 
00005 This file is part of GEL.
00006 
00007 GEL is free software; you can redistribute it and/or modify
00008 it under the terms of the GNU General Public License as published by
00009 the Free Software Foundation; either version 2, or (at your option)
00010 any later version.
00011 
00012 GEL is distributed in the hope that it will be useful,
00013 but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 GNU General Public License for more details.
00016 
00017 You should have received a copy of the GNU General Public License
00018 along with GEL; see the file COPYING.  If not, write to
00019 the Free Software Foundation, 59 Temple Place - Suite 330,
00020 Boston, MA 02111-1307, USA.  */
00021 
00022 #include "expr.h"
00023 
00024 Expression::~Expression()
00025 {
00026 }
00027 
00028 Value Expression::evaluate ()
00029 {
00030   return eval ();
00031 }
00032 
00033 // Evaluate an unary expression
00034 Value UnaryExpression::eval ()
00035 {
00036   Value v = expr_->evaluate ();
00037 
00038   if (type_ == T_MINUS)
00039     return -v;
00040   else if (type_ == T_NOT)
00041     return ~v;
00042   else
00043     return v;
00044 }
00045 
00046 // Evaluate a binary expression.
00047 Value BinaryExpression::eval ()
00048 {
00049   Value l = left_->evaluate ();
00050   Value r = right_->evaluate ();
00051 
00052   switch (type_)
00053     {
00054     case T_PLUS:
00055       return l + r;
00056     case T_MINUS:
00057       return l - r;
00058     case T_MUL:
00059       return l * r;
00060     case T_DIV:
00061       return l / r;
00062     case T_AND:
00063        return l & r;
00064     case T_OR:
00065        return l | r;
00066     case T_XOR:
00067        return l ^ r;
00068     default:
00069       return l;
00070     }
00071 }
00072 
00073 // Evaluate a final value
00074 Value ValueExpression::eval ()
00075 {
00076   return value_;
00077 }
00078 
00079 Value Expression::eval()
00080 {
00081   return 0;
00082 }
00083 
00084 void Expression::rewind (enum token t, const char*& line)
00085 {
00086   if (t == T_EOF)
00087     return;
00088   line--;
00089 }
00090 
00091 enum Expression::token Expression::get_token(const char*& line)
00092 {
00093   char c;
00094 
00095   do {
00096     c = *line++;
00097   } while (c == ' ' || c == '\t');
00098 
00099   switch (c)
00100     {
00101     case 0:
00102       line--;
00103       return T_EOF;
00104     case '-':
00105       return T_MINUS;
00106     case '+':
00107       return T_PLUS;
00108     case '*':
00109       return T_MUL;
00110     case '/':
00111       return T_DIV;
00112     case '|':
00113       return T_OR;
00114     case '&':
00115       return T_AND;
00116     case '^':
00117       return T_XOR;
00118     case '~':
00119       return T_NOT;
00120     case '(':
00121       return T_PARENT_OPEN;
00122     case ')':
00123       return T_PARENT_CLOSE;
00124     default:
00125       if (c >= '0' && c <= '9')
00126         return T_DIGIT;
00127       if (c >= 'a' && c <= 'z')
00128         return T_NAME;
00129       if (c >= 'A' && c <= 'Z')
00130         return T_NAME;
00131       return T_UNKNOWN;
00132     }
00133 }
00134 
00135 // Get the priority of the operator
00136 unsigned char Expression::get_priority(enum token t)
00137 {
00138   switch (t)
00139     {
00140     case T_MINUS:
00141     case T_PLUS:
00142       return 2;
00143       
00144     case T_AND:
00145     case T_OR:
00146     case T_XOR:
00147       return 1;
00148       
00149     case T_MUL:
00150     case T_DIV:
00151       return 3;
00152 
00153     case T_NOT:
00154       return 4;
00155 
00156     default:
00157       return 5;
00158     }
00159 }
00160    
00161 // Parse a unary expression and return it
00162 Expression* Expression::parse_unary(const char*& line)
00163 {
00164   enum token t = get_token (line);
00165   if (t == T_MINUS || t == T_NOT)
00166     {
00167       Expression* e = parse_binary (line, 0);
00168       if (e)
00169         e = new UnaryExpression (t, e);
00170       return e;
00171     }
00172   else
00173     {
00174       rewind (t, line);
00175       return parse_binary (line, 0);
00176     }
00177 }
00178 
00179 // Parse a binary expression and return it
00180 Expression* Expression::parse_binary(const char*& line, unsigned char prio)
00181 {
00182   Expression* current = parse_term (line);
00183   if (current == 0)
00184     return 0;
00185 
00186   while (1)
00187     {
00188       enum token t = get_token (line);
00189       if (t != T_MINUS && t != T_PLUS
00190           && t != T_MUL && t != T_DIV
00191           && t != T_AND && t != T_OR && t != T_XOR)
00192         {
00193           rewind (t, line);
00194           return current;
00195         }
00196 
00197       unsigned char p = Expression::get_priority (t);
00198       if (p < prio)
00199         {
00200           rewind (t, line);
00201           return current;
00202         }
00203       Expression* r;
00204       if (p > prio)
00205         r = parse_binary (line, p + 1);
00206       else
00207         r = parse_term (line);
00208 
00209       if (r == 0)
00210         {
00211           delete current;
00212           return 0;
00213         }
00214       current = new BinaryExpression (t, current, r);
00215     }
00216 }
00217 
00218 /* Try to translate a string into a number. We look first for hexadecimal
00219    format, octal and then decimal. If the string could be converted, the
00220    value is returned in `v' and the function returns 0. Otherwise, it
00221    returns -1. */
00222 // Parse a final integer value
00223 int
00224 Expression::get_value(const char*& buf, Value& v)
00225 {
00226   long value = 0;
00227   char c;
00228   
00229   if (!(*buf >= '0' && *buf <= '9'))
00230     return -1;
00231 
00232   /* Translate an hexadecimal value. */
00233   if (*buf == '0' && (buf[1] == 'x' || buf[1] == 'X'))
00234     {
00235       buf += 2;
00236       while ((c = *buf++))
00237         {
00238           if (c >= '0' && c <= '9')
00239             c = c - '0';
00240           else if (c >= 'a' && c <= 'f')
00241             c = c - 'a' + 10;
00242           else if (c >= 'A' && c <= 'F')
00243             c = c - 'A' + 10;
00244           else if (c >= 'a' && c <= 'z')
00245             return -1;
00246           else if (c >= 'A' && c <= 'Z')
00247             return -1;
00248           else
00249             {
00250               buf--;
00251               break;
00252             }
00253 
00254           value = (value << 4) | (long) ((unsigned) c);
00255         }
00256       v = value;
00257       return 0;
00258     }
00259   else
00260     {
00261       int sign = 0;
00262 
00263       if (buf[0] == '-')
00264         {
00265           sign = 1;
00266           buf++;
00267         }
00268       while ((c = *buf++) != 0)
00269         {
00270           if (c >= '0' && c <= '9')
00271             c = c - '0';
00272           else if (c >= 'a' && c <= 'Z')
00273             return -1;
00274           else if (c >= 'A' && c <= 'Z')
00275             return -1;
00276           else
00277             {
00278               buf--;
00279               break;
00280             }
00281           value = (value * 10) + (long) c;
00282         }
00283       if (sign)
00284         value = -value;
00285       v = value;
00286       return 0;
00287     }
00288   return -1;
00289 }
00290 
00291 // Parse a terminal expression
00292 Expression* Expression::parse_term(const char*& line)
00293 {
00294   enum token t = get_token (line);
00295   if (t == T_PARENT_OPEN)
00296     {
00297       Expression* e = parse_unary (line);
00298       if (e == 0)
00299         return 0;
00300 
00301       t = get_token (line);
00302       if (t == T_PARENT_CLOSE)
00303         return e;
00304 
00305       rewind (t, line);
00306       delete e;
00307       return 0;
00308     }
00309   if (t == T_DIGIT)
00310     {
00311       rewind (t, line);
00312       Value val;
00313       if (get_value (line, val) != 0)
00314         return 0;
00315 
00316       Expression* e = new ValueExpression (val);
00317       return e;
00318     }
00319   return 0;
00320 }
00321 
00322 Expression* Expression::parse(const char*& line)
00323 {
00324   return parse_unary (line);
00325 }
00326