Re: Difference between Earley and Chart Parsers

Greg,


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
== 1)
Also almost all LR(k) grammars are BS(0) and those that are not BS(0) are
definitely BS(k).


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


Regards
Philip Fortomas

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