How to go from AST to backend code?

Question

I'm working on a compiler for a programming language and I have a good representation of the source language in the form of an Abstract Syntax Tree (AST). I tried generating backend code directly by traversing the AST, but that's not working well. In general, think of mapping an AST for a C-like language down to an assembly-like language. I now think that there is some phase that I'm missing to go from the AST to backend code. The problem is that going from the AST to the next representation (say, 3-address code) is rought. It feels like there is a step in between that I'm missing.

[source lang] -> [lex/parse]-> [AST] -> [semantic analysis] -> [?] -> [backend code]

This is what I've come up with while thinking about it:

1) Transform the AST of the source language to an AST that represents the backend. This means that I would need to have 2 different ASTs. Then, output the backend from the transformed AST.

2) Transform the AST to a different type of data structure, and generated backend code based on this other structure. I'm not sure what this other struct would be.

3) Traverse the AST in a different way (from the way used to pretty print it) to generate the backend code. This is how I tried doing it first but it doesn't seem right; I feels like a hackish way to go about it.

What are my options go to from AST to backend code?

Note that I'm not asking what kinds of representations the AST could be turned into, such as 3-address code. For example, I understand that a C addition like so:

x = a + b + c

could be turned into 3-address like so:

t1 = add a, b
t2 = add t1, c
set x, t2

I am asking for techniques/guidance/experience on how to do it.

To give an example of the type of answer that I'm looking for would be:

Question: What steps can I take to perform semantic analysis on the source lang?

Answer: Parse the language into an AST and traverse the AST to perform the semantic checks.

Here you ask "how to do it" .... in comments to may answer below, you say "Maybe I do need to tansform the AST to some other representation" as if you aren't convinced. Which is it? — Ira Baxter

Ira Baxter Ira Baxter · Accepted Answer · 2014-06-27T20:38:49

One can represent the program any way one likes; you can build compilers completely using trees. The purpose of a representation is to make it easy to collect certain kinds of facts; the representation serves to make collection/processing of those specific facts easier. Thus one expects the representation of the program to change at different stages of compilation, depending on what the compiler is trying to achieve in that stage.

One typical scheme is to translate programs through these representations to produce final code:

 *  ASTs
 *  Triples
 *  Abstract machine instructions
 *  Concrete machine instructions

The fact that you don't seem to know this, means you haven't done your homework. This is pretty well described in compiler books. Go read one.

How to go from AST to backend code?

1 Answers