home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / compiler / 1523 < prev    next >
Encoding:
Internet Message Format  |  1992-09-08  |  1.3 KB
  1. Path: sparky!uunet!gatech!rutgers!faatcrl!iecc!compilers-sender
  2. From: markh@csd4.csd.uwm.edu (Mark)
  3. Newsgroups: comp.compilers
  4. Subject: Re: LR(0) vs. LALR, and the Great Parsing War
  5. Keywords: parse, LALR
  6. Message-ID: <92-09-042@comp.compilers>
  7. Date: 5 Sep 92 15:43:56 GMT
  8. References: <92-08-179@comp.compilers> <92-09-018@comp.compilers>
  9. Sender: compilers-sender@iecc.cambridge.ma.us
  10. Reply-To: markh@csd4.csd.uwm.edu (Mark)
  11. Organization: Computing Services Division, University of Wisconsin - Milwaukee
  12. Lines: 17
  13. Approved: compilers@iecc.cambridge.ma.us
  14.  
  15. goer@midway.uchicago.edu (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. >Exponential time factor, I mean.  Not "cubic"!
  20.  
  21. This is what I understand to be the case:
  22.  
  23. The later (1992) reference made a couple enhancements to the algorithm
  24. that gives it cubic worst case performance in both space and time.  That
  25. means that every possible parse, even if there is an infinite number of
  26. them, is accepted within those space and time limits.
  27.  
  28. And it is still linear on LR(1) grammars.
  29. -- 
  30. Send compilers articles to compilers@iecc.cambridge.ma.us or
  31. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  32.