Re: LR(0) vs. LALR, and the Great Parsing War

markh@csd4.csd.uwm.edu (Mark)
Sat, 5 Sep 1992 15:43:56 GMT

          From comp.compilers
Related articles
LR(0) vs. LALR, and the Great Parsing War eifrig@beanworld.cs.jhu.edu (1992-08-30)
Re: LR(0) vs. LALR, and the Great Parsing War goer@midway.uchicago.edu (1992-08-31)
Re: LR(0) vs. LALR, and the Great Parsing War goer@midway.uchicago.edu (1992-09-02)
Re: LR(0) vs. LALR, and the Great Parsing War markh@csd4.csd.uwm.edu (1992-09-05)
| List of all articles for this month |
Newsgroups: comp.compilers
From: markh@csd4.csd.uwm.edu (Mark)
Organization: Computing Services Division, University of Wisconsin - Milwaukee
Date: Sat, 5 Sep 1992 15:43:56 GMT
References: 92-08-179 92-09-018
Keywords: parse, LALR

goer@midway.uchicago.edu (Richard L. Goerwitz) writes:
>>Yes and no. If this were true, then Tomita's algorithm would have a cubic
>>worst-case time factor. He uses a graph-structured parse forest, though,
>>and claims polynomial time.
>Exponential time factor, I mean. Not "cubic"!


This is what I understand to be the case:


The later (1992) reference made a couple enhancements to the algorithm
that gives it cubic worst case performance in both space and time. That
means that every possible parse, even if there is an infinite number of
them, is accepted within those space and time limits.


And it is still linear on LR(1) grammars.
--

Post a followup to this message

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