[antlr-interest] Parser performance dropping as a function of line count

[Ric Klaren]

Hi,

On 10/2/06, Rukmal Fernando <rukmal_fernando at yahoo.com> wrote:
> I have removed it, and this seems to have rectified the problem. Thank you very much once again.

Great :)

> Out of curiosity, can anyone point out why a simple misplaced syntactic predicate could have such an impact, especially one that grew with the file size even when the number of lines parsed was fixed? (i.e.: in my case, the time the parser took to parse up to the first parser error @line 460 doubled for every 1000 lines in the source file).

A syntactic predicate let's ANTLR run in trial and error mode. E.g.
when it get's to the point that it needs to evaluate the predicate it
turns on the so called guessing mode. From this point on antlr tries
to evaluate a parse run of the predicate (with actions turned off) if
this fails parsing continues at the next alternative (or an error is
thrown). So in the best case ANTLR will look at the input twice to
parse it (once to evaluate the predicate, and once to really parse it
(but now including actions)). Worst case it will completely explode in
your face and look a gazillion times at eacht token before deciding
one alternative.. and then merrily continue with the next...

If you want to get a feel for this just make an example grammar and
look at the generated code.

Syntactic predicates are really nice to get something going. After you
got it going you should really carefully look at removing them as much
as possible. There's a trade-off in readability of the grammar (left
factoring often does not improve readability) and speed there.

Cheers,

Ric