Thu, 10 Dec 2009 10:12:35 +0100

Related articles |
---|

LALR parsing alinsoar@voila.fr (A. Soare) (2009-12-04) |

Re: LALR parsing torbenm@diku.dk (Torben AEgidius Mogensen) (2009-12-07) |

Re: LALR parsing alinsoar@voila.fr (A. Soare) (2009-12-09) |

Re: LALR parsing Danny.Dube@ift.ulaval.ca (2009-12-09) |

Re: LALR parsing torbenm@diku.dk (2009-12-10) |

Re: LALR parsing rsc@swtch.com (Russ Cox) (2009-12-11) |

Re: LALR parsing torbenm@diku.dk (2009-12-14) |

Re: LALR parsing ott@mirix.org (Matthias-Christian ott) (2009-12-14) |

Re: LALR parsing cfc@shell01.TheWorld.com (Chris F Clark) (2009-12-25) |

From: | torbenm@diku.dk (Torben Ęgidius Mogensen) |

Newsgroups: | comp.compilers |

Date: | Thu, 10 Dec 2009 10:12:35 +0100 |

Organization: | Department of Computer Science, University of Copenhagen |

References: | 09-12-007 09-12-009 09-12-018 |

Keywords: | parse, LALR, theory |

Posted-Date: | 11 Dec 2009 00:01:58 EST |

Danny.Dube@ift.ulaval.ca (Danny Dubi) writes:

*>> There may well be general parsers that are faster than matrix*

*>> multiplication. IIRC, the lower bound for CF parsing is still O(n).*

*> The following paper explains that a fast parsing algorithm can be*

*> turned into a fast (but not AS fast, though) binary matrix*

*> multiplication algorithm.*

*> author = {Lee, Lillian},*

*> title = {Fast context-free grammar parsing requires fast*

*> boolean matrix multiplication},*

I read the abstract of that paper some time ago, and as far as I recall,

the essense is that you can multiply two sqrt(n) x sqrt(n) binary

matrices in the time it takes to parse a length-n string. So if you can

multiply binary matrices in O(n^2) time, you _might_ be able to parse in

linear time. But having only read the abstract, I can't say for sure.

Also, there may be difference between parsing (constructing a

derivation) and recognition (deciding membership). It is plausible that

you can do the latter faster.

Torben

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.