I am about to release a new version of my combinator parsers when I
return from the ICFP. This new version solves some problems that may
show up when "the innocent" use my combinators (like trying to parse
epsilon*) and will, in some situations, be considerably faster. There
will be some new combinators too for describing greedy parsers. Also
the way error messages are generated has changed in an essential way:
you will get error messsages during the parsing process instead of
when parsing has completed. You may start using the parsers on the
web site, and read the papers you can find there. This new version
will also allow you to write scanners with the same set of
combinators.
We are working on a version that will also generate parsers.
Off to ICFP now,
Doaitse Swierstra
At 3:27 PM +1100 9/15/00, Manuel M. T. Chakravarty wrote:
>Doug Ransom <[EMAIL PROTECTED]> wrote,
>
>> Are combinator parsers recursive decent? Do they have any disadvantages
>> over generated parsers like that yacc would produce?
>
>Yes, they are recursive decent. As a consequence you have
>to left-factorise left-recursive productions in the grammar;
>otherwise, the parser won't terminate. Other than that,
>there are two disadvantages that I see: Speed and clarity of
>error messages during *development* of the parser.
>
>As for speed, Doitase Swierstra et al. came up with a very
>clever scheme of computing a parse table in a combinator
>parser on-the-fly during parsing, which makes things a lot
>faster:
>
> http://www.cs.uu.nl/groups/ST/Software/UU_Parsing/
>
>I provide a variant of Doaitse's parser combinators in the
>Compiler Toolkit:
>
> http://www.cse.unsw.edu.au/~chak/haskell/ctk/index.html
>
>This also includes a set of lexer combinators, which are
>also self-optimising. (Quite close to a hand written lexer:
><http://www.cse.unsw.edu.au/~chak/papers/Cha99.html>.)
>
>As for the second problem - clarity of error messages -
>there has been quite some effort in letting parser
>combinators deal gracefully with parse errors; however,
>there is another set of errors, which have received a lot
>less attention: the errors that the developer of a parser
>gets while debugging the parser. This is not so relevant
>for the toy parsers most people are writing, but if you are
>handling a complete programming language, it starts to get
>more serious.
>
>Having said that, let me point out that parser combinators
>also have strong advantages when compared to generators.
>Some can handle much more complex classes of grammars than
>what generator parsers usually over you. Its also easier to
>generate grammers on the fly or adapt the parser depending
>on the runtime configuration of the program. Moreover, you
>don't need an extra tool. And despite the mentioned
>disadvantages you can use combinators to produce parsers for
>real programming languages. The C front-end of the tool
>C->Haskell
>
> http://www.cse.unsw.edu.au/~chak/haskell/c2hs/
>
>is implemented using self-optimising lexer and parser
>combinators and I use it on C headers that (after being run
>through cpp) have up to 200k.
>
>Cheers,
>Manuel
--
__________________________________________________________________________
S. Doaitse Swierstra, Department of Computer Science, Utrecht University
P.O.Box 80.089, 3508 TB UTRECHT, the Netherlands
Mail: mailto:[EMAIL PROTECTED]
WWW: http://www.cs.uu.nl/
PGP Public Key: http://www.cs.uu.nl/people/doaitse/
tel: +31 (30) 253 3962, fax: +31 (30) 2513791
__________________________________________________________________________
