Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| 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) |
| From: | Danny.Dube@ift.ulaval.ca (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 <torbenm@diku.dk> 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.
@article{505242,
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 = {http://doi.acm.org/10.1145/505241.505242},
publisher = {ACM},
address = {New York, NY, USA},
}
--
Danny DubC), professeur
DC)partement d'informatique et de gC)nie logiciel
UniversitC) Laval
Return to the
comp.compilers page.
Search the
comp.compilers archives again.