README
上传用户:qaz666999
上传日期:2022-08-06
资源大小:2570k
文件大小:19k
源码类别:

数学计算

开发平台:

Unix_Linux

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