Re: LALR parsing

Matthias-Christian ott <ott@mirix.org>
Mon, 14 Dec 2009 21:28:42 +0100

          From comp.compilers

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)
| List of all articles for this month |

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.