Re: LALR parsing

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

Return to the comp.compilers page.
Search the comp.compilers archives again.