🚀 go-pugleaf

In article <BEVAN.92Nov1141304@otter.cs.man.ac.uk> bevan@cs.man.ac.uk (Stephen J Bevan) writes:
>There have been a few requests regarding parsing recently so I thought
>I'd bundle up a (incomplete) paper I wrote and make it available.  You

There is also a paper by Jonathan Bowen and myself (which I think has
been submitted to J. Functional Programming, Jonathan?) that shows how to
construct higher order parsers in C. Of course, the method works
equally well in your favourite (lazy) functional programming language!

This paper points out an abstract `higher order' algebraic structure in parsers
for inherited and synthetic attribute grammars and defines implementations
for the basic parsers and parser combinators. I am trying not to say
`monad'! The parser generator defined in the paper puts out C code, as I
mentioned, in order to allow for portable compilation, but there's nothing to
stop one just running the compound parsers in the usual functional programming
style.

There is a real implementation in C, called pre-cc, and tests show it
to run as fast or faster than yacc/lex parsers. There are two short
papers on pre-cc accepted for the Toulouse software engineering
conference in December, and the long JFP paper is available from OUCL
as TR-20-92: A Prettier Compiler-Compiler:
	     Generating Higher Order Parsers in C
	     Peter Breuer and Jonathan Bowen
contact me or the librarian for details (address below).

A very good paper that gives one the basic idea of how to use
combinators to implement parsers (as opposed to implementing flat automata)
is Jon Fairbairn's ``Making form follow function: an exercise in
functional programming style", in Software Practice and Experience,
1987 (some vol or other!). I believe that my paper `improves' on the
functional programming ideas there essentially only in spotting how to
build synthetic attributes in an integrated way. Jon's method was a bit
of an afterthought.

I also see that at least one of the pre-cc papers is available by anonymous
ftp from oxford.
	   ftp ftp.comlab.ox.ac.uk (login as anonymous, etc.)
	   cd Documents
	   cd papers
	   binary
	   get precc-occam.ps.Z

I guess that's the ``Occam's Razor: the cutting edge of parser
technology" paper, again by Jonathan and myself, which at least is a
good read, even if it doesn't mention FP. With luck, it'll give other
pointers. The pre-cc utility itself is available by ftp from Oxford
(cd Programs instaed of cd Documents).

Peter
---------
Peter T. Breuer
Oxford University Computing Laboratory
11 Keble Road, Oxford OX1 3QD
<ptb@uk.ac.ox.comlab, ptb@uk.ac.cam.eng>