home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / function / 1346 < prev    next >
Encoding:
Internet Message Format  |  1992-11-10  |  2.3 KB

  1. Path: sparky!uunet!mcsun!uknet!cam-eng!ptb
  2. From: ptb@eng.cam.ac.uk (P.T. Breuer)
  3. Newsgroups: comp.lang.functional
  4. Subject: Re: Functional Parsers
  5. Keywords: parsers
  6. Message-ID: <1992Nov10.170123.107@eng.cam.ac.uk>
  7. Date: 10 Nov 92 17:01:23 GMT
  8. References: <1992Nov3.145117.21227@eng.cam.ac.uk> <1992Nov3.160104.5305@odin.diku.dk> <1992Nov4.153220.8174@eng.cam.ac.uk>
  9. Sender: ptb@uk.ac.cam.eng
  10. Organization: Cambridge University Engineering Department, England
  11. Lines: 61
  12. Nntp-Posting-Host: tw308.eng.cam.ac.uk
  13.  
  14. >In article <1992Nov3.160104.5305@odin.diku.dk> torbenm@diku.dk
  15. >(Torben AEgidius Mogensen) writes:
  16. >>ptb@prg.ox.ac.uk (Peter Breuer) writes:
  17. >>
  18. >>>There is also a paper by Jonathan Bowen and myself (which I think has
  19. >>>[...]
  20. >>
  21. >>Does this parser generator handle non-LL languages?
  22. >
  23. >I don't mind admitting that I don't know what a non-LL language looks like.
  24.  
  25.  
  26. Thanks to Debora Weber-Wulff for offering a test case.
  27. The language { a^n b^n | n>=0 } apparently definitely has no LL grammar
  28. (but does have a LR(0) one) and is specifiable in pre-cc. But not all
  29. LR(0) grammars are acceptable for precc, because LR(0) presentations can be
  30. left recursive. I think all LR(0) languages are expressible, though,
  31. if you choose the right grammar presentation.
  32.  
  33. two specifications:
  34.  
  35. (1) not using attributes
  36.  
  37. @ S = AB $
  38.  
  39. @ AB = a AB b
  40. @    | a b
  41.  
  42. (2) using attributes
  43.  
  44. @ S = as\n b*n $
  45.  
  46. @ as = a as\n @n+1
  47.      | a      @1
  48.  
  49. The latter is the more powerful technique, since it is computationally
  50. complete, as I showed by specifying an interpreter for occam object
  51. code. Admittedly, that was the worst possible example to choose! But
  52. it's the basis of my claim that LR(0) languages are expressible.
  53.  
  54. If you want the functional programming interpretations, then (using the
  55. operator notation from graham hutton's soon-to-be JFP paper - see this
  56. thread)
  57.  
  58. (1)   S = AB $then EOL
  59.  
  60.       AB = (a $then AB $then b) $alt (a $then b)
  61.  
  62. (2)   S = as $into (n -> bs(n) $then EOL)
  63.       
  64.       as = (a $then as $into (n -> success(n+1)))  $alt (a $then success 1)
  65.  
  66.       bs(n) = b $then bs(n-1) , n>1
  67.             = b               , otherwise
  68.  
  69. Has anyone done a speed comparison of the pure combinator approach (aka
  70. Wadler (1985), Fairbairn (1987), etc.)  versus combinators which build new
  71. state machines from old, Using cross products of the state spaces, and
  72. so on?
  73.  
  74. Peter
  75.