Thursday, June 14, 2012

Mathematical Expression Parser in C

An updated version of this library supporting custom variables/functions as well as boolean expressions is available from Github at:

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:



 @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

sin(1.0)^2 + cos(1.0)^2=1.000000
2^-(2.0*fabs(-sqrt(sin(0.5)^2 + cos(0.5)^2)))=0.250000

You can the source code from Github:

Sunday, June 10, 2012

CGAL Build Issues Under OS-X 10.7

Update, Oct. 9, 2013: XCode 4 seems to fix the problems from this post, I have successfully built code using CGAL for tetrahedralization using Apple's distribution of LLVM and CLANG as of OS-X 10.8. I'm leaving this post up for users of 10.7 who might wonder what is the problem is.

There's recently been a bunch of trouble using CGAL (among other packages) under OS-X 10.7 Lion.  The issue appears to be that the strict rounding modes (-frounding-math in GCC) required by CGAL and other libraries that use exact geometric predicates are no longer available in the compilers shipped with Lion.

Between OS-X 10.6 and 10.7, Apple switched from using GCC to LLVM/Clang, providing a wrapper that translates GCC command-line arguments to their LLVM equivalents.  LLVM and Clang do not support correct rounding modes, so exact geometric predicates currently operate incorrectly in release builds.  The result is programs that operate correctly (at least sometimes) when in debug mode, but which crash inexplicably in optimized builds.

To the best of my knowledge, the only workaround is to install your own copy of GCC and build the relevant libraries using it.  This means you can't use XCode, since the correct options are not available, and I've heard nasty stories of the Apple compilers behaving poorly when there's another GCC installed.  I originally bought a Mac in order to have a nice development environment with the ability to run Linux/Unix software, so I'm finding this development rather irritating.

The ideal fix for this would be for LLVM and/or Clang to actually implement these rounding modes, but after a year since the first bug reports showed up, this doesn't seem to be fixed.  I find this incredible, since you would think that compliance with the floating point specification (IEEE 754) would be a fundamental priority for any serious compiler project.

3-Axis A4988 Stepper Driver Carrier

More on the perpetually in-progress CNC (see the mechanical stuff in parts I, II, III, IV)

I've recently built a prototype board for the Pololu A4988 stepper drivers carriers.  These little drivers are inexpensive (about $12) and fairly gutsy (2A per phase), but can blow fairly easily.  Using male headers they can easily be used as drop in modules for a larger CNC controller board.  My board breaks out the microstepping pins to DIP switches and adds screw terminal connections for the high-power side, with female headers for the TTL control inputs and low-power supply.

The two-pin set of female headers on the left is the low-power supply, the middle six-pin set of headers is the step/direction controls for each of the axes and the bottom six-pin header is for upper and lower limit switches for each axis.  The top set of two-pin screw-terminals is the motor power-supply and the remaining 3x6 pin connectors are the motor winding connections with the bottom two terminals for upper and lower limit inputs.  Unfortunately I ran out of space on the board to provide a 5V supply to the limit switches, so these will have to be wired externally to 5V.  I may also add some pull-down resistors to the backside of the board, since the switches are currently floating, although this does not seem to be a problem in practice for some reason.

There's a surprising number of solder joints needed for this simple board, largely due to using point-to-point wiring, but it seems to be electrically sound:

This board really cleans up my testing rig for the CNC, just a few jumper wires are all that's needed to connect my Arduino to the two mostly-finished translation stages.  Using screw-terminals instead of soldered on connectors is also much more convenient when rewiring the steppers as bipolar parallel/serial during testing:

The final machine will probably not end up using this board, I'm considering investing in a proper 3-axis board, since they can be found quite cheaply on Ebay.  That said, it's a nice tidy little package that allows the stepper drivers to be replaced as needed as well as preventing the inevitable wiring mistakes that happen when developing on breadboards.