19 Sep 1998 21:19:31 -0400

Related articles |
---|

Parsing Algorithm for General CFGs ycsun@ms7.hinet.net (Yuen-Chang Sun) (1998-09-18) |

Re: Parsing Algorithm for General CFGs corbett@lupa.Eng.Sun.COM (1998-09-19) |

Re: Parsing Algorithm for General CFGs cfc@world.std.com (Chris F Clark) (1998-09-22) |

From: | corbett@lupa.Eng.Sun.COM (Robert Corbett) |

Newsgroups: | comp.compilers,comp.theory,comp.programming |

Date: | 19 Sep 1998 21:19:31 -0400 |

Organization: | Sun Microsystems Computer Corporation |

Distribution: | inet |

References: | 98-09-076 |

Keywords: | parse, theory |

Yuen-Chang Sun <ycsun@ms7.hinet.net> wrote:

*>Could anybody please tell me the most efficient parsing algorithm you*

*>know for general context- free grammars?*

Check out the paper by Graham, Harrison, and Ruzzo in TOPLAS 2:3.

*>Actually what I really want to know is the known computational*

*>complexity of parsing general CFGs. I know there are O(n^3)*

*>algorithms. Is there a O(n^2) or even better algorithm? And is there*

*>a lower bound? (I mean an absolute lower bound higher than O(n), of*

*>course.)*

*>[General CFGs? I think it's n^3 unless you significantly restrict the*

*>grammars it can handle. -John]*

Worst-case general context-free parsing has been shown to be at least

as fast as computing transitive closures. Computing transitive

closures has been shown to be as fast as matrix multiplication. The

asymtotically best algorithm for matrix multiplication I have seen is

O(n^2.48).

There is a "hardest" context-free grammar. Parsing for any other

context-free grammar can be done in time that is at most a constant

multiple of the time required for the hardest context-free grammar.

Sincerely,

Bob Corbett

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.