At 13:40 15/09/99 +0200, Sven Panne wrote:
>Parser combinators need not necessarily do any form of backtracking.
In 'Efficient Combinator Parser' (in LNCS 1595,: Implementation of
Functional Languages, selected papers from IFL'98) I explain why ordinary
combinator parsers are slow and what can be done about that. The basic
points are:
1) The ordinary or-combinator creates parsers of polynomial complexity in
the length of the input.
2) Ordinary combinator parsers generates lots of intermediate data structures.
The combinators introduced there allow you to write ambiguous parsers, but
when you indicate that no ambiguity is needed at a certain point, you get a
deterministic behaviour and the associated efficiency.
The language used in that paper is Clean, but everything carries over to
Haskell directly.
Pieter Koopman
