Boost logo

Boost :

Subject: Re: [boost] [GSoC] Some new ideas for this year's GSoC
From: Stefan (mstefanro_at_[hidden])
Date: 2010-04-06 17:06:08


Topher Cooper wrote:
> 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
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>
Yes, I apologize. The "hard-very hard" wasn't meant to be there (I only
wanted to use very-easy and easy on the difficulty tags initially). This
is quite trivial to implement and all the other ideas are. I agree that
these alone aren't sufficient for a proposal as they would be all
finished in a relatively small amount of time, but I was thinking of
implementing some of these in addition to one of the boost's ideas.
Also, you have good points on associativity and preferring the use of
templates, appreciated.

Stefan


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk