The way I do it is like this:

First, I break the string down into a linked list of tokens. To make this very simple, I'll ignore variables and focus on numeric constants and operators only.

Numeric constant tokens are pretty simple, they just contain a number.

Operator tokens contain the operator "type" (from an enumeration), the position in the string it was (eg, it was 35 characters in) and how many opened parentheses are before it. Here's what I mean by the parentheses:

 .  . .  .  .   .  .  .3+(2+4/(4-3)+((5*4)/2)-1) 0  1 1  2  1   3  2  1  <- each operator token's parenthesis index.

(Once read in, parentheses are ignored, so I just get a chain of operators and numbers).

Now I go through and find all of the operator tokens and collect them into a list. I then sort this list, based on the following criteria:

• Are the parenthesis indices different? If so, compare them and return the result.
• Are the operators different? If so, compare then and return the result.
• Compare the token's index within the original string and return the result. (For unary operators, the further right it is the higher precedence it is. For binary operators, the further left it is the higher precedence).

To sort the operator type (eg "Addition" vs "Shift Right") they are represented by an enumeration. I multiply the "real" value by 16, and return the precedence by diving by 16. To make this clearer, as an example, * might by 0, / might be 1 and + (which is the next level down in terms of order of precedence) skips ahead to 16. That way, to get the order of precedence, I divide by 16 and find that * and / are the same, but + is different.

Now I have this sorted list, I hammer through it, and use each operator token to "merge" the two tokens to either side. A bit like this:

       {4} {+} {5}        |___ ___|            |______ Grab the outer tokens and perform the operation on them.                   {4} {9} {5}            |______ Replace the operator with the result                    .  {9}  .        |_______|__ Delete the two constants.			If it's unary:	        {-} {1}             |___ Grab the rightmost token and perform the operation on it.		              .  {-1}              |__ Replace the token with the result and delete the operator.

That way, once you've finished going through your list of operators you'll only have one token left - and that's the result.

That's the basics, and it should (hopefully?) be simple enough to extend it to support "variable" tokens or "function" tokens. I've written it up in rather more detail here.

Hopefully that's not too confusing or convoluted. (My old version used a more direct approach - string manipulation, searching for operators using substrings - that sort of thing. Needless to say it's incredibly slow and full of hacks to keep it working).

If you've got a copy of Stroustrup's The C++ Programming Language, there is a very elegant example of a math calculator that I was able to build upon to write a compiler that could handle arbitrarily complex expressions as well as functions, reference parameters etc.

I'm sure you are well aware of recursive descent parsing. The idea I've always used is to recursive descent parse an expression into a tree, then have a virtual emit() member on the node that will output the instructions for the vm to compute.

I've taken the approach in the past of a stack-based vm and the role of emit() is to emit code that always ends up with the result of the expression on the stack.



You can expand this approach to functions by having a function node that contains a vector of node pointers that point to the argument and have calling emit() on a function node emit the code to push the params on the stack, call the function and end up with the return value on the stack.

Quote:Original post by Evil Steve
Anyone got any general hints or good links for me to look at?

(1) Define your grammar. Use EBNF to formalize it.

(2) Use standard techniques to elimiate left-recursion and perform left-factoring of your grammar into an LL(k)-parsable form.

(3) Whip up a basic recursive-descent parser.

(4) Fill in the action rules in appropriate places.

It's as simple as that. The ultimate reference is the dragon book.

There is a boost library you can use to write parsers but I find it, like many boost libraries, waaay too complex. Them b'ys shure are klever, but us mundanes just want a bit of butter for our bread.

Quote:It also mentions stack based expression parsing, where I'd push the operands and operators onto two stacks, and then generate the I-code when I have an operator with the highest precedence on the top of the stack.
However, this method doesn't seem particular efficient or easy to scale with more precedence levels.

What a coincidence i was looking at this article the other day, im not sure about the effeciancy but it seems to me that it would scale fairly well because it only relies on "is the presidence of this operator higher then that one", anyway hope the article helps.