|LR(0) vs. LALR, and the Great Parsing War email@example.com (1992-08-30)|
|Re: LR(0) vs. LALR, and the Great Parsing War firstname.lastname@example.org (1992-08-31)|
|Re: LR(0) vs. LALR, and the Great Parsing War email@example.com (1992-09-02)|
|Re: LR(0) vs. LALR, and the Great Parsing War firstname.lastname@example.org (1992-09-05)|
|Organization:||Computing Services Division, University of Wisconsin - Milwaukee|
|Date:||Sat, 5 Sep 1992 15:43:56 GMT|
email@example.com (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.
Return to the
Search the comp.compilers archives again.