[davdar]

Yes, breadth first traversal of the solution space is very similar in spirit to our approach.

I have since completely rewritten the Haskell implementation. You should really check it out, especially if you are thinking about writing one of your own.

(git repo) http://david.darais.com/git/research/der-parser-3

This implementation no longer requires a special coded repetition operator to get good complexity for regular and LL(k) grammars. This is a result of our progress w.r.t. performance of the theory since the paper's submission. My technique to achieve this uses structure derivatives (context based derivatives, or pseudo-equivalently, continuations) to avoid taking unnecessary parser derivatives. It in a sense "focuses" the parser computation on a small sub-parser.

Ping me if you have any questions; this paper has been getting passed around quite a bit lately and Matt and I have made progress on certain areas since the writing of the paper -- like that of the Rep hack.