Re: Difference between Earley and Chart Parsers

"Philip Fortomas" <>
18 Dec 2000 00:43:16 -0500

          From comp.compilers

Related articles
Difference between Earley and Chart Parsers (2000-12-01)
Re: Difference between Earley and Chart Parsers (Philip Fortomas) (2000-12-18)
| List of all articles for this month |

From: "Philip Fortomas" <>
Newsgroups: comp.compilers
Date: 18 Dec 2000 00:43:16 -0500
Organization: Virgin Net Usenet Service
References: 00-12-005
Keywords: parse
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
== 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

Philip Fortomas

Post a followup to this message

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