How to profile an Antlr grammar

Question

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.

Answer 1

There is a Profiler option in the JetBrains IDEA plugin

see: https://github.com/antlr/intellij-plugin-v4/blob/master/README.md

Right click on any rule to test a rule and you'll get the tabs for

• Parse tree
• Hierarchy
• Profiler

See example screen shots below.

The ambiguity lines in the profiler tab help finding ambigous parsing rules. If you click on such a red line the rule is highlighted.

Profile Tab

Parse Tree Tab

Answer 2

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.

Answer 3

As Wolfgang Fahl said, IDEA has a great plugin, but that of course just displays the information collected by your parser.

So in case you cannot use IDEA, or for example want to do profiling live, you can do it programmatically, like this:

public void parseAndProfile(MyParser parser) {
    parser.setProfile(true);

    // do the actual parsing

    ParseInfo parseInfo = parser.getParseInfo();
    ATN atn = parser.getATN();
    for (DecisionInfo di : parseInfo.getDecisionInfo()) {
        DecisionState ds = atn.decisionToState.get(di.decision);
        String ruleName = MyParser.ruleNames[ds.ruleIndex];

        System.out.println(ruleName +" -> " + di.toString());
    }
}

Answer 4

If you already have Android studio, you may use built-in Antlr V4 plugin to use Antlr profiler.

The tutorial in the link works for me http://blog.dgunia.de/2017/10/26/creating-and-testing-an-antlr-parser-with-intellij-idea-or-android-studio/

Android Studion version used for testing: 2.3.1