]> Shamusworld >> Repos - architektonas/blob - fparser/src/fparser.txt
Refactored CAD tool bars to use predefined actions.
[architektonas] / fparser / src / fparser.txt
1   Function parser for C++  v2.51 by Warp.
2   ======================================
3
4   Optimization code contributed by Bisqwit (http://iki.fi/bisqwit/)
5
6
7   The usage license of this library is located at the end of this text file.
8
9
10
11   What's new in v2.51
12   -------------------
13   - Tiny fixes to make it work with gcc 2.x (which is still sadly common).
14
15   What's new in v2.5
16   ------------------
17   - A new AddConstant() method for adding constants to the parser.
18   - Two AddFunction() methods for adding user-defined functions to the parser.
19   - The library can now handle trigonometrical angles either in radians
20     (default) or degrees with an optional parameter of Parse().
21   - New functions added: cot(), csc() and sec().
22   - Enhancements and bug fixes to the Optimize() method (please consider
23     it still as experimental).
24
25   What's new in v2.4:
26   ------------------
27   - A new Optimize() method which tries to simplify the bytecode so that
28     it will be evaluated faster. Please note that this is still experimental.
29   - New functions added: atan2() and log10().
30   - Two new more detailed syntax error messages (previously simply
31     "Syntax error").
32
33   What's new in v2.3:
34   ------------------
35   - Variable names can now have digits and underscores (but they can't begin
36     with a digit).
37   - Parsing speed optimizations. The Parse() method can be even 40% faster
38     than in the previous version.
39     (Please be aware that the new parser has not been thoroughly tested;
40      bugs are possible.)
41   - A new "semi-undocumented" debugging function for printing the bytecode
42     of the current function (in an asm-like syntax). Mostly useless from
43     the user's point of view.
44
45
46
47 =============================================================================
48   - Preface
49 =============================================================================
50
51   Often people need to ask some mathematical expression from the user and
52 then evaluate values for that expression. The simplest example is a program
53 which draws the graphic of a user-defined function on screen.
54
55   This library adds C-style function string parsing to the program. This
56 means that you can evaluate the string "sqrt(1-x^2+y^2)" with given values
57 of 'x' and 'y'.
58
59   The library is intended to be very fast. It byte-compiles the function
60 string at parse time and interpretes this byte-code at evaluation time.
61 The evaluation is straightforward and no recursions are done (uses stack
62 arithmetic).
63   Empirical tests show that it indeed is very fast (specially compared to
64 libraries which evaluate functions by just interpreting the raw function
65 string).
66
67   The library is made in ISO C++ and requires a standard-conforming C++
68 compiler.
69
70
71 =============================================================================
72   - Usage
73 =============================================================================
74
75   To use the FunctionParser class, you have to include "fparser.hh". When
76 compiling, you have to compile fparser.cc and link it to the main program.
77 You can also make a library from the fparser.cc (see the help on your
78 compiler to see how this is done).
79
80
81   * Short descriptions of FunctionParser methods:
82     --------------------------------------------
83
84 int Parse(const std::string& Function, const std::string& Vars,
85           bool useDegrees = false);
86
87     Parses the given function and compiles it to internal format.
88     Return value is -1 if successful, else the index value to the location
89     of the error.
90
91
92 const char* ErrorMsg(void) const;
93
94     Returns an error message corresponding to the error in Parse(), or 0 if
95     no such error occurred.
96
97
98 double Eval(const double* Vars);
99
100     Evaluates the function given to Parse().
101
102
103 int EvalError(void) const;
104
105     Returns 0 if no error happened in the previous call to Eval(), else an
106     error code >1.
107
108
109 void Optimize();
110
111     Tries to optimize the bytecode for faster evaluation.
112
113
114 bool AddConstant(const std::string& name, double value);
115
116     Add a constant to the parser. Returns false if the name of the constant
117     is invalid, else true.
118
119
120 bool AddFunction(const std::string& name,
121                  double (*functionPtr)(const double*),
122                  unsigned paramsAmount);
123
124     Add a user-defined function to the parser (as a function pointer).
125     Returns false if the name of the function is invalid, else true.
126
127
128 bool AddFunction(const std::string& name, FunctionParser&);
129
130     Add a user-defined function to the parser (as a FunctionParser instance).
131     Returns false if the name of the function is invalid, else true.
132
133
134
135   * Long descriptions of FunctionParser methods:
136     -------------------------------------------
137
138 ---------------------------------------------------------------------------
139 int Parse(const std::string& Function, const std::string& Vars,
140           bool useDegrees = false);
141 ---------------------------------------------------------------------------
142
143       Parses the given function (and compiles it to internal format).
144     Destroys previous function. Following calls to Eval() will evaluate
145     the given function.
146       The strings given as parameters are not needed anymore after parsing.
147
148     Parameters:
149       Function  : String containing the function to parse.
150       Vars      : String containing the variable names, separated by commas.
151                   Eg. "x,y", "VarX,VarY,VarZ,n" or "x1,x2,x3,x4,__VAR__".
152       useDegrees: (Optional.) Whether to use degrees or radians in
153                   trigonometric functions. (Default: radians)
154
155     Variables can have any size and they are case sensitive (ie. "var",
156     "VAR" and "Var" are *different* variable names). Letters, digits and
157     underscores can be used in variable names, but the name of a variable
158     can't begin with a digit. Each variable name can appear only once in
159     the string. Function names are not legal variable names.
160
161     Using longer variable names causes no overhead whatsoever to the Eval()
162     method, so it's completely safe to use variable names of any size.
163
164     The third, optional parameter specifies whether angles should be
165     interpreted as radians or degrees in trigonometrical functions.
166     If not specified, the default value is radians.
167
168     Return values:
169     -On success the function returns -1.
170     -On error the function returns an index to where the error was found
171      (0 is the first character, 1 the second, etc). If the error was not
172      a parsing error returns an index to the end of the string + 1.
173
174     Example: parser.Parse("3*x+y", "x,y");
175
176
177 ---------------------------------------------------------------------------
178 const char* ErrorMsg(void) const;
179 ---------------------------------------------------------------------------
180
181     Returns a pointer to an error message string corresponding to the error
182     caused by Parse() (you can use this to print the proper error message to
183     the user). If no such error has occurred, returns 0.
184
185
186 ---------------------------------------------------------------------------
187 double Eval(const double* Vars);
188 ---------------------------------------------------------------------------
189
190     Evaluates the function given to Parse().
191     The array given as parameter must contain the same amount of values as
192     the amount of variables given to Parse(). Each value corresponds to each
193     variable, in the same order.
194
195     Return values:
196     -On success returns the evaluated value of the function given to
197      Parse().
198     -On error (such as division by 0) the return value is unspecified,
199      probably 0.
200
201     Example:
202
203       double Vars[] = {1, -2.5};
204       double result = parser.Eval(Vars);
205
206
207 ---------------------------------------------------------------------------
208 int EvalError(void) const;
209 ---------------------------------------------------------------------------
210
211     Used to test if the call to Eval() succeeded.
212
213     Return values:
214       If there was no error in the previous call to Eval(), returns 0,
215       else returns a positive value as follows:
216         1: division by zero
217         2: sqrt error (sqrt of a negative value)
218         3: log error (logarithm of a negative value)
219         4: trigonometric error (asin or acos of illegal value)
220
221
222 ---------------------------------------------------------------------------
223 void Optimize();
224 ---------------------------------------------------------------------------
225
226     This method can be called after calling the Parse() method. It will try
227     to simplify the internal bytecode so that it will evaluate faster (it
228     tries to reduce the amount of opcodes in the bytecode).
229
230       For example, the bytecode for the function "5+x*y-25*4/8" will be
231     reduced to a bytecode equivalent to the function "x*y-7.5" (the original
232     11 opcodes will be reduced to 5). Besides calculating constant expressions
233     (like in the example), it also performs other types of simplifications
234     with variable and function expressions.
235
236       This method is quite slow and the decision of whether to use it or
237     not should depend on the type of application. If a function is parsed
238     once and evaluated millions of times, then calling Optimize() may speed-up
239     noticeably. However, if there are tons of functions to parse and each one
240     is evaluated once or just a few times, then calling Optimize() will only
241     slow down the program.
242       Also, if the original function is expected to be optimal, then calling
243     Optimize() would be useless.
244
245       Note: Currently this method does not make any checks (like Eval() does)
246     and thus things like "1/0" will cause undefined behaviour. (On the other
247     hand, if such expression is given to the parser, Eval() will always give
248     an error code, no matter what the parameters.) If caching this type of
249     errors is important, a work-around is to call Eval() once before calling
250     Optimize() and checking EvalError().
251
252       If the destination application is not going to use this method,
253     the compiler constant SUPPORT_OPTIMIZER can be undefined at the beginning
254     of fparser.cc to make the library smaller (Optimize() can still be called,
255     but it will not do anything).
256
257     (If you are interested in seeing how this method optimizes the opcode,
258     you can call the PrintByteCode() method before and after the call to
259     Optimize() to see the difference.)
260
261
262 ---------------------------------------------------------------------------
263 bool AddConstant(const std::string& name, double value);
264 ---------------------------------------------------------------------------
265
266     This method can be used to add constants to the parser. Syntactically
267     constants are identical to variables (ie. they follow the same naming
268     rules and they can be used in the function string in the same way as
269     variables), but internally constants are directly replaced with their
270     value at parse time.
271
272       Constants used by a function must be added before calling Parse()
273     for that function. Constants are preserved between Parse() calls in
274     the current FunctionParser instance, so they don't need to be added
275     but once. (If you use the same constant in several instances of
276     FunctionParser, you will need to add it to all the instances separately.)
277
278       Constants can be added at any time and the value of old constants can
279     be changed, but new additions and changes will only have effect the next
280     time Parse() is called. (That is, changing the value of a constant
281     after calling Parse() and before calling Eval() will have no effect.)
282
283       The return value will be false if the 'name' of the constant was
284     illegal, else true. If the name was illegal, the method does nothing.
285
286     Example: parser.AddConstant("pi", 3.14159265);
287
288     Now for example parser.Parse("x*pi", "x"); will be identical to the
289     call parser.Parse("x*3.14159265", "x");
290
291
292 ---------------------------------------------------------------------------
293 bool AddFunction(const std::string& name,
294                  double (*functionPtr)(const double*),
295                  unsigned paramsAmount);
296 ---------------------------------------------------------------------------
297
298     This method can be used to add new functions to the parser. For example,
299     if you would like to add a function "sqr(A)" which squares the value
300     of A, you can do it with this method (so that you don't need to touch
301     the source code of the parser).
302
303       The method takes three parameters:
304
305     - The name of the function. The name follows the same naming conventions
306       as variable names.
307
308     - A C++ function, which will be called when evaluating the function
309       string (if the user-given function is called there). The C++ function
310       must have the form:
311           double functionName(const double* params);
312
313     - The number of parameters the function takes. NOTE: Currently this
314       value must be at least 1; the parser does not support functions which
315       take no parameters (this problem may be fixed in the future).
316
317     The return value will be false if the given name was invalid (either it
318     did not follow the variable naming conventions, or the name was already
319     reserved), else true. If the return value is false, nothing is added.
320
321     Example:
322     Suppose we have a C++ function like this:
323
324     double Square(const double* p)
325     {
326         return p[0]*p[0];
327     }
328
329     Now we can add this function to the parser like this:
330
331     parser.AddFunction("sqr", Square, 1);
332
333     parser.Parse("2*sqr(x)", "x");
334
335
336     IMPORTANT NOTE: If you use the Optimize() method, it will assume that
337     the user-given function has no side-effects, that is, it always
338     returns the same value for the same parameters. The optimizer will
339     optimize the function call away in some cases, making this assumption.
340
341
342 ---------------------------------------------------------------------------
343 bool AddFunction(const std::string& name, FunctionParser&);
344 ---------------------------------------------------------------------------
345
346     This method is almost identical to the previous AddFunction(), but
347     instead of taking a C++ function, it takes another FunctionParser
348     instance.
349
350     There are some important restrictions on making a FunctionParser instance
351     call another:
352
353     - The FunctionParser instance given as parameter must be initialized
354       with a Parse() call before giving it as parameter. That is, if you
355       want to use the parser A in the parser B, you must call A.Parse()
356       before you can call B.AddFunction("name", A).
357
358     - The amount of parameters in the FunctionParser instance given as
359       parameter must not change after it has been given to the AddFunction()
360       of another instance. Changing the number of parameters will result in
361       malfunction.
362
363     - AddFunction() will fail (ie. return false) if a recursive loop is
364       formed. The method specifically checks that no such loop is built.
365
366     - As with the other AddFunction(), the number of parameters taken by
367       the user-defined function must be at least 1 (this may be fixed in
368       the future).
369
370     Example:
371
372     FunctionParser f1, f2;
373     f1.Parse("x*x", "x");
374     f2.AddFunction("sqr", f1);
375
376
377 ---------------------------------------------------------------------------
378
379   Example program:
380
381 #include "fparser.hh"
382 #include <iostream>
383
384 int main()
385 {
386     FunctionParser fp;
387
388     int ret = fp.Parse("x+y-1", "x,y");
389     if(ret >= 0)
390     {
391         std::cerr << "At col " << ret << ": " << fp.ErrorMsg() << std::endl;
392         return 1;
393     }
394
395     double vals[] = { 4, 8 };
396
397     std::cout << fp.Eval(vals) << std::endl;
398 }
399
400
401
402 =============================================================================
403   - The function string
404 =============================================================================
405
406   The function string understood by the class is very similar to the C-syntax.
407   Arithmetic float expressions can be created from float literals, variables
408 or functions using the following operators in this order of precedence:
409
410    ()             expressions in parentheses first
411    -A             unary minus
412    A^B            exponentiation (A raised to the power B)
413    A*B  A/B  A%B  multiplication, division and modulo
414    A+B  A-B       addition and subtraction
415    A=B  A<B  A>B  comparison between A and B (result is either 0 or 1)
416    A&B            result is 1 if int(A) and int(B) differ from 0, else 0.
417    A|B            result is 1 if int(A) or int(B) differ from 0, else 0.
418
419     Since the unary minus has higher precedence than any other operator, for
420   example the following expression is valid: x*-y
421     Note that the '=' comparison can be inaccurate due to floating point
422   precision problems (eg. "sqrt(100)=10" probably returns 0, not 1).
423
424   The class supports these functions:
425
426   abs(A)    : Absolute value of A. If A is negative, returns -A otherwise
427               returns A.
428   acos(A)   : Arc-cosine of A. Returns the angle, measured in radians,
429               whose cosine is A.
430   acosh(A)  : Same as acos() but for hyperbolic cosine.
431   asin(A)   : Arc-sine of A. Returns the angle, measured in radians, whose
432               sine is A.
433   asinh(A)  : Same as asin() but for hyperbolic sine.
434   atan(A)   : Arc-tangent of (A). Returns the angle, measured in radians,
435               whose tangent is (A).
436   atan2(A,B): Arc-tangent of A/B. The two main differences to atan() is
437               that it will return the right angle depending on the signs of
438               A and B (atan() can only return values betwen -pi/2 and pi/2),
439               and that the return value of pi/2 and -pi/2 are possible.
440   atanh(A)  : Same as atan() but for hyperbolic tangent.
441   ceil(A)   : Ceiling of A. Returns the smallest integer greater than A.
442               Rounds up to the next higher integer.
443   cos(A)    : Cosine of A. Returns the cosine of the angle A, where A is
444               measured in radians.
445   cosh(A)   : Same as cos() but for hyperbolic cosine.
446   cot(A)    : Cotangent of A (equivalent to 1/tan(A)).
447   csc(A)    : Cosecant of A (equivalent to 1/sin(A)).
448   eval(...) : This a recursive call to the function to be evaluated. The
449               number of parameters must be the same as the number of parameters
450               taken by the function. Usually called inside if() to avoid
451               infinite recursion.
452   exp(A)    : Exponential of A. Returns the value of e raised to the power
453               A where e is the base of the natural logarithm, i.e. the
454               non-repeating value approximately equal to 2.71828182846.
455   floor(A)  : Floor of A. Returns the largest integer less than A. Rounds
456               down to the next lower integer.
457   if(A,B,C) : If int(A) differs from 0, the return value of this function is B,
458               else C. Only the parameter which needs to be evaluated is
459               evaluated, the other parameter is skipped; this makes it safe to
460               use eval() in them.
461   int(A)    : Rounds A to the closest integer. 0.5 is rounded to 1.
462   log(A)    : Natural (base e) logarithm of A.
463   log10(A)  : Base 10 logarithm of A.
464   max(A,B)  : If A>B, the result is A, else B.
465   min(A,B)  : If A<B, the result is A, else B.
466   sec(A)    : Secant of A (equivalent to 1/cos(A)).
467   sin(A)    : Sine of A. Returns the sine of the angle A, where A is
468               measured in radians.
469   sinh(A)   : Same as sin() but for hyperbolic sine.
470   sqrt(A)   : Square root of A. Returns the value whose square is A.
471   tan(A)    : Tangent of A. Returns the tangent of the angle A, where A
472               is measured in radians.
473   tanh(A)   : Same as tan() but for hyperbolic tangent.
474
475
476   Examples of function string understood by the class:
477
478   "1+2"
479   "x-1"
480   "-sin(sqrt(x^2+y^2))"
481   "sqrt(XCoord*XCoord + YCoord*YCoord)"
482
483   An example of a recursive function is the factorial function:
484
485   "if(n>1, n*eval(n-1), 1)"
486
487   Note that a recursive call has some overhead, which makes it a bit slower
488   than any other operation. It may be a good idea to avoid recursive functions
489   in very time-critical applications. Recursion also takes some memory, so
490   extremely deep recursions should be avoided (eg. millions of nested recursive
491   calls).
492
493   Also note that the if() function is the only place where making a recursive
494   call is safe. In any other place it will cause an infinite recursion (which
495   will make the program eventually run out of memory). If this is something
496   which should be avoided, it may be a good idea to disable the eval()
497   function completely.
498   The eval() function can be disabled with the DISABLE_EVAL precompiler
499   constant (see the beginning of fparser.cc).
500
501
502 =============================================================================
503   - Contacting the author
504 =============================================================================
505
506   Any comments, bug reports, etc. should be sent to warp@iki.fi
507
508
509 =============================================================================
510   - The algorithm used in the library
511 =============================================================================
512
513   The whole idea behind the algorithm is to convert the regular infix
514 format (the regular syntax for mathematical operations in most languages,
515 like C and the input of the library) to postfix format. The postfix format
516 is also called stack arithmetic since an expression in postfix format
517 can be evaluated using a stack and operating with the top of the stack.
518
519   For example:
520
521   infix    postfix
522   2+3      2 3 +
523   1+2+3    1 2 + 3 +
524   5*2+8/2  5 2 * 8 2 / +
525   (5+9)*3  5 9 + 3 *
526
527   The postfix notation should be read in this way:
528
529   Let's take for example the expression: 5 2 * 8 2 / +
530   - Put 5 on the stack
531   - Put 2 on the stack
532   - Multiply the two values on the top of the stack and put the result on
533     the stack (removing the two old values)
534   - Put 8 on the stack
535   - Put 2 on the stack
536   - Divide the two values on the top of the stack
537   - Add the two values on the top of the stack (which are in this case
538     the result of 5*2 and 8/2, that is, 10 and 4).
539
540   At the end there's only one value in the stack, and that value is the
541 result of the expression.
542
543   Why stack arithmetic?
544
545   The last example above can give you a hint.
546   In infix format operators have precedence and we have to use parentheses to
547 group operations with lower precedence to be calculated before operations
548 with higher precedence.
549   This causes a problem when evaluating an infix expression, specially
550 when converting it to byte code. For example in this kind of expression:
551     (x+1)/(y+2)
552 we have to calculate first the two additions before we can calculate the
553 division. We have to also keep counting parentheses, since there can be
554 a countless amount of nested parentheses. This usually means that you
555 have to do some type of recursion.
556
557   The most simple and efficient way of calculating this is to convert it
558 to postfix notation.
559   The postfix notation has the advantage that you can make all operations
560 in a straightforward way. You just evaluate the expression from left to
561 right, applying each operation directly and that's it. There are no
562 parentheses to worry about. You don't need recursion anywhere.
563   You have to keep a stack, of course, but that's extremely easily done.
564 Also you just operate with the top of the stack, which makes it very easy.
565 You never have to go deeper than 2 items in the stack.
566   And even better: Evaluating an expression in postfix format is never
567 slower than in infix format. All the contrary, in many cases it's a lot
568 faster (eg. because all parentheses are optimized away).
569   The above example could be expressed in postfix format:
570     x 1 + y 2 + /
571
572   The good thing about the postfix notation is also the fact that it can
573 be extremely easily expressed in bytecode form.
574   You only need a byte value for each operation, for each variable and
575 to push a constant to the stack.
576   Then you can interpret this bytecode straightforwardly. You just interpret
577 it byte by byte, from the beginning to the end. You never have to go back,
578 make loops or anything.
579
580   This is what makes byte-coded stack arithmetic so fast.
581
582
583
584 =============================================================================
585   Usage license:
586 =============================================================================
587
588 Copyright © 2003 Juha Nieminen, Joel Yliluoma
589
590   1. This library is free for non-commercial usage. You can do whatever you
591      like with it as long as you don't claim you made it yourself.
592
593   2. It is possible to use this library in a commercial program, but in this
594      case you MUST contact me first (warp@iki.fi) and ask express permission
595      for this. I want to know what type of program it is going to be, its
596      price and so on.
597        If you are making a free program or a shareware program with just a
598      nominal price (5 US dollars or less), you don't have to ask for
599      permission.
600        In any case, I DON'T WANT MONEY for the usage of this library. It is
601      free, period.
602
603   3. You can make any modifications you want to it so that it conforms your
604      needs. If you make modifications to it, you have, of course, credits for
605      the modified parts.
606
607   4. If you use this library in your own program, you don't have to provide
608      the source code if you don't want to (ie. the source code of your program
609      or this library).
610        If you DO include the source code for this library, this text file
611      must be included in its original intact form.
612
613   5. If you distribute a program which uses this library, and specially if you
614      provide the source code, proper credits MUST be included. Trying to
615      obfuscate the fact that this library is not made by you or that it is
616      free is expressly prohibited. When crediting the usage of this library,
617      it's enough to include my name and email address, that is:
618      "Juha Nieminen (warp@iki.fi)". Also a URL to the library download page
619      would be nice, although not required. The official URL is:
620        http://iki.fi/warp/FunctionParser/
621
622   6. And the necessary "lawyer stuff":
623
624      The above copyright notice and this permission notice shall be
625      included in all copies or substantial portions of the Software.
626
627      The software is provided "as is", without warranty of any kind,
628      express or implied, including but not limited to the warranties of
629      merchantability, fitness for a particular purpose and noninfringement.
630      In no event shall the authors or copyright holders be liable for any
631      claim, damages or other liability, whether in an action of contract,
632      tort or otherwise, arising from, out of or in connection with the
633      software or the use or other dealings in the software.