Antlr4 Listeners and Visitors - which to implement?

Question

I'm reading "The Definitive Antlr 4 Reference" and get the idea in relation to how Listeners and Visitors work. The book explains particularly well how Listeners relate to SAX parsers and makes it obvious when methods are going to be called during the implementation of each. I can see also that listeners are quite good for transforming input to output but I would appreciate a short explanation/example as to when to use a Listener and when to use a Visitor (or should they both be used in certain cases?).

My particular intention is to create an interpreter (Cucumber-style / TinyBasic Interpreter with some custom calls) that will check for syntax errors and stop executing on an error from a custom function without recovering - would love to see a complete implementation of such a thing in antlr - if anyone happens to know of one.

Thanks in advance for any advice.

Lights

@OP could you possibly post an update - what did you actually use, and any takeaways. Thanks – Sedan

Answer 1

If you plan to directly use the parser output for interpretation, the visitor is a good choice. You have full control of the traversal, so in conditionals only one branch is visited, loops can be visited n times and so on.

If you translate the input to a lower level, e.g. virtual machine instructions, both patterns may be useful.

You might take a look at "Language Implementation Patterns", which covers the basic interpreter implementations.

I mostly use the visitor pattern, as it's more flexible.

Sasha

Answer 2

Here is quote from the book that I think is relevant:

The biggest difference between the listener and visitor mechanisms is that listener methods are called 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.

In visitor pattern you have the ability to direct tree walking while in listener you are only reacting to the tree walker.

Phenformin

Answer 3

There's another important difference between these two patterns: a visitor uses the call stack to manage tree traversals, whereas the listener uses an explicit stack allocated on the heap, managed by a walker. This means that large inputs to a visitor could blow out the stack, while a listener would have no trouble.

If your inputs could be potentially unbounded, or you might call your visitor very deep in a call tree, you should use a Listener, rather than a Visitor, or at least validate that the parse tree is not too deep. Some companies' coding practices discourage or even outright forbid non-tail recursion for this reason.

Badderlocks

Do you have a source for this? I'd like to learn a bit more about the two approaches to determine which is better for my case. Thanks! – Chammy

@Chammy You can read "The Definitive ANTLR 4 Reference" by Terence Parr. – Badderlocks

Thanks for the reply! I am actually working through the book, but I was asking moreso for a source on this call stack vs explicit stack concept. Is this mentioned in the book? Or, is this found in the implementation details of the library? – Chammy

Answer 4

From the book, page 120.

Visitors work very well if we need application-specific return values because we get to use the built-in Java return value mechanism. If we prefer not having to explicitly invoke visitor methods to visit children, we can switch to the listener mechanism. Unfortunately, that means giving up the cleanliness of using Java method return values.

This is why I use visitors.

Electrochemistry

Answer 5

I conducted tests using benchmarking in Golang. The Listener is slightly faster than the Visitor, but there is no significant advantage.

cpu: Intel(R) Xeon(R) CPU E5-2630 v4 @ 2.20GHz
BenchmarkCalcVisitorCases
BenchmarkCalcVisitorCases-16                5342        224675 ns/op
BenchmarkCalcListenerCases
BenchmarkCalcListenerCases-16               4676        230239 ns/op
BenchmarkCalculatorVisitorCases
BenchmarkCalculatorVisitorCases-16          2678        428312 ns/op
BenchmarkCalculatorListenerCases
BenchmarkCalculatorListenerCases-16         2149        540031 ns/op

Doublet