In previous post, we saw how to create and parse DSL with antlr4. In this post we will compare the two tree walking mechanism provided by the library -
Visitor. Both approaches have their own advantages, and choice of preferred method depends on what you are using antlr for.
Lets take a look at generated methods in Listener and Visitor interfaces, for grammar from previous post
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4
There are 3 primary differences:
- Listener methods are called automatically by the ANTLR provided walker object, whereas visitor methods must walk their children with explicit visit calls. Forgetting to invoke visit() on a node’s children means those subtrees don’t get visited
- Listener methods can’t return a value, whereas visitor methods can return any custom type. With listener, you will have to use mutable variables to store values, whereas with visitor there is no such need.
- Listener uses an explicit stack allocated on the heap, whereas visitor uses call stack to manage tree traversals. This might lead to StackOverFlow exceptions while using visitor on deeply nested ASTs
In previous post we used listener. Lets see a equivalent visitor implementation for same usecase:
First thing which we need to do is identify and define types which will be returned by each vistor method which we will override.
1 2 3
Now we can extend the visitor class with our custom type
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
Notice that both rules
visitOperation return some value which can be shared between rules. And for the caller method:
1 2 3 4 5 6 7 8 9 10 11 12 13
At line 10, We are explicitly calling visit on
expr rule and it returns back the result of expression evaluation.
Both approaces have their advantages depending on the usecase. If you want to have full control over the traversal, dont want any mutability and your grammar rules won’t lead to deeply nested trees, then its preferred to go with visitor.
Here’s a figure showing call sequence for listener vs visitor
Good thing about listener pattern is that its all automatic and even if you don’t write any parse tree walker, then also it will figure out and trigger the enter and exit method for each rule. This is a huge benefit for translation type of usecases.
I hope this post gave you some clarity in terms of which pattern to choose while creating your DSL.