Re: The speed of an Earley parser?

Ian Woods <newspub@wuggy.co.uk> wrote:
> To me, Earley's parser seems to me a good bet: it has 2 of the
> requirements. It's only the speed which I'm concerned
> about. Although I'm likely to be alive by the time it finishes
> parsing a few thousand tokens against a realistic programming
> language grammar, is the time taken going to be to long (in the
> order of hours)?


Early should be fast enough, unless the grammar is highly ambiguous
(in which case parsing time will deteriorate). For an almost-LR
language (as most languages are), and on a modern processor, Earley
parsing time is unnoticeable. (A compiler with an Earley parser is the
basis of my daily work. Its syntax analysis phase is to fast that it's
unnoticeable, and I know that the total system wasn't designed for
speed.)


> Should I simply restrict the grammars to those able to be parsed by
> LALR(k) and just follow the crowd? Or is there some other technique
> which I haven't ran into yet which may be better than either?


LALR doesn't fit your needs. Most grammars require rewriting to make
them LALR, and the things to change aren't straightforward (unless you
have a *lot* of experience with this process). Your users would have you
for that.


Regards,
Joachim

Return to the comp.compilers page.
Search the comp.compilers archives again.