|LALR parsing email@example.com (A. Soare) (2009-12-04)|
|Re: LALR parsing firstname.lastname@example.org (Torben AEgidius Mogensen) (2009-12-07)|
|Re: LALR parsing email@example.com (A. Soare) (2009-12-09)|
|Re: LALR parsing Danny.Dube@ift.ulaval.ca (2009-12-09)|
|Re: LALR parsing firstname.lastname@example.org (2009-12-10)|
|Re: LALR parsing email@example.com (Russ Cox) (2009-12-11)|
|Re: LALR parsing firstname.lastname@example.org (2009-12-14)|
|Re: LALR parsing email@example.com (Matthias-Christian ott) (2009-12-14)|
|Re: LALR parsing cfc@shell01.TheWorld.com (Chris F Clark) (2009-12-25)|
|From:||"A. Soare" <firstname.lastname@example.org>|
|Date:||Wed, 9 Dec 2009 13:17:02 +0100 (CET)|
|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
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.
Michael Jackson, Susan Boyle, Black Eyed Peas ... Retrouvez leurs derniers titres sur http://musiline.voila.fr
Return to the
Search the comp.compilers archives again.