Re: The speed of an Earley parser?

newspub@wuggy.co.uk (Ian Woods)
28 Jun 2001 23:40:41 -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: newspub@wuggy.co.uk (Ian Woods)
Newsgroups: comp.compilers
Date: 28 Jun 2001 23:40:41 -0400
Organization: (Posted via) GTS Netcom - Public USENET Service http://pubnews.netcom.net.uk
References: 01-06-041 01-06-045
Keywords: parse
Posted-Date: 28 Jun 2001 23:40:41 EDT

sting@linguist.Dartmouth.EDU (Michael J. Fromberger) wrote
>newspub@wuggy.co.uk (Ian Woods) writes:


>>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. ...


>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).


Nice idea... I might have to look that one up!


>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.


The problem is that this tool isn't really a 'compiler' or an
'interpreter' in the normal sense - it's supposed to simplify the
evolutionary development of defining or modifying a language, and to
allow one language to be embedded into another. That's why the
generallity is important - the grammar and the semantic rules attached
to it are primarily for human rather than machine consumption.


Hopefully, I can make it work! :D


Ian Woods


Post a followup to this message

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