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