fast math expression parser

This is a code i wrote when i had inspiration from a recent topic about designing languages.
Its a math parser, i am working for adding support for math function and maybe in the future
more advanced like integration and differentiation but this goes outside my main game development interest :P
I would love to know how and if you are using in your pojects, there shouldn't be any bugs ,
i spent much time working on error detection but something may always slip from hands.

#include "stdafx.h"
#include <string>
#include <iostream>
#include <fstream>
#include <cstdarg>
#include <assert.h>

using namespace std;

/////////////////////////////////////////////////////////////////////////

#define		MAXIDSIZE		256

enum EToken
{
	TEnd,
	TValue,
	TPlus,
	TMinus,
	TMul,
	TDiv,
	TMod,
	TExp,
	TLparen,
	TRparen,
	TAssign,
	TIdent
};

enum EError
{
	ETextExpected,
	EUnknownSymbol,
	EIncompleteExpression,
	EExpectedIdentifierOrNumeric,
	EExpectedParenBalance,
	EExpectedIdentifier,
	EExpcetedNumeric,
	EExpectedLParen,
	EExpectedRParen,
	EIdentifierTooLong
};

//////////////////////////////////////////////////////////////////////////

class CExprParser 
{
	char	   *Look;
	double		Value;
	EToken		Token;
	char		Identifier[MAXIDSIZE];

	bool EatSymbol( void )
	{
		
		int Lenght=0;
		
		memset( Identifier,0,sizeof(char)*MAXIDSIZE );

		if ( isalpha( *Look ) || *Look=='_' )
		{

			Token=TIdent;

			do
			{
				Identifier[ Lenght++ ]=*Look;
				
				if ( Lenght>=MAXIDSIZE) 
					return Error( EIdentifierTooLong );
	
				Look++;
			} 
			while ( isalnum( *Look ) || *Look =='_' );
			
		}
		else
		{
			return false;
		}
		
		return true;
	};

	bool GetNextToken( void )
	{
		
		if ( *Look==NULL )
		{
			Token=TEnd; 
			return true; }

		// Skip over white space.

		while ( isspace( *Look   ) )
			Look++;

		switch ( *Look )
		{
			// check for delimiter

			case '+'  : *Look++ ; Token= TPlus;   break;
			case '-'  : *Look++ ; Token= TMinus;  break;
			case '*'  : *Look++ ; Token= TMul;    break;
			case '/'  : *Look++ ; Token= TDiv;	  break;
			case '='  : *Look++ ; Token= TAssign; break;
			case '('  : *Look++ ; Token= TLparen; break;
			case ')'  : *Look++ ; Token= TRparen; break;
			case '%'  : *Look++ ; Token= TMod;	  break;
			case '^'  : *Look++ ; Token= TExp;	  break;

			// check for numeric

			case '0'  :
			case '1'  :
			case '2'  :
			case '3'  :
			case '4'  :
			case '5'  :
			case '6'  :
			case '7'  :
			case '8'  :
			case '9'  : 
			case '.'  : 
						//////////////////////////////////////////
						// eat numeric value

						char *p;
						Value=strtod( Look,&p );
						Look=p;
						Token=TValue;
				
						break;

			// end of text

			case '\0' : Token=TEnd;	   break;
	
			// check for symbolic

			default   :	
				
						if ( !EatSymbol() ) 
							return Error( EUnknownSymbol );

						Token=TIdent ;

						break;
		}

		return true;
	}

	bool Error( int err )
	{
		switch ( err )
		{
			case ETextExpected:					ErrorString="Error: No Text\n";				    break;
			case EIncompleteExpression:			ErrorString="Error: Syntax error\n";			break;	
			case EUnknownSymbol:				ErrorString="Error: Unknown identifier\n" ;		break;
			case EExpectedIdentifierOrNumeric:  ErrorString="Expected Identifier or numeric\n"; break;
			case EExpectedIdentifier:			ErrorString="Expected Identifier\n";			break;
			case EExpcetedNumeric:				ErrorString="Expected numeric\n";				break;
			case EExpectedLParen:				ErrorString="Error: expected '('";				break;
			case EExpectedRParen:				ErrorString="Error: expected ')'";				break;
			case EExpectedParenBalance:			ErrorString="Error: Parenthesys unbalanced\n";  break;
			case EIdentifierTooLong	:			ErrorString="Error: Identifier too long\n";		break;	
		};
		return false;
	}
	
