18 Sep 1998 23:13:26 -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: | Yuen-Chang Sun <ycsun@ms7.hinet.net> |

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

Date: | 18 Sep 1998 23:13:26 -0400 |

Organization: | DCI HiNet |

Distribution: | inet |

Keywords: | parse, theory |

Could anybody please tell me the most efficient parsing algorithm you

know for general context- free grammars?

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]

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.