ANTLR Change Parse Tree

Question

I am using ANTLR4 to create a parse tree for my grammar, what I want to do is change certain nodes in the tree. This will include deleting specific nodes and inserting new ones. The purpose of this is to optimize for the language I'm writing. I have yet to find a solution to this problem. What would be the best way to do this?

Answer 1

While there is currently no real support or tools for rewriting the tree, this is very possible to do. It doesn't even hurt so much.

ParseTreeListener or your MyBaseListener can be used with ParseTreeWalker to traverse the parse tree.

Here you can delete nodes using ParserRuleContext.removeLastChild() , however you should keep track of ParseTreeWalker.walk :

 public void walk(ParseTreeListener listener, ParseTree t) { if ( t instanceof ErrorNode) { listener.visitErrorNode((ErrorNode)t); return; } else if ( t instanceof TerminalNode) { listener.visitTerminal((TerminalNode)t); return; } RuleNode r = (RuleNode)t; enterRule(listener, r); int n = r.getChildCount(); for (int i = 0; i<n; i++) { walk(listener, r.getChild(i)); } exitRule(listener, r); } 

You must replace the remote nodes with something, if the walker visited the parents of these nodes, I usually select empty ParseRuleContext objects (this is due to the cached value of n in the method above). This prevents the release of ParseTreeWalker NPE.

When adding nodes, be sure to set the mutable parent to ParseRuleContext for the new parent. Also, because of cached n in the above method, a good strategy is to detect where the changes should be before , you get where you want your changes to go in walk , so ParseTreeWalker will go through them in the same pass (otherwise you will need a few passes ...)

Your pseudo code should look like this:

 public void enterRewriteTarget(@NotNull MyParser.RewriteTargetContext ctx){ if(shouldRewrite(ctx)){ ArrayList<ParseTree> nodesReplaced = replaceNodes(ctx); addChildTo(ctx, createNewParentFor(nodesReplaced)); } } 

I used this method to write a transpiler that compiled a synchronous internal language into asynchronous javascript. It was pretty painful.

Answer 2

Another approach would be to write ParseTreeVisitor , which converts the tree back to string. (In some cases, this may be trivial because you call TerminalNode.getText() and combine into aggregateResult(..) .)

Then you add changes for this visitor so that the resulting string representation contains the changes you are trying to achieve.

Then we analyze the string and you get a parse tree with the required changes.

This, of course, is hacking, since you are parsing a string twice. On the other hand, the solution does not depend on the details of the antlr implementation.