	bool VerifyParenthesysBalance( void )
	{
		int	count=0;
	
		char *ptr;
		
		ptr=Look;

		do
		{
			if ( *ptr=='(' ) count++;
				else 
					if ( *ptr==')' ) count--;
		
			ptr++;
		}
		while ( *ptr!=0 ) ;

		return ( count==0 ) ;
	}
	
	bool Factor ( double &c )
	{
		if ( Token==TValue )
		{
			c=Value;
		}
		else if ( Token==TMinus )
		{
	 		if ( GetNextToken()==false )
				return false;

			if ( Token==TValue )
				c=-Value;

			else if ( Token==TLparen )
			{
				double b;
				
				if ( GetNextToken()==false )
					return false;
				
				Expr( b  );

				c=-b;

				if ( Token!=TRparen && Token!=TEnd )
					return Error( EExpectedRParen  );

			}
			else
			{
				return Error( EIncompleteExpression );
			}
		}
		else if ( Token==TPlus )
		{
			if ( GetNextToken()==false )
				return false;
		
			if ( Token==TValue )
				c=Value;

			else if ( Token==TLparen )
			{
				double b;
				
				if ( GetNextToken()==false )
					return false;

				Expr( b  );

				c=b;

				if ( Token!=TRparen && Token!=TEnd )
					return Error( EExpectedRParen  );

			}
			else
			{
				return Error( EIncompleteExpression );
			}

		}
		else if ( Token==TLparen )
		{
			double b;

			if ( GetNextToken()==false )
				return false;
			
			Expr( b  );

			c=b;
			
			if ( Token!=TRparen && Token!=TEnd )
				return Error( EExpectedRParen  );

		}
		else if ( Token==TRparen )
		{
			// () condition, no value returned
			c=0.0f;
			return true;
		}
		else if ( Token==TEnd )
		{
			return Error( EIncompleteExpression );
		}

		else 
		{
			return Error( EUnknownSymbol );
		}
		
		return true;
	}

	bool Term ( double &c )
	{
		double b;

		if ( Factor( c )==false ) 
			return false;

		if ( GetNextToken()==false )
			return false;

		while ( Token==TMul || Token==TDiv )
		{

			if ( Token==TMul )
			{
				if ( GetNextToken()==false )
					return false;

				if ( Factor ( b )==false )
					return false;

				c*=b;
			}
			else if ( Token==TDiv )
				{
					if ( GetNextToken()==false )
						return false;

					if ( Factor ( b )==false )
						return false;

					c/=b;
					
				}
	
			if ( GetNextToken()==false )
				return false;
		}
		
		return true;
	}
         
	bool Expr( double &c )
	{
	
		double b;

		if ( Term ( c )==false )
			return false;

		while ( Token==TPlus || Token==TMinus )
		{

			if ( Token == TPlus )
			{
				if ( GetNextToken()==false )
					return false;

				if ( Term( b )==false )
					return false;

				c+=b;
			}
			else if ( Token == TMinus )
			{
				if ( GetNextToken()==false )
					return false;
				
				if ( Term( b )==false )
					return false;

				c-=b;
			}
			
			if ( Token!=TPlus   && 
				 Token!=TMinus  && 
				 Token!=TRparen && 
				 Token!=TEnd )
				{
					return Error( EIncompleteExpression );
				}		
		}

		return true;
	}

	public :

	bool Parse( char *text )
	{
		if ( text==NULL )
			return  Error( ETextExpected ) ;

		double result;

		Look=text;

		Token=TEnd;

		Value=0.0f;

		if ( VerifyParenthesysBalance()==false )
			 return Error(EExpectedParenBalance);
	
		GetNextToken();

		Expr( result  );

		cout << result << endl;

		return true;

	}

