Mon, 14 Dec 2009 17:34:29 +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: | Mon, 14 Dec 2009 17:34:29 +0100 |

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

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

Keywords: | LALR, theory, parse |

Posted-Date: | 14 Dec 2009 14:56:41 EST |

Russ Cox <rsc@swtch.com> writes:

*> We prove a dual result: any CFG parser with time complexity*

*> O(g*n^(3-epsilon)), where g is the size of the grammar and n is*

*> the length of the input string, can be efficiently converted into*

*> an algorithm to multiply m x m Boolean matrices in time*

*> O(m^(3-epsilon/3)).*

*>*

*> The more precise version of the statement above is therefore:*

*> Unless you can do matrix multiplication in O(m^(2 1/3)) time,*

*> you cannot do context free parsing in O(g*n) time.*

http://en.wikipedia.org/wiki/Matrix_multiplication#Algorithms_for_efficient_matrix_multiplication

states that the asymptoticallty fastest known square matrix

multiplication algorithm is O(m^2.376), which isn't that far from

O(m^2.3333). Since O(m^2.376) is "only" the currently best known

result, it is quite plausible that faster methods exist. So I can't see

the statement itself being a serious impediment to linear-time general

CF parsing.

Personally, I would not look at matrix multiplication for fast general

parsing, but rather look at extensions to deterministic push-down

automata. Two-way deterministic pushdown automata (which are O(n) on a

RAM) can parse surprisingly complex grammars (including many non-CF

grammars), and AFAIK it has not been proven that they can not parse all

CF grammars. So they seem like a good point to start looking for fast

parsing.

Torben

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.