www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Math-Parser

reply Tim Holzschuh via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
Hi there,

I currently try to write a simple math-parser in D.

However.. something isn't working and I just can't figure out what's the 
problem.
(I'm relative new to D, and this is my first test to write a parser/lexer)

I'm pretty sure it's a simple layer-8-problem, but I always overlook it.

While the Lexer seems to work, the Parser just sets _index -> 0
(and I don't understand why..).

If you would take a look at [1], I'd be very thankful..

Most probably this isn't a wrong use of something D-specific, it's more 
like I am stuck..^^

Thank you,
     Tim

[1]: https://github.com/tholzschuh/math-parser
May 02 2014
next sibling parent reply "Rikki Cattermole" <alphaglosined gmail.com> writes:
On Friday, 2 May 2014 at 22:34:48 UTC, Tim Holzschuh via 
Digitalmars-d-learn wrote:

 Hi there,

 I currently try to write a simple math-parser in D.

 However.. something isn't working and I just can't figure out 
 what's the problem.
 (I'm relative new to D, and this is my first test to write a 
 parser/lexer)

 I'm pretty sure it's a simple layer-8-problem, but I always 
 overlook it.

 While the Lexer seems to work, the Parser just sets _index -> 0
 (and I don't understand why..).

 If you would take a look at [1], I'd be very thankful..

 Most probably this isn't a wrong use of something D-specific, 
 it's more like I am stuck..^^

 Thank you,
     Tim

 [1]: https://github.com/tholzschuh/math-parser


General suggestions:
Don't commit the build ext. files along with source code and in 
this case they aren't needed. Mono-D can load dub.json straight. 
As well as the obj/bin directories.

With regards to your issues I have a suspicion about it being how 
your parse the tokens. Within the parser.
Without really trying out atleast thats what I'm guessing.
May 03 2014
parent Tim Holzschuh via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
Am 03.05.2014 11:17, schrieb Rikki Cattermole via Digitalmars-d-learn:

 General suggestions:
 Don't commit the build ext. files along with source code and in this 
 case they aren't needed. Mono-D can load dub.json straight. As well as 
 the obj/bin directories.


Yeah you're right, thank you.
(And thank your for the Mono-D, dub thing, didn't know that..)

Tim
May 03 2014
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 05/03/2014 12:34 AM, Tim Holzschuh via Digitalmars-d-learn wrote:

 Most probably this isn't a wrong use of something D-specific


Some of the problems are:

 property Lexer lexer() pure { return _lexer; }

If you change the result of a call to 'lexer' this will not change 
'_lexer'. Mark the property 'ref' or get rid of it


if( !previous && !token.type == TokenType.end )
     popFront();

=>

if(!previous && token.type != TokenType.end) popFront();


Let me know if you also want hints on how to get the logic right.
May 03 2014
parent reply Tim Holzschuh via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
Am 03.05.2014 13:29, schrieb Timon Gehr via Digitalmars-d-learn:

  property Lexer lexer() pure { return _lexer; }

 If you change the result of a call to 'lexer' this will not change 
 '_lexer'. Mark the property 'ref' or get rid of it


How did I forget about Lexer being a struct is a value type...?
Thank you!


 if( !previous && !token.type == TokenType.end )
     popFront();


My favourite. *g*


 Let me know if you also want hints on how to get the logic right.


Would be very nice!
While 2*2 works, 2+2 throws an Error because the number-method gets an 
END-Token instead of a Number-Token (although I'm not sure why).

Thank you,
Tim
May 03 2014
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 05/03/2014 08:20 PM, Tim Holzschuh via Digitalmars-d-learn wrote:

 Let me know if you also want hints on how to get the logic right.


 Would be very nice!
 While 2*2 works, 2+2 throws an Error because the number-method gets an
 END-Token instead of a Number-Token (although I'm not sure why).

 Thank you,
 Tim


Get rid of 'revert' and implement the parser in terms of range 
primitives. (The first thing you do in the while loops should be a 
popFront().)
May 03 2014
parent reply Tim Holzschuh via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
Am 03.05.2014 21:47, schrieb Timon Gehr via Digitalmars-d-learn:

 On 05/03/2014 08:20 PM, Tim Holzschuh via Digitalmars-d-learn wrote:

 Let me know if you also want hints on how to get the logic right.


 Would be very nice!
 While 2*2 works, 2+2 throws an Error because the number-method gets an
 END-Token instead of a Number-Token (although I'm not sure why).

 Thank you,
 Tim


 Get rid of 'revert' and implement the parser in terms of range 
 primitives. (The first thing you do in the while loops should be a 
 popFront().)


Thank you very much, everything is working now!

I have just a few questions left:

The operator-precedence of the mathematical expressions is implemented 
through calling different functions that will parse in the 'mathematical 
way'.

I think for more complex 'interpreters' this would be very inconvenient.
So.. how is precedence of operators/keywords and so on handled for more 
complex parser? (Or better: What is a way to do it, I think there are 
many ways..)

Does anybody have some improvement-suggestions about the code?
For example:
I'm not sure whether the Token-struct is very elegant implemented..

Would in this case a Token-class with a NumberToken subclass be more 
appropriate?
Or maybe a union or something other..

Code: https://github.com/tholzschuh/math-parser/

So thanks again!
(and sorry for the bad english)

Tim
May 04 2014
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 05/04/2014 04:56 PM, Tim Holzschuh via Digitalmars-d-learn wrote:

 Am 03.05.2014 21:47, schrieb Timon Gehr via Digitalmars-d-learn:

 On 05/03/2014 08:20 PM, Tim Holzschuh via Digitalmars-d-learn wrote:

 Let me know if you also want hints on how to get the logic right.


 Would be very nice!
 While 2*2 works, 2+2 throws an Error because the number-method gets an
 END-Token instead of a Number-Token (although I'm not sure why).

 Thank you,
 Tim


 Get rid of 'revert' and implement the parser in terms of range
 primitives. (The first thing you do in the while loops should be a
 popFront().)


 Thank you very much, everything is working now!

 I have just a few questions left:

 The operator-precedence of the mathematical expressions is implemented
 through calling different functions that will parse in the 'mathematical
 way'.

 I think for more complex 'interpreters' this would be very inconvenient.
 So.. how is precedence of operators/keywords and so on handled for more
 complex parser? (Or better: What is a way to do it, I think there are
 many ways..)
 ...


http://en.wikipedia.org/wiki/Operator-precedence_parser


 Does anybody have some improvement-suggestions about the code?


Maybe, brevity?
This is roughly how I'd have written the expression evaluator:

double parse(string s){
     int prec(char op){return op=='+'||op=='-'?0:op=='*'||op=='/'?1:-1;}
     double run(char op,double a,double b){
         return op=='+'?a+b:op=='-'?a-b:op=='*'?a*b:a/b;
     }
     double expression()(int l=0){
         auto r=primary();
         while(s.length){
             auto op=s[0],p=prec(op);
             if(l>p) return r;
             s=s[1..$];
             r=run(op,r,expression(p+1));
         }
         return r;
     }
     double primary(){
         if(s[0]=='('){
             s=s[1..$];
             auto r=expression();
             if(s[0]!=')') throw new Exception("unbalanced parentheses");
             s=s[1..$];
             return r;
         }
         auto i=cast(size_t)0,r=0.0;
         for(;i<s.length&&'0'<=s[i]&&s[i]<='9';i++) r=r*10+s[i]-'0';
         if(!i) throw new Exception("expected number");
         s=s[i..$];
         return r;
     }
     auto r=expression();
     if(s.length) throw new Exception("end expected");
     return r;
}


 For example:
 I'm not sure whether the Token-struct is very elegant implemented..

 Would in this case a Token-class with a NumberToken subclass be more
 appropriate?


Not really. (You don't want to allocate a class object for every token 
read.)


 Or maybe a union or something other..

 Code: https://github.com/tholzschuh/math-parser/

 So thanks again!
 (and sorry for the bad english)

 Tim
May 04 2014
parent "Meta" <jared771 gmail.com> writes:
You could replace all those `op=='+'||op=='-'? ...` with
`op.among!('+', '-')? ...`.
May 04 2014