Re: AST's, why are they necessary?

    "Phil" <Phil@rosl.demon.co.uk> wrote:
> I am writing translators to convert about 20 robot languages into our
> own proprietary language (a derivative of VB), and on advice I have
> been looking into using AST's. However, why would, in this case an
> AST give us an advantage over just hand coding the actions into
> fprintf statements (for example).


If your source languages are not almost exactly like your target, you
will not be able to do it with fprintfs. For instance, I translated
AREV R-BASIC to VB. They were both BASICs, but different. It still
required an 8 pass translator! Most of the passes were simple, but I
had that many for ease of coding and to make sure they were done in
the right order. Four of those passes did actual transformations,
three did analysis, one emitted the VB code- properly formatted and
with comments preserved.


For instance, AREV's case block could have labels right in front of
case statements that you could jump into. It worked like a series of
if statements with the exception that only one in the block would ever
be executed. It was nothing like C's switch statement. If there were
no labels in the case block, it could be translated into a series of
if elseif else statements. If there were labels in there though, I
had to generate code to do the bookeeping to ensure that only one
alternative was executed in the block, even when jumping into the
middle of the block. In an earlier pass, of course, I eliminated all
unreachable labels so I knew that if I saw a label there it was really
used.


ANTLR's tree parsing and grammar inheritance facilites really helped
me rock through the project. Those eight passes took only a month and
a half to code to completion. The parser took two months, because
AREV is a truly ambiguous language and difficult to deal with! When
my parser was done, though, I was catching syntax errors that the AREV
interpreter wasn't! Ick.


Were I doing this project, I would be write a VB tree grammar and VB
code emitter. If any analysis is going to happen, try to push it
later in the transformation chain to take advantage of everything
being in VB tree syntax by then. I would be subclassing everything
tree pass from the VB tree grammar using ANTLR's simplistic but still
incredibly usefull grammar inheritence mechanism.


For every source language I would be writing a parser that generates a
language specific AST. Then I would transform that into a VB AST. I
would even subclass the source language tree grammar from the VB tree
grammar! Why? So I could be sure that my AREV case block tree
structure was not conflicting with the VB case block tree structure.
I know that each source will be going to a VB tree grammar. The
process of transformation would be for each pass to eliminate any
source specific structures by transforming them to pure VB structures.


Don't underestimate the amount of work translation can require. This
AREV project I did was originally going to be done in Perl, and I can
assure you they would either have given up by now or would be still
hacking at it unless they had implemented ASTs in Perl as well. I
gained an immense amount of leverage by using ANTLR (www.antlr.org).
ANTLR was written explicitly for this type of task and really helped
guide me to a good solution to my problem.


Monty


P.S. If you decide to go the ANTLR route, feel free to contact me.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.