home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / compiler / 1827 < prev    next >
Encoding:
Internet Message Format  |  1992-11-10  |  3.8 KB
  1. Path: sparky!uunet!ogicse!das-news.harvard.edu!spdcc!iecc!compilers-sender
  2. From: Peter.Breuer@prg.oxford.ac.uk (Peter Breuer)
  3. Newsgroups: comp.compilers
  4. Subject: Re: Grammar Algebra?
  5. Keywords: parse, theory, tools
  6. Message-ID: <92-11-018@comp.compilers>
  7. Date: 4 Nov 92 11:40:31 GMT
  8. Article-I.D.: comp.92-11-018
  9. References: <92-10-126@comp.compilers> <92-11-008@comp.compilers>
  10. Sender: compilers-sender@iecc.cambridge.ma.us
  11. Reply-To: Peter.Breuer@prg.oxford.ac.uk (Peter Breuer)
  12. Organization: Oxford University Computing Laboratory, UK
  13. Lines: 85
  14. Approved: compilers@iecc.cambridge.ma.us
  15.  
  16. Keith Clarke <keithc@dcs.qmw.ac.uk> writes:
  17. >I just added a few lines to my collection of parsing functionals and can now 
  18. >interpret input like:
  19. >
  20. >    (triple (aChar 'a') (aChar 'b') (aChar 'c')) "aabbcc"
  21. >
  22. [ ...]
  23.  
  24. >My parsing functions are copied from/inspired by Graham Hutton "Parsing
  25. >using Combinators", in Functional Programming Glasgow 1989, ed. Davis &
  26. >Hughes, publ Springer. 
  27.  
  28. Interesting indeed. The semantics you quote is approximately that used by
  29. the pre-cc utility (a PREttier Compiler Compiler) available from Oxford,
  30. but pre-cc outputs C. Your spec isn't quite `right' at several points,
  31. though (for me!). You neglect to differentiate between parses which
  32. `succeed' and those which `fail', which makes your definitions of union
  33. and intersection `wrong'. `Wrong' is an opinion, however. What I mean is
  34. that you are losing out on a whole lot of nice algebraic properties, which
  35. give rise to a nice specification language too.
  36.  
  37. For example, the a^n b^n c^n example you quote can be coded as follows
  38. for pre-cc
  39.  
  40.  
  41.    triple = as\n <'b'>*n <'c'>*n
  42.  
  43.        as = a as\n     @(n+1)
  44.           | /* empty*/ @0
  45.  
  46. I'm just getting the synthetic attribute for the as (the number of 'a's)
  47. out as \n in the definition of triple, and using it in the repetition
  48. count for the 'b's and 'c's. There is no `new functional operator'
  49. required.
  50.  
  51.  
  52. >Intersection works in a set-like way, on the "set of interpretations"
  53. >produced by the alternatives. Only legal parses have an interpretation, &
  54.  
  55. Yes. That's right, but I fail to see where you've specified `legal', or
  56. how, indeed, you could limit yourself to legal parses when some parsers
  57. deliberately produce outputs that coincide with `illegal' parsers outputs.
  58. But then, as I said, I don't go along with your lack of a distinct `fail'
  59. state for parsers. It's not disastrous, because you get fails as the
  60. complement of the succeeds you specify, but it's just not _right_! Compare
  61. with CSP semantics. There are a lot of things you can't express because of
  62. your restriction to complementarity. In particular (practically speaking)
  63. you don't know when a parser with an infinity of possible parses to check
  64. HAS failed. Recursive parse definitions will give rise to such things.
  65.  
  66. I thought of making `intersection' primitive in pre-cc, but one can
  67. express it using sequential composition and a `phantom' operator. The
  68. phantom ]P[ checks what P would have done, but doesn't eat any of the
  69. tokens needed.
  70.  
  71.    intersect(p,q) = ]p[ q
  72.  
  73. works in pre-cc. I hope everyone spotted the higher-order semantics!
  74. Pre-cc semantics is declarative, BTW, so these synthetic (and inherited)
  75. attributes can be safely included and used in definitions, as in the
  76. example for a^n b^n c^n above. Here are some algebraic rules
  77.  
  78.  
  79.    {a|b}|c = a|{b|c}
  80.    )0==1( | c = c | )0==1( = c
  81.  
  82.    {a|b} c = a c | b c
  83.    a {b|c} = a b | a c
  84.    {} a = a {} = a
  85.    )0==1( a = )0==1(
  86.  
  87.    a\x {b(x)|c(x)} =  a\x b(x) | a\x c(x)
  88.    {a|b}\x c(x) = a\x c(x) | b\x c(x)
  89.  
  90. etc (do your own algebra for intersection and other operators).
  91.  
  92. Pre-cc is available by anon ftp from ftp.comlab.ox.ac.uk, in the
  93. Programs directory, in case anyone cares.
  94.  
  95. -------
  96. Peter T. Breuer
  97. <ptb@uk.ac.ox.comlab, ptb@uk.ac.cam.eng>
  98. -- 
  99. Send compilers articles to compilers@iecc.cambridge.ma.us or
  100. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  101.