Re: LALR parsing

torbenm@diku.dk (Torben Ęgidius Mogensen)
Thu, 10 Dec 2009 10:12:35 +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: Thu, 10 Dec 2009 10:12:35 +0100
Organization: Department of Computer Science, University of Copenhagen
References: 09-12-007 09-12-009 09-12-018
Keywords: parse, LALR, theory
Posted-Date: 11 Dec 2009 00:01:58 EST

Danny.Dube@ift.ulaval.ca (Danny Dubi) writes:


>> There may well be general parsers that are faster than matrix
>> multiplication. IIRC, the lower bound for CF parsing is still O(n).


> The following paper explains that a fast parsing algorithm can be
> turned into a fast (but not AS fast, though) binary matrix
> multiplication algorithm.


> author = {Lee, Lillian},
> title = {Fast context-free grammar parsing requires fast
> boolean matrix multiplication},


I read the abstract of that paper some time ago, and as far as I recall,
the essense is that you can multiply two sqrt(n) x sqrt(n) binary
matrices in the time it takes to parse a length-n string. So if you can
multiply binary matrices in O(n^2) time, you _might_ be able to parse in
linear time. But having only read the abstract, I can't say for sure.


Also, there may be difference between parsing (constructing a
derivation) and recognition (deciding membership). It is plausible that
you can do the latter faster.


Torben


Post a followup to this message

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