Re: The speed of an Earley parser?

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

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