home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / compiler / 1391 < prev    next >
Encoding:
Internet Message Format  |  1992-08-16  |  2.5 KB
  1. Path: sparky!uunet!sun-barr!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: parse, bibliography
  6. Message-ID: <92-08-090@comp.compilers>
  7. Date: 17 Aug 92 01:04:02 GMT
  8. References: <92-08-016@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: 44
  13. Approved: compilers@iecc.cambridge.ma.us
  14.  
  15. dan%npt1@uunet.UU.NET (Dan White) writes:
  16. >   Do you know of any parser generators that will generate parsers for
  17. >languages that are not LALR(1)? Specifically, I want to generate a parser
  18. >for a language called CMS-2.
  19.  
  20. D Pager has produced a few algorithms which may be of some use. They are
  21. designed to handle LR(1) grammars (a proper superset of LALR(1)), but
  22. produce parsers of realistic size. He does this by merging sets (as in the
  23. standard LALR construction algorithm), but using a different criterion
  24. than equality of cores.
  25.  
  26. The references are:
  27. Pager, "A practical general method for constructing LR(k) parsers", Acta
  28. Informatica, 7, pp 249-268, 1977.
  29.  
  30. Pager, "The lane tracing algorithm for constructing LR(k) parsers",
  31. Information Science, 12, pp 19-42, 1977.
  32.  
  33. The first (ie simpler) algorithm was used in a parser compiler called
  34. "LR", the availability of which I know nothing about.
  35.  
  36. It was reviewed in:
  37. Wetherell and Shannon, "LR - automatic parser generator and LR(1) parser",
  38. IEEE Transactions on Software Engineering, SE-7, pp 274-278, 1981.
  39.  
  40. >[A common approach is to twist the syntax around until it's LALR, either by
  41. >accepting a superset of the legal language and throwing out the bad cases
  42. >semantically, or else by using lexical feedback kludges to guide the parser,
  43. >typically by passing up special tokens from the lexer. -John]
  44.  
  45. This is a really bad hack, and should be avoided. I know it's common
  46. practice, but I don't believe that it's particularly marvellous.
  47.  
  48. A nice approach was used in Gofer, where operator precedences are
  49. redefinable from the source. The way this was fixed was to store
  50. expressions as a linked list and writing another parser to handle these
  51. expressions. It's a bit like the LL and operator precedence parsers of
  52. yesteryear. I think that the moral of the story is to only use other
  53. techniques when the LR approach genuinely fails, and not before.
  54.  
  55. bromage@mullauna.cs.mu.oz.au
  56. -- 
  57. Send compilers articles to compilers@iecc.cambridge.ma.us or
  58. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  59.