	//////////////////////////////////

	string	    ErrorString;

	CExprParser()
	{
		Value=0.0f;
		Look=NULL;	
	};

   ~CExprParser()
	{
    };

};


//////////////////////////////////////////////////////////////////////////

int _tmain( )
{

	string text=" 2 + 3 - 2*( 3+2 )*4 ";

	cout << "Parsing : " << text << endl << endl;

	CExprParser parser;

	parser.Parse( &text[0] );
 
	cout << parser.ErrorString << endl;

	cin.get();

	return 0;
}

Nice, a recursive descent parser. It could be simpler though, by using Dijkstra's Shunting Yard algorithm.

Btw, it's parantheses, not paranthesys

Sorry english is not my native language

Oh interesting, I wrote an expression parser only a month ago. I implemented the Reverse Polish Notation algorithm, though. It was used on a proprietary bytecode language for a specific system I'm involved (I got to develop the custom language...).

...i was expecting harsh comments...

oh wow, this could actually be very useful for something like an in-game console. Nice work.

...i was expecting harsh comments...

Are you disappointed? :P

i forget that i am not anymore in gamedev comunity :P

Originally Posted by v71

i forget that i am not anymore in gamedev comunity :P

yep, that's what I thought XD
Do a good job there = flamed

This is also good if you want to use interpreted ai in your game, with real arithmetic calculations interpreted on the fly...

