Should I use Lex or a home-brewed solution to parse a formula?

Question

I'm in the process of writing a small, rule-based 'math' engine. I realize this is unclear, so I'll provide a small example.

Let's say you have some variable a, that holds an integer. You also have some functions you can apply to the number, i.e.

• sqr - square the number
• flp - flip the bits of the number
• dec - decrement the number
• inc - increment the number

You can then say, do_formula(a, "2sqr+inc+flp"). If a were 3, it'd square it twice (81), increment it (82), and flip the bits of it (~82 -- which is -83, if dealing with signed integers, I believe).

What would be the best way of parsing the formula? It's relatively simple, and I'm thinking of making all the opcodes be 3 characters... would it be overkill to use Lex? Should I just write a simple home-brewed solution or use something else entirely?

I realize the above example is silly; I'm not building a calculator that'll do that, but it illustrates what I'm trying to do well enough.

Answer 1

Yes, seems like an overkill in this case. Just split the string on '=", and then apply the operations one after another. Thank god for dictionaries and functions as first-class citizen your engine can be written in 0.5 - 1 pages of code.

dct = {'sqr' : lambda a: a * a, ...}

ntimes, op = token[:-3], token[-3:]
ntimes = 0 if len(ntimes) == 0 else int(ntimes)

..
dct[op](a)

Answer 2

It really depends on how big your project is going to end up being: If you're looking at creating a new language or something that's parsing more interesting grammars than just + then I'd say lex would be a fun and entertaining way to spend an afternoon.

On the other hand, writing your own parser is extremely informative and not particularly hard if you've really thought out the grammar beforehand.

The question really ends up being which language to do the parsing in? Haskell would be a really fun choice and provided a lot of interesting revelations for me when I wrote my first parser a couple years ago.

Answer 3

If you have some free time and want to learn a new programming paradigm, give Prolog a spin!

Answer 4

If your grammar isn't super-complex and you don't mind doing it in Python, pyparsing could be just what the doctor ordered. I implemented something fairly similar for parsing chemical equations and it took me an hour or so to do it. I'd add the code here, but it wouldn't be particularly relevant.

Answer 5

What's your host language? For Ruby, I really like treetop. It's a bit hard to get started, but I've used it with success for parsing more complicated math expressions.