18 Dec 2000 00:43:16 -0500

Related articles |
---|

Difference between Earley and Chart Parsers gschmidt2@ra.rockwell.com (2000-12-01) |

Re: Difference between Earley and Chart Parsers philip.fortomas@virgin.net (Philip Fortomas) (2000-12-18) |

From: | "Philip Fortomas" <philip.fortomas@virgin.net> |

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 |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.