[antlr-interest] Progressive Slowdown in Parsing

[Gavin Lambert]

At 22:54 22/12/2008, A. Saake wrote:
>The first 2000 lines can be processed in under 1 min. If I parse 
>the whole script, time increases to 15 minutes. For a correct 
>migration of this script (it's an include file), I would have to 
>embed it into another 3500 lines code script, and I'm afraid that 
>it will need a very long time. Because of the variable system of 
>the 4GL (declaration of variables is not necessary, so there's no 
>scope, I have to estimate it from context), I will have to run it 
>many times.
>
>To find out, if the slowdown is from my grammar, I tried lot's of 
>syntactic predicates and so on, until I used a profiler, which 
>names GetKindOfOps as responsible for nearly 80% of the runtime.
>
>My grammar is a combined lexer and parser, output is template and 
>I use the token rewrite mechanism.

Do you use backtracking at all, or large syntactic 
predicates?  Either will reduce the parsing speed of a grammar.

Additionally, the smaller your tokens are the more work the parser 
is typically required to do (so single-character tokens are 
generally a bad idea).

It's hard to be more specific without seeing your grammar, though.