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

goer@midway.uchicago.edu (Richard L. Goerwitz)
Mon, 31 Aug 1992 17:20:54 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: goer@midway.uchicago.edu (Richard L. Goerwitz)
Organization: University of Chicago Computing Organizations
Date: Mon, 31 Aug 1992 17:20:54 GMT
References: 92-08-179
Keywords: parse

Jonathan Eifrig writes:
> This seems quite surprising to me, given that Tomita's algorithm
>basically has to spin off on the fly new parsing automatons to follow each
>possible path in a derivation.


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.
--
      -Richard L. Goerwitz goer%midway@uchicago.bitnet
      goer@midway.uchicago.edu rutgers!oddjob!ellis!goer
--

Post a followup to this message

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