home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / function / 1353 < prev    next >
Encoding:
Text File  |  1992-11-12  |  1.9 KB  |  44 lines
  1. Newsgroups: comp.lang.functional
  2. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!jvnc.net!yale.edu!ira.uka.de!math.fu-berlin.de!weberwu
  3. From: weberwu@inf.fu-berlin.de (Debora Weber-Wulff)
  4. Subject: Re: Functional Parsers
  5. Message-ID: <NVT8YHL@math.fu-berlin.de>
  6. Keywords: parsers
  7. Sender: news@math.fu-berlin.de (Math Department)
  8. Reply-To: dww@inf.fu-berlin.de
  9. Organization: Free University of Berlin
  10. References: <1992Nov3.145117.21227@eng.cam.ac.uk> <1992Nov3.160104.5305@odin.diku.dk> <1992Nov4.153220.8174@eng.cam.ac.uk> <1992Nov10.170123.107@eng.cam.ac.uk>
  11. Date: Thu, 12 Nov 1992 13:34:48 GMT
  12. Lines: 30
  13.  
  14. ptb@eng.cam.ac.uk (P.T. Breuer) writes:
  15. >>
  16. >>I don't mind admitting that I don't know what a non-LL language looks like.
  17.  
  18.  
  19. >Thanks to Debora Weber-Wulff for offering a test case.
  20. >The language { a^n b^n | n>=0 } apparently definitely has no LL grammar
  21. >(but does have a LR(0) one) and is specifiable in pre-cc. But not all
  22.  
  23. No, Peter, the language I gave you was
  24. {a^n b^n | n >=1} \cup [that's the LaTeX union operator] {a^n c^n | n >=1}
  25. This is not LL because you have to get all the way down to the b's or
  26. c's before you can decide which way you needed to go. In LR parsing,
  27. we are constructing the reverse of a right-derivation, we shift a's
  28. onto the stack until we see a b or a c, and they we *know* which
  29. set of productions to use. 
  30.  
  31.  
  32. >it's the basis of my claim that LR(0) languages are expressible.
  33. How about a proof including the time and space complexities of
  34. your system? I so enjoyed the strangesucc function, which has proved
  35. to me that, yes, it is nice to express things with backtracking and no,
  36. I do not want my systems to use it, because I prefer termination to
  37. stack overflow.
  38.  
  39. -- 
  40. Debora Weber-Wulff                       dww@inf.fu-berlin.de
  41. Institut fuer Informatik                 +49 30 89691 124
  42. Nestorstr. 8-9                           (INCLUDE "standard.disclaimer")
  43. D-W-1000 Berlin 31                       (PRINTN (WITTY-MESSAGE TODAY))
  44.