Re: LALR parsing

"A. Soare" <alinsoar@voila.fr>
Wed, 9 Dec 2009 13:17:02 +0100 (CET)

          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: "A. Soare" <alinsoar@voila.fr>
Newsgroups: comp.compilers
Date: Wed, 9 Dec 2009 13:17:02 +0100 (CET)
Organization: Compilers Central
References: 09-12-007
Keywords: LALR
Posted-Date: 10 Dec 2009 02:24:55 EST

> > I want to implement a LALR parser for an arbitrary grammar (many
> > common point to yacc, however different).
> >
> > However, I did read that these methods are not the most fast. The
> > fastest methods use matrix multiplications, etc. In the book of Grune
> > is it explained something about the equalence between parsing and
> > matrix multiplication, but I see nothing useful apart of some vagues
> > ideas.
> >
> > My question for you is: what are the most efficient methods of lalr parsing?
>
> LALR(1) defined a class of grammars that can be parsed with a
> deterministic LALR(1) parser. These can be parsed in something
> approaching linear time. But LALR(1) can not deterministically parse
> arbitrary grammars. You can add backtracking to allow parsing of
> arbitrary grammars, but that can in the worst case give exponential
> runtimes. GLR parsers (see http://en.wikipedia.org/wiki/GLR_parser)
> handle the multiple parses in a breath-first manner instead of a
> depth-first backtracking, so they can merge identical states. This
> reduces the worst case to O(n^3).


Thanks. My question is: what implementation of lalr is the most
efficient? There are lots of implementations. For example, Simple
computation of LALR (1) lookahead sets (
http://cat.inist.fr/?aModele=afficheN&cpsidt=6679232 ) presents a
simple method by building a secondary grammar, and computing there the
follow sets. This is one method.


Another question is: is there a method of computing the lalr sets (
starting from SLR ) or whatever else using matrix multiplication?


Another question is : what reference do you recommend me in order for
me to understand the equivalence between parsing and matrix
multiplication?


And, finally, what methods of computing lalr sets are the fastest ?
There are lots of methods...




> While the matrix-multiplication methods you refer to have better
> worst-case performance, GLR will outperform them in most cases. Matrix
> multiplication can be done in O(n^2.376), but the algorithm for this has
> a huge constant factor overhead that makes the traditional O(n^3) method
> faster except for extremely large matrices. So I doubt the O(n^2.376)
> algorithm is of any practical use for parsing.


I know about glr, but I am not interested in the subject of general
grammars, but only in lalr(1) grammars.




Thanks,




Alin












____________________________________________________


Michael Jackson, Susan Boyle, Black Eyed Peas ... Retrouvez leurs derniers titres sur http://musiline.voila.fr



Post a followup to this message

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