1 /*********************************************************************** 2 * * 3 * This software is part of the ast package * 4 * Copyright (c) 1985-2007 AT&T Knowledge Ventures * 5 * and is licensed under the * 6 * Common Public License, Version 1.0 * 7 * by AT&T Knowledge Ventures * 8 * * 9 * A copy of the License is available at * 10 * http://www.opensource.org/licenses/cpl1.0.txt * 11 * (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) * 12 * * 13 * Information and Software Systems Research * 14 * AT&T Research * 15 * Florham Park NJ * 16 * * 17 * Glenn Fowler <gsf@research.att.com> * 18 * David Korn <dgk@research.att.com> * 19 * Phong Vo <kpv@research.att.com> * 20 * * 21 ***********************************************************************/ 22 #pragma prototyped 23 /* 24 * G. S. Fowler 25 * D. G. Korn 26 * AT&T Bell Laboratories 27 * 28 * long integer arithmetic expression evaluator 29 * long constants may be represented as: 30 * 31 * 0ooo octal 32 * 0[xX]hhh hexadecimal 33 * ddd decimal 34 * n#ccc base n, 2 <= b <= 36 35 * 36 * NOTE: all operands are evaluated as both the parse 37 * and evaluation are done on the fly 38 */ 39 40 #include <ast.h> 41 #include <ctype.h> 42 43 #define getchr(ex) (*(ex)->nextchr++) 44 #define peekchr(ex) (*(ex)->nextchr) 45 #define ungetchr(ex) ((ex)->nextchr--) 46 47 #define error(ex,msg) return(seterror(ex,msg)) 48 49 typedef struct /* expression handle */ 50 { 51 char* nextchr; /* next expression char */ 52 char* errchr; /* next char after error */ 53 char* errmsg; /* error message text */ 54 long (*convert)(const char*, char**, void*); 55 void* handle; /* user convert handle */ 56 } Expr_t; 57 58 /* 59 * set error message string 60 */ 61 62 static long 63 seterror(register Expr_t* ex, char* msg) 64 { 65 if (!ex->errmsg) ex->errmsg = msg; 66 ex->errchr = ex->nextchr; 67 ex->nextchr = ""; 68 return(0); 69 } 70 71 /* 72 * evaluate a subexpression with precedence 73 */ 74 75 static long 76 expr(register Expr_t* ex, register int precedence) 77 { 78 register int c; 79 register long n; 80 register long x; 81 char* pos; 82 int operand = 1; 83 84 while (c = getchr(ex), isspace(c)); 85 switch (c) 86 { 87 case 0: 88 ungetchr(ex); 89 if (!precedence) return(0); 90 error(ex, "more tokens expected"); 91 case '-': 92 n = -expr(ex, 13); 93 break; 94 case '+': 95 n = expr(ex, 13); 96 break; 97 case '!': 98 n = !expr(ex, 13); 99 break; 100 case '~': 101 n = ~expr(ex, 13); 102 break; 103 default: 104 ungetchr(ex); 105 n = 0; 106 operand = 0; 107 break; 108 } 109 for (;;) 110 { 111 switch (c = getchr(ex)) 112 { 113 case 0: 114 goto done; 115 case ')': 116 if (!precedence) error(ex, "too many )'s"); 117 goto done; 118 case '(': 119 n = expr(ex, 1); 120 if (getchr(ex) != ')') 121 { 122 ungetchr(ex); 123 error(ex, "closing ) expected"); 124 } 125 gotoperand: 126 if (operand) error(ex, "operator expected"); 127 operand = 1; 128 continue; 129 case '?': 130 if (precedence > 1) goto done; 131 if (peekchr(ex) == ':') 132 { 133 getchr(ex); 134 x = expr(ex, 2); 135 if (!n) n = x; 136 } 137 else 138 { 139 x = expr(ex, 2); 140 if (getchr(ex) != ':') 141 { 142 ungetchr(ex); 143 error(ex, ": expected for ? operator"); 144 } 145 if (n) 146 { 147 n = x; 148 expr(ex, 2); 149 } 150 else n = expr(ex, 2); 151 } 152 break; 153 case ':': 154 goto done; 155 case '|': 156 if (peekchr(ex) == '|') 157 { 158 if (precedence > 2) goto done; 159 getchr(ex); 160 x = expr(ex, 3); 161 n = n || x; 162 } 163 else 164 { 165 if (precedence > 4) goto done; 166 x = expr(ex, 5); 167 n |= x; 168 } 169 break; 170 case '^': 171 if (precedence > 5) goto done; 172 x = expr(ex, 6); 173 n ^= x; 174 break; 175 case '&': 176 if (peekchr(ex) == '&') 177 { 178 if (precedence > 3) goto done; 179 getchr(ex); 180 x = expr(ex, 4); 181 n = n && x; 182 } 183 else 184 { 185 if (precedence > 6) goto done; 186 x = expr(ex, 7); 187 n &= x; 188 } 189 break; 190 case '=': 191 case '!': 192 if (peekchr(ex) != '=') error(ex, "operator syntax error"); 193 if (precedence > 7) goto done; 194 getchr(ex); 195 x = expr(ex, 8); 196 if (c == '=') n = n == x; 197 else n = n != x; 198 break; 199 case '<': 200 case '>': 201 if (peekchr(ex) == c) 202 { 203 if (precedence > 9) goto done; 204 getchr(ex); 205 x = expr(ex, 10); 206 if (c == '<') n <<= x; 207 else n >>= x; 208 } 209 else 210 { 211 if (precedence > 8) goto done; 212 if (peekchr(ex) == '=') 213 { 214 getchr(ex); 215 x = expr(ex, 9); 216 if (c == '<') n = n <= x; 217 else n = n >= x; 218 } 219 else 220 { 221 x = expr(ex, 9); 222 if (c == '<') n = n < x; 223 else n = n > x; 224 } 225 } 226 break; 227 case '+': 228 case '-': 229 if (precedence > 10) goto done; 230 x = expr(ex, 11); 231 if (c == '+') n += x; 232 else n -= x; 233 break; 234 case '*': 235 case '/': 236 case '%': 237 if (precedence > 11) goto done; 238 x = expr(ex, 12); 239 if (c == '*') n *= x; 240 else if (x == 0) error(ex, "divide by zero"); 241 else if (c == '/') n /= x; 242 else n %= x; 243 break; 244 default: 245 if (isspace(c)) continue; 246 pos = --ex->nextchr; 247 if (isdigit(c)) n = strton(ex->nextchr, &ex->nextchr, NiL, 0); 248 else if (ex->convert) n = (*ex->convert)(ex->nextchr, &ex->nextchr, ex->handle); 249 if (ex->nextchr == pos) error(ex, "syntax error"); 250 goto gotoperand; 251 } 252 if (ex->errmsg) return(0); 253 if (!operand) error(ex, "operand expected"); 254 } 255 done: 256 ungetchr(ex); 257 if (!operand) error(ex, "operand expected"); 258 return(n); 259 } 260 261 /* 262 * evaluate an integer arithmetic expression in s 263 * 264 * (long)(*convert)(const char* string, char** end, void* handle) 265 * is a user supplied conversion routine that is called when unknown 266 * chars are encountered; string points to the part to be 267 * converted and end is adjusted to point to the next non-converted 268 * character; if string is 0 then end points to an error message string 269 * 270 * NOTE: (*convert)() may call strexpr(ex, ) 271 */ 272 273 long 274 strexpr(const char* s, char** end, long(*convert)(const char*, char**, void*), void* handle) 275 { 276 long n; 277 Expr_t ex; 278 279 ex.nextchr = (char*)s; 280 ex.errmsg = 0; 281 ex.convert = convert; 282 ex.handle = handle; 283 n = expr(&ex, 0); 284 if (peekchr(&ex) == ':') 285 seterror(&ex, "invalid use of :"); 286 if (ex.errmsg) 287 { 288 if (convert) (*convert)(NiL, &ex.errmsg, handle); 289 ex.nextchr = ex.errchr; 290 n = 0; 291 } 292 if (end) *end = ex.nextchr; 293 return(n); 294 } 295