66

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.

1
  • 5
    @OP could you possibly post an update - what did you actually use, and any takeaways. Thanks
    – Dinesh
    Commented Sep 28, 2017 at 1:40

5 Answers 5

81

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.

56

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.

0
31

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.

4
  • 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! Commented Dec 19, 2022 at 21:41
  • @andersonjwan You can read "The Definitive ANTLR 4 Reference" by Terence Parr. Commented Dec 20, 2022 at 0:08
  • 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? Commented Dec 21, 2022 at 1:16
  • Its intuitive. In your interpreter, if you use the visitor patter you will literally have to do visit() function calls [hence, using the call stack in the JVM or whatever language you use for the interpreter], while on the listener pattern you need to implement your own stack [hence using an array or something, instead of doing visit() function calls] Commented Jul 25 at 11:17
8

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.

3

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.