Expression to ASM

[Colin]

hi there, this is not related to game development, .. i am writing a compiler, so far the compiler supports many features, but is missing 1 vital thing, the ability to accept expressions, i have tried to come up with a way to do this but i always run into problems, the language allows for writing in assembly and higher level in the same code scope so what i need is a way to output assembly code (my assembler will assemble the code afterwards)

eax = myvar2 + (edx + ecx + (5 * edx)) - 5 xor myvar1;

this sort of thing, i need a way to output equiv assembly opcodes/operations. can anyone help me with this problem? Thanks in advance

[Ñuño Martínez]

This is an advanced topic. The best is to build a recursive analyzer. May be Crenshaw's paper helps you.

[code_glitch]

Hmm.. That is some very interesting stuff there Nuno... If I have time I might look into the possibility of a compiler designed to do graphics in very high speed or something to that effect. Ie. No bloat from libs as they are run at HW speed which would be nice indeed. Good luck on your compiler. If I was to evaluate expressions I would do something like:

1) find the number of brackets
2) for each bracket 'level' or sub brackets work those out and feed that back into the processor until the bracket level reaches 0
3) In each process I would identify what is a number and what is not (ie numeric first char or otherwise) and sub in values where required.
4) Process each part in BODMAS order (of if statements or similar)

Don't know if it helps but if nicely implemented it might run well. I'm working on an interpreter for rapid prototyping and debugging of my APIs and programs so I'm getting some similar challenges. Hence the use of the document Nuno posted: take interpreter and feed into binary. Done.

[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

[Colin]

hi there, thanks for replies, i have decided on first my compiler will convert the expression to an RPN (reverse polish notation), this will remove the problem of () and procedence of operators, my only problem now is the best way to output the opcodes, because i will be limited to registers since the programmer could also use them, maybe an option would be to use sse, but tbh i would rather not.

btw the problem with recursion is if the programmer has a very large expression, it would use large stack space, and maybe even an overflow. as for the compiler, i am already far beyond the basics, the compiler already has many features and very usable, you can check it out if you like - http://www.codeziron.com

[farcodev]

good luck !