Building an AST

[Korporal]

I'm trying fathom the roles of Walker, Visitor and Listener, not yet 100% clear on the intended use of these. My opening question though is, I'm developing a compiler (I did the grammar a year ago and I'm returning to the project) and I am inclined to (somehow) traverse the parse tree generated by the generated parser code and create a distinct, new tree - AST.

My grammar is rooted in a rule named translationUnit so the generated parser has this

	[RuleVersion(0)]
	public TranslationUnitContext translationUnit() {
		TranslationUnitContext _localctx = new TranslationUnitContext(Context, State);
		EnterRule(_localctx, 0, RULE_translationUnit);

My little test app has this:

            NestedSourceReader reader = new NestedSourceReader("grammar_test.ipl", regex, ReadFile);

            AntlrInputStream inputStream = new AntlrInputStream(reader);
            ImperiumLexer imperium_lexer = new ImperiumLexer(inputStream);

            imperium_lexer.SetLexicon("en");

            CommonTokenStream commonTokenStream = new CommonTokenStream(imperium_lexer);
            CustomParser imperium_parser = new CustomParser(commonTokenStream);

            imperium_parser.BuildParseTree = true;

            var tree = imperium_parser.translationUnit();

(NestedSourceReader is just a small helper class that implements TextReader).

So I get my parse tree in the tree variable.

In my mind I think I want to now take that generated tree and traverse it and in so doing so gradually build a new tree, one that represents my AST. Then with that AST I can consume that and begin the compiler proper.

To do this I started to create a class:

Which would seem to end up with a large number of methods. These methods each create a new AstNode which is the base class for all of the specific nodes I'd be creating in my new AST.

So my question is, is this reasonable? am I doing this in a sensible way or have I misunderstood something basic, is there a better approach to all this?

[kaby76]

[I]s this reasonable?

Yes. That is a correct application of the Visitor interface. A visitor returns values, which in your case is an AST. An example of this conversion is for XPath expressions in Trash. This conversion is done because the XPath engine defines an intermediate language (a tree) that is different from the parse tree. You will need to return an AST value for every parse tree node type in the visitor.

A Listener is a tree walker that by default a DFS tree traversal where EnterXXXXX() and ExitXXXXX() methods are called for node type XXXXX as the tree is traversed. Unlike a Visitor, which has "built-in" walker, a Listener requires a Walker to walk the tree. Generally, I use a listener if I need to do a computation that doesn't return an explicit result, but as a side-effect of the traverse, e.g., build a symbol table.

See https://tomassetti.me/listeners-and-visitors/

But, there are many ways to traverse the tree. In theory, you could visit any node in any order. XPath expressions define non-DFS traversals. For example, if one wants to find semantic predicates in an Antlr4 grammar, we look for an "action" followed by a "?" in the parse tree.