Wed, 9 Dec 2009 13:17:02 +0100 (CET)

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: | "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.