[antlr-interest] ANTLR performance

[Lorenzo de Lara]

I have noticed the same thing with rewrite=true and came upon this bug report from 2008, which is currently still open:

http://www.antlr.org/jira/browse/ANTLR-371

The problem is parsers with rewrite rules run in non-linear time on any inputs above a few hundred rewrites. I've verified this in both Java and C#. You can verify this for yourself by commenting out your rewrite rules and running the parser and observing much closer to linear runtime. (5 minutes with rewrite rules on vs. 5 seconds rewrite rules off on a typical 1500 line input for us) The offending method is GetKindOfOps in TokenRewriteStream taking up to 100% of the runtime according to a Java profiling tool.

I've implemented the proposed fix (in Java) which does away with calling GetKindOfOps completely and can confirm it does result in much more reasonable, linear-like performance, without introducing any new problems, as far as I can tell.

-Lorenzo

On 2010-05-11, at 5:17 , Chrobot, Stefan wrote:

Hi,



I'm using ANTLR with the C# target. The generated parser performs too
slow for my needs. My grammar uses k = 6.

Does it have a performance impact? What value should I target to get
optimum performance - 1 or *? Would changing the grammar to 1/* give
significant performance boost?





Stefan


List: http://www.antlr.org/mailman/listinfo/antlr-interest
Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address