Re: The speed of an Earley parser?

"Michael J. Fromberger" <sting@linguist.Dartmouth.EDU>
21 Jun 2001 03:08:37 -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: "Michael J. Fromberger" <sting@linguist.Dartmouth.EDU>
Newsgroups: comp.compilers
Date: 21 Jun 2001 03:08:37 -0400
Organization: Dartmouth College, Hanover, NH, USA
References: 01-06-041
Keywords: parse
Posted-Date: 21 Jun 2001 03:08:37 EDT

newspub@wuggy.co.uk (Ian Woods) writes:


>I'm working on a semi-learning, semi-serious project which requires
>some CF parsing. There are three major considerations on the
>selection of the parsing technique to be used:
>
>o It mustn't substantially restrict the layout of the grammar. [...]
>
>o The parsing operation must be completed in a reasonable period [...]
>
> [...]
>
>The question is this:
>
>What parsing techniques have the properties I require?
>
>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. ...
>
>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?


Hello there,


I used a variant of Earley's parser for a very complex natural
language based grammar in a project about five years ago, and I found
the performance to be acceptable. (The variant I used was due to
Andreas Stolcke, and basically involved tagging the productions with
probabilities, and the parser would generate "more probable" parse
trees first. This ordering helped cut down on the subsequent analysis
fairly significantly).


For many interesting context-free languages, restricting yourself to
LR(k) can make things difficult; on the other hand, if you're using
typical programming-language constructs, it seems like Earley's table
parser might be overkill. But, that's just my opinion.


Cheers,
-M


--
Michael J. Fromberger Software Engineer, Thayer School of Engineering
    sting <at> linguist.dartmouth.edu http://www.dartmouth.edu/~sting/


Post a followup to this message

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