How to generate code for an AST tree processed by a dummy language?

Question

I read the article at http://parsingintro.sourceforge.net/ and decided to try rewriting it as an exercise in Ruby. Two reasons made me do this, I wanted to learn more about how to code Ruby (background in Java, PHP, C and some Python), and I wanted to learn more about parsers / compilers.

I have a code hosted at https://github.com/parse/boatcaptain . The AST tree is generated, unfortunately, the author of the article does not understand such concepts as code generation and optimization.

Can someone help me by pointing me in the right direction how to achieve this AST tree in "code"? This is the AST tree that is generated.

I wrote a calculator in Java several years ago, it uses a lot of similar terminology and techniques that I used in this parser. But in the calculator I had methods for eval () - inputting my "classes" and, therefore, getting the result, should I strive to do something like this here? Source for calculator: https://github.com/parse/Uppsala-University-Courses/blob/master/ImpOOP-Calculator/src/Calculator.java

I would love the feedback on my way of writing Ruby, I suppose I'm still writing Ruby, as I would have written Python, missing some of the nice benefits of Ruby.

Answer 1

Generating code in its most basic form simply crosses your intermediate form - AST - and emits the appropriate instructions in your target language.

First, you need to select the target language. What platform do you want your input file to work on? Key features available to you:

• Translator from source to source
• Compiler for native code
• Compiler for bytecode (to run in real time on a virtual machine)

Choosing a target language can determine the amount of work you will need to use to map languages. For example, mapping object-oriented classes to ASM might be tricky. Matching essentially procedural code with stack-based code can also be a problem.

Whatever language you choose, the problem undoubtedly boils down to the following procedure: visit the nodes of your tree and, depending on their type, issue the appropriate instructions.

Say that you will meet the following node in your AST (as in the one you contacted):

= delta / alpha beta 

Seeing that this is the "destination" of the node, the code generator knows that it must evaluate the RHS tree before inserting this value into the LHS; "Delta". Therefore, we follow the RHS node down and see that it is a division operation. Then we know that we must evaluate both the LHS and the RHS of this node before dividing them and inserting the result into 'delta'.

So now we move down the LHS, see the variable, and we emit the “load” instruction. We return up and then down the RHS, and also release a “load” for “beta”. Then we go back through the tree (taking with us both alpha and beta), give instructions for dividing into both operands, save this result, transfer it through the tree to the assignment emitter and allow it to be stored in 'delta'.

Thus, the resulting code for this fragment can be:

 load alpha load beta tmp = div alpha beta store delta tmp 

As for the pre-existing Ruby Code generator libraries, I don't know, sorry. Hope this answer was not too general or simplified for you.