Cool stuff, I thought about doing something like this a while back (though more like using someone else's library ;)

For benchmarking purposes, here are my results:

Core 2 Duo 1.8GHz, optimized release build VS 2008

100000 Tests.

Parsing : 2 + 3 - 2 * (3 + 2) * 4 = -35
Test 1: 250 milliseconds. Result = -35
Test 2: 266 milliseconds. Result = -35
Test 3: 265 milliseconds. Result = -35
Test 4: 250 milliseconds. Result = -35
Test 5: 250 milliseconds. Result = -35

Parsing : ((1 + (2 / 3)) * 0.5) + 0.1666666 = 1
Test 1: 312 milliseconds. Result = 1
Test 2: 313 milliseconds. Result = 1
Test 3: 297 milliseconds. Result = 1
Test 4: 297 milliseconds. Result = 1
Test 5: 313 milliseconds. Result = 1

It could be speeded up a little putting the term function inside the expr function, but it would be a nightmare for readability.

Readability and performance usually don't see eye to eye But I think these results are not bad considering the flexibility here, which is more important.

but it would be a nightmare for readability

If you really want to see a nightmare for readability, try adding a manual follow-set based error recovery to your expression parser. I had to do this for an university assignment once. It was not nice.

Good work with the parser, though
Guess this is a piece of code one can reuse over and over again.
Cheers,
- Wernaeh

Originally Posted by starstutter

yep, that's what I thought XD
Do a good job there = flamed

Uhm, if I look at http://www.gamedev.net/community/for...rictTo=Replies, then three years later http://www.gamedev.net/community/for...rictTo=Replies under ban evasion, then I wonder what good stuff that would be in that case.

Anyways, Vincenzo, so far that's good work.

Let me analyze your code syntactically/cosmetically only for now:

#include "stdafx.h"

MSVC only.

using namespace std;

Dirty, not good practice.

Lenght

Typo: "Length".

#define		MAXIDSIZE		256

Hardcoded maximum size. Not good practice, error prone.

bool EatSymbol( void )

Putting "void" there is C practice, but is uncommon C++ practice.

if ( GetNextToken()==false )

Explitly comparing against boolean literals is uncommon and redundant. Just write "if (!GetNextToken())", which many programmers will also find more readable.

NULL

Not standard C++ but MSVC++. Use the literal "0" instead.

CExprParser()
	{
		Value=0.0f;
		Look=NULL;	
	};

You might want to initialize instead of assign to your members: "CExprParser() : Value(0.0f), Look(0)".

bool Parse( char *text )

If you don't plan to modify the passed string, then use "const char *text". See also http://www.parashift.com/c++-faq-lit...rrectness.html about const correct code.

int _tmain( )

In standard C++, we say "int main ()", "_tmain()" is MSVC++ again.

parser.Parse( &text[0] );

Undefined behaviour.

21.3.4 basic_string element access [lib.string.access]

const_reference operator[](size_type pos) const;
reference operator[](size_type pos);

1 Returns: If pos < size(), returns data()[pos]. Otherwise, if pos == size(), the const version returns charT(). Otherwise, the behavior is undefined.

Better use text.c_str():

21.3.6 basic_string string operations [lib.string.ops]

const charT* c_str() const;

1 Returns: A pointer to the initial element of an array of length size() + 1 whose first size() elements equal the corresponding elements of the string controlled by *this and whose last element is a null character specified by charT().

The internal representation of std::string that you are dissecting does not have a \0 (null character).

cin.get();

What if your program is run in non-interactive mode?


edit: I forgot about your list of #includes:

//#include "stdafx.h" //! why?
#include <string>
#include <iostream>
//#include <fstream> //! why?
//#include <cstdarg> //! why?
#include <cassert> //! assert.h is for C
#include <cstring> //! was missing, needed for memset()
#include <cstdlib> //! was missing, needed for strtod()

edit: Another issue:

c/=b;

Here you should catch a division by zero before it happens, otherwise your program yields undefined behaviour (cf. ISO/IEC 14882:2003(E), Section 5 Expressions:

If during the evaluation of an expression, the result is not mathematically defined or not in the range of representable values for its type, the behavior is undefined

).

Originally Posted by phresnel

...

Thanks for the great introduction to the C++ standard, freely available to all interested, but I hope you are aware of the difference between prototyping something fast and getting a stable, clear code to the market for cash that adheres to the specs and would justify the countless hours of reading the standard. Moreover there are tools for that... I actually can't believe you waste as much time writing here than he probably needed to develop the code, which is not that bad at all. Never used includes? Who cares...

Originally Posted by Mihail121

Thanks for the great introduction to the C++ standard, but I hope you are aware of the difference between prototyping something fast and releasing a stable, clear code that adheres to the specification and follows design guidelines.

I posted a more-than-1-line-critique for a buggy program, and tried to give some hints to make it less bug-full and well-formed. I think it actually helps the OP, because he stated that he thinks that

there shouldn't be any bugs

.

Moreover there are tools for that...

Tools for what? I wrote more than one point.

Anyways: What you say is "learn unportable c++ that yields undefined behaviour and trust 3rd parties to fix that for you"

I actually can't believe you waste as much time writing here than he probably needed to develop the code, which is not that bad at all. Not used includes? Who cares...

Not so much, just 25 Minutes (=roughly 0.00006 % percent of an average 73 year human life), which I hope will help v71 to learn C++ better and improve his program. What is wrong with investing some spare time to write a proper post?

See also starstutters second post which might be interesting.

Originally Posted by phresnel

....

Not flamming you for anything, it's evident you are proficient with the specification, it's completely fine to provide help, it's fine to reveal bugs, it's just that my personal belief that the point of the post is to show a quick parser and nothing more. But I'm just being ignorant, most honestly your post was fully ok, sorry. Let's not start an off-topic war.

P.S.

What you say is "learn unportable c++ that yields undefined behaviour and trust 3rd parties to fix that for you"

No, that's not what I've said, contact me on ICQ\Skype and I'll explain it in German

Originally Posted by Mihail121

Not flamming you for anything, it's evident you are proficient with the specification, it's completely fine to provide help, it's fine to reveal bugs, it's just that my personal belief that the point of the post is to show a quick parser and nothing more. But I'm just being ignorant, most honestly your post was fully ok, sorry.

If my first post was a tad too offensive in some point, then I am sorry, that was not my intention. But yes, I am guilty of prosecuting not to write unportable code, and probably go into too much detail sometimes.

On the other hand, I also highly welcome other peoples critique on me or my stuff, e.g. once I release picogen 0.3, I'd be happy if people point out bugs or otherwise bad/dumb code that I did not recognize. Because once written, the probability is pretty high that I'll never fix some subtleties that really needed to be.

Let's not start an off-topic war.

Amen

Thanks for your dissection, i will work to fix those 'bugs'
why posting a 3 years old rants from gamedev ? how did you know my name ?

why is using namespace std , dirty ?????

Originally Posted by phresnel

#include "stdafx.h"

MSVC only.

Nonsense. Naming a header 'stdafx.h' is by no means MSVC only. There is no standard stdafx.h header in MSVC++. It's a user-defined header, usually containing precompiled stuff. Probably just a result of copypasting his code out of his project. There's nothing wrong with it, and there's nothing unportable about it.

using namespace std;

Dirty, not good practice.

In a header, yes. In a sourcefile everybody should decide for himself. All names in de std namespace are defined by the standard. Other symbols in the std namespace provided by the implementation should follow reserved names rules (start with a underscore followed by a capital letter, or contain double underscores), so accidental name clashes shouldn't happen.

NULL

Not standard C++ but MSVC++. Use the literal "0" instead.

Again, nonsense. According to ISO/IEC 14882:2003, paragraph C.2.2.3/1:

The macro NULL, defined in any of <clocale>, <cstddef>, <cstdio>, <cstdlib>, <cstring>, <ctime>, or <cwchar>, is an implementation-defined C++ null pointer constant in this International Standard (18.1).

#include <cassert> //! assert.h is for C

Oh, then what is the C++ counterpart of assert()?

Originally Posted by .oisyn

Nonsense. Naming a header 'stdafx.h' [...]'s nothing unportable about it.

Nitpicky, yes. But only in this case. When code is published that #includes unpublished blackboxes, then
a) (the "mild" form) it might not compile at all
b) (the "evil" form) intended behaviour and actual behaviour might largely vary. Think of #define macros, function overloads, template partial and explicit specializations, et al.

