Home Original page

Stackless & String-processing

Neel Krishnaswami neelk at brick.cswv.com
Thu Jul 15 20:50:06 EDT 1999 
In article <7mkrrt$a81$1 at cronkite.cc.uga.edu>,
Graham Matthews <graham at sloth.math.uga.edu> wrote:
>
>[Parser Combinators] 
>
>They are something like what Neel is talking about (as the name
>"parser combinators" suggests you write small "string parsers" as
>functions, and then have "parser combinators" that stitch these
>together). Note that in this parser combinator approach there is no
>distinction between the code for "the pattern" and the code for "the
>processing" -- they are all written in the same language
>(Clean/Haskell in my case). 

Thanks for the tip -- it led me to do some digging on the web and I
found a nice description of this in a paper called "Monadic Parser
Combinators" by Graham Hutton and Erik Meijer. Its URL is:

  http://www.cs.nott.ac.uk/Department/Staff/gmh/monparsing.ps

>At first I found the idea of having the two types of code (the
>pattern and the processing) in the same language (rather than in 2
>distinct languages as in the traditional way) a bit difficult. But I
>perservered and I am glad I did. I found that once you reach a
>certain level of familiarity with combinators you can write new
>pattern and processing code very quickly and very reliably. The
>trick is to get the combinators right.

I think that this weekend I'm going to try and put together a basic
version of this parsing system in Python based on the ideas in this
paper -- basically just write a simple AST class and the combinators
they describe. Then I can add proper support for backtracking and lazy
evaluation and all the stuff with serious hack value when Christian
Tismer makes continuations available to us. :)

This really seems like a clean and straightforward way of doing
things.  My experience with recursive descent parsers has been pretty
bad, but now I suspect that this is because I wasn't organizing my
work in a systematic enough fashion. 


Neel
More information about the Python-list mailing list