• Home
  • History
  • Annotate
Name Date Size #Lines LOC

..25-Mar-2014-

Makefile.amH A D25-Mar-20141.9 KiB5512

Makefile.inH A D25-Mar-201416.9 KiB577468

READMEH A D25-Mar-201418.8 KiB502347

expr-impl.hH A D25-Mar-20144.3 KiB12672

expr.cH A D25-Mar-201426.5 KiB835606

expr.hH A D25-Mar-20145.1 KiB14381

exprf.cH A D25-Mar-20144.6 KiB12468

exprfa.cH A D25-Mar-20144.5 KiB192125

exprq.cH A D25-Mar-20145 KiB15694

exprqa.cH A D25-Mar-20142.7 KiB10154

exprv.cH A D25-Mar-20141.4 KiB5821

exprz.cH A D25-Mar-20148 KiB207143

exprza.cH A D25-Mar-20142.9 KiB10963

run-expr.cH A D25-Mar-20145.9 KiB243171

t-expr.cH A D25-Mar-201412.6 KiB511382

README

1Copyright 2001, 2004 Free Software Foundation, Inc.
2
3This file is part of the GNU MP Library.
4
5The GNU MP Library is free software; you can redistribute it and/or modify
6it 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
12or
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
18or both in parallel, as here.
19
20The GNU MP Library is distributed in the hope that it will be useful, but
21WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
22or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
23for more details.
24
25You should have received copies of the GNU General Public License and the
26GNU Lesser General Public License along with the GNU MP Library.  If not,
27see https://www.gnu.org/licenses/.
28
29
30
31
32
33
34                    GMP EXPRESSION EVALUATION
35                    -------------------------
36
37
38
39THIS CODE IS PRELIMINARY AND MAY BE SUBJECT TO INCOMPATIBLE CHANGES IN
40FUTURE VERSIONS OF GMP.
41
42
43
44The files in this directory implement a simple scheme of string based
45expression parsing and evaluation, supporting mpz, mpq and mpf.
46
47This will be slower than direct GMP library calls, but may be convenient in
48various circumstances, such as while prototyping, or for letting a user
49enter values in symbolic form.  "2**5723-7" for example is a lot easier to
50enter or maintain than the equivalent written out in decimal.
51
52
53
54BUILDING
55
56Nothing in this directory is a normal part of libgmp, and nothing is built
57or installed, but various Makefile rules are available to compile
58everything.
59
60All the functions are available through a little library (there's no shared
61library since upward binary compatibility is not guaranteed).
62
63	make libexpr.a
64
65In a program, prototypes are available using
66
67	#include "expr.h"
68
69run-expr.c is a sample program doing evaluations from the command line.
70
71	make run-expr
72	./run-expr '1+2*3'
73
74t-expr.c is self-test program, it prints nothing if successful.
75
76	make t-expr
77	./t-expr
78
79The expr*.c sources don't depend on gmp-impl.h and can be compiled with just
80a standard installed GMP.  This isn't true of t-expr though, since it uses
81some of the internal tests/libtests.la.
82
83
84
85SIMPLE USAGE
86
87int mpz_expr (mpz_t res, int base, const char *e, ...);
88int mpq_expr (mpq_t res, int base, const char *e, ...);
89int mpf_expr (mpf_t res, int base, const char *e, ...);
90
91These functions evaluate simple arithmetic expressions.  For example,
92
93	mpz_expr (result, 0, "123+456", NULL);
94
95Numbers are parsed by mpz_expr and mpq_expr the same as mpz_set_str with the
96given base.  mpf_expr follows mpf_set_str, but supporting an "0x" prefix for
97hex when base==0.
98
99	mpz_expr (result, 0, "0xAAAA * 0x5555", NULL);
100
101White space, as indicated by <ctype.h> isspace(), is ignored except for the
102purpose of separating tokens.
103
104Variables can be included in expressions by putting them in the stdarg list
105after the string.  "a", "b", "c" etc in the expression string designate
106those 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
112Here "a" will be the value from foo and "b" from bar.  Up to 26 variables
113can be included this way.  The NULL must be present to indicate the end of
114the list.
115
116Variables can also be written "$a", "$b" etc.  This is necessary when using
117bases greater than 10 since plain "a", "b" etc will otherwise be interpreted
118as numbers.  For example,
119
120        mpf_t  quux;
121        mpf_expr (f, 16, "F00F@-6 * $a", quux, NULL);
122
123All 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
141Currently only mpz_expr has the bitwise ~ % & ^ and | operators.  The
142precedence numbers are of interest in the advanced usage described below.
143
144Various functions are available too.  For example,
145
146        mpz_expr (res, 10, "gcd(123,456,789) * abs(a)", var, NULL);
147
148The 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
163All these are the same as the GMP library functions, except that min and max
164don't exist in the library.  Note also that min, max, gcd and lcm take any
165number of arguments, not just two.
166
167mpf_expr does all calculations to the precision of the destination variable.
168
169
170Expression parsing can succeed or fail.  The return value indicates this,
171and 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
179BAD_VARIABLE is when a variable is referenced that hasn't been provided.
180For example if "c" is used when only two parameters have been passed.
181BAD_TABLE is applicable to the advanced usage described below.
182
183PARSE_ERROR is a general syntax error, returned for any mal-formed input
184string.
185
186NOT_UI is returned when an attempt is made to use an operand that's bigger
187than an "unsigned long" with a function that's restricted to that range.
188For example "fib" is mpz_fib_ui and only accepts an "unsigned long".
189
190
191
192
193ADVANCED USAGE
194
195int 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])
198int 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])
201int 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
206These functions are an advanced interface to expression parsing.
207
208The string is taken as pointer and length.  This makes it possible to parse
209an expression in the middle of somewhere without copying and null
210terminating it.
211
212Variables are an array of 26 pointers to the appropriate operands, or NULL
213for variables that are not available.  Any combination of variables can be
214given, for example just "x" and "y" (var[23] and var[24]) could be set.
215
216Operators and functions are specified with a table.  This makes it possible
217to provide additional operators or functions, or to completely change the
218syntax.  The standard tables used by the simple functions above are
219available 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
225struct 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
236As an example, the standard mpz_expr table entry for multiplication is as
237follows.  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"
242indicates what parameters the function takes (among other things), and
243"precedence" sets its operator precedence.
244
245A NULL for "name" indicates the end of the table, so for example an mpf
246table 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
253A special type MPEXPR_TYPE_NEW_TABLE makes it possible to chain from one
254table to another.  For example the following would add a "mod" operator to
255the 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
262Notice the low precedence on "mod", so that for instance "45+26 mod 7"
263parses as "(45+26)mod7".
264
265
266Functions 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
268standard mpq table is
269
270	{ "abs", (mpexpr_fun_t) mpq_abs, MPEXPR_TYPE_UNARY },
271
272Functions expecting no arguments as in "foo()" can be given with
273MPEXPR_TYPE_0ARY, or actual constants to be parsed as just "foo" are
274MPEXPR_TYPE_CONSTANT.  For example if a "void mpf_const_pi(mpf_t f)"
275function existed (which it doesn't) it could be,
276
277	{ "pi", (mpexpr_fun_t) mpf_const_pi, MPEXPR_TYPE_CONSTANT },
278
279
280Parsing of operator names is done by seeking the table entry with the
281longest matching name.  So for instance operators "<" and "<=" exist, and
282when presented with "x <= y" the parser matches "<=" because it's longer.
283
284Parsing of function names, on the other hand, is done by requiring a whole
285alphanumeric word to match.  For example presented with "fib2zz(5)" the
286parser will attempt to find a function called "fib2zz".  A function "fib"
287wouldn't be used because it doesn't match the whole word.
288
289The flag MPEXPR_TYPE_WHOLEWORD can be ORed into an operator type to override
290the default parsing style.  Similarly MPEXPR_TYPE_OPERATOR into a function.
291
292
293Binary operators are left associative by default, meaning they're evaluated
294from left to right, so for example "1+2+3" is treated as "(1+2)+3".
295MPEXPR_TYPE_RIGHTASSOC can be ORed into the operator type to work from right
296to left as in "1+(2+3)".  This is generally what's wanted for
297exponentiation, 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
302Unary operators are postfix by default.  For example a factorial to be used
303as "123!" might be
304
305	{ "!", (mpexpr_fun_t) mpz_fac_ui, MPEXPR_TYPE_UNARY_UI, 215 }
306
307MPEXPR_TYPE_PREFIX can be ORed into the type to get a prefix operator.  For
308instance 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
314The same operator can exist as a prefix unary and a binary, or as a prefix
315and postfix unary, simply by putting two entries in the table.  While
316parsing the context determines which style is sought.  But note that the
317same operator can't be both a postfix unary and a binary, since the parser
318doesn't try to look ahead to decide which ought to be used.
319
320When there's two entries for an operator, both prefix or both postfix (or
321binary), then the first in the table will be used.  This makes it possible
322to override an entry in a standard table, for example to change the function
323it calls, or perhaps its precedence level.  The following would change mpz
324division 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
333The type field indicates what parameters the given function expects.  The
334following styles of functions are supported.  mpz_t is shown, but of course
335this 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
361Notice the pattern of "UI" for the last parameter as an unsigned long, or
362"I" for the result as an "int" return value.
363
364It's important that the declared type for an operator or function matches
365the function pointer given.  Any mismatch will have unpredictable results.
366
367For binary functions, a further type attribute is MPEXPR_TYPE_PAIRWISE which
368indicates that any number of arguments should be accepted, and evaluated by
369applying the given binary function to them pairwise.  This is used by gcd,
370lcm, 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
375Some special types exist for comparison operators (or functions).
376MPEXPR_TYPE_CMP_LT through MPEXPR_TYPE_CMP_GE expect an MPEXPR_TYPE_I_BINARY
377function, returning positive, negative or zero like mpz_cmp and similar.
378For example the standard mpf "!=" operator is
379
380	{ "!=", (mpexpr_fun_t) mpf_cmp, MPEXPR_TYPE_CMP_NE, 160 },
381
382But there's no obligation to use these types, for instance the standard mpq
383table just uses a plain MPEXPR_TYPE_I_BINARY and mpq_equal for "==".
384
385Further special types MPEXPR_TYPE_MIN and MPEXPR_TYPE_MAX exist to implement
386the min and max functions, and they take a function like mpf_cmp similarly.
387The standard mpf max function is
388
389	{ "max",  (mpexpr_fun_t) mpf_cmp,
390          MPEXPR_TYPE_MAX | MPEXPR_TYPE_PAIRWISE },
391
392These 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
397Other special types are used to define "(" ")" parentheses, "," function
398argument separator, "!" through "||" logical booleans, ternary "?"  ":", and
399the "$" which introduces variables.  See the sources for how they should be
400used.
401
402
403User 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
412The only fixed parts of the parsing are the treatment of numbers, whitespace
413and the two styles of operator/function name recognition.
414
415As a final example, the following would be a complete mpz table implementing
416some operators with a more mathematical syntax.  Notice there's no need to
417preserve the standard precedence values, anything can be used so long as
418they're in the desired relation to each other.  There's also no need to have
419entries in precedence order, but it's convenient to do so to show what comes
420where.
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
449INTERNALS
450
451Operator precedence is implemented using a control and data stack, there's
452no C recursion.  When an expression like 1+2*3 is read the "+" is held on
453the control stack and 1 on the data stack until "*" has been parsed and
454applied to 2 and 3.  This happens any time a higher precedence operator
455follows a lower one, or when a right-associative operator like "**" is
456repeated.
457
458Parentheses are handled by making "(" a special prefix unary with a low
459precedence so a whole following expression is read.  The special operator
460")" knows to discard the pending "(".  Function arguments are handled
461similarly, with the function pretending to be a low precedence prefix unary
462operator, and with "," allowed within functions.  The same special ")"
463operator recognises a pending function and will invoke it appropriately.
464
465The ternary "? :" operator is also handled using precedences.  ":" is one
466level higher than "?", so when a valid a?b:c is parsed the ":" finds a "?"
467on the control stack.  It's a parse error for ":" to find anything else.
468
469
470
471FUTURE
472
473The ternary "?:" operator evaluates the "false" side of its pair, which is
474wasteful, though it ought to be harmless.  It'd be better if it could
475evaluate only the "true" side.  Similarly for the logical booleans "&&" and
476"||" if they know their result already.
477
478Functions like MPEXPR_TYPE_BINARY could return a status indicating operand
479out of range or whatever, to get an error back through mpz_expr etc.  That
480would want to be just an option, since plain mpz_add etc have no such
481return.
482
483Could have assignments like "a = b*c" modifying the input variables.
484Assignment could be an operator attribute, making it expect an lvalue.
485There would want to be a standard table without assignments available
486though, so user input could be safely parsed.
487
488The closing parenthesis table entry could specify the type of open paren it
489expects, so that "(" and ")" could match and "[" and "]" match but not a
490mixture of the two.  Currently "[" and "]" can be added, but there's no
491error on writing a mixed expression like "2*(3+4]".  Maybe also there could
492be a way to say that functions can only be written with one or the other
493style of parens.
494
495
496
497----------------
498Local variables:
499mode: text
500fill-column: 76
501End:
502