Create object model from AST using visitor

Hi,

I'm writing a parser at the moment. The first step I did using petit parser to get from the grammar to my own AST like structure. Now I like to create my working model from the AST. And I'm thinking what would be the best way to do.

If I want to create a model from the structure it turns out to be more difficult than I thought it would be. I'm using a visitor for this. In a typical visitor every element is treated in isolation. I can treat subelement B in the visitor but I cannot assign it to its parent A because there is no link.  And I'm not really convinced that introducing return values in the visitor is the right way to go.

What I need to do is a visitor that transforms one thing into another thing with having the need that existing parent-child relationships need to be preserved through the transformation.

Anyone has an idea. Any hints are appreciated,

Norbert

> If I want to create a model from the structure it turns out to be more difficult than I thought it would be. I'm using a visitor for this. In a typical visitor every element is treated in isolation. I can treat subelement B in the visitor but I cannot assign it to its parent A because there is no link.  And I'm not really convinced that introducing return values in the visitor is the right way to go.

The refactoring engine essentially does that. The visitor is a big
#collect: over the AST and each visit-method returns a new/modified
element. I think this is the most natural thing to do in most cases.

> What I need to do is a visitor that transforms one thing into another thing with having the need that existing parent-child relationships need to be preserved through the transformation.

Another approach would be to keep a stack of the elements visited.
Like this you can always access the parents of the currently
constructed elements. If I remember correctly, Pier has a few of those
visitors.

If you just need the direct parent, you can only remember the last
parent in an instance variable, this is for example what OmniBrowser
does when building UIs in OBBuilder.

Alternatively you can also choose a different traversal strategy other
than the canonical one from the root to the leaves. PetitParser has a
couple of these visitors that traverse the graphs in "random" order
keeping collections of processed and unprocessed items.

There are many different ways of how you can visit your nodes. Each
approach has its advantages and disadvantages in a particular
use-case. So I guess you need to figure out yourself what works best
for you.

Lukas

--
Lukas Renggli
www.lukas-renggli.ch

Lukas,

that was exactly the type of mail I needed. I get somehow stuck in my head but now it is floating again.

Am 06.10.2011 um 17:48 schrieb Lukas Renggli:

>> If I want to create a model from the structure it turns out to be more difficult than I thought it would be. I'm using a visitor for this. In a typical visitor every element is treated in isolation. I can treat subelement B in the visitor but I cannot assign it to its parent A because there is no link.  And I'm not really convinced that introducing return values in the visitor is the right way to go.
>
> The refactoring engine essentially does that. The visitor is a big
> #collect: over the AST and each visit-method returns a new/modified
> element. I think this is the most natural thing to do in most cases.
>
Thinking about it again and with all the approaches at hand I think this a good way to go.
I think this is a good approach if the interface of the objects is rather generic and homogenous. Otherwise it is difficult for the child to know enough about the parent to deal properly with it.

> Alternatively you can also choose a different traversal strategy other
> than the canonical one from the root to the leaves. PetitParser has a
> couple of these visitors that traverse the graphs in "random" order
> keeping collections of processed and unprocessed items.
>
I never thought about this. So I take some time to get a picture what this could mean.

> There are many different ways of how you can visit your nodes. Each
> approach has its advantages and disadvantages in a particular
> use-case. So I guess you need to figure out yourself what works best
> for you.
>
Agreed. Thanks very much!

Norbert

> Do you have some pointers to classes and methods. I have trouble finding a
> visitor that does this on a bigger structure.

RBProgramNodeVisitor>>#visitNode:, RBProgramNode>>#acceptVisitor: and
its subclass implementors.

The only part of the code that is using the return value of
#visitNode: is RBParseTreeSearcher and RBParseTreeRewriter. Maybe they
are a bit complicated examples, because the new tree nodes are not
built/modified in the visitor itself but in the matching rules
triggered in #performSearches:on:. The matching rules then start new
visitors for the child nodes, if necessary.

A more strait-forward implementation of what you are looking for can
be found in PPNodeFormatter of the package 'PrettyPetit' in the
PetitParser repository. PPNodeFormatter is a subclass of
RBProgramNodeVisitor and it converts the standard RB AST to a layout
box model AST for formatting. There you see that for each RB AST node
one or more document nodes are composed and returned. The parent-child
relationship is setup automatically when composing the objects (in
this example only one way, but you could change that to also include
the link from the child to the parent).

Lukas

--
Lukas Renggli
www.lukas-renggli.ch