Home Original page

Stackless & String-processing

Graham Matthews graham at sloth.math.uga.edu
Wed Jul 21 11:09:41 EDT 1999 
[Fernando Pereira]
> But from my readings (those mentioned in the thread and others) as well
> as your comments, the whole point of monadic combinators for parsing is
> to interweave the grammatical structure with other computations,
Tim Peters (tim_one at email.msn.com) wrote:
: If it isn't clear yet <wink>, efficiency isn't driving Graham here.  He's
: found a cool new approach, and is having fun with it.

No that's not the case. Efficiency drives all my programs *when it's a
necessity*. My point is that using combinators:

a) is a very nice way of structuring a parser since it is very amenable 
   to change and robust under change. 
	 
b) doesn't have to cost anything in efficiency since you can freely mix
   combinators with other parsing techniques.

c) is a general programming technique useful in a vast range of programs
   outside of just parsing. For example I have used it for type checking
   and writing a GUI. The literature has a lot of other examples of this
   approach.

Moreover the point of combinators is not to "interweave the grammatical
structure with other computations". Combinators do do that, and I think
it's a great benefit. But the point is to:

a) clearly separate sequencing code from other code. In a combinator 
 	 program the precise control flow of the program is clear.
	 l
b) allow programs to program their own sequencing combinators (rather
   than providing some fixed set that the language designer hopes will
   be enough.

Tim Peters (tim_one at email.msn.com) wrote:
: Different strokes.  Most of my parsing life has been concerned with
: artificial languages, and there I've got a different complaint about
: intermixing syntax with semantics:  the grammar is interesting for its own
: sake, and it's a positive burden at times to clutter it up with semantic
: annotations!

I have been using combinators for some time now and never noticed the
"grammar" being cluttered with all these "semantic annotations". What
annotations one requires can easily be separated from the grammar
either by sensible layout, or by the design of clever combinators that
hide semantic annotations away.
: 
Tim Peters (tim_one at email.msn.com) wrote:
: Case in point:  Python's grammar is formally defined by the file
: Grammar/Grammar in the source distribution.  That's the input to a parser
: generator.  At 60 non-noise lines, it's quite possible to digest the whole
: thing, and minor changes in syntax can be effected without touching anything
: else (how minor? exactly what doesn't require changing anything else

Combinators are very robust under change. I have a parser written using
combinators and I often tweak the grammar, without requiring large
changes to other code or the parser itself.

Have you ever written a combinator based parser or are you just 
"theorising"?
 
Tim Peters (tim_one at email.msn.com) wrote:
: I haven't tried using parser combinators, but in reading the papers the
: question I had over and over is whether they scale well in practice, whether
: measured by speed or maintainability (they eventually answered the "speed"
: one: no).

Ah there's the rub -- you haven't written a combinator based parser so you
your comments are just what you *think* might happen if you did.

I don't know where you got the idea that speed is a problem! For some
kinds of parsing I wouldn't use combinators rather I would use
automaton techniques. But for most kinds of parsing they are plenty
fast enough.

Tim Peters (tim_one at email.msn.com) wrote:
: It didn't bode well that each new example seemed to require
: creating a new combinator, and then you've got the implementation of *that*
: to worry about on top of the target grammar and the semantics.  It seemed to
: carry the flavor of programming in an assembly language for "a real parsing
: engine" (as Icon often feels to me in contrast to SNOBOL4 as grammars get
: large).  "You can have any sequencing you want, but you have to build it
: yourself."

Let me guess Tim -- you have read two papers on combinators. One is the
Hutton/Meijer paper on "monadic parser combinators", and the other is
the chapter in the old Clean book. Each new example in these papers
requires a different combinator because each new example illustrates
some new sequencing idea -- eg. determinisation, coninuation, ...
The papers are illustrating the generality of the techniques, and hence
you expect to see a lot of different combinators. In practice however
(something you wouldn't know about right?) you don't use all these
combinators. I have written a parser for a new programming language
and I used 10 combinators (5 of which I re-used in the type checker!).
Yes you do have to build your own combinators (that's the point of the
approach!), but once done you stick them in a library and re-use them.

graham: 
-- 
            The girls is all salty, the boys is all sweet, 
                      the food ain't too shabby 
                    an' they piss in the streets
    In France, way down in France, way on down, way on down in France
More information about the Python-list mailing list