Re: LALR parsing

> > 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

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