🚀 go-pugleaf

In article <1992Oct29.095529.17894@Informatik.TU-Muenchen.DE>, nipkow@Informatik.TU-Muenchen.DE (Tobias Nipkow) writes:
> I am looking for work on parsers/parser generators for arbitrary context free
> grammars (or large subclasses) which are suitable for implementation in a
> functional language. My experience is that, for example, Earley's algorithm
> is difficult to implement efficiently in a functional language.

lazy or eager?

I am considering to implement an LR(0) parser generator.

Horst Hogenkamp
.

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
can get it by anonymous ftp as :-

  pub/haskell/library/bevan/parsing.tar.Z:anonymous@animal.cs.chalmers.se

Here is the README file that comes with it :-

The associated DVI file contains an _incomplete_ _draft_[1] of a paper
about a simple method for parsing LL(1) languages[2].  It discusses a
variation[3] of the LL(1) method using continuations to drive the parsing
process.  The paper describes the construction of a parser and lexer
for the toy language Asple.  Haskell is used as the implementation
language and use is made of Haskell's ability to declare infix
operators so that the programs look similar to ordinary BNF.
The complete code is available as either "asple.gs" (for Gofer) or
"asple.hs" (see details at the end).

Note there is no discussion of constructing an abstract syntax tree
(that is due in a later paper, when I've actually finished the current
one!), for information on how to do this, see the file "asple_cc.shar"
which contains a parser that builds an abstract syntax for Asple and
then checks the associated context conditions.  The code does contain
comments so it shouldn't be too hard to work out what is going on.

-------
[1] I intended to finish it back in August, but events have overtaken
    me.  I'm only making it available in its incomplete form since
    there have been a number of requests regarding writing (simple)
    parsers in functional languages.
[2] With judicious fiddling of the continuations, it should be possible
    to create a backtracking parser and so deal with a large class of
    grammars.
[3] Since writing most of the paper I found the same sort of method
    being used in an example file in the Edinburgh ML library.  The
    difference being that there "exceptions" are used instead of
    continuations.  

Obtaining source code
---------------------

The files mentioned previously are all available by anonymous ftp from
the Haskell library (as is this file) :-

  pub/haskell/library:anonymous@dcs.glasgow.ac.uk
  pub/haskell/library:anonymous@nebula.cs.yale.edu
  pub/haskell/library:anonymous@animal.cs.chalmers.se
  pub/haskell/library/bevan:anonymous@animal.cs.chalmers.se

or by mail server :-

  To: bevan@cs.man.ac.uk
  Subject: b-server-request
  send haskell/asple.gs

... etc. for other files.

If you have any problems obtaining files, comments on the paper or
code, ... etc., feel free to contact me :-

Stephen J. Bevan <bevan@cs.man.ac.uk> 19921101

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>

ptb@prg.ox.ac.uk (Peter Breuer) writes:

>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!

Does this parser generator handle non-LL languages?

	Torben Mogensen (torbenm@diku.dk)

Let me add this ref' of mine:

L. Allison
Some applications of continuations.
Computer Journal 31(1) 9-11 1988

Seeing the continued interest in functional parsers, I have to mention that
our book contains a chapter on combinator-based parsing, including the
transformation of combinator-based LL parsers into parsing tables and into
recursive-descent parsers.  

It's in Scheme, of course, so it has one or two hacks needed to cope with
applicative-order evaluation (functional-programming purists may pause here to
direct their flames to /dev/null), but is otherwise functional.


The reference is:

Dan Friedman, Mitch Wand, and Chris Haynes, _Essentials of Programming
Languages_, MIT Press, 1992

An updated and improved version of the code can be ftp'd from:

ftp.cs.northeastern.edu:pub/wand/parsers/*

[Also, people should be aware of Michel Mauny's paper on functional parsers,
which was presented at the 1992 ML Conference last June.]

--Mitch 
--
Mitchell Wand
College of Computer Science, Northeastern University
360 Huntington Avenue #161CN, Boston, MA 02115     Phone: (617) 437 2072
Internet: wand@flora.ccs.northeastern.edu          Fax:   (617) 437 5121