Re: LALR parsing (Danny =?utf-8?Q?Dub=C3=A9?=)
Wed, 09 Dec 2009 20:59:14 -0500

          From comp.compilers

Related articles
LALR parsing (A. Soare) (2009-12-04)
Re: LALR parsing (Torben AEgidius Mogensen) (2009-12-07)
Re: LALR parsing (A. Soare) (2009-12-09)
Re: LALR parsing (2009-12-09)
Re: LALR parsing (2009-12-10)
Re: LALR parsing (Russ Cox) (2009-12-11)
Re: LALR parsing (2009-12-14)
Re: LALR parsing (Matthias-Christian ott) (2009-12-14)
Re: LALR parsing (Chris F Clark) (2009-12-25)
| List of all articles for this month |

From: (Danny =?utf-8?Q?Dub=C3=A9?=)
Newsgroups: comp.compilers
Date: Wed, 09 Dec 2009 20:59:14 -0500
Organization: Compilers Central
References: 09-12-007 09-12-009
Keywords: bibliography, parse
Posted-Date: 10 Dec 2009 02:25:52 EST

Torben AEgidius Mogensen <> writes:

> Note, however, that while it has been proven that the complexity of
> parsing is bounded by the complexity of matrix multiplication, the
> converse is not true: 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},
  journal = {J. ACM},
  volume = {49},
  number = {1},
  year = {2002},
  issn = {0004-5411},
  pages = {1--15},
  doi = {},
  publisher = {ACM},
  address = {New York, NY, USA},

Danny DubC), professeur
DC)partement d'informatique et de gC)nie logiciel
UniversitC) Laval

Post a followup to this message

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