Implement parsing of expressions

[certik]

We'll eventually need to implement a fast parser of expressions like: https://github.com/sympy/symengine/blob/8dd550ba20c0a13fb5a3e34c197c10bfaf79ae8d/benchmarks/expr.txt

Probably the easiest and most robust is to implement our own parser, I don't think it's very difficult, since it is just parsing of expressions. Here is one tutorial that I found (there are many out there): http://www.strchr.com/expression_evaluator, we just need to replace the return type double with RCP<const Basic>, and add support for functions and symbols. I think that's it.

(The main motivation is that SymPy takes a long time to sympify this long expression.)

[certik]

Here are a few more tutorials I found:

https://en.wikipedia.org/wiki/Recursive_descent_parser (wikipedia has a nice C code that does it)
http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/
http://www.codeproject.com/Articles/318667/Mathematical-Expression-Parser-Using-Recursive-Des
http://blog.erezsh.com/how-to-write-a-calculator-in-70-python-lines-by-writing-a-recursive-descent-parser/
http://teaching.idallen.com/cst8152/98w/recursive_decent_parsing.html
https://en.wikipedia.org/wiki/Shunting-yard_algorithm
http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
http://en.literateprograms.org/Shunting_yard_algorithm_%28C%29?oldid=12454

See also some codes:

https://github.com/ColinH/PEGTL
http://piumarta.com/software/peg/
https://fastmathparser.codeplex.com/
http://muparser.sourceforge.net/
http://muparser.beltoforion.de/
http://www.speqmath.com/tutorials/expression_parser_cpp/
https://code.google.com/p/math-parser-benchmark-project/
http://www.partow.net/programming/exprtk/

[srajangarg]

@certik , have researched into this, and will begin working.

I wanted to know how symbols will be represented? Will a user be made to enter
symbol(x)+1 or just x+1
In the latter case, how do we check if it's a symbol or an integer (we receive 'tokens' x and 1, but how do we know what is what)? (This problem won't occur with the symbol() implementation) One way is to see, if token string contains anything other than digits. If it does, then it's a symbol by default, otherwise treated as a number.

Another thing was dealing with double values entered. (2.34 + 1) Here, how should we convert the double into rational? Should there be a function which convertsfloat/double to Rational?

[srajangarg]

@isuruf @Sumith1896 Thoughts? I've already got a basic version running, and need to know specifics to proceed.

[isuruf]

For double 2.34 it should be RealDouble or RealMPFR depending on the number of digits.
You can use a regex to check if the token is numeric or not.

[rwst]

This needs thought on how to provide a parser to users of symengine, at all. I mean you don't change parsers within SymPy sessions either. Or is it thought purely for symengine devs to write tests?

[isuruf]

@rwst, what do you mean by

you don't change parsers within SymPy sessions either

[rwst]

Usually SymEngine is loaded manually onto an existing SymPy session. At this time the original parser is already active and symbols may exist.

[isuruf]

Even if symbols exist, there should be no problem right?
Are you referring to GiNaC's convention of symbol("x") != symbol("x")?

[rwst]

What if in SymPy:

In [1]: ex = x+y

In [2]: from symengine import *

In [3]: sin(ex)

Wouldn't there be a problem? The new parser would take ex as symbol and not call sin(Add).

[isuruf]

You are right. That will have to be considered. For the use case though it's not really a problem as it is more of a serialize/deserialize problem.

[isuruf]

@rwst, it seems SymPy doesn't do that either.

In [1]: from sympy import *

In [2]: x = 10

In [3]: sympify("x")
Out[3]: x

[certik]

@srajangarg as the first iteration, treat every name as a symbol, unless it is a known function. I assume we can design it so that the user can customize the list of functions. So if it is a number, let's do integers and rationals only for now, then it just returns Integer or Rational. Othewise if it is some text, it will create a symbol. Finally, if it is like sin(x) or f(x), then it will create either a known function, or a "function symbol".

I would not try to parse code like symbol("x") as initializing a symbol, at least not now.

Let me know if you have any other questions.

[Sumith1896]

Fixed via #772