home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / compiler / 1420 < prev    next >
Encoding:
Internet Message Format  |  1992-08-20  |  3.1 KB
  1. Path: sparky!uunet!stanford.edu!rutgers!faatcrl!iecc!compilers-sender
  2. From: bromage@mullauna.cs.mu.OZ.AU (Andrew Bromage)
  3. Newsgroups: comp.compilers
  4. Subject: Re: A Non-LALR(1) Parser Generator
  5. Keywords: LR(1)
  6. Message-ID: <92-08-119@comp.compilers>
  7. Date: 20 Aug 92 07:03:13 GMT
  8. References: <92-08-090@comp.compilers> <92-08-104@comp.compilers>
  9. Sender: compilers-sender@iecc.cambridge.ma.us
  10. Reply-To: bromage@mullauna.cs.mu.OZ.AU (Andrew Bromage)
  11. Organization: Computer Science, University of Melbourne, Australia
  12. Lines: 55
  13. Approved: compilers@iecc.cambridge.ma.us
  14.  
  15. ejy@hrmsc.att.com (Eugene Yurek) writes:
  16.  
  17. >Charlie Wetherell originally wrote LR along with Shannon for some
  18. >government entity they were either employed for or were working on a
  19. >contract for, so, consequently, the entire source is in the public domain.
  20.  
  21. Does anybody know if LR is sitting on a server somewhere?
  22.  
  23. >This generator is not easy to use compared to YACC.  You cannot provide
  24. >semantic actions within the grammar.  They must be handled in a separate
  25. >source file, and manually tied back to the productions in the BNF (yuk!!).
  26. >Basically, I'm saying that LR works well, however, its not that easy to
  27. >use (though this is a subjective observation on my part). And as I said
  28. >above, you're going to need a Fortran compiler, and some patience to use
  29. >it.  It is, however, the only LR(1) parser generator that I've ever come
  30. >across (please, no flames!!!).
  31.  
  32. Even if it is useless from practical point of view, it would be very
  33. interesting to have a look at the source code. Apparently, also, LR had
  34. excellent output options, since the emphasis, I think, was to accept a
  35. very large class of grammars. Because of this, you could get from LR just
  36. about any diagnostic about your grammar that you could ever hope for.
  37.  
  38. Since my original article, I have been told this description of the first
  39. of Pager's algorithms:
  40.  
  41.     "Two items with the same lookahead symbol and different
  42.     cores should not be put together in a merged state unless
  43.     there are already two items in one of the states with those
  44.     cores and a common lookahead."
  45.  
  46. If anybody can make head or tail of this description, they're welcome to
  47. it.
  48.  
  49. His second algorithm ("strong compatibility") will merge _all_ item sets
  50. which can be merged without introducing a shift-reduce conflict into the
  51. parser, but is apparently computationally expensive. So here's a challenge
  52. for programmers out there: write a parser generator, which has the same
  53. conflict resolving capabilities as YACC, but will parse LR(1) grammars. By
  54. the way, parsers created must be of a reasonable size - i.e. some item set
  55. merging must take place.
  56.  
  57. While I'm on the subject of parser generators, I heard about an LALR
  58. parser generator written in Sasl the other day. Does anybody know about
  59. this?  
  60.  
  61. Also, have any other parser generators ever been written for LR(1)
  62. grammars (or any other superset of LALR(1) grammars for that matter)?  I
  63. know about some algorithms for parsing all context-free grammars, but they
  64. are all either parallel or run in cubic time...
  65.  
  66. bromage@mullauna.cs.mu.oz.au
  67. -- 
  68. Send compilers articles to compilers@iecc.cambridge.ma.us or
  69. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  70.