Wed, 4 Nov 1992 11:40:31 GMT

Related articles |
---|

Grammar Algebra? hallpwcd@ucunix.san.uc.EDU (1992-10-26) |

Re: Grammar Algebra? wand@dec5120z.ccs.northeastern.edu (1992-10-27) |

Re: Grammar Algebra? hallpwcd@ucunix.san.uc.EDU (1992-10-31) |

Re: Grammar Algebra? jan@klikspaan.si.hhs.nl (1992-11-02) |

re: Grammar Algebra? keithc@dcs.qmw.ac.uk (Keith Clarke) (1992-11-02) |

Re: Grammar Algebra? hdev@dutiaj.twi.tudelft.nl (1992-11-03) |

Re: Grammar Algebra? Peter.Breuer@prg.oxford.ac.uk (1992-11-04) |

Newsgroups: | comp.compilers |

From: | Peter.Breuer@prg.oxford.ac.uk (Peter Breuer) |

Organization: | Oxford University Computing Laboratory, UK |

Date: | Wed, 4 Nov 1992 11:40:31 GMT |

Keywords: | parse, theory, tools |

References: | 92-10-126 92-11-008 |

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>

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.