Sat, 5 Sep 1992 15:43:56 GMT

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

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.