home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / compiler / 1499 < prev    next >
Encoding:
Internet Message Format  |  1992-09-01  |  1.2 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!usc!rutgers!faatcrl!iecc!compilers-sender
  2. From: goer@midway.uchicago.edu (Richard L. Goerwitz)
  3. Newsgroups: comp.compilers
  4. Subject: Re: LR(0) vs. LALR, and the Great Parsing War
  5. Keywords: parse, LALR, comment
  6. Message-ID: <92-09-018@comp.compilers>
  7. Date: 2 Sep 92 00:47:47 GMT
  8. References: <92-08-179@comp.compilers> <92-09-011@comp.compilers>
  9. Sender: compilers-sender@iecc.cambridge.ma.us
  10. Reply-To: goer@midway.uchicago.edu (Richard L. Goerwitz)
  11. Organization: University of Chicago Computing Organizations
  12. Lines: 15
  13. Approved: compilers@iecc.cambridge.ma.us
  14.  
  15. Richard L. Goerwitz writes:
  16. >Yes and no.  If this were true, then Tomita's algorithm would have a cubic
  17. >worst-case time factor.  He uses a graph-structured parse forest, though,
  18. >and claims polynomial time.
  19.  
  20. Exponential time factor, I mean.  Not "cubic"!
  21.  
  22. -- 
  23.  
  24.    -Richard L. Goerwitz              goer%midway@uchicago.bitnet
  25.    goer@midway.uchicago.edu          rutgers!oddjob!ellis!goer
  26. [Oops, shoulda caught that. -John]
  27. -- 
  28. Send compilers articles to compilers@iecc.cambridge.ma.us or
  29. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  30.