Re: The speed of an Earley parser?

"Joachim Durchholz" <joachim_d@gmx.de>
21 Jun 2001 03:16:47 -0400

          From comp.compilers

Related articles
The speed of an Earley parser? newspub@wuggy.co.uk (2001-06-17)
Re: The speed of an Earley parser? sting@linguist.Dartmouth.EDU (Michael J. Fromberger) (2001-06-21)
Re: The speed of an Earley parser? joachim_d@gmx.de (Joachim Durchholz) (2001-06-21)
Re: The speed of an Earley parser? newspub@wuggy.co.uk (2001-06-28)
Re: The speed of an Earley parser? idbaxter@semdesigns.com (Ira D. Baxter) (2001-07-02)
Re: The speed of an Earley parser? news0@greynode.net (Benjamin S.Scarlet) (2001-08-06)
Re: The speed of an Earley parser? Mark.van.den.Brand@cwi.nl (M.G.J. van den Brand) (2001-08-08)
Re: The speed of an Earley parser? holzmueller@ics-ag.de (2001-08-15)
| List of all articles for this month |

From: "Joachim Durchholz" <joachim_d@gmx.de>
Newsgroups: comp.compilers
Date: 21 Jun 2001 03:16:47 -0400
Organization: Compilers Central
References: 01-06-041
Keywords: parse
Posted-Date: 21 Jun 2001 03:16:46 EDT

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


Post a followup to this message

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