home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / compiler / 1492 < prev    next >
Encoding:
Internet Message Format  |  1992-09-01  |  1.2 KB
  1. Path: sparky!uunet!cis.ohio-state.edu!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
  6. Message-ID: <92-09-011@comp.compilers>
  7. Date: 31 Aug 92 17:20:54 GMT
  8. References: <92-08-179@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: 14
  13. Approved: compilers@iecc.cambridge.ma.us
  14.  
  15. Jonathan Eifrig writes:
  16. >    This seems quite surprising to me, given that Tomita's algorithm
  17. >basically has to spin off on the fly new parsing automatons to follow each
  18. >possible path in a derivation.
  19.  
  20. Yes and no.  If this were true, then Tomita's algorithm would have a cubic
  21. worst-case time factor.  He uses a graph-structured parse forest, though,
  22. and claims polynomial time.
  23. -- 
  24.    -Richard L. Goerwitz              goer%midway@uchicago.bitnet
  25.    goer@midway.uchicago.edu          rutgers!oddjob!ellis!goer
  26. -- 
  27. Send compilers articles to compilers@iecc.cambridge.ma.us or
  28. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  29.