|Difference between Earley and Chart Parsers email@example.com (2000-12-01)|
|Re: Difference between Earley and Chart Parsers firstname.lastname@example.org (Philip Fortomas) (2000-12-18)|
|From:||"Philip Fortomas" <email@example.com>|
|Date:||18 Dec 2000 00:43:16 -0500|
|Organization:||Virgin Net Usenet Service|
|Posted-Date:||18 Dec 2000 00:43:16 EST|
Though it is true that Earley's algortihm is O(n^3), this is only true for
totally unrestricted context-free grammars. Those that *are* Bounded Direct
Ambiguity (BDA) compile in O(n^2) time and more - interestingly - all
Bounded State with lookahead k - BS(k) - are compliled in linear time O(n).
In fact, the only unambiguous grammars that it does not compile in linear
time are some palindrome grammars with unmarked centres and variations on
them like the following:
A --> x | xAx (this generates sentences of the form x^n where n >= 1 and n%2
Also almost all LR(k) grammars are BS(0) and those that are not BS(0) are
The only chart parsing algorithm that I know which is able to parse general
context-free grammars with a complexity that approaches that of Earley's is
the Cocke-Younger-Kasami one (1967) that achieves the same upper bounds with
the proviso that the grammar is put into normal form, i.e. that every
production is of the form A --> a or A --> BC.
Hope this helps a bit
Return to the
Search the comp.compilers archives again.