Creating case-based bytecode from an abstract syntax tree?

Question

What are some well-known strategies for generating bytecode based on foundations from this anstract syntax tree (AST)?

Consider this expression 1 + 2 - 3 * 4 / 5 4/5 and its form AST:

 bin_exp(-) bin_exp(+) num_exp(1) num_exp(2) bin_exp(/) bin_exp(*) num_exp(3) num_exp(4) num_exp(5) 

I'm struggling to convert AST to the appropriate bytecode procedurally. So far, I have found only one article in which he only briefly talks about this. My interpretation of what he is trying to say ...

 int ridx; // register index function visit_exp(exp) { switch (exp) { case bin_exp: visit_exp(exp.left); visit_exp(exp.right); printf("add %i, %i -> %i\n", ridx - 2, ridx - 1, ridx); // save ridx, as it contains the result break; case num_exp: printf("mov %i -> %i\n", ridx, exp.value); break; } } 

Please give me a hand, thanks.

Answer 1

Follow these steps:

• Give each node expression a unique en number. You can do this when walking through a tree, on the fly.
• For the node sheet with number el, generate "MOV el, operand"
• For each interval node "OP" with number er, with binary children es and et, generate "OP er, es, et". Use the obvious generalization to handle statements with an arbitrary number of children.

This will lead to a “naive” code in the sense that the numbers of the virtual register can be arbitrarily large (for example, determined by the size of the program).

A more complex version will contain a pool of node numbers, assign the smallest available amount from the pool to each node when you encounter them from left to right, and put the numbers for the operands for entering OP instructions back into the pool (since they are now "free"), since it is generated every team is OP. This in practice will create a much smaller set of virtual register numbers.

If you want to be smarter, after you have done this, apply the coloring register to the generated code to enable the use of a fixed register number.