Re: Grammar Algebra?

Keith Clarke <keithc@dcs.qmw.ac.uk> writes:
>I just added a few lines to my collection of parsing functionals and can now
>interpret input like:
>
> (triple (aChar 'a') (aChar 'b') (aChar 'c')) "aabbcc"
>
[ ...]


>My parsing functions are copied from/inspired by Graham Hutton "Parsing
>using Combinators", in Functional Programming Glasgow 1989, ed. Davis &
>Hughes, publ Springer.


Interesting indeed. The semantics you quote is approximately that used by
the pre-cc utility (a PREttier Compiler Compiler) available from Oxford,
but pre-cc outputs C. Your spec isn't quite `right' at several points,
though (for me!). You neglect to differentiate between parses which
`succeed' and those which `fail', which makes your definitions of union
and intersection `wrong'. `Wrong' is an opinion, however. What I mean is
that you are losing out on a whole lot of nice algebraic properties, which
give rise to a nice specification language too.


For example, the a^n b^n c^n example you quote can be coded as follows
for pre-cc




      triple = as\n <'b'>*n <'c'>*n


              as = a as\n @(n+1)
                    | /* empty*/ @0


I'm just getting the synthetic attribute for the as (the number of 'a's)
out as \n in the definition of triple, and using it in the repetition
count for the 'b's and 'c's. There is no `new functional operator'
required.




>Intersection works in a set-like way, on the "set of interpretations"
>produced by the alternatives. Only legal parses have an interpretation, &


Yes. That's right, but I fail to see where you've specified `legal', or
how, indeed, you could limit yourself to legal parses when some parsers
deliberately produce outputs that coincide with `illegal' parsers outputs.
But then, as I said, I don't go along with your lack of a distinct `fail'
state for parsers. It's not disastrous, because you get fails as the
complement of the succeeds you specify, but it's just not _right_! Compare
with CSP semantics. There are a lot of things you can't express because of
your restriction to complementarity. In particular (practically speaking)
you don't know when a parser with an infinity of possible parses to check
HAS failed. Recursive parse definitions will give rise to such things.


I thought of making `intersection' primitive in pre-cc, but one can
express it using sequential composition and a `phantom' operator. The
phantom ]P[ checks what P would have done, but doesn't eat any of the
tokens needed.


      intersect(p,q) = ]p[ q


works in pre-cc. I hope everyone spotted the higher-order semantics!
Pre-cc semantics is declarative, BTW, so these synthetic (and inherited)
attributes can be safely included and used in definitions, as in the
example for a^n b^n c^n above. Here are some algebraic rules




      {a|b}|c = a|{b|c}
      )0==1( | c = c | )0==1( = c


      {a|b} c = a c | b c
      a {b|c} = a b | a c
      {} a = a {} = a
      )0==1( a = )0==1(


      a\x {b(x)|c(x)} = a\x b(x) | a\x c(x)
      {a|b}\x c(x) = a\x c(x) | b\x c(x)


etc (do your own algebra for intersection and other operators).


Pre-cc is available by anon ftp from ftp.comlab.ox.ac.uk, in the
Programs directory, in case anyone cares.


-------
Peter T. Breuer
<ptb@uk.ac.ox.comlab, ptb@uk.ac.cam.eng>
--

Return to the comp.compilers page.
Search the comp.compilers archives again.