Antlr 4 parsing large c file takes forever

Question

I have a large c-code file (>9000 LoC) and attempt to parse it using this grammar:

https://github.com/antlr/grammars-v4/blob/master/c/C.g4

I waited for over an hour before aborting. The machine is a Core 2 Duo L9400 with 4GB of ram. Maximum java vm-heap-size is set to 2GB. It does not produce any parse errors, but it simply doesn't finish.

After doing some research, I set the prediction mode to SLL, which produces a "no viable alternative at input" within seconds.

Next, I set the prediction mode to LL_EXACT_AMBIG_DETECTION and attached a DiagnosticErrorListener to the parser. This produces a lot of "Ambiguity reports", mainly concerning declarations/declaration-specifiers. I assume this forces the parser to backtrack extremely often, which I is probably the explaination for the long parsing time?

Is there anything I can do to improve performance other than attempting to rewrite the grammar?

Any help is appreciated ;)

Answer 1

Yep. we converted that from the spec with only a single rule change is a demonstration that you could do it. We will optimize that one soon.

Answer 2

First of all, it's important to note that ANTLR 4 never backtracks during parsing.

The grammar you are referring to is not SLL, which prevents you from using ANTLR 4 in its fastest mode. However, during or experiments we were able to identify a single rule which we altered to make the grammar SLL. You may be able to obtain the altered grammar via the antlr-interest mailing list. I'm at a concert now so I don't have access to it.