Mon, 14 Dec 2009 21:28:42 +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: | Matthias-Christian ott <ott@mirix.org> |

Newsgroups: | comp.compilers |

Date: | Mon, 14 Dec 2009 21:28:42 +0100 |

Organization: | Compilers Central |

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

Keywords: | LALR, parse |

Posted-Date: | 15 Dec 2009 00:32:58 EST |

On Mon, Dec 14, 2009 at 05:34:29PM +0100, Torben o?=gidius Mogensen wrote:

*> 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.*

This is also the opinion of Grune and Jacobs [1], but just because

there hasn't been a prove that general CF parsing isn't possible in

O(n). So all statements about the possibility of general CF parsing in

O(n) are simply speculations.

They also claim that boolean matrix multiplication requires at least

O(n^2) actions, so such a linear parsing algorithms is probably not

based on it or has correlation with it.

Regards,

Matthias-Christian

[1] Dick Grune, Ceriel J.H. Jacobs (2008), Parsing Techniques.

A Practical Guide (2nd ed.), Springer, New York, p. 100,

ISBN-13 978-0-387-20248-8

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.