Where is the portability when a) or b) strike?

In a header, yes. In a sourcefile everybody should decide for himself.

In my opinion, blanket using statements should never exceed function scope. Scope should (imho) be as big as needed, but not bigger.

All names in de std namespace are defined by the standard.

And as the standard does not define which names may be defined outside "de std namespace", those pulled-in names may very well collide with your code. Sooner or later, with or without tweaking the sourcefile in question.

revision 0:
foo.hh:

#ifndef FOO_HH
#define FOO_HH
#endif

bar.cc:

#include <string>
using namespace std;
#include "foo.hh"
class list {};
int main () {
    list frogs;
}

revision 2048:
foo.hh:

#ifndef FOO_HH
#define FOO_HH
#include <list>
#endif

Example consequence (note: bar.cc was never changed anymore!):

main.cc: In function ‘int main()’:
main.cc:10: error: reference to ‘list’ is ambiguous
main.cc:6: error: candidates are: class list
/usr/include/c++/4.3/bits/stl_list.h:416: error:                 template<class _Tp, class _Alloc> class std::list
main.cc:10: error: reference to ‘list’ is ambiguous
main.cc:6: error: candidates are: class list
/usr/include/c++/4.3/bits/stl_list.h:416: error:                 template<class _Tp, class _Alloc> class std::list
main.cc:10: error: expected `;' before ‘frogs’

Again, nonsense. According to ISO/IEC 14882:2003, paragraph C.2.2.3/1:

int main () {
        int *p;
        if (NULL == p) {
        }
}

main.cc: In function ‘int main()’:
main.cc:3: error: ‘NULL’ was not declared in this scope

I am not sure whether I shall now dive into all my source code files and pull in unrelated #include files just to have NULL defined, or just follow the well established and less redundant convention of using a builtin literal that also happens to be portable.

Oh, then what is the C++ counterpart of assert()?

The macro assert(). Why?

Anyways, it is good practice to use the C++ counterparts of the C library where available. E.g., math.h defines cos and cosf, whereas cmath only defines the function name cos with three function overloads, thus reducing redundancy, improving readability of template code, helping to avoid the subtle issues when accidentally using 64bit floating point where only 32bit floating point is intended. There are some more less than irrelevant differences.

cassert and assert.h are the same, but why make an exception to the rule for only the assert macro?

Originally Posted by phresnel

Nitpicky, yes.

No, just wrong. "stdafx.h" is by no means "MSVC++ only"

In my opinion, blanket using statements should never exceed function scope. Scope should (imho) be as big as needed, but not bigger.

I agree with you on this, but the point is that it is not wrong or evil to do otherwise (as opposed to putting a using directive in a header, which *is* evil). It's just a matter of taste.

And as the standard does not define which names may be defined outside "de std namespace", those pulled-in names may very well collide with your code. Sooner or later, with or without tweaking the sourcefile in question.

And some think that you shouldn't use those names in the first place to avoid confusion. This is especially true for functions, due to the two phase name lookup in templates.
and obviously I meant "the" std namespace

int main () {
        int *p;
        if (NULL == p) {
        }
}

main.cc: In function int main():
main.cc:3: error: NULL was not declared in this scope

I am not sure whether I shall now dive into all my source code files and pull in unrelated #include files just to have NULL defined, or just follow the well established and less redundant convention of using a builtin literal that also happens to be portable.

That is besides the point. NULL is not C only. It is just as well C++, and pulling in a header for a language construct is nothing strange (see typeid()). And some think using NULL makes the code more readable. Of course, it has other problems as well (the 0 literal has these as well, but would make these more evident to the programmer), but that will be fixed with nullptr, in which case we will al be using 'nullptr' rather than '0'.

The macro assert(). Why?

I'm sorry, I misread your comment. I thought you said you didn't need <cassert> as assert() is not C++, but I see now that you meant that you should include <cassert> rather than <assert.h>. Of course I can do nothing other than to agree on that

Man, you guys need to get out more

Originally Posted by .oisyn

No, just wrong. "stdafx.h" is by no means "MSVC++ only"

Oops, okay. My intention was more to tell about #including unknown code, rather than to complain about what was MSVC once. Bad wording from my side.

I agree with you on this, but the point is that it is not wrong or evil to do otherwise (as opposed to putting a using directive in a header, which *is* evil). It's just a matter of taste.

Okay. My taste is to pollute namespaces and scope as sparse as possible. I think it makes my code more "future compatible".

And some think that you shouldn't use those names in the first place to avoid confusion.

But then the problem is that only the fewest know which words are reserved for the standard (I don't belong to them), and it doesn't help that every decade a plethora of new words are reserved. Especially the upcoming standard will describe a lot of new names, of which are some pretty common in some C++ milieus (e.g. I've seen several different mt19937 in the one or another path tracer implementation; I can only hope they [and me] did not use using namespace, as C++0x describes that name [for kicks, g++-4.4 -std=c++0x, header should be <random>], and many, many others).

That is besides the point. NULL is not C only. It is just as well C++, and pulling in a header for a language construct is nothing strange (see typeid()). And some think using NULL makes the code more readable. Of course, it has other problems as well (the 0 literal has these as well, but would make these more evident to the programmer), but that will be fixed with nullptr, in which case we will al be using 'nullptr' rather than '0'.

That's right. Though I think 0 vs. pointers is evident enough. I personally consider typeid() and NULL a bit, uhm, dirty, for you must include headers for them (in that respect, I find typeid() even dirtier -> typeid()=first class operator, but "return value" of it needs header ). Okay, personal opinion.

Originally Posted by TheNut

Man, you guys need to get out more

Where, ..., there are people?

joke aside, actually I have a significant other, enjoy pubs, and from time to time go for a walk: http://phresnel.deviantart.com/

Originally Posted by TheNut

Man, you guys need to get out more