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.

Latterly

Answer 1

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.

Piperonal

I have tried to find the profiler in ANTLRWorks2, but I can't seem to find it. Where is it located? – Latterly

@Latterly I added a section to the bottom of my answer with the information. – Piperonal

The update URL tunnelvisionlabs.com/downloads/nbupdates/aw21/updates.xml gives a 404. I am also unsure if I have the latest version. I downloaded it in February, but it says that is is version 2.0 and not 2.1 in the Plugins dialog. More specfically version ANTLRWorks 2 20130716-5d2e7d936ca1 – Latterly

@Latterly As I mentioned in the post, you no longer need to add a custom update URL to the NetBeans settings dialog. ANTLRWorks is distributed through the standard update center making it visible to all NetBeans 7.4 and NetBeans 8.0 users. – Piperonal

I found it now. I had downloaded ANTLRWorks 2 from the Tunnel Vision Labs website and for that the update did not work. – Latterly

@220Z28 I can't really get the profiler to work though. I do Interpret Parser and pick a file to parse and it only opens the file that should be parsed and gives it a .pinterp suffix. – Latterly

@Latterly Did you open the Parser Debugger Controller window pane? It should have numerous tables of statistics showing the details of the parser performance. – Piperonal

I opened the window, but all the tables where empty. I also tried rerunning it with the window already open, but the tables where still empty. The result came very quickly so it didnt seem like the parser had been running. Just running the example in the test rig takes at least 10 seconds. – Latterly

@220Z28 I am using Netbeans 8.0 if that matters. – Latterly

@Latterly I believe the window is asynchronously populated. Wait a minute and see if the results appear. Also, check to see if NetBeans is using your CPU after executing the Interpret Parser command. – Piperonal

@220Z28 Turns out there is a NullPointerException in org.antlr.v4.runtime.DiagnosticErrorListener.getConflictingAlts that causes problems for my particular test file. Do you have a bug tracker where I can report the problem? – Latterly

Is there a way to use the profiler with a grammar that needs embedded actions (all Java) and where the parser needs to be instantiated manually(A special constructor has to be used)? – Rhamnaceous

Answer 2

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

Guadalcanal

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());
    }
}

Confirmed

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

Inevitable