Expression to ASM

[circular]

One thing to take into account is operator priority. Let's say you have the expression
1 + 2*4 + 8

If you analyse from left to right, rirst you encounter 1, then '+', then 2. So you temporarily conclude that it is an addition of 1 and 2 :
+(1, 2)

Then you find '*' and 4, which have a higher priority, so multiplication is included into the '+' and combined with the 2 :

+(1, *(2,4))

Then you find '+' and 8, which has a lower priority, so it gets out of the multiplication. It has the same proprity as the first '+', and it is generally assumed that operations are made from left to right, so it gets out of the last addition too. Thus, the full expression is combined with the 8 :

+( +(1, *(2,4)), 8 )

Let's check :

*(2,4) = 8
+(1, 8 ) = 9
+(9, 8 ) = 17

Notice that to implement it this way, you need to remember the current position in the expression, which can be a value token, an operation token, or nothing if there is nothing parsed, or if you get to the global level with a low priority.

A parenthesis is to be treated as a whole, until the corresponding end bracket is found. You can implement it recursively, using the same function to return the subexpression result, treated as a value token.

Let's try with :
1+ 2*(4+1) + 3

tree : none
current operation : nil
potential left operand : nil

input: + 2*(4+1) + 3

tree : token(1)
current operation : nil
potential left operand : token(1)

input: *(4+1) + 3

=> combine left and right operands

tree : +(1,2)
current operation : +(1,2)
potential left operand : current operation

=> '*' has a higher prority, so get inside

current operation : +(1,2)
potential left operand : token(2)

=> after reading '*', do a recursive call that returns +(4,1)

input : +3

=> combine left and right operands, which gives *(2, +(4,1))

=> replace token in current operation

tree : +(1, *(2, +(4,1) ) )
current operation : *(2, +(4,1))
potential left operand : current operation

=> '+' has a lower priority and is from left to right so

current operation : nil
potential left operand : +(1, *(2, +(4,1) ) ) = tree

=> combine left and right operands

input : none
tree : +( +(1, *(2, +(4,1) ) ), 3)
current operation : tree
potential left operand : tree

Note that the current operation may not be the whole tree, so you need to loop to search the parent.

Then there are two cases :
- either there is no current operation and one potential left operand : you can decide to raise an error or do a function call
- or there is a current operation, which can have a result or not (an assignment has the lowest priority and has no result)

To handle parameters of functions, you need to handle the parenthesis differently depending on the situation. If you have a potential left operand and have no operator, then it is a parameter list. If you've just read an operator, then it is not a parameter list.

Hope this helps