Creation of intermediate code in the compiler. Is AST or a parse tree always necessary when working with conditional expressions?

Question

I take the compiler design class, where we have to implement our own compiler (using flex and bison). I had experience in parsing (writing EBNF parsers and recursive descent), but this is the first time I am writing a compiler.

The language design is quite open (the professor left it to us). In the classroom, the professor moved on to generating intermediate code. He said that we do not need to create an abstract syntax tree or a parsing tree during parsing and that we can generate intermediate code as we move.

I found this confusing for two reasons:

• What if you call a function before defining it? How can you solve the branch problem? I suppose you would need to make this a rule so that you define functions before using them or perhaps predefine them (e.g. C does?)

• How do you feel about conventions? If you have an if-else or even just if , how can you resolve the branch target for if when the condition is false (if you generate the code along the way)?

I planned to create an AST, and then walk around the tree after it was created to resolve the addresses of functions and chain branches. Is this correct or am I missing something?

Answer 1

A common solution to both of your problems is to keep a list of addresses that need to be "fixed." You generate code and leave holes for missing addresses or offsets. At the end of the compilation block, you look at the list of holes and fill them.

In FORTH, a “list” of patches is stored in the control stack and unwinds as each control structure completes. See Dimensions FORTH

Anecdote: an early Lisp compiler (I believe it was Lisp) generated a list of machine code instructions in a symbolic format with direct links to a list of machine code for each conditional branch. Then he generated the binary code going backward through the list. Thus, the location of the code for all the forward branches was known when it was necessary to issue a branch instruction.

Answer 2

The Crenshaw tutorial is a concrete example of how not to use AST of any type. It builds a working compiler (including conditional expressions, obviously) with an immediate assembly of m68k code generation.

You can read the document in the afternoon, and it's worth it.