Plain – Algebraic Expression Parser

Dealing with math it is quite handy to use a standard algebraic expression format. But, to do so we need a parser that translate the expression into a sequence of simple math instructions. In this case we expect the Assembler to “compile” the expression into P-Code that we later execute as part of the VM’s Assign instruction. The Parser is a C++ class library used by Plain Assembler. The module was actually created prior to Plain as part of a different project.

The parser logic is quite simple

  1.  You parse 1st sequence consisting of start parenthesis, value, end parenthesis and an operator. End of Expression is also an “operator” in this sence.
  2. You parse 2nd sequence.
  3. You evaluate 1st and 2nd priority. if 1-op has higher pri than 2-op, you compute 1 by generating a output table entry (P-Code).
  4. Repeat from 2.

Example 1:  3 + 4 * 5

This is the classic example to test priority as we know that 4 * 5 must be computed before 3 + … The parser will build a tree as listed below:

0 :          3 +
1 :          4 *                 // + lower pri than * so continue
2 :   5 END                  // 'END' is lowest pri

This will generate the following P Code:

T1 = 4 * 5                  
T0 = 3 + T1               

In this case we could end up with an Assign instruction with 2 P-Code table entries. I say ‘could’ because the actual parser will in this case detect that it is only constants and pre-calculate the value 20.

Leave a Reply