Brains, Programming Languages, Disconnected Enthusiasms

Monday, October 01, 2007

A simple calculator

After a long struggle with some wildly inefficient algorithms, I've given up on Parsnip's more exotic parse strategies. Unfortunately, this means my long held goal of allowing left-recursion is out. To keep Parsnip user code readable (by avoiding left-factoring) I just wrote the OpTableParser class, which implements operator precedence parsing. The syntax of operator parsing is a bit funky, but not so mysterious if you keep in mind that infix_left returns an OpTableParser pointer. For an example, here's a parser/evaluator for simple mathematical expressions.

//First we need some functions to evaluate our mathematical expressions

double multiply(double x, double y) { return x*y; }
double add(double x, double y) { return x+y; }
double subtract(double x, double y) { return x-y; }
double divide(double x, double y) { return x/y; }

// Our parser will accept a string and return a double

typedef Parser<string, double>::type NumParser;

// Here is the new operator precedence parser
// The infix_left method accepts an operator string, its precedence and
// an associate reducer function

NumParser ops = op_table(real)
->infix_left("+", 10, add)
->infix_left("-", 10, subtract)
->infix_left("*", 20, multiply)
->infix_left("/", 20, divide);

Our parser will return a double if it succeeds. The returned value, along
with any error info, will be stored in a ParseResult object

ParseResult<double> result;

result = parse("3+4*2", ops);

if (result.parse_finished())
std::cout <<;