Search code examples
parsingantlrantlr4

How to profile an Antlr grammar

I have an Antlr grammar that is currently about 1200 lines. It parses the language that I want, but for at least one construct it is prohibitively slow even for smaller input files. The execution time seems to be growing exponentially for each added element of the construct.

I want to know if there are any good guidelines for debugging/profiling such performance problems.

I have already tried with VisualVM and that gave be the name of the two methods closureCheckingStopState and closure_, but that does not bring be much closer to figure out what is wrong with the grammar.

Solution

  • I rely on two primary items to analyze and improve the performance of a grammar.

    1. The latest release of ANTLRWorks 2 includes advanced profiling capabilities. Current limitations include the following:

      • The profiler doesn't support languages which require a custom CharStream or TokenStream (e.g. for preprocessing the input).
      • The profiler doesn't execute custom embedded actions in the lexer or parser, so your grammar needs to be able to produce a parse tree without relying on these operations. Standard lexer commands such as -> skip or -> channel(HIDDEN) do not pose a problem.
      • The output of the profiler is tables of numbers which are not easily understood by most ANTLR users, especially in terms of knowing what you should do in response to the numbers.

    2. I use a fork of the primary release which includes a number of optimizations not present in the reference release of ANTLR 4. Note that these features are "sparingly" documented as their only purpose to date was supporting the in-house development of ANTLRWorks and GoWorks. For most grammars, this fork performs roughly equivalent to the reference release. However, for some known grammars the "optimized" release performs over 200x as fast as the reference release.

    If you could provide the grammar and an input which is particularly, I could run the analysis and try to interpret the key pieces of the results.

    The latest release of ANTLRWorks is distributed through the official NetBeans Update Center. Simply run Tools → Plugins, go to Available Plugins and locate ANTLRWorks Editor.

    To run the profiler, use the Run → Interpret Parser... command. The results window is available after the parsing operation by choosing Window → Parser Debugger Controller.