Need a way to parse algebraic expressions in C

Question

I need to parse algebraic expressions for an application I'm working on and am hoping to garnish a bit of collective wisdom before taking a crack at it and, possibly, heading down the wrong road.

What I need to do is pretty straight forward: given a textual algebraic expression (3*x - 4(y - sin(pi))) create a object representation of the equation. The custom objects already exist, so I need a parser that creates a tree I can walk to instantiate the objects I need.

The basic requirements would be:

1. Ability to express the algebra as a grammar so I have control and can customize/extend it as necessary.

2. The initial syntax will include integers, real numbers, constants, variables, arithmetic operators (+, - , *, /), powers (^), equations (=), parenthesis, precedence, and simple functions (sin(pi)). I'm hoping to extend my app fairly quickly to support functions proper (f(x) = 3x +2).

3. Must compile in C as it needs to be integrated into my code.

I DON'T need to evaluate the expression mathematically, so software that solves for a variable or performs the arithmetic is noise.

I've done my Google homework and it looks like the best approach is to use a BNF grammar and software to generate a compiler in C. So my questions:

1. Does a BNF grammar with corresponding parser generator for algebraic expressions (or better yet, LaTex) already exist? Someone has to have done this already. I REALLY want to avoid rolling my own, mainly because I don't want to test it. I'd be willing to pay a reasonable amount for a library (under $50)

2. If not, which parser generator for C do you think is the easiest to learn/use here? Lex? YACC? Flex, Bison, Python/SymPy, Others? I'm not familiar with any of these.

Answer 1

I've had very good luck with ANTLR. It has runtimes for many different languages, including C, and has a very nice syntax for specifying grammars and building trees. I recently wrote a similar grammar (algebraic expressions) in 131 lines, which is definitely manageable.

Answer 2

The standard Linux tools flex and bison would probably be most appropriate here. IIRC the sample parsers and lexers used in these tools do something close to what you want, so you might be able to just modify that code to get what you need.

These tools seem like they meet your specifications. You can customize the grammars, compile down to C, and use any operator you want.

Answer 3

I used the code (found on the net) from the following:

Program Translation Fundamentals" by Peter Calingaert

I enhanced it to handle functions, which lets you implement things like "if(a, b, c)" (kind of like how Excel does things).

Answer 4

you can build simple parser yourself or use any of popular "compiler-compiler" (some of them were listed by other posts). just decide if your parser will be complicated enough to use (and learn) an external tool. in any case you'll need to define the grammar, usually it's the most brain intensive task if you don't have prior experience. the formal way to define syntactic grammars is BNF or EBNF