Strategy for implementing an AST builder

[The-Futurist]

I'm just starting to look at the ways I can implement a AST from an APT (Antlr Parse Tree).

The visitor mechanism seems suitable to me.

As you know the generated visitor exposes a host of virtual methods corresponding to the many parser rules in the grammar.

The raw visitor walks the tree in a depth-first manner and visits every single node, even "pointless" ones (from an AST perspective).

So the approach that occurs to me is something like this:

1. Define an AstNode abstract node, and then derive various syntax specific nodes from that IfNode, LoopNode, DeclarationNode and so on, for nodes that represent the relevant language abstractions.
2. Derive a visitor class that using AstNode as the generic return type.
3. Override the outermost visitor class, the root of the grammar.
4. In there analyze that root context node and then "manually" call specific overridden visit methods and use their returned AstNode to populate my root node and eventually return that.

This means that there'll be no calls to things like return base.VisitDeclare_stmt(context); anymore UNLESS it is an overridden method.

So if I do that the visitor is no longer "automatic" the tree walking will be done as direct by my own override methods. Is this a sensible way to do this?

What I want is that the visitor ultimately returns with a root AstNode to a tree of other AstNodes that my overridden code has built.

There's a puzzling method too AggregateResult in AbstractParseTreeVisitor that seems to do not very much but return the most recent result of calling a visitor method and thus "losing" any prior results that sibling visitor methods might have returned.

Is this sensible or am I missing some core features of the generated visitor pattern here? My code is all C# by the way.

--- TICK TOCK ----

OK I just stumbled upon this and it's a huge help, is this then the best overall pattern?

I'm seeing some sets of classes with very similar names too, example Identifier_Context and IdentifierContext where the former is derived from the latter, not quite understanding that relationship...

[kaby76]

There are a couple of ways to do this. You could use the "Convert parse tree to abstract syntax tree visitor" algorithm (https://stackoverflow.com/a/29996191/4779853). Another alternative is the "Antlr grammar returns tree construction" algorithm, which uses the "returns" values of a parser rule declaration to construct the AST during the parse. See page 179 of Parr's book on Antlr. In the alternative ("returns") method, make sure to turn off the default tree construction. If and when I ever get around to a tree rewrite engine, my plan is to make an extension to Antlr that reintroduces the AST tree construction operators that was in Antlr3 and removed in Antlr4, using the alternative method. Incidentally, you don't have to use "visitor.Visit()". You could call the "Visit method" for each node type yourself in the visitor class.

[The-Futurist]

@kaby76 - Thanks, that Stackoverflow post is very helpful, I'm using as an initial guide, if you get a slot please take a quick peek at this crude implementation, this is possibly "throw away" code, I'm writing it to try to see what patterns and structures emerge before I fully commit to a pattern for this.

That code creates a node for the translation unit then a node for each contained "scope" (aka namespace) and then inside a scope, a node for each declare or define statement. The nodes are more or less empty, to be filled in with relevant members later.

[kaby76]

A few comments.

• You don't need a semicolon here. https://github.com/Steadsoft/imperium/blob/7b7f6fcc925bcf5189af85d6b995b50fb0e98653/grammar/AntlrCSharp/AntlrCSharp/Classes/ImperiumVisitor.cs#L12
• This call to Visit() will call a bunch of code that goes through the children. Please check the runtime and debug. Otherwise, call the VisitFooBar() method for node "FooBar" directly.

[The-Futurist]

Thanks @kaby76 - I will call those specific visitor methods, much neater. I do wish I could pass an additional arg into these methods though. Relying only on a returned value is a bit restrictive. Since the code is single threaded I could just have a CurrentNode property that is set by caller before calling a visitor method for a subordinate construct, but I don't love that idea...

Actually that's a non-starter the parser is full of recursion so no global node will ever work!

If the base classes RuleContext or ParserRuleContext included a UserContext member (say of type Object) then this would suffice. One could simply set that to their AST node and the called Visitor could access it easily.

[kaby76]

You can always subclass the tree node itself. https://github.com/antlr/antlr4/blob/master/doc/options.md#contextsuperclass

[The-Futurist]

@kaby76 - That's excellent! Thanks for that info. It works like a dream (only issue is that I generate both C# and Java - so that I can run the Antlr GUI tool routinely. That Java code fails to compile now...)

Sorted, haven't used Java in years but creating a class is all that was needed.

[The-Futurist]

This is all going very well now. I found myself calling methods in context objects that get sub trees, but these are optional grammar constructs in many cases so might be absent.

This has made the code easier to write:

public static bool Has<T>(Func<T> ContextFunc, out T Context) where T : class
{
    Context = ContextFunc();

    return Context != null;
}

Calling code is now neater:

if (Has(context.declarationBody, out var body))
{

}

Because the out variable body only exists in the case where the body does actually exist, subtle coding errors are reduced too.

[The-Futurist]

This is the kind of pattern that's emerging:

For terminals themselves there's an overload of Has:

Enjoy.