Sat, 26 Feb 1994 01:31:45 GMT

Related articles |
---|

Parsing with infinite lookahead Matt_Timmermans@msl.isis.org (Matt Timmermans/MSL) (1994-02-22) |

Re: Parsing with infinite lookahead jos@and.nl (1994-02-24) |

Parsing with infinite lookahead bevan@cs.man.ac.uk (Stephen J Bevan) (1994-02-24) |

Re: Parsing with infinite lookahead dwohlfor@cs.uoregon.edu (1994-02-24) |

Re: Parsing with infinite lookahead parrt@s1.arc.umn.edu (Terence Parr) (1994-02-25) |

Re: Parsing with infinite lookahead corbett@lupa.Eng.Sun.COM (1994-02-26) |

Re: Parsing with infinite lookahead nandu@cs.clemson.edu (1994-02-27) |

Re: Parsing with infinite lookahead hbaker@netcom.com (1994-02-28) |

Re: Parsing with infinite lookahead hbaker@netcom.com (1994-03-01) |

Re: Parsing with infinite lookahead bromage@mundil.cs.mu.OZ.AU (1994-03-02) |

Re: Parsing with infinite lookahead mareb@cis0.levels.unisa.edu.au (1994-03-24) |

Newsgroups: | comp.compilers |

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

Keywords: | parse, theory |

Organization: | Sun |

References: | 94-02-174 94-02-188 |

Date: | Sat, 26 Feb 1994 01:31:45 GMT |

dwohlfor@cs.uoregon.edu (Clai'omh Dorcha) writes:

*>The CYK algorithm (as seen in Hopcroft & Ullman) is capable of parsing*

*>_any_ context free grammar. The bummer is that it is O(n^3) where n is*

*>the length of the input string. Most folks aren't too keen on using it*

*>when a linear parser exists for most CFG's. But it is the only general*

*>purpose parsing algorithm.*

The ONLY general-purpose parsing algorithm? HARDLY! Earley's

algorithm (CACM 13:2), the Graham, Harrison, Ruzzo algorithm

(TOPLAS 2:3), backtracking algorithms all handle general

context-free grammars.

BTW, the order complexity of context-free parsing has been shown to

be less than or equal to the order complexity of matrix multiplication.

Yours truly,

Robert Corbett

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.