|LALR parsing firstname.lastname@example.org (A. Soare) (2009-12-04)|
|Re: LALR parsing email@example.com (Torben AEgidius Mogensen) (2009-12-07)|
|Re: LALR parsing firstname.lastname@example.org (A. Soare) (2009-12-09)|
|Re: LALR parsing Danny.Dube@ift.ulaval.ca (2009-12-09)|
|Re: LALR parsing email@example.com (2009-12-10)|
|Re: LALR parsing firstname.lastname@example.org (Russ Cox) (2009-12-11)|
|Re: LALR parsing email@example.com (2009-12-14)|
|Re: LALR parsing firstname.lastname@example.org (Matthias-Christian ott) (2009-12-14)|
|Re: LALR parsing cfc@shell01.TheWorld.com (Chris F Clark) (2009-12-25)|
|From:||Matthias-Christian ott <email@example.com>|
|Date:||Mon, 14 Dec 2009 21:28:42 +0100|
|References:||09-12-007 09-12-009 09-12-018 09-12-019 09-12-021 09-12-024|
|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 <firstname.lastname@example.org> 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.
> 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 , 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.
 Dick Grune, Ceriel J.H. Jacobs (2008), Parsing Techniques.
A Practical Guide (2nd ed.), Springer, New York, p. 100,
Return to the
Search the comp.compilers archives again.