One key component of any Parser is the Expression Parser. This one is used to parse mathematical or logical expressions into a list of micro-statements. Plain have a separate instruction to execute math, but the parser need to build the list correct.
Example : 4 + 5 * 3
If we add 4+5 we get 9 and if we multiply that with 3 we get 27 which is wrong because * (multiplication) have higher priority than +. So the correct processing is:
5*3 gives us 15 and adding 4 gives us 19.
I have a preference for using tables to compute expressions. I need one temp table, a operator priority table and an output table for micro-instructions. The algorithm is quite simple as we parse a value and a operator before we evaluate the tree.
First is 4 +. As this is the first we can’t do any temp calculations.
Second is 5 *. Since * have higher priority than + we just add it to out temp table and parse 3 =. Our table will now look like this:
- 4 +
- 5 *
- 3 =
=is the highest priority so we now output a micro statement:
- t1 = 5 * 3
And we modify our table to the following:
- 4 +
- t1 =
Next we output t1 = 4+t1. t1 is our result leading to a small math script as follows:
- t1= 5 * 3
- t1 = t1 + 4
What we now lack is parenthesis, variables and function calls and we have an algebraic expression parser. Many language parsers will build the language on this, but my preference have always been to handle the language and expressions separately.
Dealing with this in plain was a challenge because a normal language would implement assembly instructions like Add, Sub, Mul, Div etc. At this point I decided to implement a math instruction that take the parsed tree as input to enable math to be done as close to C as possible. This keeps the instruction set small + it preserves execution speed.
