views:

371

answers:

4

Hello everyone,

I'm currently pondering how best to take an AST generated using Antlr and convert it into useful objects which I can use in my program.

The purpose of my grammar (apart from learning) is to create an executable (runtime interpretted) language.

For example, how would I take an attribute sub-tree and have a specific Attribute class instanciated. E.g.

The following code in my language:

Print(message:"Hello stackoverflow")

would product the following AST:

alt text

My current line of thinking is that a factory class could read the tree, pull out the name (message), and type(STRING) value("Hello stackoverflow"). Now, knowing the type I could instanciate the correct class (e.g. A StringAttribute class) and pass in the required attribute data - the name and value.

The same approach could be used for a definition factory, pulling out the definition name (Print), instanciating the Print class, and then passing in the attributes generated from the attribute factory.

Things do get a bit more complicated with a more complicated program:

Program(args:[1,2,3,4,5])
{
    If(isTrue:IsInArray(array:{Program.args} value:5))
    {
        Then {
            Print(message:"5 is in the array")
        } Else {
            Print(message:"More complex " + "message")
        }
    }
}

alt text

ANY/ALL help or thoughts are very welcome. Many thanks.

Previous related questions by me (Could be useful):

  1. How do I make a tree parser
  2. Solving LL recursion problem
  3. Antrl3 conditional tree rewrites
A: 

Once you have the AST, all you need is an iterator to walk the tree and the template to emit the objects you want.

duffymo
Are you aware of any examples which explain this concept better? Thanks
Richie_W
Yes, the ANTLR book has a chapter on templates and AST.
duffymo
+3  A: 

I recommend reading chapter 9, Building High-Level Interpreters, from Language Implementation Patterns by Terence Parr.

EDIT

Okay, to get you through the time waiting for that book, here's what you're (at least) going to need:

  • a global memory space;
  • function spaces (each function space will also have a (local) memory space);

and classes that spring to mind (in UML-ish style):

  • class Interpreter
    • global : MemorySpace
    • functions : Stack<Function>
    • ...

  • class MemorySpace
    • vars : Map<String, Object>
    • ...

  • class Function
    • local: MemorySpace
    • execute(): void
    • ...
Bart Kiers
Thanks, I bought the book. Should arrive in the next few days. Hmm...stuck until then :|
Richie_W
@Richie_W, see my **EDIT**.
Bart Kiers
Book arrived today. Looks like the sort of stuff I need. Many thanks for the recommendation
Richie_W
You're welcome Richie.
Bart Kiers
A: 

This Tutorial is based on Flex and Bison but at the end he details how he converts his AST to LLVM assembly code, it might be helpful.

Lolindrath
+1  A: 

Here's one with ANTLR -> LLVM:

Terence Parr