1 Copyright 2001, 2004 Free Software Foundation, Inc. 2 3 This file is part of the GNU MP Library. 4 5 The GNU MP Library is free software; you can redistribute it and/or modify 6 it under the terms of either: 7 8 * the GNU Lesser General Public License as published by the Free 9 Software Foundation; either version 3 of the License, or (at your 10 option) any later version. 11 12 or 13 14 * the GNU General Public License as published by the Free Software 15 Foundation; either version 2 of the License, or (at your option) any 16 later version. 17 18 or both in parallel, as here. 19 20 The GNU MP Library is distributed in the hope that it will be useful, but 21 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 22 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 23 for more details. 24 25 You should have received copies of the GNU General Public License and the 26 GNU Lesser General Public License along with the GNU MP Library. If not, 27 see https://www.gnu.org/licenses/. 28 29 30 31 32 33 34 GMP EXPRESSION EVALUATION 35 ------------------------- 36 37 38 39 THIS CODE IS PRELIMINARY AND MAY BE SUBJECT TO INCOMPATIBLE CHANGES IN 40 FUTURE VERSIONS OF GMP. 41 42 43 44 The files in this directory implement a simple scheme of string based 45 expression parsing and evaluation, supporting mpz, mpq and mpf. 46 47 This will be slower than direct GMP library calls, but may be convenient in 48 various circumstances, such as while prototyping, or for letting a user 49 enter values in symbolic form. "2**5723-7" for example is a lot easier to 50 enter or maintain than the equivalent written out in decimal. 51 52 53 54 BUILDING 55 56 Nothing in this directory is a normal part of libgmp, and nothing is built 57 or installed, but various Makefile rules are available to compile 58 everything. 59 60 All the functions are available through a little library (there's no shared 61 library since upward binary compatibility is not guaranteed). 62 63 make libexpr.a 64 65 In a program, prototypes are available using 66 67 #include "expr.h" 68 69 run-expr.c is a sample program doing evaluations from the command line. 70 71 make run-expr 72 ./run-expr '1+2*3' 73 74 t-expr.c is self-test program, it prints nothing if successful. 75 76 make t-expr 77 ./t-expr 78 79 The expr*.c sources don't depend on gmp-impl.h and can be compiled with just 80 a standard installed GMP. This isn't true of t-expr though, since it uses 81 some of the internal tests/libtests.la. 82 83 84 85 SIMPLE USAGE 86 87 int mpz_expr (mpz_t res, int base, const char *e, ...); 88 int mpq_expr (mpq_t res, int base, const char *e, ...); 89 int mpf_expr (mpf_t res, int base, const char *e, ...); 90 91 These functions evaluate simple arithmetic expressions. For example, 92 93 mpz_expr (result, 0, "123+456", NULL); 94 95 Numbers are parsed by mpz_expr and mpq_expr the same as mpz_set_str with the 96 given base. mpf_expr follows mpf_set_str, but supporting an "0x" prefix for 97 hex when base==0. 98 99 mpz_expr (result, 0, "0xAAAA * 0x5555", NULL); 100 101 White space, as indicated by <ctype.h> isspace(), is ignored except for the 102 purpose of separating tokens. 103 104 Variables can be included in expressions by putting them in the stdarg list 105 after the string. "a", "b", "c" etc in the expression string designate 106 those values. For example, 107 108 mpq_t foo, bar; 109 ... 110 mpq_expr (q, 10, "2/3 + 1/a + b/2", foo, bar, NULL); 111 112 Here "a" will be the value from foo and "b" from bar. Up to 26 variables 113 can be included this way. The NULL must be present to indicate the end of 114 the list. 115 116 Variables can also be written "$a", "$b" etc. This is necessary when using 117 bases greater than 10 since plain "a", "b" etc will otherwise be interpreted 118 as numbers. For example, 119 120 mpf_t quux; 121 mpf_expr (f, 16, "F00F@-6 * $a", quux, NULL); 122 123 All the standard C operators are available, with the usual precedences, plus 124 "**" for exponentiation at the highest precedence (and right associative). 125 126 Operators Precedence 127 ** 220 128 ~ ! - (unary) 210 129 * / % 200 130 + - 190 131 << >> 180 132 <= < >= > 170 133 == != 160 134 & 150 135 ^ 140 136 | 130 137 && 120 138 || 110 139 ? : 100/101 140 141 Currently only mpz_expr has the bitwise ~ % & ^ and | operators. The 142 precedence numbers are of interest in the advanced usage described below. 143 144 Various functions are available too. For example, 145 146 mpz_expr (res, 10, "gcd(123,456,789) * abs(a)", var, NULL); 147 148 The following is the full set of functions, 149 150 mpz_expr 151 abs bin clrbit cmp cmpabs congruent_p divisible_p even_p fib fac 152 gcd hamdist invert jacobi kronecker lcm lucnum max min nextprime 153 odd_p perfect_power_p perfect_square_p popcount powm 154 probab_prime_p root scan0 scan1 setbit sgn sqrt 155 156 mpq_expr 157 abs, cmp, den, max, min, num, sgn 158 159 mpf_expr 160 abs, ceil, cmp, eq, floor, integer_p, max, min, reldiff, sgn, 161 sqrt, trunc 162 163 All these are the same as the GMP library functions, except that min and max 164 don't exist in the library. Note also that min, max, gcd and lcm take any 165 number of arguments, not just two. 166 167 mpf_expr does all calculations to the precision of the destination variable. 168 169 170 Expression parsing can succeed or fail. The return value indicates this, 171 and will be one of the following 172 173 MPEXPR_RESULT_OK 174 MPEXPR_RESULT_BAD_VARIABLE 175 MPEXPR_RESULT_BAD_TABLE 176 MPEXPR_RESULT_PARSE_ERROR 177 MPEXPR_RESULT_NOT_UI 178 179 BAD_VARIABLE is when a variable is referenced that hasn't been provided. 180 For example if "c" is used when only two parameters have been passed. 181 BAD_TABLE is applicable to the advanced usage described below. 182 183 PARSE_ERROR is a general syntax error, returned for any mal-formed input 184 string. 185 186 NOT_UI is returned when an attempt is made to use an operand that's bigger 187 than an "unsigned long" with a function that's restricted to that range. 188 For example "fib" is mpz_fib_ui and only accepts an "unsigned long". 189 190 191 192 193 ADVANCED USAGE 194 195 int mpz_expr_a (const struct mpexpr_operator_t *table, 196 mpz_ptr res, int base, const char *e, size_t elen, 197 mpz_srcptr var[26]) 198 int mpq_expr_a (const struct mpexpr_operator_t *table, 199 mpq_ptr res, int base, const char *e, size_t elen, 200 mpq_srcptr var[26]) 201 int mpf_expr_a (const struct mpexpr_operator_t *table, 202 mpf_ptr res, int base, unsigned long prec, 203 const char *e, size_t elen, 204 mpf_srcptr var[26]) 205 206 These functions are an advanced interface to expression parsing. 207 208 The string is taken as pointer and length. This makes it possible to parse 209 an expression in the middle of somewhere without copying and null 210 terminating it. 211 212 Variables are an array of 26 pointers to the appropriate operands, or NULL 213 for variables that are not available. Any combination of variables can be 214 given, for example just "x" and "y" (var[23] and var[24]) could be set. 215 216 Operators and functions are specified with a table. This makes it possible 217 to provide additional operators or functions, or to completely change the 218 syntax. The standard tables used by the simple functions above are 219 available as 220 221 const struct mpexpr_operator_t * const mpz_expr_standard_table; 222 const struct mpexpr_operator_t * const mpq_expr_standard_table; 223 const struct mpexpr_operator_t * const mpf_expr_standard_table; 224 225 struct mpexpr_operator_t is the following 226 227 struct mpexpr_operator_t { 228 const char *name; 229 mpexpr_fun_t fun; 230 int type; 231 int precedence; 232 }; 233 234 typedef void (*mpexpr_fun_t) (void); 235 236 As an example, the standard mpz_expr table entry for multiplication is as 237 follows. See the source code for the full set of standard entries. 238 239 { "*", (mpexpr_fun_t) mpz_mul, MPEXPR_TYPE_BINARY, 200 }, 240 241 "name" is the string to parse, "fun" is the function to call for it, "type" 242 indicates what parameters the function takes (among other things), and 243 "precedence" sets its operator precedence. 244 245 A NULL for "name" indicates the end of the table, so for example an mpf 246 table with nothing but addition could be 247 248 struct mpexpr_operator_t table[] = { 249 { "+", (mpexpr_fun_t) mpf_add, MPEXPR_TYPE_BINARY, 190 }, 250 { NULL } 251 }; 252 253 A special type MPEXPR_TYPE_NEW_TABLE makes it possible to chain from one 254 table to another. For example the following would add a "mod" operator to 255 the standard mpz table, 256 257 struct mpexpr_operator_t table[] = { 258 { "mod", (mpexpr_fun_t) mpz_fdiv_r, MPEXPR_TYPE_BINARY, 125 }, 259 { (const char *) mpz_expr_standard_table, NULL, MPEXPR_TYPE_NEW_TABLE } 260 }; 261 262 Notice the low precedence on "mod", so that for instance "45+26 mod 7" 263 parses as "(45+26)mod7". 264 265 266 Functions are designated by a precedence of 0. They always occur as 267 "foo(expr)" and so have no need for a precedence level. mpq_abs in the 268 standard mpq table is 269 270 { "abs", (mpexpr_fun_t) mpq_abs, MPEXPR_TYPE_UNARY }, 271 272 Functions expecting no arguments as in "foo()" can be given with 273 MPEXPR_TYPE_0ARY, or actual constants to be parsed as just "foo" are 274 MPEXPR_TYPE_CONSTANT. For example if a "void mpf_const_pi(mpf_t f)" 275 function existed (which it doesn't) it could be, 276 277 { "pi", (mpexpr_fun_t) mpf_const_pi, MPEXPR_TYPE_CONSTANT }, 278 279 280 Parsing of operator names is done by seeking the table entry with the 281 longest matching name. So for instance operators "<" and "<=" exist, and 282 when presented with "x <= y" the parser matches "<=" because it's longer. 283 284 Parsing of function names, on the other hand, is done by requiring a whole 285 alphanumeric word to match. For example presented with "fib2zz(5)" the 286 parser will attempt to find a function called "fib2zz". A function "fib" 287 wouldn't be used because it doesn't match the whole word. 288 289 The flag MPEXPR_TYPE_WHOLEWORD can be ORed into an operator type to override 290 the default parsing style. Similarly MPEXPR_TYPE_OPERATOR into a function. 291 292 293 Binary operators are left associative by default, meaning they're evaluated 294 from left to right, so for example "1+2+3" is treated as "(1+2)+3". 295 MPEXPR_TYPE_RIGHTASSOC can be ORed into the operator type to work from right 296 to left as in "1+(2+3)". This is generally what's wanted for 297 exponentiation, and for example the standard mpz table has 298 299 { "**", (mpexpr_fun_t) mpz_pow_ui, 300 MPEXPR_TYPE_BINARY_UI | MPEXPR_TYPE_RIGHTASSOC, 220 } 301 302 Unary operators are postfix by default. For example a factorial to be used 303 as "123!" might be 304 305 { "!", (mpexpr_fun_t) mpz_fac_ui, MPEXPR_TYPE_UNARY_UI, 215 } 306 307 MPEXPR_TYPE_PREFIX can be ORed into the type to get a prefix operator. For 308 instance negation (unary minus) in the standard mpf table is 309 310 { "-", (mpexpr_fun_t) mpf_neg, 311 MPEXPR_TYPE_UNARY | MPEXPR_TYPE_PREFIX, 210 }, 312 313 314 The same operator can exist as a prefix unary and a binary, or as a prefix 315 and postfix unary, simply by putting two entries in the table. While 316 parsing the context determines which style is sought. But note that the 317 same operator can't be both a postfix unary and a binary, since the parser 318 doesn't try to look ahead to decide which ought to be used. 319 320 When there's two entries for an operator, both prefix or both postfix (or 321 binary), then the first in the table will be used. This makes it possible 322 to override an entry in a standard table, for example to change the function 323 it calls, or perhaps its precedence level. The following would change mpz 324 division from tdiv to cdiv, 325 326 struct mpexpr_operator_t table[] = { 327 { "/", (mpexpr_fun_t) mpz_cdiv_q, MPEXPR_TYPE_BINARY, 200 }, 328 { "%", (mpexpr_fun_t) mpz_cdiv_r, MPEXPR_TYPE_BINARY, 200 }, 329 { (char *) mpz_expr_standard_table, NULL, MPEXPR_TYPE_NEW_TABLE } 330 }; 331 332 333 The type field indicates what parameters the given function expects. The 334 following styles of functions are supported. mpz_t is shown, but of course 335 this is mpq_t for mpq_expr_a, mpf_t for mpf_expr_a, etc. 336 337 MPEXPR_TYPE_CONSTANT void func (mpz_t result); 338 339 MPEXPR_TYPE_0ARY void func (mpz_t result); 340 MPEXPR_TYPE_I_0ARY int func (void); 341 342 MPEXPR_TYPE_UNARY void func (mpz_t result, mpz_t op); 343 MPEXPR_TYPE_UNARY_UI void func (mpz_t result, unsigned long op); 344 MPEXPR_TYPE_I_UNARY int func (mpz_t op); 345 MPEXPR_TYPE_I_UNARY_UI int func (unsigned long op); 346 347 MPEXPR_TYPE_BINARY void func (mpz_t result, mpz_t op1, mpz_t op2); 348 MPEXPR_TYPE_BINARY_UI void func (mpz_t result, 349 mpz_t op1, unsigned long op2); 350 MPEXPR_TYPE_I_BINARY int func (mpz_t op1, mpz_t op2); 351 MPEXPR_TYPE_I_BINARY_UI int func (mpz_t op1, unsigned long op2); 352 353 MPEXPR_TYPE_TERNARY void func (mpz_t result, 354 mpz_t op1, mpz_t op2, mpz_t op3); 355 MPEXPR_TYPE_TERNARY_UI void func (mpz_t result, mpz_t op1, mpz_t op2, 356 unsigned long op3); 357 MPEXPR_TYPE_I_TERNARY int func (mpz_t op1, mpz_t op2, mpz_t op3); 358 MPEXPR_TYPE_I_TERNARY_UI int func (mpz_t op1, mpz_t op2, 359 unsigned long op3); 360 361 Notice the pattern of "UI" for the last parameter as an unsigned long, or 362 "I" for the result as an "int" return value. 363 364 It's important that the declared type for an operator or function matches 365 the function pointer given. Any mismatch will have unpredictable results. 366 367 For binary functions, a further type attribute is MPEXPR_TYPE_PAIRWISE which 368 indicates that any number of arguments should be accepted, and evaluated by 369 applying the given binary function to them pairwise. This is used by gcd, 370 lcm, min and max. For example the standard mpz gcd is 371 372 { "gcd", (mpexpr_fun_t) mpz_gcd, 373 MPEXPR_TYPE_BINARY | MPEXPR_TYPE_PAIRWISE }, 374 375 Some special types exist for comparison operators (or functions). 376 MPEXPR_TYPE_CMP_LT through MPEXPR_TYPE_CMP_GE expect an MPEXPR_TYPE_I_BINARY 377 function, returning positive, negative or zero like mpz_cmp and similar. 378 For example the standard mpf "!=" operator is 379 380 { "!=", (mpexpr_fun_t) mpf_cmp, MPEXPR_TYPE_CMP_NE, 160 }, 381 382 But there's no obligation to use these types, for instance the standard mpq 383 table just uses a plain MPEXPR_TYPE_I_BINARY and mpq_equal for "==". 384 385 Further special types MPEXPR_TYPE_MIN and MPEXPR_TYPE_MAX exist to implement 386 the min and max functions, and they take a function like mpf_cmp similarly. 387 The standard mpf max function is 388 389 { "max", (mpexpr_fun_t) mpf_cmp, 390 MPEXPR_TYPE_MAX | MPEXPR_TYPE_PAIRWISE }, 391 392 These can be used as operators too, for instance the following would be the 393 >? operator which is a feature of GNU C++, 394 395 { ">?", (mpexpr_fun_t) mpf_cmp, MPEXPR_TYPE_MAX, 175 }, 396 397 Other special types are used to define "(" ")" parentheses, "," function 398 argument separator, "!" through "||" logical booleans, ternary "?" ":", and 399 the "$" which introduces variables. See the sources for how they should be 400 used. 401 402 403 User definable operator tables will have various uses. For example, 404 405 - a subset of the C operators, to be rid of infrequently used things 406 - a more mathematical syntax like "." for multiply, "^" for powering, 407 and "!" for factorial 408 - a boolean evaluator with "^" for AND, "v" for OR 409 - variables introduced with "%" instead of "$" 410 - brackets as "[" and "]" instead of "(" and ")" 411 412 The only fixed parts of the parsing are the treatment of numbers, whitespace 413 and the two styles of operator/function name recognition. 414 415 As a final example, the following would be a complete mpz table implementing 416 some operators with a more mathematical syntax. Notice there's no need to 417 preserve the standard precedence values, anything can be used so long as 418 they're in the desired relation to each other. There's also no need to have 419 entries in precedence order, but it's convenient to do so to show what comes 420 where. 421 422 static const struct mpexpr_operator_t table[] = { 423 { "^", (mpexpr_fun_t) mpz_pow_ui, 424 MPEXPR_TYPE_BINARY_UI | MPEXPR_TYPE_RIGHTASSOC, 9 }, 425 426 { "!", (mpexpr_fun_t) mpz_fac_ui, MPEXPR_TYPE_UNARY_UI, 8 }, 427 { "-", (mpexpr_fun_t) mpz_neg, 428 MPEXPR_TYPE_UNARY | MPEXPR_TYPE_PREFIX, 7 }, 429 430 { "*", (mpexpr_fun_t) mpz_mul, MPEXPR_TYPE_BINARY, 6 }, 431 { "/", (mpexpr_fun_t) mpz_fdiv_q, MPEXPR_TYPE_BINARY, 6 }, 432 433 { "+", (mpexpr_fun_t) mpz_add, MPEXPR_TYPE_BINARY, 5 }, 434 { "-", (mpexpr_fun_t) mpz_sub, MPEXPR_TYPE_BINARY, 5 }, 435 436 { "mod", (mpexpr_fun_t) mpz_mod, MPEXPR_TYPE_BINARY, 6 }, 437 438 { ")", NULL, MPEXPR_TYPE_CLOSEPAREN, 4 }, 439 { "(", NULL, MPEXPR_TYPE_OPENPAREN, 3 }, 440 { ",", NULL, MPEXPR_TYPE_ARGSEP, 2 }, 441 442 { "$", NULL, MPEXPR_TYPE_VARIABLE, 1 }, 443 { NULL } 444 }; 445 446 447 448 449 INTERNALS 450 451 Operator precedence is implemented using a control and data stack, there's 452 no C recursion. When an expression like 1+2*3 is read the "+" is held on 453 the control stack and 1 on the data stack until "*" has been parsed and 454 applied to 2 and 3. This happens any time a higher precedence operator 455 follows a lower one, or when a right-associative operator like "**" is 456 repeated. 457 458 Parentheses are handled by making "(" a special prefix unary with a low 459 precedence so a whole following expression is read. The special operator 460 ")" knows to discard the pending "(". Function arguments are handled 461 similarly, with the function pretending to be a low precedence prefix unary 462 operator, and with "," allowed within functions. The same special ")" 463 operator recognises a pending function and will invoke it appropriately. 464 465 The ternary "? :" operator is also handled using precedences. ":" is one 466 level higher than "?", so when a valid a?b:c is parsed the ":" finds a "?" 467 on the control stack. It's a parse error for ":" to find anything else. 468 469 470 471 FUTURE 472 473 The ternary "?:" operator evaluates the "false" side of its pair, which is 474 wasteful, though it ought to be harmless. It'd be better if it could 475 evaluate only the "true" side. Similarly for the logical booleans "&&" and 476 "||" if they know their result already. 477 478 Functions like MPEXPR_TYPE_BINARY could return a status indicating operand 479 out of range or whatever, to get an error back through mpz_expr etc. That 480 would want to be just an option, since plain mpz_add etc have no such 481 return. 482 483 Could have assignments like "a = b*c" modifying the input variables. 484 Assignment could be an operator attribute, making it expect an lvalue. 485 There would want to be a standard table without assignments available 486 though, so user input could be safely parsed. 487 488 The closing parenthesis table entry could specify the type of open paren it 489 expects, so that "(" and ")" could match and "[" and "]" match but not a 490 mixture of the two. Currently "[" and "]" can be added, but there's no 491 error on writing a mixed expression like "2*(3+4]". Maybe also there could 492 be a way to say that functions can only be written with one or the other 493 style of parens. 494 495 496 497 ---------------- 498 Local variables: 499 mode: text 500 fill-column: 76 501 End: 502
Indexes created Mon Mar 02 05:31:46 UTC 2026