Re: The speed of an Earley parser?

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/

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