1/*********************************************************************** 2* * 3* This software is part of the ast package * 4* Copyright (c) 1985-2011 AT&T Intellectual Property * 5* and is licensed under the * 6* Common Public License, Version 1.0 * 7* by AT&T Intellectual Property * 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 49typedef 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 62static long 63seterror(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 75static long 76expr(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 273long 274strexpr(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