I recent wrote a recursive-descent mathematical expression parser. I started mainly to get a handle on the expression aspects of a mostly compliant NIST RS274NGC GCode interpreter that I would like to write. It is written in ANSI C with the hopes of being able to cross-compile for AVR, ARM, PIC and Propeller devices, while still supporting standard PCs as well. This pretty much rules out anything but C. Note that this parser does not support the expression syntax for GCode, but was written as a warmup exercise.
It's a pretty fun and surprisingly easy programming exercise to write one of these parsers; I recommend it for everyone. But for those who don't want to, I'm releasing the source code free for non-commercial use. For those who don't want to write it themselves but do want to to use it commercially (probably no-one), please contact me and generous terms can be arranged.
Anyway, the parser supports the standard infix mathematical notation, with operator precendence, unary +/-, an exponentiation operator (^) and the most useful of the math.h functions, like sin(), cos(), etc. The code is well commented for those that want to dive in and modify it.
Shown below is a sample driver script illustrating use of the parser:
#include<math.h>
#include<stdio.h>
#include"expression_parser.h"
/**
@brief macro to compare values as computed by C to those computed by the parser. creates a scope, initializes the parser and parses the string, then prints the expression, C result and parsed result. Does not handle the exponent operator '^', since it is not equivalent in C.
*/
#define parser_check( expr ) printf( "Parsing: '%s'\n", #expr ); \
printf( " C: %f\n", expr ); \
printf( " parser: %f\n\n", parse_expression( #expr ) );
void parser_test( const char *expr ){
double val = parse_expression( expr );
printf( "%s=%f\n", expr, val );
}
int main( int argc, char **argv ){
parser_check( 1.0 + 2.0 );
parser_check( -1.e-03 + 2E+1 );
parser_check( asin( sin( 1.0 ) ) );
parser_check( pow( sin(1.0), 2.0 ) + pow( cos(1.0), 2.0 ) );
parser_check( (0.1 + 4.9)*(2.5*2)*(-3.0-2.0) );
parser_check( log( exp( 25.0 ) ) );
parser_test( "2^2^3" );
parser_test( "sin(1.0)^2 + cos(1.0)^2" );
parser_test( "2^-2" );
parser_test( "2^-(2.0*fabs(-sqrt(sin(0.5)^2 + cos(0.5)^2)))" );
return 0;
}
The above code produces the output below:
Parsing: '1.0 + 2.0' C: 3.000000 parser: 3.000000 Parsing: '-1.e-03 + 2E+1' C: 19.999000 parser: 19.999000 Parsing: 'asin( sin( 1.0 ) )' C: 1.000000 parser: 1.000000 Parsing: 'pow( sin(1.0), 2.0 ) + pow( cos(1.0), 2.0 )' C: 1.000000 parser: 1.000000 Parsing: '(0.1 + 4.9)*(2.5*2)*(-3.0-2.0)' C: -125.000000 parser: -125.000000 Parsing: 'log( exp( 25.0 ) )' C: 25.000000 parser: 25.000000 2^2^3=256.000000 sin(1.0)^2 + cos(1.0)^2=1.000000 2^-2=0.250000 2^-(2.0*fabs(-sqrt(sin(0.5)^2 + cos(0.5)^2)))=0.250000
You can the source code from Github: https://github.com/jamesgregson/expression_parser
