Re: LALR parsing

torbenm@diku.dk (Torben Ęgidius Mogensen)
Mon, 14 Dec 2009 17:34:29 +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: 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.