Re: [boost] [GSoC] Some new ideas for this year's GSoC

Subject: Re: [boost] [GSoC] Some new ideas for this year's GSoC
From: Topher Cooper (topher_at_[hidden])
Date: 2010-04-06 14:29:36

Actually the difficulty is "easy".  The basic precedence parser  could be whipped out in an hour or so.  Another day or a bit more to do the interfacing, define the expression data structures, and do the constant folding.

Operators also need associativity, or, more expressively, two precedences -- a left and a right precedence.

You don't really need to specify "allowed variables" any more than you need to specify allowed literals -- if the parser sees a variable it can use it.

Personally I would include templates rather than just an operator string and then depend on the arity to determine the type.  Then you can handle ternary and postfix operators.

Topher

On Apr 6, 2010, at 8:01 AM, Stefan wrote:

> * A parser capable of evaluating mathematical expressions which contains operands,operators,function calls,variable names and constant names (also considering priority of operators):
> 1. a list of valid operators described by: a) number of operands (unary/binary/ternary?); b) allowed operand types; c) the precedence (priority of the operator)
> 2. a list of existent functions described by: a) function name; b) number of parameters; c) type of each parameter and return type; d) a callback (maybe just automatically deduce type based on the callback's type if possible)
> 3. a list of constants
> 4. a list of allowed variable names and types
> 
> Here's a pseudo-C++ code sample on how it should look like:
> namespace m = boost::math_expressions_parser;
> m::parser p;
> p.add_operators()
> ('+', 1, ret<int32_t>(_1+_2)) // binary +, precedence 1
> ('*', 2, ret<int32_t>(_1*_2)) // binary -, precedence 2
> ('+', 3, ret<int32_t>(_1)) // unary +, precedence 3
> ('-', 3, ret<int32_t>(-_1)); // unary - (also a funny face), precedence 3
> p.add_functions()
> ("sin", ret<int32_t>(sin(_1)));
> p.add_constants()
> ("PI", 3);
> p.add_allowed_variables()
> (allowed_var<int32_t>("x"));
> 
> m::expression E("1 + 3*sin(PI*x)", p); // evaluates mathematical expression E against parser p
> if (!E.valid()) { /* ... */ }
> else {
> std::cout << E.evaluate( ("x", 3) ); // evaluate this expression by letting x=3
> E.let() ("x",4);
> std::cout << E.evaluate();
> }
> //Maybe an optimization so only the parts that depend on the changed variable will be recalculated every time?. E.g.: for expression f(x)+y, f(x) is recomputed only when x is changed. This may cause problems for functions that do not always yield the same results for the same input. Maybe make this optimization optional, only if the user marks the function/operator as "volatile" or something
> Difficulty: hard-very hard