Compilers - Code generation from AST

Author

Code generation from AST

Lucas S. Silva

2007-11-10, 10:13 pm

Dear compiler enthusiasts,

I am writing a compiler for a OO language and I am looking for an
algorithms that I can use to generate code from an AST.

The algorithm I am using doesn't deal very well with recursive
expression such as:

a = f.g.h(a , x.y.o(1,2) )

I am using the visitor to process the AST, so when I get to node f it
could be a simple function call or a compound which have parameters
that may also be a function call, an so on.

Is there any good algorithm to deal with this type of situation? I am
planning to use stack but I am not sure if it is the most appropriate
method.

Thanks in advance,
Lucas S. Silva

Dmitry A. Kazakov

2007-11-11, 10:14 pm

On Sat, 10 Nov 2007 23:09:57 +0100, Lucas S. Silva wrote:

> The algorithm I am using doesn't deal very well with recursive
> expression such as:
>
> a = f.g.h(a , x.y.o(1,2) )
>
> I am using the visitor to process the AST, so when I get to node f it
> could be a simple function call or a compound which have parameters
> that may also be a function call, an so on.
>
> Is there any good algorithm to deal with this type of situation? I am
> planning to use stack but I am not sure if it is the most appropriate
> method.

I make "." and "()" operations. The above becomes (depending on
priorities), the following tree:

"="
{ a,
"()"
{ "." { "." { f, g }, h }, -- The first argument is f.g.h
a, -- The second argument of "()"
"()" -- The third argument of "()"
{ "." { "." { x, y }, o },
1,
2
} } }

Then "()" can be overloaded by "function call" and "array indexing", at
the semantics analysis stage you will decide what it is depending on the
first argument of. So if f.g.h renders to a function then "()" is a call.
When x.y.o is an array, then its "()" is indexing.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Hans-Peter Diettrich

2007-11-11, 10:14 pm

Lucas S. Silva wrote:

> The algorithm I am using doesn't deal very well with recursive
> expression such as:
>
> a = f.g.h(a , x.y.o(1,2) )

You can transform this statement (i.e. the AST) into Reverse Polish
Notation (RPN), like

1 2 x y . o . () a f g . h . () a =

Now the sequence of the required actions (machine code) should be quite
obvious.

DoDi

Sponsored Links